# W[2]

List of accepted papers for IPEC 2012

**1**. Marcin Pilipczuk and Michał Pilipczuk. 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-eps_d)^n n^O(1) time, for some constant eps_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-eps_d)^-n; hence, we prove that their number is bounded by (2-eps_d)^n.

**2**. Yijia Chen, Kord Eickmeyer and Jörg Flum. The exponential time hypothesis and the parameterized clique problem**Abstract**: In parameterized complexity there are three natural definitions offixed-parameter tractability called strongly uniform, weakly uniformand nonuniform fpt. Similarly, there are three notions ofsubexponential time, yielding three flavours of the exponential timehypothesis (ETH) stating that 3SAT is not solvable in subexponentialtime. It is known that ETH implies that p-Clique is notfixed-parameter tractable if both are taken to be strongly uniform orboth are taken to be uniform, and we extend this to the nonuniformcase. We also show that even weakly uniform subexponential time isstrictly contained in nonuniform subexponential time. Furthermore, wededuce from nonuniform ETH that no single exponent d allows forarbitrarily good fpt-approximations of clique.

**3**. Bruno Escoffier, Jérôme Monnot, Vangelis Paschos and Mingyu Xiao. 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 eachedge 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 scheme (with respect to the standard parameter) for the problem and, finally, we develop an O*(1.821^tau)-time exact algorithm where tau is the size of a minimumvertex cover of G.

**4**. Ivan Bliznets and Alexander Golovnev. 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 number of cases that need to be considered. Our improvement is based on a simple algorithm for a special case of MAX-SAT where each variable appears at most 3 times.

**5**. Paola Bonizzoni, Riccardo Dondi, Giancarlo Mauri and Italo Zoppis. 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 beensuccessfully applied. In this paper we consider two variants of SCS that have beenrecently introduced, Restricted Common Superstring (RCS) andSwapped Common Superstring (SWCS), and we investigate their parameterized complexity.We give two fixed-parameter algorithms, where the parameter is the size of thesolution, for SWCS and l-RCS (the RCS problem restricted to strings of lengthbounded by a parameter l). Furthermore, we complement these results by showingthat SWCS and l-RCS do not admit a polynomial kernel.

**6**. Lukasz Kowalik. Nonblocker in H-minor free graphs: kernelization meets discharging**Abstract**: Perhaps the best known kernelization result is the kernel of size $335k$ for the {\sc Planar Dominating Set} problem by Alber et al. [JACM 2004], later improved to $67k$ by Chen et al. [SICOMP 2007]. 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 $\epsilon>0$, unless $\P=\NP$. This improves the previous lower bound of $(2-\epsilon)k$ of Chen et al. 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 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 1-vertices is at distance at least 5 and every pair of 2-vertices is at distance at least 2 has a dominating set of size at most $\frac{3}7n$.

**7**. Jörg Flum and Moritz Müller. 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.

**8**. Petr Golovach, Pinar Heggernes, Dieter Kratsch and Reza Saei. An exact algorithm for Subset Feedback Vertex Set on chordal graphs**Abstract**: Given a graph G=(V,E) and a subset S of V, a subset U of 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^n) 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^n) 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^n) running time.

**9**. Fedor V. Fomin, Bart Jansen and Michał Pilipczuk. 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 a 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, Planarization, Eta 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 F-Minor-Free Deletion, which is to delete at most k vertices to obtain a graph with no minor from a fixed finite set 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 is contained in coNP/poly, we show that the problem of testing if a graph contains a given 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.

**10**. Cédric Bentz. A polynomial-time algorithm for planar multicuts with few source-sink pairs**Abstract**: Given an edge-weighted undirected graph and a list of ksource-sink pairs of vertices, the well-known minimum multicut problemconsists in selecting a minimum-weight set of edges whose removal leavesno path between every source and its corresponding sink. We give thefirst polynomial-time algorithm to solve this problem in planar graphs,when k is fixed. Previously, this problem was known to remain NP-hardin general graphs with fixed k, and in trees with arbitrary k; the mostnoticeable tractable case known so far was in planar graphs with fixed kand sources and sinks lying on the outer face.

