Parameterized and Exact Computation

Frontmatter

Randomized Disposal of Unknowns and Implicitly Enforced Bounds on Parameters

Abstract

We study two algorithmic techniques that have turned out to be useful in the recent development of parameterized algorithms: randomized disposal of a small unknown subset of a given universal set, and implicitly enforced bounds on parameters in a branch-and-search process. These techniques are simple, effective, and have led to improved algorithms for a number of well-known parameterized problems.

Jianer Chen

Algorithmic Graph Minors and Bidimensionality

Abstract

Robertson and Seymour developed the seminal Graph Minor Theory over the past two decades. This breakthrough in graph structure theory tells us that a very wide family of graph classes (anything closed under deletion and contraction) have a rich structure similar to planar graphs. This structure has many algorithmic applications that have become increasingly prominent over the past decade. For example, Fellows and Langston showed in 1988 that it immediately leads to a wealth of (nonconstructive) fixed-parameter algorithms.

One recent approach to algorithmic graph minor theory is “bidimensionality theory”. This theory provides general tools for designing fast (constructive, often subexponential) fixed-parameter algorithms, and approximation algorithms (often PTASs), for a wide variety of NP-hard graph problems in graphs excluding a fixed minor. For example, some of the most general algorithms for feedback vertex set and connected dominating set are based on bidimensionality. Another approach is “deletion and contraction decompositions”, which split any graph excluding a fixed minor into a bounded number of small-treewidth graphs. For example, this approach has led to some of the most general algorithms for graph coloring and the Traveling Salesman Problem on graphs. I will describe these and other approaches to efficient algorithms through graph minors.

Erik D. Demaine

Algorithmic Meta-theorems

Abstract

Algorithmic meta-theorems are algorithmic results that apply to a whole range of problems, instead of addressing just one specific problem. This kind of theorems are often stated relative to a certain class of graphs, so the general form of a meta theorem reads “every problem in a certain class of problems can be solved efficiently on every graph satisfying a certain property ”. A particularly well known example of a meta-theorem is Courcelle’s theorem that every decision problem definable in monadic second-order logic (MSO) can be decided in linear time on any class of graphs of bounded tree-width [1].

Stephan Kreutzer

Parameterized Complexity of the Smallest Degree-Constrained Subgraph Problem

Abstract

In this paper we study the problem of finding an induced subgraph of size at most k with minimum degree at least d for a given graph G, from the parameterized complexity perspective. We call this problem Minimum Subgraph of Minimum Degree _≥ d (MSMD _d ). For d = 2 it corresponds to finding a shortest cycle of the graph. Our main motivation to study this problem is its strong relation to Dense k -Subgraph and Traffic Grooming problems.

First, we show that MSMS _d is fixed-parameter intractable (provided FPT ≠ W[1]) for d ≥ 3 in general graphs, by showing it to be W[1]-hard using a reduction from Multi-Color Clique. In the second part of the paper we provide explicit fixed-parameter tractable (FPT) algorithms for the problem in graphs with bounded local tree-width and graphs with excluded minors, faster than those coming from the meta-theorem of Frick and Grohe [13] about problems definable in first order logic over “locally tree-decomposable structures”. In particular, this implies faster fixed-parameter tractable algorithms in planar graphs, graphs of bounded genus, and graphs with bounded maximum degree.

Omid Amini, Ignasi Sau, Saket Saurabh

Fixed Structure Complexity

Abstract

We consider a non-standard parametrization, where, for problems consisting of a combinatorial structure and a number, we parameterize by the combinatorial structure, rather than by the number. For example, in the Short-Nondeterministic-Halt problem, which is to determine if a nondeterministic machine M accepts the empty string in t steps, we parameterize by |M|, rather than t. We call such parametrization fixed structure parametrization. Fixed structure parametrization not only provides a new set of parameterized problems, but also results in problems that do not seem to fall within the classical parameterized complexity classes. In this paper we take the first steps in understanding these problems. We define fixed structure analogues of various classical problems, including graph problems, and provide complexity, hardness and equivalence results.

Yonatan Aumann, Yair Dombb

An Improved Fixed-Parameter Algorithm for Minimum-Flip Consensus Trees

Abstract

In computational phylogenetics, the problem of constructing a consensus tree for a given set of input trees has frequently been addressed. In this paper we study the Minimum-Flip Problem: the input trees are transformed into a binary matrix, and we want to find a perfect phylogeny for this matrix using a minimum number of flips, that is, corrections of single entries in the matrix. In its graph-theoretical formulation, the problem is as follows: Given a bipartite graph G = (V _t  ∪ V _c , E), the problem is to find a minimum set of edge modifications such that the resulting graph has no induced path with four edges which starts and ends in V _t .

We present a fixed-parameter algorithm for the Minimum-Flip Problem with running time O(4.83 ^k (m + n) + mn) for n taxa, m characters, and k flips. Additionally, we discuss several heuristic improvements. We also report computational results on phylogenetic data.

