Search

12th International Symposium on Parameterized and Exact Computation (IPEC 2017); International audience; Given a graph G, we define bcg(G) as the minimum k for which G can be contracted to the uniformly triangulated grid Γk. A graph class G has the SQGC property if every graph G ∈ G has treewidth O(bcg(G)c) for some 1 ≤ c < 2. The SQGC property is important for algo- rithm design as it defines the applicability horizon of a series of meta-algorithmic results, in the framework of bidimensionality theory, related to fast parameterized algorithms, kernelization, and approximation schemes. These results apply to a wide family of problems, namely problems that are contraction-bidimensional. Our main combinatorial result reveals a general family of graph classes that satisfy the SQGC property and includes bounded-degree string graphs. This considerably extends the applicability of bidimensionality theory for several intersection graph classes of 2-dimensional geometrical objects.

In the Parameterized Connected Dominating Set problem the input consists of a graph G and a positive integer k, and the question is whether there is a set S of at most k vertices in G—a connected dominating set of G—such that (i) S is a dominating set of G, and (ii) the subgraph G[S] induced by S is connected; the parameter is k. The underlying decision problem is a basic connectivity problem which is long known to be NP-complete, and it has been extensively studied using several algorithmic approaches. Parameterized Connected Dominating Set is W[2]-hard, and therefore it is unlikely (Downey and Fellows, Parameterized Complexity, Springer, 1999) that the problem has fixed-parameter tractable (FPT) algorithms or polynomial kernels in graphs in general. We investigate the effect of excluding short cycles, as subgraphs, on the kernelization complexity of Parameterized Connected Dominating Set. The girth of a graph G is the length of a shortest cycle in G. It turns out that the Parameterized Connected Dominating Set problem is hard on graphs with small cycles, and becomes progressively easier as the girth increases. More precisely, we obtain the following kernelization landscape: Parameterized Connected Dominating Set While there is a large and growing collection of parameterized complexity results available for problems on graph classes characterized by excluded minors, our results add to the very few known in the field for graph classes characterized by excluded subgraphs.

The Power Dominating Set problem is an extension of the well-known domination problem on graphs in a way that we enrich it by a second propagation rule: given a graph G(V,E), a set P⊆V is a power dominating set if every vertex is observed after the exhaustive application of the following two rules. First, a vertex is observed if v∈P or it has a neighbor in P. Secondly, if an observed vertex has exactly one unobserved neighbor u, then also u will be observed, as well. We show that Power Dominating Set remains $\mathcal{NP}$ -hard on cubic graphs. We design an algorithm solving this problem in time $\mathcal{O}^{*}(1.7548^{n})$ on general graphs, using polynomial space only. To achieve this, we introduce so-called reference search trees that can be seen as a compact representation of usual search trees, providing non-local pointers in order to indicate pruned subtrees.

We explore three important avenues of research in algorithmic graph-minor theory, which all stem from a key min-max relation between the treewidth of a graph and its largest grid minor. This min-max relation is a keystone of the Graph Minor Theory of Robertson and Seymour, which ultimately proves Wagner’s Conjecture about the structure of minor-closed graph properties. First, we obtain the only known polynomial min-max relation for graphs that do not exclude any fixed minor, namely, map graphs and power graphs. Second, we obtain explicit (and improved) bounds on the min-max relation for an important class of graphs excluding a minor, namely, K 3,k -minor-free graphs, using new techniques that do not rely on Graph Minor Theory. These two avenues lead to faster fixed-parameter algorithms for two families of graph problems, called minor-bidimensional and contraction-bidimensional parameters, which include feedback vertex set, vertex cover, minimum maximal matching, face cover, a series of vertex-removal parameters, dominating set, edge dominating set, R-dominating set, connected dominating set, connected edge dominating set, connected R-dominating set, and unweighted TSP tour. Third, we disprove a variation of Wagner’s Conjecture for the case of graph contractions in general graphs, and in a sense characterize which graphs satisfy the variation. This result demonstrates the limitations of a general theory of algorithms for the family of contraction-closed problems (which includes, for example, the celebrated dominating-set problem). If this conjecture had been true, we would have had an extremely powerful tool for proving the existence of efficient algorithms for any contraction-closed problem, like we do for minor-closed problems via Graph Minor Theory.