**11**. Chiranjit Chakraborty and Rahul Santhanam. Instance Compression for the Polynomial Hierarchy and Beyond**Abstract**: We define instance compressibility for parametric problems in PH and PSPACE. We observe that the problem \Sigma_{i}CircuitSAT of deciding satisfiability of a quantified Boolean circuit with i-1 alternations of quantifiers starting with an existential uantifier is complete for parametric problems in \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 \Sigma_{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 is contained in NP/poly and PH collapses to the third level.Next, we define Succinct Interactive Proof (Succinct IP) and scrutinizing the proof of IP = PSPACE, we show that QBFormulaSAT (Quantified Boolean Formula Satisfiability) is in Succinct IP. On the contrary if QBFormulaSAT has Succinct PCPs, Polynomial Hierarchy (PH) collapses.

**12**. Abhijin Adiga, Jasine Babu and L. Sunil Chandran. 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 $\mathbb{R}^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 - \epsilon})$ factor for any $\epsilon >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. This generalizes the results in [3]. 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.

**13**. Petteri Kaski, Mikko Koivisto and Jesper Nederlof. 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.

**14**. Petteri Kaski, Mikko Koivisto and Janne H. Korhonen. Fast Monotone Summation over Disjoint Sets**Abstract**: We study the problem of computing an ensemble of multiplesums where the summands in each sum are indexed by subsetsof 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, thesum over the values of all subsetsof size $p$ that are {\em disjoint} from the subset of size $q$.We present an arithmetic circuit that, without subtraction, solves the problemusing $O((n^p+n^q)\log n)$ arithmetic gates, all monotone;for constant $p$, $q$ this is within the factor $\log n$ of theoptimal. The circuit design is based on viewingthe summation as a ``set nucleation'' task and using atree-projection approach to implement the nucleation.Applications include improved algorithms for counting heaviest $k$-paths in a weightedgraph, computing permanents of rectangular matrices, and dynamic feature selectionin machine learning.

**15**. Markus Bläser and Radu Curticapean. Weighted counting of k-matchings is #W[1]-hard**Abstract**: In the seminal paper for parameterized counting complexity, 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 kedges in total. This hardness result even holds for unweighted graphs.

**16**. Kenta Kitsunai, Yasuaki Kobayashi, Keita Komuro, Hisao Tamaki and Toshihiro Tano. Computing directed pathwidth in $O(1.89^n)$ time**Abstract**: We give an algorithm for computingthe directed pathwidth of a digraph with $n$ verticesin $O(1.89^{n})$ time. This is the first algorithmwith running time better than the straightforward $O^*(2^n)$.As a special case, it computes the pathwidth of an undirectedgraph in the same amount of time, improving onthe algorithm due to Suchan and Villanger whichruns in $O(1.9657^n)$ time.

