Search

Bidimensionality theory was introduced by [E. D. Demaine et al., J. ACM, 52 (2005), pp. 866--893] as a tool to obtain subexponential time parameterized algorithms on H-minor-free graphs. In [E. D. Demaine and M. Hajiaghayi, Bidimensionality: New connections between FPT algorithms and PTASs, in Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), SIAM, Philadelphia, 2005, pp. 590--601] this theory was extended in order to obtain polynomial time approximation schemes (PTASs) for bidimensional problems. In this work, we establish a third meta-algorithmic direction for bidimensionality theory by relating it to the existence of linear kernels for parameterized problems. In particular, we prove that every minor (resp., contraction) bidimensional problem that satisfies a separation property and is expressible in Countable Monadic Second Order Logic (CMSO) admits a linear kernel for classes of graphs that exclude a fixed graph (resp., an apex graph) H as a minor. Our results imply that a multitude of bidimensional problems admit linear kernels on the corresponding graph classes. For most of these problems no polynomial kernels on H-minor-free graphs were known prior to our work. [ABSTRACT FROM AUTHOR]

A central problem in parameterized algorithms is to obtain algorithms with running time f(k) · nO(1) such that f is as slow growing a function of the parameter k as possible. In particular, a large number of basic parameterized problems admit parameterized algorithms where f(k) is single-exponential, that is, ck for some constant c, which makes aiming for such a running time a natural goal for other problems as well. However, there are still plenty of problems where the f(k) appearing in the best-known running time is worse than single-exponential and it remained "slightly superexponential" even after serious attempts to bring it down. A natural question to ask is whether the f(k) appearing in the running time of the best-known algorithms is optimal for any of these problems. In this paper, we examine parameterized problems where f(k) is kO(k) = 2O(k log k) in the best-known running time, and for a number of such problems we show that the dependence on k in the running time cannot be improved to single-exponential. More precisely we prove the following tight lower bounds, for four natural problems, arising from three different domains: (1) In the Closest String problem, given strings s1, ..., st over an alphabet Σ of length L each, and an integer d, the question is whether there exists a string s over Σ of length L, such that its hamming distance from each of the strings si, 1 ≤ i ≤ t, is at most d. The pattern matching problem Closest String is known to be solvable in times 2O(d log d) · nO(1) and 2O(d log |Σ|) · nO(1). We show that there are no 2o(d log d) · nO(1) or 2o(d log |Σ|) · nO(1) time algorithms, unless the Exponential Time Hypothesis (ETH) fails. (2) The graph embedding problem Distortion, that is, deciding whether a graph G has a metric embedding into the integers with distortion at most d can be solved in time 2O(d log d) · nO(1). We show that there is no 2o(d log d) · nO(1) time algorithm, unless the ETH fails. (3) The Disjoint Paths problem can be solved in time 2O(w log w) · nO(1) on graphs of treewidth at most w. We show that there is no 2o(w log w) · nO(1) time algorithm, unless the ETH fails. (4) The Chromatic Number problem can be solved in time 2O(w log w) ·nO(1) on graphs of treewidth at most w. We show that there is no 2o(w log w) · nO(1) time algorithm, unless the ETH fails. To obtain our results, we first prove the lower bound for variants of basic problems: finding cliques, independent sets, and hitting sets. These artificially constrained variants form a good starting point for proving lower bounds on natural problems without any technical restrictions and could be of independent interest. Several follow-up works have already obtained tight lower bounds by using our framework, and we believe it will prove useful in obtaining even more lower bounds in the future. [ABSTRACT FROM AUTHOR]

We prove the following theorem. Given a planar graph G and an integer k, it is possible in polynomial time to randomly sample a subset A of vertices of G with the following properties: A induces a subgraph of G of treewidth O(√k log k), and for every connected subgraph H of G on at most k vertices, the probability that A covers the whole vertex set of H is at least (2O(√k log² k)⋅nO(1))-1, where n is the number of vertices of G. Together with standard dynamic programming techniques for graphs of bounded treewidth, this result gives a versatile technique for obtaining (randomized) subexponential-time parameterized algorithms for problems on planar graphs, usually with running time bound 2O(√k log² k)nO(1). The technique can be applied to problems expressible as searching for a small, connected pattern with a prescribed property in a large host graph; examples of such problems include Directed k -Path, Weighted k -Path, Vertex Cover Local Search, and Subgraph Isomorphism, among others. Up to this point, it was open whether these problems could be solved in subexponential parameterized time on planar graphs, because they are not amenable to the classic technique of bidimensionality. Furthermore, all our results hold in fact on any class of graphs that exclude a fixed apex graph as a minor, in particular on graphs embeddable in any fixed surface. [ABSTRACT FROM AUTHOR]

In the classic Minimum Bisection problem we are given as input an undirected graph G and an integer k. The task is to determine whether there is a partition of V (G) into two parts A and B such that | | A| | B| | \leq 1 and there are at most k edges with one endpoint in A and the other in B. In this paper we give an algorithm for Minimum Bisection with running time 2O(k3)n³ log³ n. This is the first fixed parameter tractable algorithm for Minimum Bisection parameterized by k. At the core of our algorithm lies a new decomposition theorem that states that every graph G can be decomposed by small separators into parts where each part is "highly connected"" in the following sense: any separator of bounded size can separate only a limited number of vertices from each part of the decomposition. Our techniques generalize to the weighted setting, where we seek a bisection of minimum weight among solutions that contain at most k edges. [ABSTRACT FROM AUTHOR]

We give a fixed-parameter tractable algorithm that, given a parameter k and two graphs G1, G2, either concludes that one of these graphs has treewidth at least k or determines whether G1 and G2 are isomorphic. The running time of the algorithm on an n-vertex graph is ...⋅n5, and this is the first fixed-parameter algorithm for GRAPH ISOMORPHISM parameterized by treewidth. Our algorithm in fact solves the more general canonization problem. We namely design a procedure working in ...⋅n5 time that, for a given graph G on n vertices, either concludes that the treewidth of G is at least k or (i) finds in an isomorphic-invariant way a graph c(G) that is isomorphic to G; (ii) finds an isomorphism-invariant construction term--an algebraic expression that encodes G together with a tree decomposition of G of width less than k. Hence, the isomorphism test reduces to verifying whether the computed isomorphic copies or the construction terms for G1 and G2 are equal. [ABSTRACT FROM AUTHOR]

We obtain asymptotically tight algorithmic bounds for Max-Cut and Edge Dominating Set problems on graphs of bounded clique-width. We show that on an n-vertex graph of clique-width t both problems (1) cannot be solved in time f(t)no(t) for any function f of t unless exponential time hypothesis fails, and (2) can be solved in time nO(t). [ABSTRACT FROM AUTHOR]

We show that Edge Dominating Set, Hamiltonian Cycle, and Graph Coloring are W[1]-hard parameterized by clique-width. It was an open problem, explicitly mentioned in several papers, whether any of these problems is fixed parameter tractable when parameterized by the clique-width, that is, solvable in time g(k) ∙ nO(1) on n-vertex graphs of clique-width k, where g is some function of k only. Our results imply that the running time O(nf(k)) of many clique-widthbased algorithms is essentially the best we can hope for (up to a widely believed assumption from parameterized complexity, namely FPT ≠ W[1]). [ABSTRACT FROM AUTHOR]