The NP-complete Power Dominating Set problem is an “electric power networks variant” of the classical domination problem in graphs: Given an undirected graph G=(V,E), find a minimum-size set P⊆V such that all vertices in V are “observed” by the vertices in P. Herein, a vertex observes itself and all its neighbors, and if an observed vertex has all but one of its neighbors observed, then the remaining neighbor becomes observed as well. We show that Power Dominating Set can be solved by “bounded-treewidth dynamic programs.” For treewidth being upper-bounded by a constant, we achieve a linear-time algorithm. In particular, we present a simplified linear-time algorithm for Power Dominating Set in trees. Moreover, we simplify and extend several NP-completeness results, particularly showing that Power Dominating Set remains NP-complete for planar graphs, for circle graphs, and for split graphs. Specifically, our improved reductions imply that Power Dominating Set parameterized by |P| is W[2]-hard and it cannot be better approximated than Dominating Set.

We present a fixed-parameter algorithm that constructively solves the $k$-dominating set problem on any class of graphs excluding a single-crossing graph (a graph that can be drawn in the plane with at most one crossing) as a minor in $O(4^{9.55\sqrt{k}}n^{O(1)})$ time. Examples of such graph classes are the $K_{3,3}$-minor-free graphs and the $K_{5}$-minor-free graphs. As a consequence, we extend our results to several other problems such as vertex cover, edge dominating set, independent set, clique-transversal set, kernels in digraphs, feedback vertex set, and a collection of vertex-removal problems. Our work generalizes and extends the recent results of exponential speedup in designing fixed-parameter algorithms on planar graphs due to Alber et al. to other (nonplanar) classes of graphs.

We present an algorithm that constructively produces a solution to the k -DOMINATING SET problem for planar graphs in time O(c^ \sqrt k n) , where c=4^ 6\sqrt 34 . To obtain this result, we show that the treewidth of a planar graph with domination number γ (G) is O(\sqrt \rule 0pt 4pt \smash γ (G) ) , and that such a tree decomposition can be found in O(\sqrt \rule 0pt 4pt \smash γ (G) n) time. The same technique can be used to show that the k -FACE COVER problem (find a size k set of faces that cover all vertices of a given plane graph) can be solved in O(c 1 ^ \sqrt k n) time, where c 1 =3^ 36\sqrt 34 and k is the size of the face cover set. Similar results can be obtained in the planar case for some variants of k -DOMINATING SET, e.g., k -INDEPENDENT DOMINATING SET and k -WEIGHTED DOMINATING SET.

We say a vertex v in a graph G covers a vertex w if v=w or if v and w are adjacent. A subset of vertices of G is a dominating set if it collectively covers all vertices in the graph. The dominating set problem, which is NP-hard, consists of finding a smallest possible dominating set for a graph. The straightforward greedy strategy for finding a small dominating set in a graph consists of successively choosing vertices which cover the largest possible number of previously uncovered vertices. Several variations on this greedy heuristic are described and the results of extensive testing of these variations is presented. A more sophisticated procedure for choosing vertices, which takes into account the number of ways in which an uncovered vertex may be covered, appears to be the most successful of the algorithms which are analyzed. For our experimental testing, we used both random graphs and graphs constructed by test case generators which produce graphs with a given density and a specified size for the smallest dominating set. We found that these generators were able to produce challenging graphs for the algorithms, thus helping to discriminate among them, and allowing a greater variety of graphs to be used in the experiments.

AnO(n log logn) (resp.O(n2 log2 n)) algorithm is presented to solve the minimum cardinality (resp. weight) dominating set problem on permutation graphs, assuming the input is a permutation. The best-known previous algorithm was given by FArber and Keil, where they use dynamic programming to get anO(n2 (resp.O(n3)) algorithm. Our improvement is based on the following three factors: (1) an observation on the order among the intermediate terms in the dynamic programming, (2) a new construction formula for the intermediate terms, and (3) efficient data structures for manipulating these terms.

The dominating set problem in graphs asks for a minimum size subset of vertices with the following property: each vertex is required to be either in the dominating set, or adjacent to some vertex in the dominating set. We focus on the related question of finding a connected dominating set of minimum size, where the graph induced by vertices in the dominating set is required to be connected as well. This problem arises in network testing, as well as in wireless communication. Two polynomial time algorithms that achieve approximation factors of 2H(Δ)+2 and H(Δ)+2 are presented, where Δ is the maximum degree and H is the harmonic function. This question also arises in relation to the traveling tourist problem, where one is looking for the shortest tour such that each vertex is either visited or has at least one of its neighbors visited. We also consider a generalization of the problem to the weighted case, and give an algorithm with an approximation factor of (cn+1) \ln n where cn ln k is the approximation factor for the node weighted Steiner tree problem (currently cn = 1.6103 ). We also consider the more general problem of finding a connected dominating set of a specified subset of vertices and provide a polynomial time algorithm with a (c+1) H(Δ) +c-1 approximation factor, where c is the Steiner approximation ratio for graphs (currently c = 1.644 ).