Skip to main content
main-content

Über dieses Buch

This book constitutes the thoroughly refereed post-conference proceedings of the 6th International Symposium on Parameterized and Exact Computation, IPEC 2011, in Saarbrücken, Germany, in September 2011. The 21 revised full papers presented were carefully reviewed and selected from 40 submissions. The topics addressed cover research in all aspects of parameterized and exact computation and complexity, including but not limited to new techniques for the design and analysis of parameterized and exact algorithms, fixed-parameter tractability results, parameterized complexity theory, relationship between parameterized complexity and traditional complexity classifications, applications of parameterized and exact computation, and implementation issues of parameterized and exact algorithms.

Inhaltsverzeichnis

Frontmatter

On Multiway Cut Parameterized above Lower Bounds

Abstract
In this paper we consider two above lower bound parameterizations of the Node Multiway Cut problem — above the maximum separating cut and above a natural LP-relaxation — and prove them to be fixed-parameter tractable. Our results imply O *(4 k ) algorithms for Vertex Cover above Maximum Matching and Almost 2-SAT as well as an O *(2 k ) algorithm for Node Multiway Cut with a standard parameterization by the solution size, improving previous bounds for these problems.
Marek Cygan, Marcin Pilipczuk, Michał Pilipczuk, Jakub Onufry Wojtaszczyk

Parameterized Complexity of Firefighting Revisited

Abstract
The Firefighter problem is to place firefighters on the vertices of a graph to prevent a fire with known starting point from lighting up the entire graph. In each time step, a firefighter may be permanently placed on an unburned vertex and the fire spreads to its neighborhood in the graph in so far no firefighters are protecting those vertices. The goal is to let as few vertices burn as possible. This problem is known to be NP-complete, even when restricted to bipartite graphs or to trees of maximum degree three. Initial study showed the Firefighter problem to be fixed-parameter tractable on trees in various parameterizations. We complete these results by showing that the problem is in FPT on general graphs when parameterized by the number of burned vertices, but has no polynomial kernel on trees, resolving an open problem. Conversely, we show that the problem is W[1]-hard when parameterized by the number of unburned vertices, even on bipartite graphs. For both parameterizations, we additionally give refined algorithms on trees, improving on the running times of the known algorithms.
Marek Cygan, Fedor V. Fomin, Erik Jan van Leeuwen

Parameterized Complexity in Multiple-Interval Graphs: Domination

Abstract
We show that several variants of the problem k -Dominating Set, including k -Connected Dominating Set, k -Independent Dominating Set, k -Dominating Clique, d -Distance k -Dominating Set, k -Perfect Code and d -Distance k -Perfect Code, when parameterized by the solution size k, remain W[1]-hard in either multiple-interval graphs or their complements or both.
Minghui Jiang, Yong Zhang

A Faster Algorithm for Dominating Set Analyzed by the Potential Method

Abstract
Measure and Conquer is a recently developed technique to analyze worst-case complexity of backtracking algorithms. The traditional measure and conquer analysis concentrates on one branching at once by using only small number of variables. In this paper, we extend the measure and conquer analysis and introduce a new analyzing technique named “potential method” to deal with consecutive branchings together. In potential method, the optimization problem becomes sparse; therefore, we can use large number of variables. We applied this technique to the minimum dominating set problem and obtained the current fastest algorithm that runs in O(1.4864 n ) time and polynomial space. We also combined this algorithm with a precalculation by dynamic programming and obtained O(1.4689 n ) time and space algorithm. These results show the power of the potential method and possibilities of future applications to other problems.
Yoichi Iwata

Contracting Graphs to Paths and Trees

