Parameterized and Exact Computation

Frontmatter

The Path Taken for k-Path

Abstract

We give a historical account of the parametrized results for the k-Path problem: given a graph G and a positive integer k, is there a simple path in G of length k. Throughout the years several ingenious approaches have been used, steadily decreasing the run time bound. Moreover, the techniques used have often found lots of other applications. We will revisit some of the old results, as well as cover the state-of-the-art techniques based on algebraic sieves. We will also briefly talk about what is known about counting k-paths.

Andreas Björklund

Randomized Techniques for Parameterized Algorithms

Abstract

Since the introduction of the Color Coding technique in 1994 by Alon, Yuster, and Zwick, randomization has been part of the toolkit for proving fixed-parameter tractability results. It seems that randomization is very well suited to parameterized algorithms: if the task is to find a solution of size k and only those random choices need to be correct that are directly related to the solution, then typically we can bound the error probability by a function of k. The talk will overview through various concrete examples how randomization appears in fixed-parameter tractability results. We argue that in many cases randomization appears in form of a reduction: it allows us to reduce the problem we are trying to solve to an easier and more structured problem.

Dániel Marx

Finding a Maximum Induced Degenerate Subgraph Faster Than 2 n

Abstract

In this paper we study the problem of finding a maximum induced d-degenerate subgraph in a given n-vertex graph from the point of view of exact algorithms. We show that for any fixed d one can find a maximum induced d-degenerate subgraph in randomized \((2-\varepsilon _d)^nn^{\mathcal{O}(1)}\) time, for some constant ε _d  > 0 depending only on d. Moreover, our algorithm can be used to sample inclusion-wise maximal induced d-degenerate subgraphs in such a manner that every such subgraph is output with probability at least (2 − ε _d )^− n ; hence, we prove that their number is bounded by (2 − ε _d ) ⁿ .

Marcin Pilipczuk, Michał Pilipczuk

The Exponential Time Hypothesis and the Parameterized Clique Problem

Abstract

In parameterized complexity there are three natural definitions of fixed-parameter tractability called strongly uniform, weakly uniform and nonuniform fpt. Similarly, there are three notions of subexponential time, yielding three flavours of the exponential time hypothesis (ETH) stating that 3Sat is not solvable in subexponential time. It is known that ETH implies that p -Clique is not fixed-parameter tractable if both are taken to be strongly uniform or both are taken to be uniform, and we extend this to the nonuniform case. We also show that even the containment of weakly uniform subexponential time in nonuniform subexponential time is strict. Furthermore, we deduce from nonuniform ETH that no single exponent d allows for arbitrarily good fpt-approximations of clique.

Yijia Chen, Kord Eickmeyer, Jörg Flum

New Results on Polynomial Inapproximability and Fixed Parameter Approximability of edge dominating set

Abstract

An edge dominating set in a graph G = (V,E) is a subset S of edges such that each edge in E − S is adjacent to at least one edge in S. The edge dominating set problem, to find an edge dominating set of minimum size, is a basic and important NP-hard problem that has been extensively studied in approximation algorithms and parameterized complexity. In this paper, we present improved hardness results and parameterized approximation algorithms for edge dominating set. More precisely, we first show that it is NP-hard to approximate edge dominating set in polynomial time within a factor better than 1.18. Next, we give a parameterized approximation schema (with respect to the standard parameter) for the problem and, finally, we develop an O ^*(1.821 ^τ )-time exact algorithm where τ is the size of a minimum vertex cover of G.

Bruno Escoffier, Jérôme Monnot, Vangelis Th. Paschos, Mingyu Xiao

A New Algorithm for Parameterized MAX-SAT

Abstract

We show how to check whether at least k clauses of an input formula in CNF can be satisfied in time O ^*(1.358 ^k ). This improves the bound O ^*(1.370 ^k ) proved by Chen and Kanj more than 10 years ago. Though the presented algorithm is based on standard splitting techniques its core are new simplification rules that often allow to reduce the size of case analysis. Our improvement is based on a simple algorithm for a special case of MAX-SAT where each variable appears at most 3 times.

Ivan Bliznets, Alexander Golovnev

Restricted and Swap Common Superstring: A Parameterized View

Abstract