Sebastian Böcker, Quang Bao Anh Bui, Anke Truss

An O *(1.0977 n ) Exact Algorithm for max independent set in Sparse Graphs

Abstract

We present an O ^*(1.0977 ⁿ ) search-tree based exact algorithm for max independent set in graphs with maximum degree 3. It can be easily seen that this algorithm also works in graphs with average degree 3.

Nicolas Bourgeois, Bruno Escoffier, Vangelis Th. Paschos

New Fixed-Parameter Algorithms for the Minimum Quartet Inconsistency Problem

Abstract

Given a set of n taxa S, exactly one topology for every subset of four taxa, and a positive integer k as the parameter, the parameterized Minimum Quartet Inconsistency (MQI) problem is to decide whether we can find an evolutionary tree inducing a set of quartet topologies that differs from the given set in at most k quartet topologies. The best fixed-parameter algorithm devised so far for the parameterized MQI problem runs in time O(4 ^k n + n ⁴). In this paper, first we present an O(3.0446 ^k n + n ⁴) algorithm and an O(2.0162 ^k n ³ + n ⁵) algorithm. Finally, we give an O ^*((1 + ε) ^k ) algorithm with an arbitrarily small constant ε> 0.

Maw-Shang Chang, Chuang-Chieh Lin, Peter Rossmanith

Capacitated Domination and Covering: A Parameterized Perspective

Abstract

Capacitated versions of Vertex Cover and Dominating Set have been studied intensively in terms of polynomial time approximation algorithms. Although the problems Dominating Set and Vertex Cover have been subjected to considerable scrutiny in the parameterized complexity world, this is not true for their capacitated versions. Here we make an attempt to understand the behavior of the problems Capacitated Dominating Set and Capacitated Vertex Cover from the perspective of parameterized complexity.

The original, uncapacitated versions of these problems, Vertex Cover and Dominating Set, are known to be fixed parameter tractable when parameterized by a structure of the graph called the treewidth (tw). In this paper we show that the capacitated versions of these problems behave differently. Our results are:

– Capacitated Dominating Set is W1-hard when parameterized by treewidth. In fact, Capacitated Dominating Set is W1-hard when parameterized by both treewidth and solution size k of the capacitated dominating set.

– Capacitated Vertex Cover is W1-hard when parameterized by treewidth.

– Capacitated Vertex Cover can be solved in time 2 ^{O(tw logk)} n ^O(1) where tw is the treewidth of the input graph and k is the solution size. As a corollary, we show that the weighted version of Capacitated Vertex Cover in general graphs can be solved in time 2 ^{O(k logk)} n ^O(1). This improves the earlier algorithm of Guo et al. [15] running in time \(O(1.2^{k^2}+n^2)\). Capacitated Vertex Cover is, therefore, to our knowledge the first known “subset problem” which has turned out to be fixed parameter tractable when parameterized by solution size but W1-hard when parameterized by treewidth.

Michael Dom, Daniel Lokshtanov, Saket Saurabh, Yngve Villanger

Some Fixed-Parameter Tractable Classes of Hypergraph Duality and Related Problems

Abstract

In this paper we present fixed-parameter algorithms for the problem Dual—given two hypergraphs, decide if one is the transversal hypergraph of the other—and related problems. In the first part, we consider the number of edges of the hypergraphs, the maximum degree of a vertex, and a vertex complementary degree as our parameters.

In the second part, we use an Apriori approach to obtain FPT results for generating all maximal independent sets of a hypergraph, all minimal transversals of a hypergraph, and all maximal frequent sets where parameters bound the intersections or unions of edges.

Khaled Elbassioni, Matthias Hagen, Imran Rauf

A Purely Democratic Characterization of W[1]

Abstract

We give a novel characterization of W[1], the most important fixed-parameter intractability class in the W-hierarchy, using Boolean circuits that consist solely of majority gates. Such gates have a Boolean value of 1 if and only if more than half of their inputs have value 1. Using majority circuits, we define an analog of the W-hierarchy which we call the \(\widetilde{\mathrm{W}}\)-hierarchy, and show that \(\mathrm{W}[1] = \widetilde{\mathrm{W}}[1]\) and \(\mathrm{W}[t] \subseteq \widetilde{\mathrm{W}}[t]\) for all t. This gives the first characterization of W[1] based on the weighted satisfiability problem for monotone Boolean circuits rather than antimonotone. Our results are part of a wider program aimed at exploring the robustness of the notion of weft, showing that it remains a key parameter governing the combinatorial nondeterministic computing strength of circuits, no matter what type of gates these circuits have.

Michael Fellows, Danny Hermelin, Moritz Müller, Frances Rosamond

Parameterized Complexity and Approximability of the SLCS Problem

Abstract

