-
Parameterizing by the Number of Numbers
(with Michael R. Fellows and Frances A. Rosamond),
IPEC 2010: Proceedings of the 5th International Symposium on Parameterized and Exact Computation (formerly IWPEC), to appear.
[pdf] [More InfoLess Info]
Abstract: The usefulness of parameterized algorithmics has often depended on what Niedermeier has called
"the art of problem parameterization". In this paper we introduce and explore a novel but
general form of parameterization: the number of numbers.
Several classic numerical problems, such as Subset Sum, Partition, 3-Partition, Numerical 3-Dimensional Matching, and Numerical Matching with Target Sums,
have multisets of integers as input. We initiate the study of parameterizing these problems by the number of distinct integers in the input.
We rely on an FPT result for Integer Linear Programming Feasibility to show that all the above-mentioned problems are fixed-parameter tractable when parameterized in this way.
In various applied settings, problem inputs often consist in part of multisets of integers or multisets of weighted objects (such as edges in a graph, or jobs to be scheduled).
Such number-of-numbers parameterized problems often reduce to subproblems about transition
systems of various kinds, parameterized by the size of the system description.
We consider several core problems of this kind relevant to number-of-numbers parameterization.
Our main hardness result considers the problem: given a non-deterministic Mealy machine M
(a finite state automaton outputting a letter on each transition), an input word x, and a census requirement c
for the output word specifying how many times each letter of the output alphabet should be written, decide whether
there exists a computation of M reading x that outputs a word y that meets the requirement c.
We show that this problem is hard for W[1]. If the question is whether there exists an input word x
such that a computation of M on x outputs a word that meets c, the problem becomes fixed-parameter tractable.
-
Feedback Vertex Sets in Tournaments
(with Matthias Mnich),
ESA 2010: Proceedings of the 18th Annual European Symposium on Algorithms, Part 1, Springer LNCS 6346, pp. 267 - 277.
[pdf] [More InfoLess Info]
Abstract: We study combinatorial and algorithmic questions around minimal feedback vertex sets in tournament graphs.
On the combinatorial side, we derive strong upper and lower bounds on the maximum number of minimal feedback vertex sets in an n-vertex tournament.
We prove that every tournament on n vertices has at most 1.6740^n minimal feedback vertex sets and that there is an infinite family of tournaments, all having at least 1.5448^n minimal feedback vertex sets.
This improves and extends the bounds of Moon (1971).
On the algorithmic side, we design the first polynomial space algorithm that enumerates the minimal feedback vertex sets of a tournament with polynomial delay.
The combination of our results yields the fastest known algorithm for finding a minimum size feedback vertex set in a tournament.
-
Kernels for Feedback Arc Set In Tournaments
(with Stéphane Bessy, Fedor V. Fomin, Christophe Paul, Anthony Perez, Saket Saurabh, and Stéphan Thomassé),
FSTTCS 2009: Proceedings of the 29th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science,
LIPIcs 4, pp. 37 - 47.
[pdf] [More InfoLess Info]
Abstract: A tournament T = (V,A) is a directed graph in which there is exactly one arc between every pair of distinct vertices. Given a digraph on n vertices and an integer parameter k, the Feedback Arc Set problem asks whether the given digraph has a set of k arcs whose removal results in an acyclic digraph. The Feedback Arc Set problem restricted to tournaments is known as the k-Feedback Arc Set in Tournaments k-FAST problem. In this paper we obtain a linear vertex kernel for k-FAST. That is, we give a polynomial time algorithm, which, given an input instance T to k-FAST, obtains an equivalent instance T' on O(k) vertices. In fact, given any fixed ε > 0, the kernelized instance has at most (2 + ε)k vertices.Our result improves the previous known bound of O(k^2) on the kernel size for k-FAST. Our kernelization algorithm solves the problem on a subclass of tournaments in polynomial time and uses a known polynomial time approximation scheme for k-FAST.
-
A Linear Vertex Kernel for Maximum Internal Spanning Tree
(with Fedor V. Fomin, Saket Saurabh, and Stéphan Thomassé),
ISAAC 2009: Proceedings of the 20th International Symposium on Algorithms and Computation,
Springer LNCS 5878, pp. 275 - 282.
[pdf] [More InfoLess Info]
Abstract: We present a polynomial time algorithm that for any graph G and integer k ≥ 0, either finds a spanning tree with at least k internal vertices, or outputs a new graph G' on at most 3k vertices and an integer k' such that G has a spanning tree with at least k internal vertices if and only if G' has a spanning tree with at least k' internal vertices. In other words, we show that the Maximum Internal Spanning Tree problem parameterized by the number of internal vertices k has a 3k-vertex kernel. Our result is based on an innovative application of a classical min-max result about hypertrees in hypergraphs which states that "a hypergraph H contains a hypertree if and only if H is partition connected."
-
An Exponential Time 2-Approximation Algorithm for Bandwidth
(with Martin Fürer and Shiva Prasad Kasiviswanathan),
IWPEC 2009: Proceedings of the 4th International Workshop on Parameterized and Exact Computation,
Springer LNCS 5917, pp. 173 - 184.
[pdf] [More InfoLess Info]
Abstract: The bandwidth of a graph G on n vertices is the minimum b such that the vertices of G can be labeled from 1 to n such that the labels of every pair of adjacent vertices differ by at most b.
In this paper, we present a 2-approximation algorithm for the Bandwidth problem that takes worst-case O(1.9797^n) = O(3^(0.6217 n)) time and uses polynomial space. This improves both the previous best 2- and 3-approximation algorithms of Cygan et al. which have O*(3^n) and O*(2^n) worst-case time bounds, respectively. Our algorithm is based on constructing bucket decompositions of the input graph. A bucket decomposition partitions the vertex set of a graph into ordered sets (called buckets) of (almost) equal sizes such that all edges are either incident on vertices in the same bucket or on vertices in two consecutive buckets. The idea is to find the smallest bucket size for which there exists a bucket decomposition. The algorithm uses a simple divide-and-conquer strategy along with dynamic programming to achieve this improved time bound.
-
Exact and Parameterized Algorithms for Max Internal Spanning Tree (with Henning Fernau and Daniel Raible)
WG 2009: Proceedings of the 35th International Workshop on Graph-Theoretic Concepts in Computer Science,
Springer LNCS 5911, pp. 100 - 111.
[pdf] [More InfoLess Info]
Abstract: We consider the NP-hard problem of finding a spanning tree with a maximum number of internal vertices. This problem is a generalization of the famous Hamiltonian Path problem. Our dynamic-programming algorithms for general and degree-bounded graphs have running times of the form O*(c^n) (c ≤ 3). The main result, however, is a branching algorithm for graphs with maximum degree three. It only needs polynomial space and has a running time of O(1.8669^n) when analyzed with respect to the number of vertices. We also show that its running time is 2.1364^k*n^(O(1)) when the goal is to find a spanning tree with at least k internal vertices. Both running time bounds are obtained via a Measure & Conquer analysis, the latter one being a novel use of this kind of analysis for parameterized algorithms.
Subsequent work: Nederlof (ICALP 2009) uses Möbius inversion to design a polynomial space O*(2^n)-time algorithm to solve Max Internal Spanning Tree for general graphs.
The journal version of the paper (see below) breaks even the O*(2^n) time bound for degree-bounded graphs.
-
Exact exponential-time algorithms for finding bicliques in a graph (with Henning Fernau, Dieter Kratsch, Mathieu Liedloff, and Daniel Raible)
CTW 2009: Proceedings of the 8th Cologne Twente Workshop on Graphs and Combinatorial Optimization, Ecole Polytechnique and CNAM, pp. 205 - 209.
[pdf] [More InfoLess Info]
Abstract:
We show that, given a graph G on n vertices, deciding whether G has a complete bipartite subgraph with k1 vertices in one part and k2 vertices in the other part of its bipartition can be done in time O(1.8899^n) and polynomial space and in time O(1.8458^n) and exponential space.
Subsequent work:
In a journal submission (see below), a subset of the authors design design a polynomial-space O(1.6914^n)-time algorithm for this problem.
-
A universally fastest algorithm for Max 2-Sat, Max 2-CSP, and everything in between
(with Gregory B. Sorkin),
SODA 2009: Proceedings of the 20th annual ACM-SIAM Symposium on Discrete Algorithms,
SIAM, pp. 606 - 615.
[pdf] [More InfoLess Info]
Abstract: We introduce "hybrid" Max 2-CSP formulas consisting of "simple clauses", namely conjunctions and disjunctions of pairs of variables, and general 2-variable clauses, which can be any integer-valued functions of pairs of boolean variables. This allows an algorithm to use both efficient reductions specific to AND and OR clauses, and other powerful reductions that require the general CSP setting.
Parametrizing an instance by the fraction p of nonsimple clauses, we give an exact (exponential-time) algorithm that is the fastest polynomial-space algorithm known for Max 2-Sat (and other p = 0 formulas, with arbitrary mixtures of AND and OR clauses); the only efficient algorithm for mixtures of AND, OR, and general integer-valued clauses; and tied for fastest for general Max 2-CSP (p = 1). Since a pure 2-Sat input instance may be transformed to a general CSP instance in the course of being solved, the algorithm's efficiency and generality go hand in hand.
Our novel analysis results in a family of running-time bounds, each optimized for a particular value of p. The algorithm uses new reductions introduced here, as well as recent reductions such as "clause-learning" and "2-reductions" adapted to our setting's mixture of simple and general clauses. Each reduction imposes constraints on various parameters, and the running-time bound is an "objective function" of these parameters and p. The optimal running-time bound is obtained by solving a convex nonlinear program, which can be done efficiently and with a certificate of optimality.
-
Iterative Compression and Exact Algorithms
(with Fedor V. Fomin, Dieter Kratsch, Mathieu Liedloff, and Saket Saurabh),
MFCS 2008: Proceedings of the 33rd International Symposium on Mathematical Foundations of Computer Science,
Springer LNCS 5162, pp. 335 - 346.
[pdf] [More InfoLess Info]
Abstract: Iterative Compression has recently led to a number of breakthroughs in parameterized complexity. The main purpose of this paper is to show that iterative compression can also be used in the design of exact exponential time algorithms. We exemplify our findings with algorithms for the Maximum Independent Set problem, a counting version of k-Hitting Set and the Maximum Induced Cluster Subgraph problem.
-
On Independent Sets and Bicliques in Graphs
(with Dieter Kratsch and Mathieu Liedloff),
WG 2008: Proceedings of the 34th International Workshop on Graph-Theoretic Concepts in Computer Science,
Springer LNCS 5344, pp. 171 - 182.
[pdf] [More InfoLess Info]
Abstract: Bicliques of graphs have been studied extensively, partially motivated by the large number of applications. One of the main algorithmic interests is in designing algorithms to enumerate all maximal bicliques of a (bipartite) graph. Polynomial-time reductions have been used explicitly or implicitly to design polynomial delay algorithms to enumerate all maximal bicliques.
Based on polynomial-time Turing reductions, various algorithmic problems on (maximal) bicliques can be studied by considering the related problem for (maximal) independent sets. In this line of research, we improve Prisner's upper bound on the number of maximal bicliques [Combinatorica, 2000] and show that the maximum number of maximal bicliques in a graph on n vertices is exactly 3^(n/3) (up to a polynomial factor). The main results of this paper are O(1.3642^n) time algorithms to compute the number of maximal independent sets and maximal bicliques in a graph.
-
A Moderately Exponential Time Algorithm for Full Degree Spanning Tree
(with Saket Saurabh and Alexey A. Stepanov),
TAMC 2008: Proceedings of the 5th Annual Conference on Theory and Applications of Models of Computation,
Springer LNCS 4978, pp. 479 - 489.
[pdf] [More InfoLess Info]
Abstract: We consider the well studied Full Degree Spanning Tree problem, a NP-complete variant of the Spanning Tree problem, in the realm of moderately exponential time exact algorithms. In this problem, given a graph G, the objective is to find a spanning tree T of G which maximizes the number of vertices that have the same degree in T as in G. This problem is motivated by its application in fluid networks and is basically a graph-theoretic abstraction of the problem of placing flow meters in fluid networks. We give an exact algorithm for Full Degree Spanning Tree running in time O(1.9172^n). This adds Full Degree Spanning Tree to a very small list of "non-local problems", like Feedback Vertex Set and Connected Dominating Set, for which non-trivial (non brute force enumeration) exact algorithms are known.
Erratum: Reduction Rule R6 and the running time computation are faulty. In the journal version, these mistakes are corrected and a running time of O(1.9465^n) is proved.
-
Improved Exact Algorithms for Counting 3- and 4-Colorings
(with Fedor V. Fomin and Saket Saurabh),
COCOON 2007: Proceedings of the 13th Annual International Computing and Combinatorics Conference,
Springer LNCS 4598, pp. 65 - 74.
[pdf] [More InfoLess Info]
Abstract: We introduce a generic algorithmic technique and apply it on decision and counting versions of graph coloring. Our approach is based on the following idea: either a graph has nice (from the algorithmic point of view) properties which allow a simple recursive procedure to find the solution fast, or the pathwidth of the graph is small, which in turn can be used to find the solution by dynamic programming. By making use of this technique we obtain the fastest known exact algorithms
- running in time O(1.7272^n) for deciding if a graph is 4-colorable
- running in time O(1.6262^n) and O(1.9464^n) for counting the number of k-colorings for k = 3 and 4 respectively.
Erratum: The running time for counting all 4-colorings of a graph does not hold. Thus, there is no known algorithm counting all 4-colorings of a graph, which is exponentially faster than O(2^n) yet.
-
Branching and Treewidth Based Exact Algorithms
(with Fedor V. Fomin and Saket Saurabh),
ISAAC 2006: Proceedings of the 17th International Symposium on Algorithms and Computation,
Springer LNCS 4288, pp. 16 - 25,
received the Best Student Paper Award.
[pdf] [More InfoLess Info]
Abstract: Branch & Reduce and dynamic programming on graphs of bounded treewidth are among the most common and powerful techniques used in the design of exact (exponential time) algorithms for NP hard problems. In this paper we discuss the efficiency of simple algorithms based on combinations of these techniques. We give several examples of possible combinations of branching and programming which provide the fastest known algorithms for a number of NP hard problems: Minimum Maximal Matching and some variations, counting the number of maximum weighted independent sets. We also briefly discuss how similar techniques can be used to design parameterized algorithms. As an example, we give fastest known algorithm solving k-Weighted Vertex Cover problem.
Subsequent work: Wahlström (IWPEC 2008) designs a O(1.2377^n)-time algorithm for counting all maximum weight solutions to a 2-Sat formula. Thus, the number of maximum weighted independent sets can be counted within the same time bound, improving on our O(1.2431^n)-time algorithm.
-
Finding a Minimum Feedback Vertex Set in time O(1.7548n)
(with Fedor V. Fomin and Artem V. Pyatkin),
IWPEC 2006: Proceedings of the 2nd International Workshop on Parameterized and Exact Computation,
Springer LNCS 4169, pp. 184 - 191.
[pdf] [More InfoLess Info]
Abstract: We present an O(1.7548^n) algorithm finding a minimum feedback vertex set in a graph on n vertices.
Keywords: minimum feedback vertex set, maximum induced forest, exact exponential algorithm.
Subsequent work: Using completely different ideas, Fomin and Villanger (STACS 2010) design a faster O(1.7347^n)-time algorithm for Feedback Vertex Set.
-
A branch-and-reduce algorithm for finding a minimum independent dominating set in graphs
(with Mathieu Liedloff),
WG 2006: Proceedings of the 32nd International Workshop on Graph-Theoretic Concepts in Computer Science,
Springer LNCS 4271, pp. 78 - 89.
[pdf] [More InfoLess Info]
Abstract: A dominating set D of a graph G=(V,E) is a subset of vertices such that every vertex
in V \ D has at least one neighbour in D. Moreover if D is an independent set, i.e. no vertices in D
are pairwise adjacent, then D is said to be an independent dominating set. Finding a minimum independent
dominating set in a graph is an NP-hard problem. We give an algorithm computing a minimum independent
dominating set of a graph on n vertices in time O(1.3575^n). Furthermore, we show that Ω(1.3247^n)
is a lower bound on the worst-case running time of this algorithm.
Erratum: There is an issue with the Reduction Rule RedClique. It is corrected in the journal
version of the paper (see below), which also proves a slightly better upper bound on the running time.
Subsequent work: Bourgeois et al. (SIROCCO 2010) designed an algorithm with running time
O(1.3417^n).
-
Exponential time algorithms for the minimum dominating set problem on
some graph classes
(with Dieter Kratsch and Mathieu Liedloff),
SWAT 2006: Proceedings of the 10th Scandinavian Workshop on Algorithm Theory,
Springer LNCS 4059, pp. 148 - 159.
[pdf] [More InfoLess Info]
Abstract: The Minimum Dominating Set problem remains NP-hard when restricted to chordal graphs, circle graphs and c-dense graphs (i.e. |E| ≥ c*n^2 for a constant c, 0<c<1/2). For each of these three graph classes we present an exponential time algorithm solving the Minimum Dominating Set problem. The running times of those algorithms are O(1.4173^n) for chordal graphs, O(1.4956^n) for circle graphs, and O(1.2303^((1+√1-2c )*n) for c-dense graphs.
Subsequent work: Most running times of this paper have been improved by van Rooij et al. (ESA 2009).
-
A Branch-and-Reduce Algorithm for Finding a Minimum Independent Dominating Set
(with Mathieu Liedloff)
submitted.
[pdf] [More InfoLess Info]
Abstract:
An independent dominating set D of a graph G=(V,E) is a subset of vertices such that
every vertex in V \ D has at least one neighbor in D and D is an independent set,
i.e. no two vertices of D are adjacent in G. Finding a minimum independent dominating set
in a graph is an NP-hard problem. Whereas it is hard to cope with this problem using
parameterized and approximation algorithms, there is a simple exact O(1.4423^n)-time
algorithm solving the problem by enumerating all maximal independent sets. In this paper
we improve the latter result, providing the first non trivial algorithm computing a minimum
independent dominating set of a graph in time O(1.3569^n). Furthermore, we give a lower
bound of Ω(1.3247^n) on the worst-case running time of this algorithm, showing that
the running time analysis is almost tight.
Subsequent work: Bourgeois et al. (SIROCCO 2010) designed an algorithm with running time
O(1.3417^n).
-
Exact and Parameterized Algorithms for Max Internal Spanning Tree
(with Daniel Binkele-Raible, Henning Fernau, and Mathieu Liedloff)
submitted.
[pdf] [More InfoLess Info]
Abstract:
We consider the NP-hard problem of finding a spanning tree with a maximum
number of internal vertices. This problem is a generalization of the famous Hamiltonian
Path problem. Our dynamic-programming algorithms for general and degree-bounded
graphs have running times of the form O*(c^n) with c ≤ 2. For graphs with bounded degree,
c < 2. The main result, however, is a branching algorithm for graphs with maximum degree
three. It only needs polynomial space and has a running time of O(1.8669^n) when analyzed
with respect to the number of vertices. We also show that its running time is 2.1364^k n^(O(1))
when the goal is to find a spanning tree with at least k internal vertices. Both running
time bounds are obtained via a Measure & Conquer analysis, the latter one being a novel
use of this kind of analysis for parameterized algorithms.
-
Exact exponential-time algorithms for finding bicliques
(with Daniel Binkele-Raible, Henning Fernau, and Mathieu Liedloff)
submitted.
[pdf] [More InfoLess Info]
Abstract:
Due to a large number of applications, bicliques of graphs have been widely considered in
the literature. This paper focuses on non-induced bicliques. Given a graph G=(V,E)
on n vertices, a pair (X,Y), with X,Y ⊆ V , X ∩ Y = ∅, is a non-induced biclique if
{x,y} ∈ E for any x ∈ X and y ∈ Y . The NP-complete problem of finding a non-induced
(k1,k2)-biclique asks to decide whether G contains a non-induced biclique (X,Y) such
that |X|=k1 and |Y|=k2. In this paper, we design a polynomial-space O(1.6914^n)-time
algorithm for this problem. It is based on an algorithm for bipartite graphs that
runs in time O(1.30052^n). In deriving this algorithm, we also exhibit a relation to the
spare allocation problem known from memory chip fabrication.
Keywords: exact exponential-time algorithms, NP-hard problem, complete bipartite
subgraphs
-
Feedback Vertex Sets in Tournaments
(with Matthias Mnich),
submitted.
[pdf] [More InfoLess Info]
Abstract: We study combinatorial and algorithmic questions around minimal feedback vertex sets in tournament graphs.
On the combinatorial side, we derive strong upper and lower bounds on the maximum number of minimal feedback vertex sets in an n-vertex tournament.
We prove that every tournament on n vertices has at most 1.6740^n minimal feedback vertex sets and that there is an infinite family of tournaments, all having at least 1.5448^n minimal feedback vertex sets.
This improves and extends the bounds of Moon (1971).
On the algorithmic side, we design the first polynomial space algorithm that enumerates the minimal feedback vertex sets of a tournament with polynomial delay.
The combination of our results yields the fastest known algorithm for finding a minimum size feedback vertex set in a tournament.
-
A Linear Vertex Kernel for Maximum Internal Spanning Tree
(with Fedor V. Fomin, Saket Saurabh, and Stéphan Thomassé),
submitted.
[pdf] [More InfoLess Info]
Abstract: We present a polynomial time algorithm that for any graph G and integer
k ≥ 0, either finds a spanning tree with at least k internal vertices,
or outputs a new graph G' on at most 3k vertices and an integer k such
that G has a spanning tree with at least k internal vertices if and only
if G' has a spanning tree with at least k internal vertices. In other
words, we show that the Maximum Internal Spanning Tree problem
parameterized by the number of internal vertices k has a 3k-vertex kernel.
Our result is based on an innovative application of a classical min-max
result about hypertrees in hypergraphs which states that "a hypergraph H
contains a hypertree if and only if H is partition connected."
Keywords: algorithm, crown decomposition, kernelization, parameterized complexity, preprocessing
-
On Independent Sets and Bicliques in Graphs
(with Dieter Kratsch and Mathieu Liedloff),
submitted.
[pdf] [More InfoLess Info]
Abstract: Bicliques of graphs have been studied extensively, partially motivated by the large
number of applications. One of the main algorithmic interests is in designing algorithms
to enumerate all maximal bicliques of a (bipartite) graph. Polynomial-time
reductions have been used explicitly or implicitly to design polynomial delay algorithms
to enumerate all maximal bicliques.
Based on polynomial-time Turing reductions, various algorithmic problems on
(maximal) bicliques can be studied by considering the related problem for (maximal)
independent sets. In this line of research, we improve Prisner's upper bound on
the number of maximal bicliques [Combinatorica, 2000] and show that the maximum
number of maximal bicliques in a graph on n vertices is exactly 3n/3 (up to a polynomial
factor). We also give algorithms for various problems related to bicliques, and
mainly O(1.3642^n) time algorithms to compute the number of maximal independent
sets and maximal bicliques in a graph.
-
A universally fastest algorithm for Max 2-Sat, Max 2-CSP, and everything in between
(with Gregory B. Sorkin),
submitted.
[pdf] [More InfoLess Info]
Abstract: In this paper we introduce "hybrid" Max 2-CSP formulas consisting of "simple clauses",
namely conjunctions and disjunctions of pairs of variables, and general 2-variable clauses, which can
be any integer-valued functions of pairs of boolean variables. This allows an algorithm to use both
efficient reductions specific to AND and OR clauses, and other powerful reductions that require
the general CSP setting. We use new reductions introduced here, and recent reductions such as
"clause-learning" and "2-reductions" generalized to our setting's mixture of simple and general
clauses.
Parametrizing an instance by the fraction p of non-simple clauses, we give an exact (exponential-time)
algorithm that is the fastest known polynomial-space algorithm for p = 0 (which includes
the well-studied Max 2-Sat problem but also instances with arbitrary mixtures of AND and OR
clauses); the only efficient algorithm for mixtures of AND, OR, and general integer-valued clauses;
and tied for fastest for general Max 2-CSP (p = 1). Since a pure 2-Sat input instance may be
transformed to a general CSP instance in the course of being solved, the algorithm's efficiency and
generality go hand in hand.
Our algorithm analysis and optimization are a variation on the familiar measure-and-conquer
approach, resulting in an optimizing mathematical program that is convex not merely quasi-convex,
and thus can be solved efficiently and with a certificate of optimality. We produce a family of
running-time upper-bound formulas, each optimized for instances with a particular value of p but
valid for all instances.
-
A Moderately Exponential Time Algorithm for Full Degree Spanning Tree
(with Saket Saurabh and Alexey A. Stepanov),
submitted.
[pdf] [More InfoLess Info]
Abstract: We present a moderately exponential time exact algorithm for the
well-studied Full Degree Spanning Tree problem, an NP-hard variant of
the Spanning Tree problem. Given a graph G, the objective is to find
a spanning tree T of G which maximizes the number of vertices that
have the same degree in T as in G. The problem is motivated by its
application in fluid networks and is basically a graph-theoretic abstraction
of the problem of placing flow meters in fluid networks. We give an exact
algorithm for Full Degree Spanning Tree running in time O(1.9465^n).
This adds Full Degree Spanning Tree to a very small list of "non-local
problems", like Feedback Vertex Set and Connected Dominating
Set, for which non-trivial (non brute force enumeration) exact algorithms
are known.
-
Kernels for Feedback Arc Set In Tournaments
(with Stéphane Bessy, Fedor V. Fomin, Christophe Paul, Anthony Perez, Saket Saurabh, and Stéphan Thomassé),
Journal of Computer and System Sciences, to appear.
[pdf] [More InfoLess Info]
Abstract: A tournament T = (V,A) is a directed graph in which there is exactly one arc
between every pair of distinct vertices. Given a digraph on n vertices and an integer
parameter k, the Feedback Arc Set problem asks whether the given digraph has
a set of k arcs whose removal results in an acyclic digraph. The Feedback Arc
Set problem restricted to tournaments is known as the k-Feedback Arc Set in
Tournaments (k-FAST) problem. In this paper we obtain a linear vertex kernel
for k-FAST. That is, we give a polynomial time algorithm, which, given an input
instance T to k-FAST, obtains an equivalent instance T' on O(k) vertices. In fact,
given any fixed ε > 0, the kernelized instance has at most (2 + ε)*k vertices. Our
result improves the previous known bound of O(k^2) on the kernel size for k-FAST.
Our kernelization algorithm solves the problem on a subclass of tournaments in
polynomial time and uses a known polynomial time approximation scheme for k-FAST.
-
Parameterized Algorithm for Eternal Vertex Cover
(with Fedor V. Fomin, Petr Golovach, Dieter Kratsch, and Saket Saurabh),
Information Processing Letters 110(16): 702-706, 2010.
[pdf] [More InfoLess Info]
Abstract: In this paper we initiate the study of a "dynamic" variant of the classical Vertex Cover
problem, the Eternal Vertex Cover problem, from parameterized algorithmic perspective.
Klostermeyer and Mynhardt introduced the Eternal Vertex Cover problem, which
consists in placing a minimum number of guards on the vertices of a graph such that these
guards can protect the graph from any sequence of attacks on its edges. In response to
an attack, each guard is allowed either to stay in his vertex, or to move to a neighboring
vertex. However, at least one guard has to fix the attacked edge by moving along it. The
other guards may move to reconfigure and prepare for the next attack. Thus at every step
the vertices occupied by guards form a vertex cover. We show that the problem admits a
kernel of size 4^k*(k + 1) + 2k, which shows that the problem is fixed parameter tractable when
parameterized by the number of available guards k. Finally, we also provide an algorithm
with running time O(2^(O(k^2)) + 1.2738^k*m + n) for Eternal Vertex Cover, where n is
the number of vertices and m the number of edges of the input graph. In passing we also
observe that Eternal Vertex Cover is NP-hard but that there is a polynomial time
2-approximation algorithm.
-
Parallel Cleaning of a Network with Brushes
(with Margaret-Ellen Messinger, Pawel Pralat, and Richard J. Nowakowski),
Discrete Applied Mathematics 158(5): 467-478, 2010.
[pdf] [More InfoLess Info]
Abstract: We consider the process of cleaning a network where at each time step, all vertices that have at least as many brushes as incident, contaminated edges, send brushes down these edges and remove them from the network. An added condition is that, because of the contamination model used, the final configuration must be the initial configuration of another cleaning of the network. We find the minimum number of brushes required for trees, cycles, complete bipartite networks; and for all networks when all edges must be cleaned on each step. Finally, we give bounds on the number of brushes required for complete networks.
Keywords: Brush number; Edge searching; Chip firing game.
-
Iterative Compression and Exact Algorithms
(with Fedor V. Fomin, Dieter Kratsch, Mathieu Liedloff, and Saket Saurabh),
Theoretical Computer Science 411(7-9): 1045-1053, 2010.
[pdf] [More InfoLess Info]
Abstract: Iterative compression has recently led to a number of breakthroughs in parameterized complexity. Here, we show that the technique can also be useful in the design of exact exponential time algorithms to solve NP-hard problems. We exemplify our findings with algorithms for the Maximum Independent Set problem, a parameterized and a counting version of d-Hitting Set and the Maximum Induced Cluster Subgraph problem.
Keywords: Exponential time algorithms; Graph algorithms; Independent set; Hitting set; Induced cluster; Fixed parameter algorithms; Iterative compression.
Subsequent work: Dom et al. (Journal of Discrete Algorithms 8(1), 2010) independently obtain the same result for the parameterized 4- and 5-Hitting Set problems (our Corollary 13). They also use Iterative Compression to obtain an exact exponential time algorithm for Feedback Vertex Set in Tournaments.
-
Exponential time algorithms for the minimum dominating set problem on some graph classes
(with Dieter Kratsch, Mathieu Liedloff, and Ioan Todinca),
ACM Transactions on Algorithms 6(1): Article 9, 1-21, 2009.
[pdf] [More InfoLess Info]
Abstract: The minimum dominating set problem remains NP-hard when restricted to any of the following graph classes: c-dense graphs, chordal graphs, 4-chordal graphs, weakly chordal graphs, and circle graphs. Developing and using a general approach, for each of these graph classes we present an exponential time algorithm solving the minimum dominating set problem faster than the best known algorithm for general graphs. Our algorithms have the following running time: O(1.4124^n) for chordal graphs, O(1.4776^n) for weakly chordal graphs, O(1.4845^n) for 4-chordal graphs, O(1.4887^n) for circle graphs, and O(1.2273^(1+√1-2c )n) for c-dense graphs.
Keywords: Moderately exponential-time algorithms, dominating set problem, graph classes
Subsequent work: Most running times of this paper have been improved by van Rooij et al. (ESA 2009).
-
On Two Techniques of Combining Branching and Treewidth
(with Fedor V. Fomin, Saket Saurabh, and Alexey A. Stepanov)
Algorithmica 54(2): 181-207, 2009.
[pdf] [More InfoLess Info]
Abstract: Branch & Reduce and dynamic programming on graphs of bounded treewidth are among the most common and powerful techniques used in the design of moderately exponential time exact algorithms for NP hard problems. In this paper we discuss the efficiency of simple algorithms based on combinations of these techniques. The idea behind these algorithms is very natural: If a parameter like the treewidth of a graph is small, algorithms based on dynamic programming perform well. On the other side, if the treewidth is large, then there must be vertices of high degree in the graph, which is good for branching algorithms. We give several examples of possible combinations of branching and programming which provide the fastest known algorithms for a number of NP hard problems. All our algorithms require non-trivial balancing of these two techniques.
In the first approach the algorithm either performs fast branching, or if there is an obstacle for fast branching, this obstacle is used for the construction of a path decomposition of small width for the original graph. Using this approach we give the fastest known algorithms for Minimum Maximal Matching and for counting all 3-colorings of a graph.
In the second approach the branching occurs until the algorithm reaches a subproblem with a small number of edges (and here the right choice of the size of subproblems is crucial) and then dynamic programming is applied on these subproblems of small width. We exemplify this approach by giving the fastest known algorithm to count all minimum weighted dominating sets of a graph.
We also discuss how similar techniques can be used to design faster parameterized algorithms.
Keywords: Exact exponential time algorithms; Parameterized algorithms; NP hard problems; Treewidth; #3-Coloring; #Minimum dominating set; Minimum maximal matching; k-Weighted vertex cover
Subsequent work: For Minimum Maximal Matching, van Rooij and Bodlaender (IWPEC 2008) give a faster O(1.3226^n)-time algorithm. Gaspers et al. (COCOON 2007) give a slightly faster O(1.6262^n)-time algorithm for counting all 3-colorings of a graph. For counting minimum dominating sets, van Rooij et al. obtain a faster O(1.5048^n)-time algorithm.
-
Clean the Graph Before You Draw It!
(with Margaret-Ellen Messinger, Pawel Pralat, and Richard J. Nowakowski),
Information Processing Letters 109(10): 463-467, 2009.
[pdf] [More InfoLess Info]
Abstract: We prove a relationship between the Cleaning problem and the Balanced Vertex-Ordering problem, namely that the minimum total imbalance of a graph equals twice the brush number of a graph. This equality has consequences for both problems. On one hand, it allows us to prove the NP-completeness of the Cleaning problem, which was conjectured by Messinger et al. [M.-E. Messinger, R.J. Nowakowski, P. Pralat, Cleaning a network with brushes, Theoret. Comput. Sci. 399 (2008) 191–205]. On the other hand, it also enables us to design a faster algorithm for the Balanced Vertex-Ordering problem [J. Kára, K. Kratochvíl, D. Wood, On the complexity of the balanced vertex ordering problem, Discrete Math. Theor. Comput. Sci. 9 (1) (2007) 193–202].
Keywords: Brush number; Balanced vertex-ordering; Graph algorithms; Computational complexity.
-
On the minimum feedback vertex set problem: Exact and enumeration algorithms
(with Fedor V. Fomin, Artem V. Pyatkin, and Igor Razgon)
Algorithmica 52(2): 293-307, 2008.
[pdf] [More InfoLess Info]
Abstract: We present a time O(1.7548^n) algorithm finding a minimum feedback vertex set in an undirected graph on n vertices. We also prove that a graph on n vertices can contain at most 1.8638^n minimal feedback vertex sets and that there exist graphs having 105^(n/10) ≈ 1.5926^n minimal feedback vertex sets.
Keywords: Minimum feedback vertex set; Maximum induced forest; Exact exponential algorithm; Number of minimal feedback vertex sets.