In several areas, in particular in bioinformatics and in AI planning, Shortest Common Superstring problem (SCS) and variants thereof have been successfully applied. In this paper we consider two variants of SCS recently introduced (Restricted Common Superstring, \(\ensuremath{\text{\textsc{RCS}}}\)) and (Swapped Common Superstring, \(\ensuremath{\text{\textsc{SWCS}}}\)). In \(\ensuremath{\text{\textsc{RCS}}}\) we are given a set S of strings and a multiset, and we look for an ordering \(\mathcal{M}_o\) of \(\mathcal{M}\) such that the number of input strings which are substrings of \(\mathcal{M}_o\) is maximized. In \(\ensuremath{\text{\textsc{SWCS}}}\) we are given a set S of strings and a text \(\mathcal{T}\), and we look for a swap ordering \(\mathcal{T}_o\) of \(\mathcal{T}\) (an ordering of \(\mathcal{T}\) obtained by swapping only some pairs of adjacent characters) such that the number of input strings which are substrings of \(\mathcal{T}_o\) is maximized. In this paper we investigate the parameterized complexity of the two problems. We give two fixed-parameter algorithms, where the parameter is the size of the solution, for \(\ensuremath{\text{\textsc{SWCS}}}\) and \(\ensuremath{\text{\textsc{$\ell$-RCS}}} \) (the \(\ensuremath{\text{\textsc{RCS}}}\) problem restricted to strings of length bounded by a parameter ℓ). Furthermore, we complement these results by showing that \(\ensuremath{\text{\textsc{SWCS}}}\) and \(\ensuremath{\text{\textsc{$\ell$-RCS}}} \) do not admit a polynomial kernel.

Paola Bonizzoni, Riccardo Dondi, Giancarlo Mauri, Italo Zoppis

Nonblocker in H-Minor Free Graphs: Kernelization Meets Discharging

Abstract