We introduce the Longest Compatible Sequence (Slcs) problem. This problem deals with p-sequences, which are strings on a given alphabet where each letter occurs at most once. The Slcs problem takes as input a collection of k p-sequences on a common alphabet L of size n, and seeks a p-sequence on L which respects the precedence constraints induced by each input sequence, and is of maximal length with this property. We investigate the parameterized complexity and the approximability of the problem. As a by-product of our hardness results for Slcs, we derive new hardness results for the Longest Common Subsequence problem and other problems hard for the W-hierarchy.

Sylvain Guillemot

FPT Algorithms for Path-Transversals and Cycle-Transversals Problems in Graphs

Abstract

In this article, we consider problems on graphs of the following form: given a graph, remove p edges/vertices to achieve some property. The first kind of problems are separation problems on undirected graphs, where we aim at separating distinguished vertices in an graph. The second kind of problems are feedback set problems on group-labelled graphs, where we aim at breaking nonnull cycles in a group-labelled graph. We obtain new FPT algorithms for these different problems. A building stone for our algorithms is a general O ^*(4 ^p ) algorithm for a class of problems aiming at breaking a set of paths in a graph, provided that the set of paths has a special property called homogeneity.

Sylvain Guillemot

Wheel-Free Deletion Is W[2]-Hard

Abstract

We show that the two problems of deciding whether k vertices or k edges can be deleted from a graph to obtain a wheel-free graph is W[2]-hard. This immediately implies that deciding whether k edges can be added to obtain a graph that contains no complement of a wheel as an induced subgraph is W[2]-hard, thereby resolving an open problem of Heggernes et al. [7] (STOC07) who ask whether there is a polynomial time recognizable hereditary graph class Π with the property that computing the minimum Π-completion is W[t]-hard for some t.

Daniel Lokshtanov

Parameterized Derandomization

Abstract

The class is a parameterized analogue of . Chen et al. [4] have given a machine characterization of . The corresponding machine model gives rise to a parameterized analogue of BPP. What is the connection between parameterized and classical derandomization?

Moritz Müller

A Linear Kernel for Planar Feedback Vertex Set

Abstract

In this paper we show that Feedback Vertex Set on planar graphs has a kernel of size at most . We give a polynomial time algorithm, that given a planar graph G finds a equivalent planar graph G′ with at most vertices, where k ^* is the size of the minimum Feedback Vertex Set of G. The kernelization algorithm is based on a number of reduction rules. The correctness of most of these rules is shown using a new notion: bases of induced subgraphs. We also show how to use this new notion to automatically prove safeness of reduction rules and obtain tighter bounds for the size of the kernel.

Hans L. Bodlaender, Eelko Penninkx

Parameterized Chess

Abstract

It has been suggested that the parameterized complexity class AW[*] is the natural home of k-move games, but to date the number of problems known to be in this class has remained small. We investigate the complexity of Short Generalized Chess—the problem of deciding whether a chess player can force checkmate in the next k moves. We show that this problem is complete for AW[*].

Allan Scott, Ulrike Stege

The Time Complexity of Constraint Satisfaction

Abstract

We study the time complexity of (d,k)-CSP, the problem of deciding satisfiability of a constraint system with n variables, domain size d, and at most k variables per constraint. We are interested in the question how the domain size d influences the complexity of deciding satisfiability. We show, assuming the Exponential Time Hypothesis, that two special cases, namely (d,2)-CSP with bounded variable frequency and d-UNIQUE-CSP, already require exponential time Ω(d ^c·n ) for some c > 0 independent of d. UNIQUE-CSP is the special case for which it is guaranteed that every input constraint system has at most 1 satisfying assignment.

Patrick Traxler

A Tighter Bound for Counting Max-Weight Solutions to 2SAT Instances

Abstract

We give an algorithm for counting the number of max-weight solutions to a 2SAT formula, and improve the bound on its running time to . The main source of the improvement is a refinement of the method of analysis, where we extend the concept of compound (piecewise linear) measures to multivariate measures, also allowing the optimal parameters for the measure to be found automatically. This method extension should be of independent interest.

Magnus Wahlström

Exact Algorithms for Edge Domination

Abstract

In this paper we present a faster exact exponential time algorithm for the edge dominating set problem. Our algorithm uses O(1.3226 ⁿ ) time and polynomial space. The algorithm combines an enumeration approach based on enumerating minimal vertex covers with the branch and reduce paradigm. Its time bound is obtained using the measure and conquer technique. The algorithm is obtained by starting with a slower algorithm which is refined stepwise. In this way a series of algorithms appears, each one slightly faster than the previous, resulting in the O(1.3226 ⁿ ) time algorithm.

The techniques also gives faster exact algorithms for: minimum weight edge dominating set, minimum (weight) maximal matching, matrix domination and the parametrised version of minimum weight maximal matching.

Johan M. M. van Rooij, Hans L. Bodlaender

Backmatter