Abstract
Vertex deletion and edge deletion problems play a central role in Parameterized Complexity. Examples include classical problems like Feedback Vertex Set, Odd Cycle Transversal, and Chordal Deletion. The study of analogous edge contraction problems has so far been left largely unexplored from a parameterized perspective. We consider two basic problems of this type: Tree Contraction and Path Contraction. These two problems take as input an undirected graph G on n vertices and an integer k, and the task is to determine whether we can obtain an acyclic graph or a path, respectively, by a sequence of at most k edge contractions in G. We present an algorithm with running time 4.98 k n O(1) for Tree Contraction, based on a variant of the color coding technique of Alon, Yuster and Zwick, and an algorithm with running time 2 k + o(k) + n O(1) for Path Contraction. Furthermore, we show that Path Contraction has a kernel with at most 5k + 3 vertices, while Tree Contraction does not have a polynomial kernel unless NP ⊆ coNP/poly. We find the latter result surprising, because of the connection between Tree Contraction and Feedback Vertex Set, which is known to have a kernel with 4k 2 vertices.
Pinar Heggernes, Pim van ’t Hof, Benjamin Lévêque, Daniel Lokshtanov, Christophe Paul

Increasing the Minimum Degree of a Graph by Contractions

Abstract
The Degree Contractibility problem is to test whether a given graph G can be modified to a graph of minimum degree at least d by using at most k contractions. We prove the following three results. First, Degree Contractibility is NP-complete even when d = 14. Second, it is fixed-parameter tractable when parameterized by k and d. Third, it is W[1]-hard when parameterized by k. We also study its variant where the input graph is weighted, i.e., has some edge weighting and the contractions preserve these weights. The Weighted Degree Contractibility problem is to test if a weighted graph G can be contracted to a weighted graph of minimum weighted degree at least d by using at most k weighted contractions. We show that this problem is NP-complete and that it is fixed-parameter tractable when parameterized by k.
Petr A. Golovach, Marcin Kamiński, Daniël Paulusma, Dimitrios M. Thilikos

Planar Disjoint-Paths Completion