**17**. James Abello, Pavel Klavík, Jan Kratochvíl and Tomáš Vyskočil. MSOL Restricted Contractibility to Planar Graphs**Abstract**: We study the computational complexity of graph planarization via edge contraction.The problem {\sc 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 $O(n^2 f(k))$ which solves a more general problem {\sc $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 $\ell$-subgraph contractability problem. In this setting, the set $S$ is required to contain connected subgraphs of size at most $\ell$. This problem can be solved in time $O(n^2 f'(k,l))$ using the general algorithm. We also show that for $\ell \ge 2$ the problem is NP-complete. And it remains NP-complete when generalized for a fixed genus(instead of planar graphs).

**18**. Michael Elberfeld, Christoph Stockhusen and Till Tantau. On the Space Complexity of Parameterized Problems**Abstract**: Parameterized complexity theory measures the complexity ofcomputational problems predominantly in terms of their parameterizedtime complexity. The purpose of the present paper is todemonstrate that the study of parameterized space complexitycan give new insights into the complexity of well-studiedparameterized problems like the feedback vertex set problem. We showthat the undirected and the directed feedback vertex set problems havedifferent parameterized space complexities, unless L = NL; whichexplains why the two problem variants seem to necessitate differentalgorithmic approaches even though their parameterized time complexityis the same. For a number of further natural parameterized problems,including the longest common subsequence problem and the acceptanceproblem for multi-head automata, we show that they lie in or arecomplete for different parameterized space classes; which explains whyprevious attempts at proving completeness of these problems forparameterized time classes have failed.

**19**. Adam Bouland, Anuj Dawar and Eryk Kopczyński. On Tractable Parameterizations of Graph Isomorphism**Abstract**: We show that the Graph Isomorphism problem is fixed-parameter tractable when parameterized by the tree-depth of the graph and when parameterized by the max-leaf-number. A common generalization of these two results is proved by deploying new variants of cops-and-robbers games.

**20**. Sepp Hartung, Christian Komusiewicz and Andre Nichterlein. Parameterized Algorithmics for Finding 2-Clubs: Upper and Lower Bounds and Computational Experiments**Abstract**: Given an undirected graph $G=(V,E)$ and an integer $\size \ge 1$, the NP-hard 2-Club problem asks for a vertex set $S\subseteq V$ of size at least $k$ 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 coNP\subset NP/poly, 2-Clubdoes not admit a polynomial kernel with respect to the size of a vertex cover of $G$.Second, we show that, under the strong exponential time hypothesis, a previous $O^*(2^{|V|-k})$ search tree algorithm [Schäfer et al., Optim.~Lett.~2012] cannot be improved and that, unless coNP\subset NP/poly, there is no polynomialkernel for the dual parameter $|V|-k$. Finally, we show that, in spite of this lower bound, the search tree algorithm for the dual parameter~$|V|-\size$ can betuned into an efficient exact algorithm for 2-Club that substantially outperforms previous implementations.

**21**. Christian Komusiewicz and Manuel Sorge. Finding Dense Subgraphs of Sparse Graphs**Abstract**: We further investigate the computational complexity of the Densest-k-Subgraph problem, where the input is an undirected graph $G$, and one wantsto find a subgraph on exactly $k$ vertices with a maximum number ofedges. We extend previous work on Densest-k-Subgraph by studying itsparameterized complexity. On the positive side, we showthat, when fixing some constant minimum density of the soughtsubgraph, Densest-k-Subgraph becomes fixed-parameter tractable with respect toeither of the parameters maximum degree and $h$-index. Furthermore,we obtain a fixed-parameter algorithm for Densest-k-Subgraph with respect to thecombined parameter ``degeneracy of $G$ and $n-k$''. On the negativeside, we find that Densest-k-subgraph is W[1]-hard with respect to the combinedparameter ``solution size $k$ and degeneracy of $G$'', and, somewhatsurprisingly, that \dsg{} is W[1]-hard with respect to theparameter $n-k$ in graphs with $n$ vertices.

**22**. Narges Simjour and Naomi Nishimura. Enumerating neighbour and closest strings**Abstract**: We present the first parameterized enumeration algorithm for the neighbour string problem, where a neighbour string of m input strings, each of length l, 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 (the distance allotments) are equal; this is known as the closest string problem, with applications in computational biology and coding theory.Earlier parameterized algorithms all built on the search-tree approach of Gramm et al. on the closest string problem, generalized by Ma and Sun to the neighbour string problem; a solution was built step by step in different subsets of the positions, each subset based on differences between two (or, more recently, three) strings in the input. Our new approach gives a clean way to make use of all theinput strings in categorizing solutions, as well as the ability to tune the running time to optimize the algorithm for varying relative values of $m$ and d = max_i d_i. Using a new analysis technique, we show that for strings over an alphabetSigma, we can choose a tuning constant lambda <= 0.75 to obtain an algorithm that runs in time O(ml + (md)^{f(lambda)}(|Sigma|-1)^d 5^{(1+lambda)d}), where f is a function that decreases with increasing lambda. When Sigma = {0,1}, the dependency on d is improved asymptotically over the previous best parameterized time bound of O(ml + md^3 6.7308^d) for finding a single solution. When d is logarithmically bounded in terms of the input size, our enumeration algorithm runs in polynomial time.

**23**. Faisal Abu-Khzam and Mazen Bu Khuzam. 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' \leq k$ and $|V(G')| < 97k$.In addition to the improved kernel bound (from $112k$ to $97k$), our algorithmfeatures simple linear-time reduction procedures that can be applied to the general Feedback Vertex Set problem.