Perhaps the best known kernelization result is the kernel of size 335k for the Planar Dominating Set problem by Alber et al. [1], later improved to 67k by Chen et al. [5]. This result means roughly, that the problem of finding the smallest dominating set in a planar graph is easy when the optimal solution is small. On the other hand, it is known that Planar Dominating Set parameterized by k′ = |V| − k (also known as Planar Nonblocker) has a kernel of size 2k′. This means that Planar Dominating Set is easy when the optimal solution is very large. We improve the kernel for Planar Nonblocker to \(\frac{7}{4}k'\). This also implies that Planar Dominating Set has no kernel of size at most \((\frac{7}{3}-\epsilon)k\), for any ε > 0, unless P = NP. This improves the previous lower bound of (2 − ε)k of [5]. Both of these results immediately generalize to H-minor free graphs (without changing the constants).

In our proof of the bound on the kernel size we use a variant of the discharging method (used e.g. in the proof of the four color theorem). We give some arguments that this method is natural in the context of kernelization and we hope it will be applied to get improved kernel size bounds for other problems as well.

As a by-product we show a result which might be of independent interest: every n-vertex graph with no isolated vertices and such that every pair of degree 1 vertices is at distance at least 5 and every pair of degree 2 vertices is at distance at least 2 has a dominating set of size at most \(\frac{3}7n\).

Łukasz Kowalik

Some Definitorial Suggestions for Parameterized Proof Complexity

Abstract

We introduce a (new) notion of parameterized proof system. For parameterized versions of standard proof systems such as Extended Frege and Substitution Frege we compare their complexity with respect to parameterized simulations.

Jörg Flum, Moritz Müller

An Exact Algorithm for Subset Feedback Vertex Set on Chordal Graphs

Abstract

Given a graph G = (V,E) and a set S ⊆ V, a set U ⊆ V is a subset feedback vertex set of (G,S) if no cycle in G[V ∖ U] contains a vertex of S. The Subset Feedback Vertex Set problem takes as input G, S, and an integer k, and the question is whether (G,S) has a subset feedback vertex set of cardinality or weight at most k. Both the weighted and the unweighted versions of this problem are NP-complete on chordal graphs, even on their subclass split graphs. We give an algorithm with running time O(1.6708 ⁿ ) that enumerates all minimal subset feedback vertex sets on chordal graphs with n vertices. As a consequence, Subset Feedback Vertex Set can be solved in time O(1.6708 ⁿ ) on chordal graphs, both in the weighted and in the unweighted case. On arbitrary graphs, the fastest known algorithm for the problems has O(1.8638 ⁿ ) running time.

Petr A. Golovach, Pinar Heggernes, Dieter Kratsch, Reza Saei

Preprocessing Subgraph and Minor Problems: When Does a Small Vertex Cover Help?

Abstract

We prove a number of results around kernelization of problems parameterized by a vertex cover of the input graph. We provide two simple general conditions characterizing problems admitting kernels of polynomial size. Our characterizations not only give generic explanations for the existence of many known polynomial kernels for problems like Odd Cycle Transversal, Chordal Deletion, η -Transversal, Long Path, Long Cycle, or H -packing, parameterized by the size of a vertex cover, they also imply new polynomial kernels for problems like \(\mathcal{F}\)-Minor-Free-Deletion, which is to delete at most k vertices to obtain a graph with no minor from a fixed finite set \(\mathcal{F}\).

While our characterization captures many interesting problems, the kernelization complexity landscape of problems parameterized by vertex cover is much more involved. We demonstrate this by several results about induced subgraph and minor containment, which we find surprising. While it was known that testing for an induced complete subgraph has no polynomial kernel unless NP ⊆ coNP/poly, we show that the problem of testing if a graph contains a complete graph on t vertices as a minor admits a polynomial kernel. On the other hand, it was known that testing for a path on t vertices as a minor admits a polynomial kernel, but we show that testing for containment of an induced path on t vertices is unlikely to admit a polynomial kernel.

Fedor V. Fomin, Bart M. P. Jansen, Michał Pilipczuk

A Polynomial-Time Algorithm for Planar Multicuts with Few Source-Sink Pairs

Abstract

Given an edge-weighted undirected graph and a list of k source-sink pairs of vertices, the well-known minimum multicut problem consists in selecting a minimum-weight set of edges whose removal leaves no path between every source and its corresponding sink. We give the first polynomial-time algorithm to solve this problem in planar graphs, when k is fixed. Previously, this problem was known to remain NP-hard in general graphs with fixed k, and in trees with arbitrary k; the most noticeable tractable case known so far was in planar graphs with fixed k and sources and sinks lying on the outer face.

Cédric Bentz

Instance Compression for the Polynomial Hierarchy and beyond

Abstract

We define instance compressibility ([5,7]) for parametric problems in PH and PSPACE. We observe that the problem Σ _i CircuitSAT of deciding satisfiability of a quantified Boolean circuit with i − 1 alternations of quantifiers starting with an existential quantifier is complete for parametric problems in the class \(\Sigma_{i}^{p}\) with respect to W-reductions, and that analogously the problem QBCSAT (Quantified Boolean Circuit Satisfiability) is complete for parametric problems in PSPACE with respect to W-reductions. We show the following results about these problems:

1

If CircuitSAT is non-uniformly compressible within NP, then Σ _i CircuitSAT is non-uniformly compressible within NP, for any i ≥ 1.

 

2

If QBCSAT is non-uniformly compressible (or even if satisfiability of quantified Boolean CNF formulae is non-uniformly compressible), then PSPACE ⊆ NP/poly and PH collapses to the third level.

 

Next, we define Succinct Interactive Proof (Succinct IP) and by adapting the proof of IP = PSPACE ([4,2]), we show that QBFormulaSAT (Quantified Boolean Formula Satisfiability) is in Succinct IP. On the contrary if QBFormulaSAT has Succinct PCPs ([11]), Polynomial Hierarchy (PH) collapses.

Chiranjit Chakraborty, Rahul Santhanam

Polynomial Time and Parameterized Approximation Algorithms for Boxicity

Abstract

The boxicity (cubicity) of a graph G, denoted by box(G) (respectively cub(G)), is the minimum integer k such that G can be represented as the intersection graph of axis parallel boxes (cubes) in ℝ ^k . The problem of computing boxicity (cubicity) is known to be inapproximable in polynomial time even for graph classes like bipartite, co-bipartite and split graphs, within an O(n ^{0.5 − ε} ) factor for any ε > 0, unless NP = ZPP.

We prove that if a graph G on n vertices has a clique on n − k vertices, then box(G) can be computed in time \(n^2 2^{{O(k^2 \log k)}}\). Using this fact, various FPT approximation algorithms for boxicity are derived. The parameter used is the vertex (or edge) edit distance of the input graph from certain graph families of bounded boxicity - like interval graphs and planar graphs. Using the same fact, we also derive an \(O\left(\frac{n\sqrt{\log \log n}}{\sqrt{\log n}}\right)\) factor approximation algorithm for computing boxicity, which, to our knowledge, is the first o(n) factor approximation algorithm for the problem. We also present an FPT approximation algorithm for computing the cubicity of graphs, with vertex cover number as the parameter.

Abhijin Adiga, Jasine Babu, L. Sunil Chandran

Homomorphic Hashing for Sparse Coefficient Extraction

Abstract

We study classes of Dynamic Programming (DP) algorithms which, due to their algebraic definitions, are closely related to coefficient extraction methods. DP algorithms can easily be modified to exploit sparseness in the DP table through memorization. Coefficient extraction techniques on the other hand are both space-efficient and parallelisable, but no tools have been available to exploit sparseness. We investigate the systematic use of homomorphic hash functions to combine the best of these methods and obtain improved space-efficient algorithms for problems including LINEAR SAT, SET PARTITION and SUBSET SUM. Our algorithms run in time proportional to the number of nonzero entries of the last segment of the DP table, which presents a strict improvement over sparse DP. The last property also gives an improved algorithm for CNF SAT and SET COVER with sparse projections.

Petteri Kaski, Mikko Koivisto, Jesper Nederlof

Fast Monotone Summation over Disjoint Sets

Abstract

We study the problem of computing an ensemble of multiple sums where the summands in each sum are indexed by subsets of size p of an n-element ground set. More precisely, the task is to compute, for each subset of size q of the ground set, the sum over the values of all subsets of size p that are disjoint from the subset of size q. We present an arithmetic circuit that, without subtraction, solves the problem using O((n ^p  + n ^q )logn) arithmetic gates, all monotone; for constant p, q this is within the factor logn of the optimal. The circuit design is based on viewing the summation as a “set nucleation” task and using a tree-projection approach to implement the nucleation. Applications include improved algorithms for counting heaviest k-paths in a weighted graph, computing permanents of rectangular matrices, and dynamic feature selection in machine learning.

Petteri Kaski, Mikko Koivisto, Janne H. Korhonen

Weighted Counting of k-Matchings Is #W[1]-Hard

Abstract

In the seminal paper for parameterized counting complexity [1], the following problem is conjectured to be #W[1]-hard: Given a bipartite graph G and a number k ∈ ℕ, which is considered as a parameter, count the number of matchings of size k in G.

We prove hardness for a natural weighted generalization of this problem: Let G = (V,E,w) be an edge-weighted graph and define the weight of a matching as the product of weights of all edges in the matching. We show that exact evaluation of the sum over all such weighted matchings of size k is #W[1]-hard for bipartite graphs G.

As an intermediate step in our reduction, we also prove #W[1]- hardness of the problem of counting k-partial cycle covers, which are vertex-disjoint unions of cycles including k edges in total. This hardness result even holds for unweighted graphs.

Markus Bläser, Radu Curticapean

Computing Directed Pathwidth in O(1.89 n ) Time

Abstract

We give an algorithm for computing the directed pathwidth of a digraph with n vertices in O(1.89 ⁿ ) time. This is the first algorithm with running time better than the straightforward O ^*(2 ⁿ ). As a special case, it computes the pathwidth of an undirected graph in the same amount of time, improving on the algorithm due to Suchan and Villanger which runs in O(1.9657 ⁿ ) time.

Kenta Kitsunai, Yasuaki Kobayashi, Keita Komuro, Hisao Tamaki, Toshihiro Tano

MSOL Restricted Contractibility to Planar Graphs

Abstract

We study the computational complexity of graph planarization via edge contraction. The problem Contract asks whether there exists a set S of at most k edges that when contracted produces a planar graph. We give an FPT algorithm in time \(\mathcal{O}(n^2 f(k))\) which solves a more general problem P-RestrictedContract in which S has to satisfy in addition a fixed inclusion-closed MSOL formula P.

For different formulas P we get different problems. As a specific example, we study the ℓ-subgraph contractability problem in which edges of a set S are required to form disjoint connected subgraphs of size at most ℓ. This problem can be solved in time \(\mathcal{O}(n^2 f'(k,l))\) using the general algorithm. We also show that for ℓ ≥ 2 the problem is NP-complete. And it remains NP-complete when generalized for a fixed genus (instead of planar graphs).

James Abello, Pavel Klavík, Jan Kratochvíl, Tomáš Vyskočil

On the Space Complexity of Parameterized Problems

Abstract

Parameterized complexity theory measures the complexity of computational problems predominantly in terms of their parameterized time complexity. The purpose of the present paper is to demonstrate that the study of parameterized space complexity can give new insights into the complexity of well-studied parameterized problems like the feedback vertex set problem. We show that the undirected and the directed feedback vertex set problems have different parameterized space complexities, unless L = NL; which explains why the two problem variants seem to necessitate different algorithmic approaches even though their parameterized time complexity is the same. For a number of further natural parameterized problems, including the longest common subsequence problem and the acceptance problem for multi-head automata, we show that they lie in or are complete for different parameterized space classes; which explains why previous attempts at proving completeness of these problems for parameterized time classes have failed.

Michael Elberfeld, Christoph Stockhusen, Till Tantau

On Tractable Parameterizations of Graph Isomorphism

Abstract

The fixed-parameter tractability of graph isomorphism is an open problem with respect to a number of natural parameters, such as tree-width, genus and maximum degree. We show that graph isomorphism is fixed-parameter tractable when parameterized by the tree-depth of the graph. We also extend this result to a parameter generalizing both tree-depth and max-leaf-number by deploying new variants of cops-and-robbers games.

Adam Bouland, Anuj Dawar, Eryk Kopczyński

Parameterized Algorithmics and Computational Experiments for Finding 2-Clubs

Abstract

Given an undirected graph G = (V,E) and an integer ℓ ≥ 1, the NP-hard 2-Club problem asks for a vertex set S ⊆ V of size at least ℓ such that the subgraph induced by S has diameter at most two. In this work, we extend previous parameterized complexity studies for 2-Club. On the positive side, we give polynomial kernels for the parameters “feedback edge set size of G” and “size of a cluster editing set of G” and present a direct combinatorial algorithm for the parameter “treewidth of G”. On the negative side, we first show that unless NP ⊆ coNP/poly, 2-Club does not admit a polynomial kernel with respect to the “size of a vertex cover of G”. Next, we show that, under the strong exponential time hypothesis, a previous O ^*(2^{|V| − ℓ}) search tree algorithm [Schäfer et al., Optim. Lett. 2012] cannot be improved and that, unless NP ⊆ coNP/poly, there is no polynomial kernel for the dual parameter |V| − ℓ. Finally, we show that, in spite of this lower bound, the search tree algorithm for the dual parameter |V| − ℓ can be tuned into an efficient exact algorithm for 2-Club that substantially outperforms previous implementations.

Sepp Hartung, Christian Komusiewicz, André Nichterlein

Finding Dense Subgraphs of Sparse Graphs

Abstract

We investigate the computational complexity of the Densest- k -Subgraph (D k S) problem, where the input is an undirected graph G = (V,E) and one wants to find a subgraph on exactly k vertices with a maximum number of edges. We extend previous work on D k S by studying its parameterized complexity. On the positive side, we show that, when fixing some constant minimum density μ of the sought subgraph, D k S becomes fixed-parameter tractable with respect to either of the parameters maximum degree and h-index of G. Furthermore, we obtain a fixed-parameter algorithm for D k S with respect to the combined parameter “degeneracy of G and |V| − k”. On the negative side, we find that D k S is W[1]-hard with respect to the combined parameter “solution size k and degeneracy of G”. We furthermore strengthen a previous hardness result for D k S [Cai, Comput. J., 2008] by showing that for every fixed μ, 0 < μ < 1, the problem of deciding whether G contains a subgraph of density at least μ is W[1]-hard with respect to the parameter |V| − k.

Christian Komusiewicz, Manuel Sorge

Enumerating Neighbour and Closest Strings

Abstract

We present the first parameterized enumeration algorithm for the neighbour string problem, where a neighbour string of n input strings, each of length ℓ, is a string that differs from input s _i in no more than d _i positions. The problem is NP-complete even when the d _i ’s are equal; this is the well-known closest string problem.

Our new approach gives us the ability to tune the running time to optimize the algorithm for varying relative values of n and d =  max _i d _i . For strings over an alphabet Σ, we can choose a tuning constant λ to obtain an algorithm that runs in time O(nℓ + (n d) ^f(λ)(|Σ| − 1) ^d 5^{(1 + λ)d} ), where f is a function that decreases with increasing λ. When Σ = {0,1}, the dependency on d is an asymptotic improvement over the previous best parameterized time bound of O(nℓ + n d ³ 6.7308 ^d ) for finding a single solution.

Naomi Nishimura, Narges Simjour

An Improved Kernel for the Undirected Planar Feedback Vertex Set Problem

Abstract

We consider the parameterized Feedback Vertex Set problem on unweighted, undirected planar graphs. We present a kernelization algorithm that takes a planar graph G and an integer k as input and either decides that (G,k) is a no instance or produces an equivalent (kernel) instance (G′,k′) such that k′ ≤ k and |V(G′)| < 97k. In addition to the improved kernel bound (from 112k to 97k), our algorithm features simple linear-time reduction procedures that can be applied to the general Feedback Vertex Set problem.

Faisal N. Abu-Khzam, Mazen Bou Khuzam

Backmatter