Abstract
We introduce Planar Disjoint Paths Completion, a completion counterpart of the Disjoint Paths problem, and study its parameterized complexity. The problem can be stated as follows: given a plane graph G, k pairs of terminals, and a face F of G, find a minimum-size set of edges, if one exists, to be added inside F so that the embedding remains planar and the pairs become connected by k disjoint paths in the augmented network. Our results are twofold: first, we give an explicit bound on the number of necessary additional edges if a solution exists. This bound is a function of k, independent of the size of G. Second, we show that the problem is fixed-parameter tractable, in particular, it can be solved in time f(kn 2.
Isolde Adler, Stavros G. Kolliopoulos, Dimitrios M. Thilikos

Sparse Solutions of Sparse Linear Systems: Fixed-Parameter Tractability and an Application of Complex Group Testing

Abstract
A vector with at most k nonzeros is called k-sparse. We show that enumerating the support vectors of k-sparse solutions to a system Ax = b of r-sparse linear equations (i.e., where the rows of A are r-sparse) is fixed-parameter tractable (FPT) in the combined parameter r,k. For r = 2 the problem is simple. For 0,1-matrices A we can also compute an O(rk r ) kernel. For systems of linear inequalities we get an FPT result in the combined parameter d,k, where d is the total number of minimal solutions. This is achieved by interpeting the problem as a case of group testing in the complex model. The problems stem from the reconstruction of chemical mixtures by observable reaction products.
Peter Damaschke

New Upper Bounds for MAX-2-SAT and MAX-2-CSP w.r.t. the Average Variable Degree

Abstract
MAX-2-SAT and MAX-2-CSP are important NP-hard optimization problems generalizing many graph problems. Despite many efforts, the only known algorithm (due to Williams) solving them in less than 2 n steps uses exponential space. Scott and Sorkin give an algorithm with \(2^{n(1-\frac{2}{d+1})}\) time and polynomial space for these problems, where d is the average variable degree. We improve this bound to \(O^*(2^{n(1-\frac{10/3}{d+1})})\) for MAX-2-SAT and \(O^*(2^{n(1-\frac{3}{d+1})})\) for MAX-2-CSP. We also prove stronger upper bounds for d bounded from below. E.g., for d ≥ 10 the bounds improve to \(O^*(2^{n(1-\frac{3.469}{d+1})})\) and \(O^*(2^{n(1-\frac{3.221}{d+1})})\), respectively. As a byproduct we get a simple proof of an \(O^*(2^\frac{m}{5.263})\) upper bound for MAX-2-CSP, where m is the number of constraints. This matches the best known upper bound w.r.t. m due to Gaspers and Sorkin.
Alexander Golovnev

Improved Parameterized Algorithms for above Average Constraint Satisfaction

Abstract
For many constraint satisfaction problems, the algorithm which chooses a random assignment achieves the best possible approximation ratio. For instance, a simple random assignment for Max-E3-Sat allows 7/8-approximation and for every ε > 0 there is no polynomial-time (7/8 + ε)-approximation unless P=NP. Another example is the Permutation CSP of bounded arity. Given the expected fraction ρ of the constraints satisfied by a random assignment (i.e. permutation), there is no (ρ + ε)-approximation algorithm for every ε > 0, assuming the Unique Games Conjecture (UGC).
In this work, we consider the following parameterization of constraint satisfaction problems. Given a set of m constraints of constant arity, can we satisfy at least ρm + k constraint, where ρ is the expected fraction of constraints satisfied by a random assignment? Constraint Satisfaction Problems above Average have been posed in different forms in the literature [18,17]. We present a faster parameterized algorithm for deciding whether m/2 + k/2 equations can be simultaneously satisfied over \({\mathbb F}_2\). As a consequence, we obtain O(k)-variable bikernels for boolean CSPs of arity c for every fixed c, and for permutation CSPs of arity 3. This implies linear bikernels for many problems under the “above average” parameterization, such as Max-c-Sat, Set-Splitting, Betweenness and Max Acyclic Subgraph. As a result, all the parameterized problems we consider in this paper admit 2O(k)-time algorithms.
We also obtain non-trivial hybrid algorithms for every Max c-CSP: for every instance I, we can either approximate I beyond the random assignment threshold in polynomial time, or we can find an optimal solution to I in subexponential time.
Eun Jung Kim, Ryan Williams

On Polynomial Kernels for Structural Parameterizations of Odd Cycle Transversal

Abstract
The Odd Cycle Transversal problem (OCT) asks whether a given graph can be made bipartite (i.e., 2-colorable) by deleting at most ℓ vertices. We study structural parameterizations of OCT with respect to their polynomial kernelizability, i.e., whether instances can be efficiently reduced to a size polynomial in the chosen parameter. It is a major open problem in parameterized complexity whether Odd Cycle Transversal admits a polynomial kernel when parameterized by ℓ.
On the positive side, we show a polynomial kernel for OCT when parameterized by the vertex deletion distance to the class of bipartite graphs of treewidth at most w (for any constant w); this generalizes the parameter feedback vertex set number (i.e., the distance to a forest).
Complementing this, we exclude polynomial kernels for OCT parameterized by the distance to outerplanar graphs, conditioned on the assumption that NP \(\nsubseteq\) coNP/poly. Thus the bipartiteness requirement for the treewidth w graphs is necessary. Further lower bounds are given for parameterization by distance from cluster and co-cluster graphs respectively, as well as for Weighted OCT parameterized by the vertex cover number (i.e., the distance from an independent set).
Bart M. P. Jansen, Stefan Kratsch

Kernel Bounds for Path and Cycle Problems

Abstract
Connectivity problems like k-Path and k-Disjoint Paths relate to many important milestones in parameterized complexity, namely the Graph Minors Project, color coding, and the recent development of techniques for obtaining kernelization lower bounds. This work explores the existence of polynomial kernels for various path and cycle problems, by considering nonstandard parameterizations. We show polynomial kernels when the parameters are a given vertex cover, a modulator to a cluster graph, or a (promised) max leaf number. We obtain lower bounds via cross-composition, e.g., for Hamiltonian Cycle and related problems when parameterized by a modulator to an outerplanar graph.
Hans L. Bodlaender, Bart M. P. Jansen, Stefan Kratsch

On the Hardness of Losing Width

Abstract
Let η ≥ 0 be an integer and G be a graph. A set X ⊆ V(G) is called a η-transversal in G if G ∖ X has treewidth at most η. Note that a 0-transversal is a vertex cover, while a 1-transversal is a feedback vertex set of G. In the \(\eta \slash \rho\)-transversal problem we are given an undirected graph G, a ρ-transversal X ⊆ V(G) in G, and an integer ℓ and the objective is to determine whether there exists an η-transversal Z ⊆ V(G) in G of size at most ℓ. In this paper we study the kernelization complexity of \(\eta \slash \rho\)-transversal parameterized by the size of X. We show that for every fixed η and ρ that either satisfy 1 ≤ η < ρ, or η = 0 and 2 ≤ ρ, the \(\eta \slash \rho\)-transversal problem does not admit a polynomial kernel unless \(\textrm{NP} \subseteq \textrm{coNP}/\textrm{poly}\). This resolves an open problem raised by Bodlaender and Jansen in [STACS 2011]. Finally, we complement our kernelization lower bounds by showing that \(\rho \slash 0\)-transversal admits a polynomial kernel for any fixed ρ.
Marek Cygan, Daniel Lokshtanov, Marcin Pilipczuk, Michał Pilipczuk, Saket Saurabh

Safe Approximation and Its Relation to Kernelization

Abstract
We introduce a notion of approximation, called safe approximation, for minimization problems that are subset problems. We first study the relation between the standard notion of approximation and safe approximation, and show that the two notions are different unless some unlikely collapses in complexity theory occur. We then study the relation between safe approximation and kernelization. We demonstrate how the notion of safe approximation can be useful in designing kernelization algorithms for certain fixed-parameter tractable problems. On the other hand, we show that there are problems that have constant-ratio safe approximation algorithms but no polynomial kernels, unless the polynomial hierarchy collapses to the third level.
Jiong Guo, Iyad Kanj, Stefan Kratsch

Simpler Linear-Time Kernelization for Planar Dominating Set

Abstract
We describe a linear-time algorithm that inputs a planar graph G and outputs a planar graph of size O(k) and with domination number k, where k is the domination number of G, i.e., the size of a smallest dominating set in G. In the language of parameterized computation, the new algorithm is a linear-time kernelization for the NP-complete Planar Dominating Set problem that produces a kernel of linear size. Such an algorithm was previously known (van Bevern et al., these proceedings), but the new algorithm and its analysis are considerably simpler.
Torben Hagerup

Linear-Time Computation of a Linear Problem Kernel for Dominating Set on Planar Graphs

Abstract
We present a linear-time kernelization algorithm that transforms a given planar graph G with domination number γ(G) into a planar graph G′ of size O(γ(G)) with γ(G) = γ(G′). In addition, a minimum dominating set for G can be inferred from a minimum dominating set for G′. In terms of parameterized algorithmics, this implies a linear-size problem kernel for the NP-hard Dominating Set problem on planar graphs, where the kernelization takes linear time. This improves on previous kernelization algorithms that provide linear-size kernels in cubic time.
René van Bevern, Sepp Hartung, Frank Kammer, Rolf Niedermeier, Mathias Weller

Tight Complexity Bounds for FPT Subgraph Problems Parameterized by Clique-Width

Abstract
We give tight algorithmic lower and upper bounds for some double-parameterized subgraph problems when the clique-width of the input graph is one of the parameters. Let G be an arbitrary input graph on n vertices with clique-width at most w. We prove the following results.
  • The Dense (Sparse) k -Subgraph problem, which asks whether there exists an induced subgraph of G with k vertices and at least q edges (at most q edges, respectively), can be solved in time k O(w)·n, but it cannot be solved in time 2 o(wlogk)·n O(1) unless the Exponential Time Hypothesis (ETH) fails.
  • The d -Regular Induced Subgraph problem, which asks whether there exists a d-regular induced subgraph of G, and the Minimum Subgraph of Minimum Degree at least d problem, which asks whether there exists a subgraph of G with k vertices and minimum degree at least d, can be solved in time d O(w)·n, but they cannot be solved in time 2 o(wlogd)·n O(1) unless ETH fails.
Hajo Broersma, Petr A. Golovach, Viresh Patel

Finding Good Decompositions for Dynamic Programming on Dense Graphs

Abstract
It is well-known that for graphs with high edge density the tree-width is always high while the clique-width can be low. Boolean-width is a new parameter that is never higher than tree-width or clique-width and can in fact be as small as logarithmic in clique-width. Boolean-width is defined using a decomposition tree by evaluating the number of neighborhoods across the resulting cuts of the graph. Several NP-hard problems can be solved efficiently by dynamic programming when given a decomposition of boolean-width k, e.g. Max Weight Independent Set in time O(n 2 k22k ) and Min Weight Dominating Set in time O(n 2 + nk23k ). Finding decompositions of low boolean-width is therefore of practical interest. There is evidence that computing boolean-width is hard, while the existence of a useful approximation algorithm is still open. In this paper we introduce and study a heuristic algorithm that finds a reasonably good decomposition to be used for dynamic programming based on boolean-width. On a set of graphs of practical relevance, specifically graphs in TreewidthLIB, the best known upper bound on their tree-width is compared to the upper bound on their boolean-width given by our heuristic. For the large majority of the graphs on which we made the tests, the tree-width bound is at least twice as big as the boolean-width bound, and boolean-width compares better the higher the edge density. This means that, for problems like Dominating Set, using boolean-width should outperform dynamic programming by tree-width, at least for graphs of edge density above a certain bound. In view of the amount of previous work on heuristics for tree-width these results indicate that boolean-width could in the future outperform tree-width in practice for a large class of graphs and problems.
Eivind Magnus Hvidevold, Sadia Sharmin, Jan Arne Telle, Martin Vatshelle

Parameterized Maximum Path Coloring

Abstract
We study the well-known Max Path Coloring problem from a parameterized point of view, focusing on trees and low-treewidth networks. We observe the existence of a variety of reasonable parameters for the problem, such as the maximum degree and treewidth of the network graph, the number of available colors and the number of requests one seeks to satisfy or reject. In an effort to understand the impact of each of these parameters on the problem’s complexity we study various parameterized versions of the problem deriving fixed-parameter tractability and hardness results both for undirected and bi-directed graphs.
Michael Lampis

On Cutwidth Parameterized by Vertex Cover

Abstract
We study the Cutwidth problem, where input is a graph G, and the objective is find a linear layout of the vertices that minimizes the maximum number of edges intersected by any vertical line inserted between two consecutive vertices. We give an algorithm for Cutwidth with running time O(2 k n O(1)). Here k is the size of a minimum vertex cover of the input graph G, and n is the number of vertices in G. Our algorithm gives an O(2 n/2 n O(1)) time algorithm for Cutwidth on bipartite graphs as a corollary. This is the first non-trivial exact exponential time algorithm for Cutwidth on a graph class where the problem remains NP-complete. Additionally, we show that Cutwidth parameterized by the size of the minimum vertex cover of the input graph does not admit a polynomial kernel unless \(\ensuremath{\textrm{NP} \subseteq \textrm{coNP}/\textrm{poly}}\). Our kernelization lower bound contrasts the recent result of Bodlaender et al.[ICALP 2011] that Treewidth parameterized by vertex cover does admit a polynomial kernel.
Marek Cygan, Daniel Lokshtanov, Marcin Pilipczuk, Michał Pilipczuk, Saket Saurabh

Twin-Cover: Beyond Vertex Cover in Parameterized Algorithmics

Abstract
Parameterized algorithms are a very useful tool for dealing with NP-hard problems on graphs. In this context, vertex cover is used as a powerful parameter for dealing with problems which are hard to solve even on graphs of bounded tree-width. The drawback of vertex cover is that bounding it severely restricts admissible graph classes. We introduce a new parameter called twin-cover and show that it is capable of solving a wide range of hard problems while also being much less restrictive than vertex cover and attaining low values even on dense graphs.
The article begins by introducing a new FPT algorithm for Graph Motif on graphs of bounded vertex cover. This is the first algorithm of this kind for Graph Motif. We continue by defining twin-cover and providing some related results and notions. The next section contains a number of new FPT algorithms on graphs of bounded twin-cover, with a special emphasis on solving problems which are hard even on graphs of bounded tree-width. Finally, section five generalizes the recent results of Michael Lampis for \(M\!S_1\) model checking from vertex cover to twin-cover.
Robert Ganian

Backmatter

Weitere Informationen

Premium Partner

    Bildnachweise