 |
Discrete Mathematics & Theoretical Computer Science |
Vol. 17 no. 1
1. A randomized algorithm for finding a maximum clique in the visibility graph of a simple polygon
We present a randomized algorithm to compute a clique of maximum size in the visibility graph G of the vertices of a simple polygon P. The input of the problem consists of the visibility graph G, a Hamiltonian cycle describing the boundary of P, and a parameter δ∈(0,1) controlling the probability of error of the algorithm. The algorithm does not require the coordinates of the vertices of P. With probability at least 1-δ the algorithm runs in O( |E(G)|2 / ω(G) log(1/δ)) time and returns a maximum clique, where ω(G) is the number of vertices in a maximum clique in G. A deterministic variant of the algorithm takes O(|E(G)|2) time and always outputs a maximum size clique. This compares well to the best previous algorithm by Ghosh et al. (2007) for the problem, which is deterministic and runs in O(|V(G)|2 |E(G)|) time.
Section:
Discrete Algorithms
2. Ore-degree threshold for the square of a Hamiltonian cycle
A classic theorem of Dirac from 1952 states that every graph with minimum degree at least n=2 contains a Hamiltonian cycle. In 1963, P´osa conjectured that every graph with minimum degree at least 2n=3 contains the square of a Hamiltonian cycle. In 1960, Ore relaxed the degree condition in the Dirac’s theorem by proving that every graph with deg(u) + deg(v) ≥ n for every uv =2 E(G) contains a Hamiltonian cycle. Recently, Chˆau proved an Ore-type version of P´osa’s conjecture for graphs on n ≥ n0 vertices using the regularity–blow-up method; consequently the n0 is very large (involving a tower function). Here we present another proof that avoids the use of the regularity lemma. Aside from the fact that our proof holds for much smaller n0, we believe that our method of proof will be of independent interest.
Section:
Graph Theory
3. An approximability-related parameter on graphs―-properties and applications
We introduce a binary parameter on optimisation problems called separation. The parameter is used to relate the approximation ratios of different optimisation problems; in other words, we can convert approximability (and non-approximability) result for one problem into (non)-approximability results for other problems. Our main application is the problem (weighted) maximum H-colourable subgraph (Max H-Col), which is a restriction of the general maximum constraint satisfaction problem (Max CSP) to a single, binary, and symmetric relation. Using known approximation ratios for Max k-cut, we obtain general asymptotic approximability results for Max H-Col for an arbitrary graph H. For several classes of graphs, we provide near-optimal results under the unique games conjecture. We also investigate separation as a graph parameter. In this vein, we study its properties on circular complete graphs. Furthermore, we establish a close connection to work by Šámal on cubical colourings of graphs. This connection shows that our parameter is closely related to a special type of chromatic number. We believe that this insight may turn out to be crucial for understanding the behaviour of the parameter, and in the longer term, for understanding the approximability of optimisation problems such as Max H-Col.
Section:
Graph Theory
4. On the 1-2-3-conjecture
A k-edge-weighting of a graph G is a function w:E(G)→{1,…,k}. An edge-weighting naturally induces a vertex coloring c, where for every vertex v∈V(G), c(v)=∑e∼vw(e). If the induced coloring c is a proper vertex coloring, then w is called a vertex-coloring k-edge-weighting (VC k-EW). Karoński et al. (J. Combin. Theory Ser. B, 91 (2004) 151 13;157) conjectured that every graph admits a VC 3-EW. This conjecture is known as the 1-2-3-conjecture. In this paper, first, we study the vertex-coloring edge-weighting of the Cartesian product of graphs. We prove that if the 1-2-3-conjecture holds for two graphs G and H, then it also holds for G□H. Also we prove that the Cartesian product of connected bipartite graphs admits a VC 2-EW. Moreover, we present several sufficient conditions for a graph to admit a VC 2-EW. Finally, we explore some bipartite graphs which do not admit a VC 2-EW.
Section:
Graph Theory
5. Connectivity of Fibonacci cubes, Lucas cubes and generalized cubes
If f is a binary word and d a positive integer, then the generalized Fibonacci cube Qd(f) is the graph obtained from the d-cube Qd by removing all the vertices that contain f as a factor, while the generalized Lucas cube Qd(lucas(f)) is the graph obtained from Qd by removing all the vertices that have a circulation containing f as a factor. The Fibonacci cube Γd and the Lucas cube Λd are the graphs Qd(11) and Qd(lucas(11)), respectively. It is proved that the connectivity and the edge-connectivity of Γd as well as of Λd are equal to ⌊ d+2 / 3⌋. Connected generalized Lucas cubes are characterized and generalized Fibonacci cubes are proved to be 2-connected. It is asked whether the connectivity equals minimum degree also for all generalized Fibonacci/Lucas cubes. It was checked by computer that the answer is positive for all f and all d≤9.
Section:
Graph Theory
6. Classification of skew translation generalized quadrangles, I
We describe new classification results in the theory of generalized quadrangles (= Tits-buildings of rank 2 and type B2), more precisely in the (large) subtheory of skew translation generalized quadrangles (``STGQs''). Some of these involve, and solve, long-standing open problems.
Section:
Combinatorics
7. Symmetric bipartite graphs and graphs with loops
We show that if the two parts of a finite bipartite graph have the same degree sequence, then there is a bipartite graph, with the same degree sequences, which is symmetric, in that it has an involutive graph automorphism that interchanges its two parts. To prove this, we study the relationship between symmetric bipartite graphs and graphs with loops.
Section:
Graph Theory
8. Edge stability in secure graph domination
A subset X of the vertex set of a graph G is a secure dominating set of G if X is a dominating set of G and if, for each vertex u not in X, there is a neighbouring vertex v of u in X such that the swap set (X-v)∪u is again a dominating set of G. The secure domination number of G is the cardinality of a smallest secure dominating set of G. A graph G is p-stable if the largest arbitrary subset of edges whose removal from G does not increase the secure domination number of the resulting graph, has cardinality p. In this paper we study the problem of computing p-stable graphs for all admissible values of p and determine the exact values of p for which members of various infinite classes of graphs are p-stable. We also consider the problem of determining analytically the largest value ωn of p for which a graph of order n can be p-stable. We conjecture that ωn=n-2 and motivate this conjecture.
Section:
Graph Theory
9. Bootstrapping and double-exponential limit laws
We provide a rather general asymptotic scheme for combinatorial parameters that asymptotically follow a discrete double-exponential distribution. It is based on analysing generating functions Gh(z) whose dominant singularities converge to a certain value at an exponential rate. This behaviour is typically found by means of a bootstrapping approach. Our scheme is illustrated by a number of classical and new examples, such as the longest run in words or compositions, patterns in Dyck and Motzkin paths, or the maximum degree in planted plane trees.
Section:
Combinatorics
10. Avoider-enforcer star games
In this paper, we study (1 : b) Avoider-Enforcer games played on the edge set of the complete graph on n vertices. For every constant k≥3 we analyse the k-star game, where Avoider tries to avoid claiming k edges incident to the same vertex. We consider both versions of Avoider-Enforcer games — the strict and the monotone — and for each provide explicit winning strategies for both players. We determine the order of magnitude of the threshold biases fmonF, f-F and f+F, where F is the hypergraph of the game.
Section:
Combinatorics
11. p-box: a new graph model
In this document, we study the scope of the following graph model: each vertex is assigned to a box in ℝd and to a representative element that belongs to that box. Two vertices are connected by an edge if and only if its respective boxes contain the opposite representative element. We focus our study on the case where boxes (and therefore representative elements) associated to vertices are spread in ℝ. We give both, a combinatorial and an intersection characterization of the model. Based on these characterizations, we determine graph families that contain the model (e. g., boxicity 2 graphs) and others that the new model contains (e. g., rooted directed path). We also study the particular case where each representative element is the center of its respective box. In this particular case, we provide constructive representations for interval, block and outerplanar graphs. Finally, we show that the general and the particular model are not equivalent by constructing a graph family that separates the two cases.
Section:
Graph Theory
12. Guarded subgraphs and the domination game
We introduce the concept of guarded subgraph of a graph, which as a condition lies between convex and 2-isometric subgraphs and is not comparable to isometric subgraphs. Some basic metric properties of guarded subgraphs are obtained, and then this concept is applied to the domination game. In this game two players, Dominator and Staller, alternate choosing vertices of a graph, one at a time, such that each chosen vertex enlarges the set of vertices dominated so far. The aim of Dominator is that the graph is dominated in as few steps as possible, while the aim of Staller is just the opposite. The game domination number is the number of vertices chosen when Dominator starts the game and both players play optimally. The main result of this paper is that the game domination number of a graph is not smaller than the game domination number of any guarded subgraph. Several applications of this result are presented.
Section:
Graph Theory
13. Extending a perfect matching to a Hamiltonian cycle
Ruskey and Savage conjectured that in the d-dimensional hypercube, every matching M can be extended to a Hamiltonian cycle. Fink verified this for every perfect matching M, remarkably even if M contains external edges. We prove that this property also holds for sparse spanning regular subgraphs of the cubes: for every d ≥7 and every k, where 7 ≤k ≤d, the d-dimensional hypercube contains a k-regular spanning subgraph such that every perfect matching (possibly with external edges) can be extended to a Hamiltonian cycle. We do not know if this result can be extended to k=4,5,6. It cannot be extended to k=3. Indeed, there are only three 3-regular graphs such that every perfect matching (possibly with external edges) can be extended to a Hamiltonian cycle, namely the complete graph on 4 vertices, the complete bipartite 3-regular graph on 6 vertices and the 3-cube on 8 vertices. Also, we do not know if there are graphs of girth at least 5 with this matching-extendability property.
Section:
Graph Theory
14. A conjecture on the number of Hamiltonian cycles on thin grid cylinder graphs
We study the enumeration of Hamiltonian cycles on the thin grid cylinder graph $C_m \times P_{n+1}$. We distinguish two types of Hamiltonian cycles, and denote their numbers $h_m^A(n)$ and $h_m^B(n)$. For fixed $m$, both of them satisfy linear homogeneous recurrence relations with constant coefficients, and we derive their generating functions and other related results for $m\leq10$. The computational data we gathered suggests that $h^A_m(n)\sim h^B_m(n)$ when $m$ is even.
Section:
Graph Theory
15. Cost-effectiveness of algorithms
In this paper we discuss how to assess the performance of algorithms for optimisation problems in a way that balances solution quality and time. We propose measures of cost-effectiveness for such algorithms. These measures give the gain in solution quality per time unit over a sequence of inputs, and give a basis for deciding which algorithm to use when aiming for best accumulated solution quality for a given time investment over such an input sequence. Cost-effectiveness measures can be defined for both average-case and worst-case performance. We apply these ideas to three problems: maximum matching, graph colouring and Kolmogorov complexity. For the latter, we propose a cost-effectiveness measure for the time-bounded complexity Kτ(x), and argue that it can be used to measure the cost-effectiveness both of finding a short program to output x and of generating x from such a program. Under mild assumptions, we show that (roughly speaking) if the time-bounded complexity Kτ(x) is to be a cost-effective approximation to K(x) then τ(n)=O(n2).
Section:
Discrete Algorithms
16. On probe 2-clique graphs and probe diamond-free graphs
Given a class G of graphs, probe G graphs are defined as follows. A graph G is probe G if there exists a partition of its vertices into a set of probe vertices and a stable set of nonprobe vertices in such a way that non-edges of G, whose endpoints are nonprobe vertices, can be added so that the resulting graph belongs to G. We investigate probe 2-clique graphs and probe diamond-free graphs. For probe 2-clique graphs, we present a polynomial-time recognition algorithm. Probe diamond-free graphs are characterized by minimal forbidden induced subgraphs. As a by-product, it is proved that the class of probe block graphs is the intersection between the classes of chordal graphs and probe diamond-free graphs.
Section:
Graph Theory
17. Parameterized complexity of synchronization and road coloring
First, we close the multi-parameter analysis of a canonical problem concerning short reset words (SYN) initiated by Fernau et al. (2013). Namely, we prove that the problem, parameterized by the number of states, does not admit a polynomial kernel unless the polynomial hierarchy collapses. Second, we consider a related canonical problem concerning synchronizing road colorings (SRCP). Here we give a similar complete multi-parameter analysis. Namely, we show that the problem, parameterized by the number of states, admits a polynomial kernel and we close the previous research of restrictions to particular values of both the alphabet size and the maximum length of a reset word.
Section:
Automata, Logic and Semantics
18. Graphs with large disjunctive total domination number
Let G be a graph with no isolated vertex. In this paper, we study a parameter that is a relaxation of arguably the most important domination parameter, namely the total domination number, γt(G). A set S of vertices in G is a disjunctive total dominating set of G if every vertex is adjacent to a vertex of S or has at least two vertices in S at distance 2 from it. The disjunctive total domination number, γdt(G), is the minimum cardinality of such a set. We observe that γdt(G) ≤γt(G). Let G be a connected graph on n vertices with minimum degree δ. It is known [J. Graph Theory 35 (2000), 21 13;45] that if δ≥2 and n ≥11, then γt(G) ≤4n/7. Further [J. Graph Theory 46 (2004), 207 13;210] if δ≥3, then γt(G) ≤n/2. We prove that if δ≥2 and n ≥8, then γdt(G) ≤n/2 and we characterize the extremal graphs.
Section:
Graph Theory
19. A note on a recent attempt to improve the Pin-Frankl bound
We provide a counterexample to a lemma used in a recent tentative improvement of the Pin-Frankl bound for synchronizing automata. This example naturally leads us to formulate an open question, whose answer could fix the line of the proof, and improve the bound.
Section:
Automata, Logic and Semantics
20. Output sensitive algorithms for covering many points
In this paper we devise some output sensitive algorithms for a problem where a set of points and a positive integer, m, are given and the goal is to cover a maximal number of these points with m disks. We introduce a parameter, ρ, as the maximum number of points that one disk can cover and we analyse the algorithms based on this parameter. At first, we solve the problem for m=1 in O(nρ) time, which improves the previous O(n2) time algorithm for this problem. Then we solve the problem for m=2 in O(nρ + 3 log ρ) time, which improves the previous O(n3 log n) algorithm for this problem. Our algorithms outperform the previous algorithms because ρ is much smaller than n in many cases. Finally, we extend the algorithm for any value of m and solve the problem in O(mnρ + (mρ)2m - 1 log mρ) time. The previous algorithm for this problem runs in O(n2m - 1 log n) time and our algorithm usually runs faster than the previous algorithm because mρ is smaller than n in many cases. We obtain output sensitive algorithms by confining the areas that we should search for the result. The techniques used in this paper may be applicable in other covering problems to obtain faster algorithms.
Section:
Discrete Algorithms
21. An efficient certificateless aggregate signature scheme for vehicular ad-hoc networks
The state-of-the-art telecommunication technologies have widely been adapted for sensing the traffic related information and collection of it. Vehicular Ad-Hoc Networks (VANETs) have emerged as a novel technology for revolutionizing the driving experiences of human. The most effective and widely recognized way for mutual authentication among entities in VANETs is digital signature scheme. The new and attractive paradigm which eliminates the use of certificates in public key cryptography and solves the key escrow problem in identity based cryptography is certificateless cryptography. A new certificateless aggregate signature scheme is proposed in the paper for VANETs with constant pairing computations. Assuming the hardness of computational Diffie-Hellman Problem, the scheme is proved to be existentially unforgeable in the random oracle model against adaptive chosen-message attacks.
Section:
Distributed Computing and Networking
22. Maximum difference about the size of optimal identifying codes in graphs differing by one vertex
Let G=(V,E) be a simple undirected graph. We call any subset C⊆V an identifying code if the sets I(v)={c∈C | {v,c}∈E or v=c } are distinct and non-empty for all vertices v∈V. A graph is called twin-free if there is an identifying code in the graph. The identifying code with minimum size in a twin-free graph G is called the optimal identifying code and the size of such a code is denoted by γ(G). Let GS denote the induced subgraph of G where the vertex set S⊂V is deleted. We provide a tight upper bound for γ(GS)-γ(G) when both graphs are twin-free and |V| is large enough with respect to |S|. Moreover, we prove tight upper bound when G is a bipartite graph and |S|=1.
Section:
Graph Theory
23. On the Hausdorff measure of regular ω-languages in Cantor space
This paper deals with the calculation of the Hausdorff measure of regular ω-languages, that is, subsets of the Cantor space definable by finite automata. Using methods for decomposing regular ω-languages into disjoint unions of parts of simple structure we derive two sufficient conditions under which ω-languages with a closure definable by a finite automaton have the same Hausdorff measure as this closure. The first of these condition is related to the homogeneity of the local behaviour of the Hausdorff dimension of the underlying set, and the other with a certain topological density of the set in its closure.
Section:
Automata, Logic and Semantics
24. Snarks with total chromatic number 5
A k-total-coloring of G is an assignment of k colors to the edges and vertices of G, so that adjacent and incident elements have different colors. The total chromatic number of G, denoted by χT(G), is the least k for which G has a k-total-coloring. It was proved by Rosenfeld that the total chromatic number of a cubic graph is either 4 or 5. Cubic graphs with χT = 4 are said to be Type 1, and cubic graphs with χT = 5 are said to be Type 2. Snarks are cyclically 4-edge-connected cubic graphs that do not allow a 3-edge-coloring. In 2003, Cavicchioli et al. asked for a Type 2 snark with girth at least 5. As neither Type 2 cubic graphs with girth at least 5 nor Type 2 snarks are known, this is taking two steps at once, and the two requirements of being a snark and having girth at least 5 should better be treated independently. In this paper we will show that the property of being a snark can be combined with being Type 2. We will give a construction that gives Type 2 snarks for each even vertex number n≥40. We will also give the result of a computer search showing that among all Type 2 cubic graphs on up to 32 vertices, all but three contain an induced chordless cycle of length 4. These three exceptions contain triangles. The question of the existence of a Type 2 cubic graph with girth at least 5 remains open.
Section:
Graph Theory
25. On substitution tilings of the plane with n-fold rotational symmetry
A method is described for constructing, with computer assistance, planar substitution tilings that have n-fold rotational symmetry. This method uses as prototiles the set of rhombs with angles that are integer multiples of pi/n, and includes various special cases that have already been constructed by hand for low values of n. An example constructed by this method for n = 11 is exhibited; this is the first substitution tiling with elevenfold symmetry appearing in the literature.
Section:
Discrete Algorithms
26. Intervals and factors in the Bruhat order
In this paper we study those generic intervals in the Bruhat order of the symmetric group that are isomorphic to the principal order ideal of a permutation w, and consider when the minimum and maximum elements of those intervals are related by a certain property of their reduced words. We show that the property does not hold when w is a decomposable permutation, and that the property always holds when w is the longest permutation.
Section:
Combinatorics
27. How often should you clean your room?
We introduce and study a combinatorial optimization problem motivated by the question in the title. In the simple case where you use all objects in your room equally often, we investigate asymptotics of the optimal time to clean up in terms of the number of objects in your room. In particular, we prove a logarithmic upper bound, solve an approximate version of this problem, and conjecture a precise logarithmic asymptotic.
Section:
Analysis of Algorithms