50 research outputs found
Constrained Bipartite Vertex Cover: The Easy Kernel is Essentially Tight
No full textThe CONSTRAINED BIPARTITE VERTEX COVER problem asks, for a bipartite graph G with partite sets A and B, and integers k_A and k_B, whether there is a vertex cover for G containing at most k_A vertices from A and k_B vertices from B. The problem has an easy kernel with 2 * k_A * k_B edges and 4 k_A * k_B vertices, based on the fact that every vertex in A of degree more than k_B has to be included in the solution, together with every vertex in B of degree more than k_A. We show that the number of vertices and edges in this kernel are asymptotically essentially optimal in terms of the product k_A * k_B. We prove that if there is a polynomial-time algorithm that reduces any instance (G,A,B,k_A,k_B) of CONSTRAINED BIPARTITE VERTEX COVER to an equivalent instance (G',A',B',k'_A,k'_B) such that k'_A in (k_A)^{O(1)}, k'_B in (k_B)^{O(1)}, and |V(G')| in O((k_A * k_B)^{1 - epsilon}), for some epsilon > 0, then NP subseteq coNP/poly and the polynomial-time hierarchy collapses. Using a different construction, we prove that if there is a polynomial-time algorithm that reduces any n-vertex instance into an equivalent instance (of a possibly different problem) that can be encoded in O(n^{2- epsilon}) bits, then NP subseteq coNP/poly
Faster Subgraph Counting in Sparse Graphs
No full textA fundamental graph problem asks to compute the number of induced copies of a k-node pattern graph H in an n-node graph G. The fastest algorithm to date is still the 35-years-old algorithm by Nešetřil and Poljak [Nešetřil and Poljak, 1985], with running time f(k) * O(n^{omega floor[k/3] + 2}) where omega <=2.373 is the matrix multiplication exponent. In this work we show that, if one takes into account the degeneracy d of G, then the picture becomes substantially richer and leads to faster algorithms when G is sufficiently sparse. More precisely, after introducing a novel notion of graph width, the DAG-treewidth, we prove what follows. If H has DAG-treewidth tau(H) and G has degeneracy d, then the induced copies of H in G can be counted in time f(d,k) * O~(n^{tau(H)}); and, under the Exponential Time Hypothesis, no algorithm can solve the problem in time f(d,k) * n^{o(tau(H)/ln tau(H))} for all H. This result characterises the complexity of counting subgraphs in a d-degenerate graph. Developing bounds on tau(H), then, we obtain natural generalisations of classic results and faster algorithms for sparse graphs. For example, when d=O(poly log(n)) we can count the induced copies of any H in time f(k) * O~(n^{floor[k/4] + 2}), beating the Nešetřil-Poljak algorithm by essentially a cubic factor in n
Optimal Sparsification for Some Binary CSPs Using Low-Degree Polynomials
No full textThis paper analyzes to what extent it is possible to efficiently reduce the number of clauses in NP-hard satisfiability problems, without changing the answer. Upper and lower bounds are established using the concept of kernelization. Existing results show that if NP is not contained in coNP/poly, no efficient preprocessing algorithm can reduce n-variable instances of CNF-SAT with d literals per clause, to equivalent instances with O(n^{d-epsilon}) bits for any epsilon > 0. For the Not-All-Equal SAT problem, a compression to size tilde-O(n^{d-1}) exists. We put these results in a common framework by analyzing the compressibility of binary CSPs. We characterize constraint types based on the minimum degree of multivariate polynomials whose roots correspond to the satisfying assignments, obtaining (nearly) matching upper and lower bounds in several settings. Our lower bounds show that not just the number of constraints, but also the encoding size of individual constraints plays an important role. For example, for Exact Satisfiability with unbounded clause length it is possible to efficiently reduce the number of constraints to n+1, yet no polynomial-time algorithm can reduce to an equivalent instance with O(n^{2-epsilon}) bits for any epsilon > 0, unless NP is contained in coNP/poly
Fine-grained parameterized complexity analysis of graph coloring problems
No full textThe q -Coloring problem asks whether the vertices of a graph can be properly colored with q colors. Lokshtanov et al. [SODA 2011] showed that q -Coloring on graphs with a feedback vertex set of size k cannot be solved in time O ∗ ((q−ε) k ) , for any ε>0 , unless the Strong Exponential-Time Hypothesis (SETH) fails. In this paper we perform a fine-grained analysis of the complexity of q -Coloring with respect to a hierarchy of parameters. We show that even when parameterized by the vertex cover number, q must appear in the base of the exponent: Unless ETH fails, there is no universal constant θ such that q -Coloring parameterized by vertex cover can be solved in time O ∗ (θ k ) for all fixed q . We apply a method due to Jansen and Kratsch [Inform. & Comput. 2013] to prove that there are O ∗ ((q−ε) k ) time algorithms where k is the vertex deletion distance to several graph classes F for which q -Coloring is known to be solvable in polynomial time. We generalize earlier ad-hoc results by showing that if F is a class of graphs whose (q+1) -colorable members have bounded treedepth, then there exists some ε>0 such that q -Coloring can be solved in time O ∗ ((q−ε) k ) when parameterized by the size of a given modulator to F . In contrast, we prove that if F is the class of paths - some of the simplest graphs of unbounded treedepth - then no such algorithm can exist unless SETH fails
The Power of Data Reduction : Kernels for Fundamental Graph Problems
No full textThe purpose of this thesis is to give a mathematical analysis of the power of data reduction for dealing with fundamental NP-hard graph problems. It has often been observed that the use of heuristic reduction rules in a preprocessing phase gives significant performance gains when solving such problems. However, there is little scientific explanation for these empirically observed successes. We use the concept of kernelization, developed within the field of parameterized complexity theory, to give a mathematical analysis of the power of such data reduction techniques. A kernelization, or kernel, is a polynomial-time preprocessing algorithm that transforms an instance of a parameterized problem into an equivalent instance whose size depends only on the parameter. The concept of kernelization therefore formalizes efficient and provably effective preprocessing. In our analysis of fundamental graph problems we utilize various structural measures of graphs as the complexity parameter; these include the vertex cover number, the feedback vertex number, the treewidth, and the vertex-deletion distance to various well-studied graph classes. We parameterize four fundamental classes of graph problems by such graph-structural measures. We determine which of these parameterizations admit kernelizations for which the size of the output is bounded by a polynomial in the parameter. Towards this end, we also develop technical tools to prove that a parameterized problem does not admit a kernel of polynomial size, subject to certain complexity-theoretic assumptions. The four fundamental problems we study are Vertex Cover, Treewidth, Graph Coloring, and Longest Path. For the Vertex Cover problem we introduce novel reduction rules that provably reduce the size of an instance to at most O(k^3) vertices in polynomial time, where k is the size of a feedback vertex set of the input graph. We also prove that the existence of a kernel for the parameterization by the vertex-deletion distance to an outerplanar graph or a clique, leads to a collapse of the polynomial hierarchy and is therefore unlikely. In our analysis of the Treewidth problem, we prove that preprocessing rules that were initially developed for heuristic algorithms, lead to a polynomial kernel for Treewidth parameterized by the vertex cover number. By developing additional rules that eliminate almost-simplicial vertices and shrink clique-seeing paths, we obtain a polynomial kernel parameterized by the feedback vertex number. Finally, we prove that Treewidth and Pathwidth do not admit polynomial kernels parameterized by the vertex-deletion distance to a clique, unless the polynomial hierarchy collapses. We analyze the kernelization complexity of graph coloring problems with respect to parameterizations that measure the vertex-deletion to graph classes such as cographs and co-chordal graphs. We show that the existence of polynomial kernels is determined by the extremal properties of No-instances of the List Coloring problem on such graph classes. Finally, we investigate Longest Path and related problems, with structural parameterizations. We obtain polynomial kernels for parameterizations by the vertex cover number, the max leaf number, and the vertex-deletion distance to a cluster graph. These results are complemented by a lower bound for the parameterization by the deletion distance to an outerplanar grap
Turing Kernelization for Finding Long Paths in Graphs Excluding a Topological Minor
No full textThe notion of Turing kernelization investigates whether a polynomial-time algorithm can solve an NP-hard problem, when it is aided by an oracle that can be queried for the answers to bounded-size subproblems. One of the main open problems in this direction is whether k-PATH admits a polynomial Turing kernel: can a polynomial-time algorithm determine whether an undirected graph has a simple path of length k, using an oracle that answers queries of size k^{O(1)}?
We show this can be done when the input graph avoids a fixed graph H as a topological minor, thereby significantly generalizing an earlier result for bounded-degree and K_{3,t}-minor-free graphs. Moreover, we show that k-PATH even admits a polynomial Turing kernel when the input graph is not H-topological-minor-free itself, but contains a known vertex modulator of size bounded polynomially in the parameter, whose deletion makes it so. To obtain our results, we build on the graph minors decomposition to show that any H-topological-minor-free graph that does not contain a k-path has a separation that can safely be reduced after communication with the oracle
On sparsification for computing treewidth
No full textWe investigate whether an n -vertex instance (G,k) of Treewidth, asking whether the graph G has treewidth at most k , can efficiently be made sparse without changing its answer. By giving a special form of OR -cross-composition, we prove that this is unlikely: if there is an ¿>0 and a polynomial-time algorithm that reduces n -vertex Treewidth instances to equivalent instances, of an arbitrary problem, with O(n2-¿) bits, then NP ¿ coNP / poly and the polynomial hierarchy collapses to its third level. Our sparsification lower bound has implications for structural parameterizations of Treewidth: parameterizations by measures l that do not exceed the number of vertices cannot have kernels with O(l2-¿) bits for any ¿>0 , unless NP ¿ coNP / poly. Motivated by the question of determining the optimal kernel size for Treewidth parameterized by the size of a vertex cover X , we improve the O(|X|3) -vertex kernel from Bodlaender et al. (SIDMA 2013) to a kernel with O(|X|2) vertices. Our improved kernel is based on the novel notion of treewidth-invariant set. We use the q -expansion lemma of Fomin et al. (STACS 2011) to find such sets efficiently in graphs whose order is superquadratic in their vertex cover number. We believe that our new reduction rule will be useful in practice
Turing kernelization for finding long paths and cycles in restricted graph classes
No full textThe k-PATH problem asks whether a given undirected graph has a (simple) path of length k. We prove that k-PATH has polynomial-size Turing kernels when restricted to planar graphs, graphs of bounded degree, claw-free graphs, or to K 3,t-minor-free graphs. This means that there is an algorithm that, given a k-PATH instance (G,k) belonging to one of these graph classes, computes its answer in polynomial time when given access to an oracle that solves k-PATH instances of size polynomial in k in a single step. Our techniques also apply to k-CYCLE, which asks for a cycle of length at least k
Kernelization lower bounds by cross-composition
No full textWe introduce the framework of cross-composition for proving kernelization lower bounds. A classical problem L and/or-cross-composes into a parameterized problem Q if it is possible to efficiently construct an instance of Q with polynomially bounded parameter value that expresses the logical and or or of a sequence of instances of L. Building on work by Bodlaender et al. and using results of Fortnow and Santhanam, Dell and van Melkebeek, and Drucker, we show that if an NP-hard problem and/or-cross-composes into a parameterized problem Q, then Q does not admit a polynomial kernel unless NP ⊆ coNP/poly and the polynomial hierarchy collapses. Our technique generalizes and strengthens the techniques of using composition algorithms and of transferring the lower bounds via polynomial parameter transformations. We show its applicability by proving kernelization lower bounds for a number of important graphs problems with structural (nonstandard) parameterizations, e.g., Clique, Chromatic Number, Weighted Feedback Vertex Set, and Weighted Odd Cycle Transversal do not admit polynomial kernels with respect to the vertex cover number of the input graphs unless the polynomial hierarchy collapses, contrasting the fact that these problems are trivially fixed-parameter tractable for this parameter. We have similar lower bounds for Feedback Vertex Set and Odd Cycle Transversal under structural parameterizations. After learning of our results, several teams of authors have successfully applied the cross-composition framework to different parameterized problems. For completeness, our presentation of the framework includes several extensions based on this follow-up work. For example, we show how a relaxed version of or-cross-compositions may be used to give lower bounds on the degree of the polynomial in the kernel size
Lower Bounds for Protrusion Replacement by Counting Equivalence Classes
No full textGarnero et al. [SIAM J. Discrete Math. 2015, 29(4):1864-1894] recently introduced a framework based on dynamic programming to make applications of the protrusion replacement technique constructive and to obtain explicit upper bounds on the involved constants. They show that for several graph problems, for every boundary size t one can find an explicit set R_t of representatives. Any subgraph H with a boundary of size t can be replaced with a representative H' in R_t such that the effect of this replacement on the optimum can be deduced from H and H' alone. Their upper bounds on the size of the graphs in R_t grow triple-exponentially with t. In this paper we complement their results by lower bounds on the sizes of representatives, in terms of the boundary size t. For example, we show that each set of planar representatives R_t for the Independent Set problem contains a graph with Omega(2^t / sqrt{4t}) vertices. This lower bound even holds for sets that only represent the planar subgraphs of bounded pathwidth. To obtain our results we provide a lower bound on the number of equivalence classes of the canonical equivalence relation for Independent Set on t-boundaried graphs. We also find an elegant characterization of the number of equivalence classes in general graphs, in terms of the number of monotone functions of a certain kind. Our results show that the number of equivalence classes is at most 2^{2^t}, improving on earlier bounds of the form (t+1)^{2^t}
