Conference version:
In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing
(STOC 2018), 574-586, 2018.
(with:
Mark de Berg,
Hans L. Bodlaender,
Sándor Kisfaludi-Bak, and
Tom C. van der
Zanden)
Algorithmica 82(8): 2135-2155, 2020.
(with:
Stefan
Kratsch,
Shaohua Li,
Marcin Pilipczuk,
and
Magnus Wahlström)
Conference version:
In 13th International Symposium on Parameterized and Exact Computation (IPEC
2018), 18:1-18:14, 2018.
(with:
Stefan
Kratsch,
Shaohua Li,
Marcin Pilipczuk,
and
Magnus Wahlström)
Algorithmica 82(7): 1989-2005, 2020.
(with: Andreas
Feldmann)
Conference version:
In 16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT
2018), 19:1-19:13, 2018.
(with:
Andreas
Feldmann)
Algorithmica 81(10): 3890-3935, 2019.
(with:
Édouard Bonnet,
Nick Brettell,
and
O-joung Kwon)
Conference version:
42nd In 12th International Symposium on Parameterized and Exact Computation
(IPEC 2017), 7:1-7:13, 2017.
(with:
Édouard Bonnet,
Nick Brettell,
and
O-joung Kwon)
Inf. Process. Lett. 151, 7:1-7:11, 2019.
(with:
Saeed Akhoondian
Amiri,
Stephan
Kreutzer, and
Roman
Rabinovich)
Conference version:
41st International Symposium on Mathematical Foundations of Computer Science
(MFCS 2016), 7:1-7:11, 2016.
(with:
Saeed Akhoondian
Amiri,
Stephan
Kreutzer, and
Roman
Rabinovich)
Algorithmica,81(2):421-438, 2019.
(with:
Gábor Bacsó,
Daniel
Lokshtanov,
Marcin Pilipczuk,
Zsolt Tuza, and
Erik Jan van Leeuwen)
Conference version:
11th International Symposium on Parameterized and Exact Computation (IPEC
2016),3:1-3:12, 2016.
(with:
Gábor Bacsó
and
Zsolt Tuza)
ACM Transactions on Algorithms, 14(2):13:1-13:30, 2018.
(with: Daniel Lokshtanov and
Saket Saurabh)
Conference version:
In Proceedings of the 22nd ACM-SIAM Symposium on Discrete Algorithms (SODA
2011), 777-789, 2011.
(with:
Daniel Lokshtanov and
Saket Saurabh)
We obtain a number of lower bounds on the running time of algorithms solving
problems on graphs of bounded treewidth. We prove the results under the
Strong Exponential Time Hypothesis of Impagliazzo and Paturi. In particular,
assuming that SAT cannot be solved in
(2-ε)
nmO(1)
time, we show that for any ε> 0;
- INDEPENDENT SET cannot be solved in
(2-ε)tw(G)|V(G)|O(1) time,
- DOMINATING SET cannot be solved in
(3-ε)tw(G)|V(G)|O(1)
time,
- MAX CUT cannot be solved in
(2-ε)tw(G)|V(G)|O(1)
time,
- ODD CYCLE TRANSVERSAL cannot be solved in
(2-ε)tw(G)|V(G)|O(1)
time,
- For any q≥3, q-COLORING cannot be solved in
(q-ε)tw(G)|V(G)|O(1)
time,
- PARTITION INTO TRIANGLES cannot be solved in
(2-ε)tw(G)|V(G)|O(1)
time.
Our lower bounds match the running times for the best known algorithms for
the problems, up to the ε in the base.
SIAM Journal on Computing, 47(3):675-702, 2018..
(with: Daniel Lokshtanov and
Saket Saurabh)
Conference version:
In Proceedings of the 22nd ACM-SIAM Symposium on Discrete Algorithms (SODA
2011), 760-776, 2011.
(with:
Daniel Lokshtanov and
Saket Saurabh)
A central problem in parameterized algorithms is to obtain algorithms
with running time
f(
k)
nO(1) such that
f is as slow growing
function of the parameter
k as possible.
In particular, the first natural goal is to make
f(
k) single-exponential,
that is,
c^
k for some constant
c.
This has led to the development of parameterized algorithms for various
problems
where
f(
k) appearing in their
running time is of form 2
O(k). However there are still plenty of
problems
where the 'slightly superexponential'
f(
k) appearing in the best known
running time has remained non single-exponential even after a
lot of attempts to bring it down. A natural question to ask is whether the
f(
k) appearing in the running time of the best-known algorithms is optimal
for any of these problems.
In this paper, we examine parameterized problems where
f(
k) is
kO(k)=2
O(klog
k) in the best known running time and for a number of
such problems, we show that the dependence
on
k in the running time cannot be improved to single exponential.
More precisely we prove following tight lower bounds, for three natural
problems, arising
from three different domains:
- The pattern matching problem CLOSEST STRING is known to be solvable in
time
2O(dlog d)nO(1)
and
2O(dlog
|Σ|)nO(1).
We show that there is no
2o(dlog d)nO(1)
and
2o(dlog
|Σ|)nO(1) time algorithm, unless
Exponential Time
Hypothesis (ETH) fails.
- The graph embedding problem DISTORTION, that is, deciding whether a graph
G has a metric
embedding into the integers with distortion at most d can be done in time
2O(dlog d)nO(1).
We show that there is no 2o(dlog d)nO(1)
time algorithm, unless ETH fails.
- The DISJOINT PATHS problem can be solved in time in time
2O(wlog w)nO(1) on graphs of treewidth at most
w. We show that
there is no
2o(wlog w)nO(1)
time algorithm, unless ETH fails.
To obtain our result we first prove the lower bound for variants
of basic problems: finding cliques, independent sets, and hitting
sets. These artificially constrained variants
form a good starting point for proving lower bounds on natural
problems without any technical restrictions and could be of independent
interest. We believe that many further
results of this form can be obtained by using the framework of the current
paper.
Journal of Computational Geometry, 9(2):47-80, 2018.
(with: Csaba
Bíró,
Édouard
Bonnet,
Till Miltzow, and
Pawel Rzazewski)
Conference version:
In Proceedings of the 33rd International Symposium on Computational Geometry (SoCG 2017),
18:1-18:16, 2017.
(with:
Csaba
Bíró,
Édouard
Bonnet,
Till Miltzow, and
Pawel Rzazewski)
J. Combinatorial Theory Ser. B, 122:428-437, 2017.
(with: Paul Seymour
and
Paul Wollan)
Algorithmica, 78(1):110-146, 2017.
(with: Rajesh Chitnis,
László Egri)
Conference version:
In Proceedings of the 21st European Symposium on Algorithms (ESA
2013), Lecture Notes in Computer Science Volume 8125, Springer, 313-324,
2013.
(with:
Rajesh Chitnis,
László Egri)
In the deletion version of the list homomorphism problem, we are given
graphs G and H, a list
L(v)⊆V(H) for each vertex
v\∈V(G), and an integer k. The task is
to decide whether there exists a set W⊆V(G) of size at
most k such that there is a homomorphism from G\W to
H respecting the lists. We show that DL-HOM(H), parameterized by
k and
|H|, is fixed-parameter
tractable for any (P6,C6)-free bipartite graph
H; already for
this restricted class of graphs, the problem generalizes Vertex
Cover, Odd Cycle Transversal, and Vertex Multiway Cut parameterized by the
size of the cutset and the number of terminals. We conjecture that
DL-HOM(H) is fixed-parameter tractable for the class of graphs
H for
which the list homomorphism problem (without deletions) is
polynomial-time solvable; by a result of Feder et
al., a graph H belongs to this class precisely
if
it is a bipartite graph whose complement is a circular arc graph. We
show that this conjecture is equivalent to the fixed-parameter
tractability of a single fairly natural satisfiability problem,
Clause Deletion Chain-SAT.
Information and Computation, 256:62-82, 2017.
(with:Marek Cygan,
Marcin Pilipczuk,
Michal Pilipczuk)
Conference version:
Mathematical foundations of computer science (MFCS 2014), (2)489-500, Lecture
Notes in Comput. Sci., 8635, Springer, 2014.
(with:
Marek Cygan,
Marcin Pilipczuk,
Michal Pilipczuk)
We study the complexity of a generic hitting problem H-SUBGRAPH
HITTING, where given a
fixed pattern graph H and an input graph G we seek for the minimum size
of a set X of vertices that hits all subgraphs of G isomorphic to H.
In the colorful variant of the problem, each vertex of G is precolored
with
some color from V(H) and we require to hit only H-subgraphs
with matching
colors. Standard techniques (e.g., Courcelle's theorem) show that, for every
fixed H and the problem is fixed-parameter tractable parameterized by the
treewidth of G; however, it is not clear how exactly the running time
should depend on treewidth. For the colorful variant, we demonstrate matching
upper and lower bounds showing that the dependence of the running time
on treewidth of G is tightly governed by μ(H),
the maximum size of a
minimal vertex separator in H. That is, we show for every fixed
H that,
on a graph of treewidth t, the colorful problem can be solved in time
2O(tμ(H))|V(G)|,
but cannot be solved in time
2o(tμ(H))|V(G)|O(1),
assuming the Exponential Time
Hypothesis (ETH). Furthermore, we give some preliminary results showing
that, in the absence of colors, the parameterized complexity landscape of
H-SUBGRAPH HITTING is much richer.
Journal of Graph Theory, 85(4):814-838, 2017.
(with:Pierre Aboulker,
Nick Brettel,
Fréderic
Havét,
Nicolas Trotignon)
A graph G has maximal local edge-connectivity k if
the maximum number of edge-disjoint paths between every pair of distinct vertices
x and y is at most k.
We prove Brooks-type theorems for k-connected graphs with maximal local edge-connectivity
k, and for any graph with maximal local edge-connectivity 3.
We also consider several related graph classes defined by constraints on connectivity.
In particular, we show that there is
a polynomial-time algorithm that, given a 3-connected graph G with maximal local connectivity 3, outputs an optimal colouring for
G.
On the other hand,
we prove, for k ≥ 3, that k-COLOURABILITY is NP-complete when restricted to minimally
k-connected graphs,
and 3-COLOURABILITY is NP-complete when restricted to (k-1)-connected graphs with maximal local connectivity
k.
Finally, we consider a parameterization of k-COLOURABILITY based on the number
of vertices of degree at least k+1, and prove that, even when
k is part of the input, the corresponding parameterized problem is FPT.
ACM Transactions on Computation Theory, 8(1):1:1-1:28, 2016.
(with: Stefan
Kratsch, Magnus Wahlström)
Conference version:
Mathematical foundations of computer science (MFCS 2010), 489-500, Lecture
Notes in Comput. Sci., 6281, Springer, 2010.
(with:
Stefan
Kratsch,
Magnus Wahlström)
For a finite set Γ of Boolean relations, Max Ones SAT(Γ) and
Exact Ones SAT(Γ) are generalized satisfiability problems where every
constraint relation is from Γ, and the task is to find a satisfying
assignment with at least/exactly k variables set to 1, respectively. We
study the parameterized complexity of these problems, including the question
whether they admit polynomial kernels. For Max Ones SAT(Γ), we give a
classification into 5 different complexity levels: polynomial-time solvable,
admits a polynomial kernel, fixed-parameter tractable, solvable in
polynomial time for fixed k, and NP-hard already for k=1. For Exact Ones
SAT(Γ), we refine the classification obtained earlier by having a
closer look at the fixed-parameter tractable cases and classifying the sets
Γ for which Exact Ones SAT(Γ) admits a polynomial kernel.
ACM Transactions on Algorithms, 12(3):41:1-41:24, 2016.
(with:Marek Cygan,
Holger Dell,
Daniel
Lokshtanov,
Jesper Nederlof,
Yoshio Okamoto,
Ramamohan Paturi,
Saket Saurabh,
Magnus Wahlström)
Conference version:
Proceedings of the 27th Annual IEEE Conference on Computational Complexity
(CCC 2012), 74-84, 2012.
(with:
Marek Cygan,
Holger Dell,
Daniel
Lokshtanov,
Jesper Nederlof,
Yoshio Okamoto,
Ramamohan Paturi,
Saket Saurabh,
Magnus Wahlström)
The field of exact exponential time algorithms for NP-hard problems
has thrived over the last decade.
While exhaustive search remains asymptotically the fastest known
algorithm for some basic problems, difficult and non-trivial
exponential time algorithms have been found for a myriad of problems,
including GRAPH COLORING, HAMILTONIAN PATH, DOMINATING SET, 3-CNF-SAT.
In some instances, improving these algorithms further seems to be out
of reach.
The CNF-SAT problem is the canonical example of a problem for
which the trivial exhaustive search algorithm runs in time
O(2n),
where n is the number of variables in the input formula.
While there exist non-trivial algorithms for CNF-SAT that run in
time o(2n),
no algorithm was able to improve the growth
rate 2 to a smaller constant, and hence it is natural to
conjecture
that 2 is the optimal growth rate.
The strong exponential time hypothesis (SETH) by Impagliazzo and
Paturi [JCSS 2001] goes a little bit further and asserts that, for
every ε<1, there is a (large) integer k such
that that
k-CNF-SAT cannot be computed in time 2εn.
In this paper, we show that, for every ε<1, the problems
HITTING SET, SET SPLITTING, and NAE-SAT cannot be
computed in
time O(2εn) unless SETH fails.
Here n is the number of elements or variables in the input.
For these problems, we actually get an equivalence to SETH in a
certain sense.
We conjecture that SETH implies a similar statement for SET COVER,
and prove that, under this assumption, the fastest known algorithms
for
STEINER TREE, CONNECTED VERTEX COVER, SET PARTITIONING, and the pseudo-polynomial time
algorithm for SUBSET SUM cannot be significantly improved.
Finally, we justify our assumption about the hardness of SET COVER
by showing that the parity of the number of set covers
cannot be computed in time O(2εn) for any
ε<1
unless SETH fails.
Algorithmica, 75(1):118-137, 2016.
(with: Yixin Cao)
Conference version:
In Proceedings of
31st International Symposium on Theoretical Aspects of Computer Science
(STACS 2014), 214-225, 2014.
(with:
Yixin Cao)
Graph modification problems are typically asked as follows: is there a set
of k operations that transforms a given graph to have a certain property.
The most commonly considered operations include vertex deletion, edge
deletion, and edge addition; for the same property, one can define
significantly different versions by allowing different operations. We study
a very general graph modification problem which allows all three types of
operations: given a graph G and integers k1,
k2, and k3, the CHORDAL
EDITING problem asks if G can be transformed into a chordal graph by at most
k1 vertex deletions, k2 edge deletions, and
k3 edge additions. Clearly,
this problem generalizes both CHORDAL VERTEX/EDGE DELETION and CHORDAL
COMPLETION (also known as MINIMUM FILL-IN). Our main result is an algorithm
for CHORDAL EDITING in time 2O(k log(k))
nO(1), where k:=
k1+
k2+
k3;
therefore, the problem is fixed-parameter tractable parameterized by the
total number of allowed operations. Our algorithm is both more efficient and
conceptually simpler than the previously known algorithm for the special
case CHORDAL DELETION.
SIAM Journal on Computing, 44(1):114-159, 2015.
(with:
Martin Grohe)
Conference version:
In Proceedings of the 44th annual ACM symposium on Theory of computing (STOC
2012), 173-192, 2012.
(with:
Martin Grohe)
We generalize the structure theorem of Robertson and Seymour for
graphs excluding a fixed graph H as a minor to graphs excluding
H as a topological subgraph. We prove that for a fixed H, every
graph excluding H as a topological subgraph has a tree
decomposition where each part is either ``almost embeddable'' to a
fixed surface or has bounded degree with the exception of a bounded
number of vertices. Furthermore, such a decomposition
is computable by an algorithm that is fixed-parameter tractable with
parameter |H|.
We present two algorithmic applications of our structure theorem. To
illustrate the mechanics of a ``typical'' application of the
structure theorem, we show that on graphs excluding H as a
topological subgraph, PARTIAL DOMINATING SET (find k
vertices whose closed neighborhood has maximum size) can be solved
in time f(H,k)nO(1) time. More significantly, we show
that on graphs excluding H as a topological subgraph,
GRAPH ISOMORPHISM can be solved in time
nf(H). This
result unifies and generalizes two previously known important
polynomial-time solvable cases of GRAPH ISOMORPHISM:
bounded-degree graphs and H-minor free graph. The proof of this result needs a generalization of our
structure theorem to the context of invariant treelike
decomposition.
ACM Transaction on Algorithms, 11(3):21, 2015.
(with: Yixin Cao)
Conference version:
In Proceedings of the 25th ACM-SIAM Symposium on Discrete Algorithms (SODA
2014), 122-141, 2014.
(with:
Yixin Cao)
We study the minimum interval deletion problem, which asks for the removal
of a set of at most k vertices to make a graph on n vertices into an
interval graph. We present a parameterized algorithm of runtime
10knO(1)
for this problem, thereby showing its fixed-parameter tractability.
ACM Transaction on Algorithms, 11(4):27m 2015.
(with: László
A. Végh)
Conference version:
40th International Colloquium on Automata, Languages and Programming (ICALP
2013), 721-732, Lecture Notes in Comput. Sci., 7965, Springer, 2013.
(with:
László
A. Végh)
We consider connectivity-augmentation problems in a setting where
each potential new edge has a nonnegative cost associated with it, and
the task is to achieve a certain connectivity target with at most
p
new
edges of minimum total cost. The main result is that the minimum
cost augmentation of edge-connectivity from k-1 to k with at
most p new edges is fixed-parameter tractable parameterized by
p
and admits a polynomial kernel. We also prove the
fixed-parameter
tractability of increasing edge-connectivity from 0 to 2, and
increasing node-connectivity from 1 to 2.
ACM Transaction on Algorithms, 11(4):28, 2015.
(with: Rajesh Chitnis,
Marek Cygan,
and
MohammadTaghi Hajiaghayi)
Conference version:
39th International Colloquium on Automata, Languages and Programming (ICALP
2012), 230-241, Lecture Notes in Comput. Sci., 7391, Springer, 2012..
(with:
Rajesh Chitnis,
Marek Cygan,
and
MohammadTaghi Hajiaghayi)
Given a graph G and an integer k, the FEEDBACK VERTEX SET
(FVS)
problem asks if there is a vertex set T of size at most k
that hits all cycles in the graph. Bodlaender (WG '91) gave the first
fixed-parameter algorithm for FVS in undirected graphs. The
fixed-parameter tractability status of FVS in directed graphs was
along-standing open problem until Chen et al. (STOC '08) showed that it is
fixed-parameter tractable by giving an
4kk!nO(1) algorithm. In the
subset versions of this problems, we are given an additional subset S of
vertices (resp. edges) and we want to hit all cycles passing through a vertex
of S (resp. an edge of S). Indeed both the edge and vertex versions are
known to be equivalent in the parameterized sense. Recently the
SUBSET FEEDBACK VERTEX SET in undirected graphs was shown to be FPT
by Cygan et al. (ICALP '11) and Kakimura et al. (SODA '12). We generalize
the result of Chen et al. (STOC '08) by showing that SUBSET FEEDBACK VERTEX
SET in directed graphs can be solved in time
22O(k)nO(1),
i.e., FPT parameterized by size k of the solution. By our result, we
complete the picture for feedback vertex set problems and their subset
versions in undirected and directed graphs. The technique of random sampling
of important separators was used by Marx and Razgon (STOC '11) to show
that UNDIRECTED MULTICUT is FPT and was generalized by Chitnis et
al. (SODA '12) to directed graphs to show that DIRECTED MULTIWAY CUT
is FPT. In this paper we give a general family of problems (which includes
DIRECTED MULTIWAY CUT and DIRECTED SUBSET FEEDBACK VERTEX SET
among others) for which we can do random sampling of
important separators and obtain a set which is disjoint from a minimum
solution and covers its "shadow". We believe this general approach will be
useful for showing the fixed-parameter tractability of other problems in
directed graphs.
Algorithmica, 72(3):687-713, 2015.
(with: Pinar Heggernes,
Pim van 't Hof,
Neeldhara Misra, and
Yngve Villanger)
Conference version:
38th International Workshop on Graph Theoretic Concepts in
Computer Science (WG 2012), 332-343, Lecture Notes in Comput. Sci.,
7551,
Springer, 2012.
(with:
Pinar Heggernes,
Pim van 't Hof,
Neeldhara Misra, and
Yngve Villanger)
We study the problem of finding small
s-
t separators that induce
graphs having certain properties. It is known that finding a minimum clique
s-
t} separator is polynomial-time solvable (Tarjan 1985), while
for example the problems of finding a minimum
s-
t separator that
is a connected graph or an independent set are fixed-parameter tractable
(Marx, O'Sullivan and Razgon, manuscript). We extend these results the
following way:
- Finding a minimum c-connected
s-t separator is FPT for c=2 and W[1]-hard for any
c≥3
-
Finding a minimum s-t separator with diameter at
most d is W[1]-hard for any d≥2.
- Finding a minimum
r-regular s-t separator is W[1]-hard for any
r≥1
- For any decidable graph property, finding a minimum
s-t separator with this property is FPT parameterized jointly by
the size of the separator and the maximum degree.
We also
show that finding a connected
s-
t separator of minimum size does
not have a polynomial kernel, even when restricted to graphs of maximum
degree at most 3, unless NP is a subset of coNP/poly.
SIAM Journal on Computing, 43(2):355-388, 2014.
(with: Andrei
Bulatov)
Conference version:
38th International Colloquium on Automata, Languages and Programming (ICALP
2011), 424-436, Lecture Notes in Comput. Sci., 6755, Springer, 2011.
(with:
Andrei
Bulatov)
In the constraint satisfaction problem (CSP) corresponding to a
constraint language (i.e., a set of relations) Γ, the goal is
to find an assignment of values to variables so that a given set of
constraints specified by relations from Γ is satisfied. In
this paper we study the fixed-parameter tractability of constraint
satisfaction problems parameterized by the size of the solution in
the following sense: one of the possible values, say 0, is ``free,''
and the number of variables allowed to take other, ``expensive,''
values is restricted. A size constraint requires that exactly k
variables take nonzero values. We also study a more refined version
of this restriction: a global cardinality constraint prescribes how
many variables have to be assigned each particular value. We study
the parameterized complexity of these types of CSPs where the
parameter is the required number k of nonzero variables. As
special cases, we can obtain natural and well-studied parameterized
problems such as INDEPENDENT SET, VERTEX COVER, -HITTING SET, BICLIQUE,
etc.
In the case of constraint languages closed under substitution of
constants, we give a complete characterization of the
fixed-parameter tractable cases of CSPs with size constraints, and
we show that all the remaining problems are W[1]-hard. For CSPs with
cardinality constraints, we obtain a similar classification, but for
some of the problems we are only able to show that they are
BICLIQUE-hard. The exact parameterized complexity of the
BICLIQUE problem is a notorious open problem, although it
is believed to be W[1]-hard.
SIAM Journal on Computing, 43(2):355-388, 2014.
(with: Igor
Razgon)
Conference version:
In Proceedings of the 43rd annual ACM symposium on Theory of computing (STOC
2011), 469-478, 2011.
(with:
Igor
Razgon)
Given an undirected graph G, a collection
{(s1,t1),...,(sk,tk)}
of pairs of vertices, and an integer p, the Edge Multicut problem ask if
there is a set S of at most p edges such that the removal of
S disconnects every si from the corresponding
ti. Vertex Multicut is the
analogous problem where S is a set of at most p vertices. Our main
result is that both problems can be solved in time
2O(p3)nO(1),
i.e., fixed-parameter tractable parameterized by the size p of the cutset
in the solution. By contrast, it is unlikely that an algorithm with running
time of the form 2O(p3)nO(1) exists for the directed version of the
problem, as we show it to be W[1]-hard parameterized by the size of the
cutset.
ACM Transactions on Algorithms, 10(4):21, 2014
(with: Holger Dell,
Thore Husfeldt,
Nina Taslaman, Martin Wahlén)
We show conditional lower bounds for well-studied #P-hard problems:
-
The number of satisfying assignments of a 2-CNF formula with n variables
cannot be computed in time exp(o(n)), and the same is true for computing the
number of all independent sets in an n-vertex graph.
-
The permanent of an n*n matrix with entries 0 and 1 cannot be computed
in time exp(o(n)).
-
The Tutte polynomial of an n-vertex multigraph cannot be computed in time
exp(o(n)) at most evaluation points (x; y) in the case of multigraphs, and
it
cannot be computed in time exp(o(n/ poly log n)) in the case of simple
graphs.
Our lower bounds are relative to (variants of) the Exponential Time
Hypothesis
(ETH), which says that the satisfiability of
n-variable 3-CNF formulas
cannot be
decided in time exp(
o(
n)). We relax this hypothesis by introducing its
counting
version #ETH, namely that the satisfying assignments cannot be counted in
time
exp(
o(
n)). In order to use #ETH for our lower bounds, we transfer the
sparsification
lemma for
d-CNF formulas to the counting setting.
ACM Transactions on Algorithms, 11(1):4, 2014.
(with: Martin Grohe)
Conference version:
In Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete
Algorithms (SODA 2006), 289-298, 2006.
(with:
Martin Grohe)
Many important combinatorial problems can be modeled as constraint
satisfaction problems. Hence identifying polynomial-time solvable classes
of constraint satisfaction problems has received a lot of attention. In
this paper, we are interested in structural properties that can make the
problem tractable. So far, the largest structural class that is known to be
polynomial-time solvable is the class of bounded hypertree width instances
introduced by Gottlob et al. Here we identify a new class of
polynomial-time solvable instances: those having bounded fractional edge
cover number.
Combining hypertree width and fractional edge cover number,
we then introduce the notion of fractional hypertree width. We prove that
constraint satisfaction problems with bounded fractional hypertree width
can be solved in polynomial time (provided that a the tree decomposition is
given in the input). Together with a recent approximation algorithm for
finding such decompositions, it follows that
bounded fractional hypertree width is now the most general known structural
property that guarantees polynomial-time solvability.
ACM Transactions on Algorithms, 11(2):14, 2014.
(with: Erik Demaine, MohammadTaghi Hajiaghayi)
Conference version:
In Proceedings of the 17th European Symposium on Algorithms (ESA 2009),
Lecture Notes in Comput. Sci., 5757, Springer, Berlin, 718-729, 2009.
(with:
Erik Demaine,
MohammadTaghi Hajiaghayi)
We study an extensive class of movement minimization problems which
arise from many practical scenarios but so far have little
theoretical study. In general, these problems involve planning the
coordinated motion of a collection of agents (representing
robots, people, map labels, network messages, etc.) to achieve a
global property in the network while minimizing the maximum or
average movement (expended energy). The only previous
theoretical
results about this class of problems are about approximation, and
mainly negative: many movement problems of interest have polynomial
inapproximability. Given that the number of mobile agents is
typically much smaller than the complexity of the environment, we
turn to fixed-parameter tractability. We characterize the
boundary
between tractable and intractable movement problems in a very
general set up: it turns out the complexity of the problem
fundamentally depends on the treewidth of the minimal
configurations. Thus the complexity of a particular problem can be
determined by answering a purely combinatorial question. Using
our
general tools, we determine the complexity of several concrete
problems and fortunately show that many movement problems of
interest can be solved efficiently.
SIAM Journal on Discrete Mathematics, 28(1):503-520, 2014
(with:
Paul Wollan)
We consider the problem of how much edge connectivity is necessary to force
a graph G to contain a fixed graph H as an immersion. We show that if the maximum
degree in H is Δ, then
all the examples of Δ-edge connected graphs which do not contain
H as a weak
immersion must have
a treelike decomposition called a tree-cut decomposition of bounded width.
If we consider strong
immersions, then it is easy to see that there are arbitrarily highly edge
connected graphs which do
not contain a fixed clique Kt as a strong immersion. We give a structure
theorem which roughly
characterizes those highly edge connected graphs which do not contain Kt as
a strong immersion.
Algorithmica, 68(1):41-61, 2014
(with:
Marek Cygan,
Marcin Pilipczuk,
Michal Pilipczuk,
Ildikó Schlotter)
Conference version:
37th International Workshop on Graph-Theoretic Concepts in Computer Science (WG
2011), 131-142, Lecture Notes in Comput. Sci., 6986, Springer, Berlin, 2011.
(with:
Marek Cygan,
Marcin Pilipczuk,
Michal Pilipczuk,
Ildikó Schlotter)
We study a family of problems where the goal is to
make a graph
Eulerian by a minimum number of deletions. We completely classify the
parameterized
complexity of various versions: undirected or directed graphs, vertex or
edge deletions, with or without the requirement of connectivity, etc. Of
particular
interest is a randomized FPT algorithm for making an undirected graph
Eulerian
by deleting the minimum number of edges.
Journal of the ACM, 60(6):42, 2013.
Conference version:
In Proceedings of the 42nd ACM Symposium on Theory of Computing (STOC 2010),
735-744.
An important question in the study of constraint satisfaction problems (CSP)
is understanding how the graph or hypergraph describing the incidence
structure of the constraints influences the complexity of the problem. For
binary CSP instances (i.e., where each constraint involves only two
variables), the situation is well understood: the complexity of the problem
essentially depends on the treewidth of the graph of the constraints.
However, this is not the correct answer if constraints with unbounded number
of variables are allowed, and in particular, for CSP instances arising from
query evaluation problems in database theory. Formally, if H is a class of
hypergraphs, then let CSP(H) be CSP restricted to instances whose hypergraph
is in H. Our goal is to characterize those classes of hypergraphs for which
CSP(H) is polynomial-time solvable or fixed-parameter tractable,
parameterized by the number of variables. Note that in the applications
related to database query evaluation, we usually assume that the number of
variables is much smaller than the size of the instance, thus
parameterization by the number of variables is a meaningful question.
The most general known property of H that makes CSP(H) polynomial-time
solvable is bounded fractional hypertree width. Here we introduce a new
hypergraph measure called submodular width, and show that bounded submodular
width of H implies that CSP(H) is fixed-parameter tractable. In a matching
hardness result, we show that if H has unbounded submodular width, then
CSP(H) is not fixed-parameter tractable, unless the Exponential Time
Hypothesis fails.
SIAM Journal on Computing, 42(4):1737-1767, 2013.
(with: Albert
Atserias,
Martin Grohe)
Conference version:
In Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer
Science (FOCS 2008), 739-748, 2008.
(with:
Albert
Atserias,
Martin Grohe)
Relational joins are at the core of relational algebra, which in turn is the
core of the standard database query language SQL. As their evaluation is
expensive and very often dominated by the output size, it is an important
task for database query optimisers to compute estimates on the size of joins
and to find good execution plans for sequences of joins. We study these
problems from a theoretical perspective, both in the worst-case model, and
in an average-case model where the database is chosen according to a known
probability distribution. In the former case, our first key observation is
that the worst-case size of a query is characterised by the fractional edge
cover number of its underlying hypergraph, a combinatorial parameter
previously known to provide an upper bound. We complete the picture by
proving a matching lower bound, and by showing that there exist queries for
which the join-project plan suggested by the fractional edge cover approach
may be substantially better than any join plan that does not use
intermediate projections.
On the other hand, we show that in the average-case model, every
join-project plan can be turned into a plan containing no projections in
such a way that the expected time to evaluate the plan increases only by a
constant factor independent of the size of the database. Not surprisingly,
the key combinatorial parameter in this context is the maximum density of
the underlying hypergraph. We show how to make effective use of this
parameter to eliminate the projections.
SIAM Journal on Computing, 42(4):1674-1696, 2013.
(with: Rajesh Chitnis and
MohammadTaghi Hajiaghayi)
Conference version:
In Proceedings of the 23rd ACM-SIAM Symposium on Discrete Algorithms (SODA
2012), 1713-1725, 2012.
(with:
Rajesh Chitnis and
MohammadTaghi Hajiaghayi)
Given a directed graph G, a set of k terminals and an integer
p, the DIRECTED VERTEX MULTIWAY CUT problem asks if there
is a set S of at most p (nonterminal) vertices whose removal
disconnects each
terminal from all other terminals. DIRECTED EDGE MULTIWAY CUT
is the analogous problem where S is a set of at most p
edges. These two problems indeed are known to be equivalent. A
natural generalization of the multiway cut is the multicut
problem, in which we want to disconnect only a set of k given
pairs instead of all
pairs.
Marx (Theor. Comp. Sci. 2006) showed that in undirected graphs
multiway cut is fixed-parameter tractable (FPT) parameterized by
p. Marx and Razgon (STOC 2011) showed that undirected multicut is
FPT and directed multicut is W[1]-hard parameterized by $. We
complete the picture here by our main result which is that both
DIRECTED VERTEX MULTIWAY CUT and DIRECTED EDGE MULTIWAY CUT
can be solved in time
22O(p)nO(1), i.e.,
FPT parameterized by size p of the cutset of the solution. This
answers an open question raised by Marx (Theor. Comp. Sci. 2006) and Marx
and Razgon (STOC
2011). It follows from our result that DIRECTED MULTICUT is FPT
for the case of k=2 terminal pairs, which answers another open
problem raised in Marx and Razgon (STOC 2011).
ACM Transactions on Algorithms, 9(4):30, 2013.
(with:
Barry O'Sullivan,
Igor Razgon)
Conference version:
27th International Symposium on Theoretical Aspects of Computer Science
(STACS 2010), 561-572, 2010.
(with:
Barry O'Sullivan,
Igor Razgon)
We present a method for reducing the treewidth of a graph while
preserving all of its minimal
s-
t separators up to a certain fixed size
k. This technique allows us to solve
s-
t CUT and
MULTICUT problems with various additional restrictions (e.g., the
vertices being removed from the graph form an independent set or induce a
connected graph) in linear time for every fixed number
k of removed
vertices.
Our results have applications for problems that are not directly
defined by separators, but the known solution methods depend on some
variant of separation. For example, we can solve similarly restricted
generalizations of BIPARTIZATION (delete at most k vertices from
G to make it bipartite) in almost linear time for every fixed number
k
of removed vertices.These results answer a number of open questions in the
area of parameterized complexity. Furthermore, our technique turns out to
be relevant for (H,C,k)- and (H,C,≤k)-coloring problems as well, which are
cardinality constrained variants of the classical H-coloring problem. We
make progress in the classification of the parameterized complexity of
these problems by identifying new cases that can be solved in almost linear
time for every fixed cardinality bound.
Algorithmica, 65(2):275-316, 2013.
(with: Ildikó
Schlotter)
We investigate a special case of the INDUCED SUBGRAPH ISOMORPHISM
problem,
where both input graphs are interval graphs. We show the NP-hardness of this
problem,
and we prove fixed-parameter tractability of the problem with non-standard
parameterization,
where the parameter is the difference
|V(G)|-|V(H)|, with G and H
being the
larger and the smaller input graph, respectively.
Intuitively, we can interpret this problem as ``cleaning'' the graph
G,
regarded as a pattern containing
extra vertices indicating errors, in order to obtain the graph H
representing the original pattern.
We also prove W[1]-hardness for the standard parameterization where the
parameter is |V(H)|.
Information and Computation, 222:278-292, 2013.
(with: Daniel
Lokshtanov)
Conference version:
38th International Colloquium on Automata, Languages and Programming (ICALP
2011), 785-797, Lecture Notes in Comput. Sci., 6755, Springer, 2011.
(with:
Daniel
Lokshtanov)
We study a family of graph clustering problems where each cluster has to
satisfy a certain local requirement. Formally, let μ be a
function on the subsets of vertices of a graph G. In the
(μ,p,q)-PARTITION problem, the task is to find a partition of the
vertices into clusters where each cluster C satisfies the requirements
that (1)
at most q edges leave C and (2) μ(C)≤p. Our first result
shows that if μ is an arbitrary polynomial-time computable
monotone function, then (μ,p,q)-PARTITION can be solved in time
nO(q), i.e., it is polynomial-time solvable
for every fixed q. We study in detail three concrete functions
μ
(number of nonedges in the cluster, maximum number of non-neighbours a
vertex has in the cluster, the number of vertices in the cluster), which
correspond to
natural clustering problems. For these functions, we show
that (μ,p,q)-PARTITION can be solved in time
2O(p) nO(1) and
in randomized time 2O(q) nO(1), i.e., the problem is
fixed-parameter tractable parameterized by p or by q.
Journal of Computer and System Sciences, 79(1):144-151, 2013.
Conference version:
In Proceedings of the 25th Annual IEEE Conference on Computational Complexity,
Cambridge, Massachusetts, 181-187, 2010.
We prove that weighted monotone/antimonotone circuit satisfiability
has no fixed-parameter tractable approximation algorithm with any approximation ratio function
ρ, unless FPT≠W[1]. In particular, not having such an fpt-approximation algorithm
implies that these problems have no polynomial-time
approximation algorithms with ratio ρ(OPT) for any nontrivial
function ρ.
Journal of Computer and System Sciences, 79(1):39-49, 2013.
(with: Klaus
Jansen, Stefan
Kratsch, Ildikó Schlotter)
Conference version:
12th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2010),
260-271, Lecture Notes in Comput. Sci., 6139, Springer, Berlin, 2010.
(with:
Klaus
Jansen,
Stefan
Kratsch,
Ildikó Schlotter)
As Bin Packing is NP-hard already for k=2 bins, it is
unlikely to be solvable in polynomial time even if the number of
bins is a fixed constant. However, if the sizes of the items are
polynomially bounded integers, then the problem can be solved
in time nO(k) for an input of length
n by dynamic programming.
We show, by proving the W[1]-hardness of Unary Bin Packing
(where the sizes are given in unary encoding),
that this running time cannot be improved to f(k)
nO(1)
for any function f(k) (under standard complexity assumptions).
On the other hand, we provide an algorithm for Bin Packing
that obtains in time 2O(k log2
k)+O(n) a solution with
additive error at most 1, i.e., either finds a packing into~k+1
bins or decides that k bins do not suffice.
Information Processing Letters, 113(22-24):906-912, 2013.
(with: Sylvain
Guillemot)
Conference version:
8th International Symposium on Parameterized and Exact Computation (IPEC
2013), 177-188, Lecture Notes in Comput. Sci., vol.
8246, Springer, 2013.
(with:
Sylvain
Guillemot)
The BIPARTITE CONTRACTION problem is to decide, given a graph G
and a parameter k, whether we can can obtain a bipartite graph from
G
by at most k edge contractions. The fixed-parameter tractability of the
problem was shown by Heggernes et al., with an algorithm
whose running time has double-exponential dependence on k. We present a
new randomized FPT algorithm for the problem, which is both conceptually
simpler and achieves an improved 2O(k2) running time, i.e.,
avoiding the double-exponential dependence on k. The algorithm can be
derandomized using standard techniques.
Journal of Artificial Intelligence Research, 45:47-78, 2012.
(with:
David Cohen,
Martin
Cooper,
Páidí Creed,
András Z. Salamon)
The constraint satisfaction problem (CSP) is a general problem
central to computer science and artificial intelligence. Although the
CSP is NP-hard in general, considerable effort has been spent on
identifying tractable subclasses. The main two approaches consider
structural properties (restrictions on the hypergraph of
constraint scopes) and
relational properties (restrictions on
the language of constraint relations). Recently, some authors have
considered
hybrid properties that restrict the constraint
hypergraph and the relations simultaneously.
Our key contribution is the novel concept of a CSP pattern and
classes of problems defined by forbidden patterns (which can be
viewed as forbidding generic sub-problems). We describe the
theoretical framework which can be used to reason about classes of
problems defined by forbidden patterns. We show that this framework
generalises certain known hybrid tractable classes.
Although we are not close to obtaining a complete characterisation
concerning the tractability of general forbidden patterns, we prove a
dichotomy in a special case: classes of problems that arise when we
can only forbid binary negative patterns (generic sub-problems in
which only disallowed tuples are specified). In this case we show
that all (finite sets of) forbidden patterns define either
polynomial-time solvable or NP-complete classes of instances.
ACM Transactions on Algorithms, 8(2):19, 2012.
(with: Andrei Krokhin)
Conference version:
35rd International Colloquium on
Automata, Languages and Programming (ICALP 2008),
662-673, Lecture Notes in Comput. Sci., 5125, Springer, Berlin, 2008.
(with:
Andrei Krokhin)
We study the complexity of local search for the Boolean constraint
satisfaction problem (CSP), in the following form: given a CSP
instance, that is, a collection of constraints, and a solution to
it, the question is whether there is a better (lighter, i.e., having
strictly less Hamming weight) solution
within a given distance from the initial solution. We classify the
complexity, both classical and parameterized, of such problems by a
Schaefer-style dichotomy result, that is, with a restricted set of
allowed types of constraints. Our results show that there is a
considerable amount of such problems that are NP-hard, but
fixed-parameter tractable when parameterized by the distance.
Journal of Computer and System Sciences, 78(2):638-650, 2012.
(with: Andrei Bulatov,
Víctor Dalmau,
Martin Grohe)
Conference version:
26th International Symposium on Theoretical Aspects of Computer Science
(STACS 2009), 231-242, 2009.
(with:
Andrei Bulatov,
Víctor Dalmau,
Martin Grohe)
The homomorphism problem for relational structures is an abstract way of
formulating constraint satisfaction problems (CSP) and various problems in
database theory. The decision version of the homomorphism problem received
a lot of attention in literature; in particular, the way the
graph-theoretical structure of the variables and constraints influences the
complexity of the problem is intensively studied. Here we study the
problem of
enumerating all the solutions with polynomial delay from a similar point of
view. It turns out that the enumeration problem behaves very differently
from the decision version. We give evidence that it is unlikely that a
characterization result similar to the decision version can be obtained.
Nevertheless, we show nontrivial cases where enumeration can be done with
polynomial delay.
Algorithmica, 62(3-4):807-822, 2012.
(with: Ildikó
Schlotter)
Conference version:
33rd International Workshop on Graph-Theoretic Concepts in Computer Science
(WG 2007),
292-303, Lecture Notes in Comput. Sci., 4769, Springer, Berlin,
2007.
(with:
Ildikó
Schlotter)
In the Planar + k vertex problem the task is to find at
most k vertices whose deletion makes the given graph planar. The graphs
for which there exists a solution form a minor closed class of graphs, hence
by the deep results of Robertson and Seymour, there is an
O(n3)
time algorithm for every fixed value of k. However, the proof is extremely
complicated and the constants hidden by the big-O notation are huge.
Here we give a much simpler algorithm for this problem with quadratic
running time, by iteratively reducing the input graph and then applying
techniques for graphs of bounded treewidth.
Journal of the ACM, 58(5):21, 2011.
(with: MohammadHossein Bateni,
MohammadTaghi Hajiaghayi)
Conference version:
In Proceedings of the 42nd ACM Symposium on Theory of Computing (STOC 2010),
211-220.
(with:
MohammadHossein Bateni,
MohammadTaghi Hajiaghayi)
We give the first polynomial-time approximation scheme (PTAS) for the
Steiner forest problem on planar graphs and, more generally, on graphs of
bounded genus. As a first step, we show how to build a Steiner forest
spanner for such graphs. The crux of the process is a clustering procedure
called prize-collecting clustering that breaks down the input instance into
separate subinstances which are easier to handle; moreover, the terminals in
different subinstances are far from each other. Each subinstance has a
relatively inexpensive Steiner tree connecting all its terminals, and the
subinstances can be solved (almost) separately. Another building block is a
PTAS for Steiner forest on graphs of bounded treewidth. Surprisingly,
Steiner forest is NP-hard even on graphs of treewidth 3. Therefore, our PTAS
for bounded treewidth graph needs a nontrivial combination of approximation
arguments and dynamic programming on the tree decomposition. We further show
that Steiner forest can be solved in polynomial time for series-parallel
graphs (graphs of treewidth at most two) by a novel combination of dynamic
programming and minimum cut computations, completing our thorough complexity
study of Steiner forest in the range of bounded treewidth graphs, planar
graphs, and bounded genus graphs.
Bulletin of the EATCS, 84, 41-71, 2011.
(with: Daniel Lokshtanov and
Saket Saurabh)
In this article we survey algorithmic lower bound results that have been
obtained in the field of exact exponential time algorithms and
parameterized complexity under certain assumptions on the running time of
algorithms solving CNF-SAT, namely Exponential time hypothesis (ETH) and
Strong Exponential time hypothesis (SETH).
ACM Transactions on Algorithms, 7(4):43 (2011)
(with: Sergio
Cabello, Panos
Giannopoulos, Christian
Knauer, Günter Rote)
We study the parameterized complexity of the k-center problem on a given
n-pointset P in Rd, with the dimension
d as the parameter. We
show that the rectilinear 3-center problem is fixed-parameter tractable, by
giving an algorithm that runs in O(nlog n) time for any fixed dimension
d. On the other hand, we show that this is unlikely to be the case with
both the Euclidean and rectilinear k-center problems for any
k≥2 and
k≥4 respectively. In particular, we prove that deciding whether
P can
be covered by the union of 2 balls of given radius or by the union of 4
cubes of given side length is W[1]-hard with respect to d, and thus not
fixed-parameter tractable unless FPT=W[1]. For the Euclidean case we also
show that even an no(d)-time algorithm does not exist, unless there is a
2o(n)-time algorithm for n-variable 3SAT, i.e., the Exponential Time
Hypothesis fails.
SIAM J. Discrete Math., 25(2): 631-644, 2011
(with: Noga Alon)
We consider the problem of partitioning the vertices of an
n-vertex graph with maximum degree d into k classes
V1,
..., Vk of size at most n/k in a way that
minimizes the number of pairs (i,j) for which there is an edge
between
Vi and
Vj. We show that there is always such a
partition with O(k2-2/d) adjacent pairs and this bound is
tight. This problem is related to questions about the depth of
certain graph embeddings, which have been used in the study of the
complexity of subgraph and constraint satisfaction problems.
Theor. Comput. Sci., 412(29): 3487-3500, 2011.
A k-clique-coloring of a graph G is an assignment of
k colors to
the vertices of G such that every maximal (i.e., not extendable)
clique of G contains two vertices with different colors. We show
that deciding whether a graph has a k-clique-coloring is
Σ2p?-complete for every k≥ 2. The complexity of two related
problems are also considered. A graph is k-clique-choosable, if for
every k-list-assignment, one can select a clique coloring from these
lists. This problem turns out to be Π3p-complete for every
k≥
2. A graph G is hereditarty k-clique-colorable if every induced
subgraph of G is k-clique-colorable. We prove that deciding
hereditary k-clique-colorability is also
Π3p-complete for every
k≥ 3.
J. Artif. Intell. Res. (JAIR),, 41:97-130, 2011
(with: Emmanuel Hebrard,
Barry O'Sullivan,
Igor Razgon)
Conference version:
15th International Conference on
Principles and Practice of Constraint Programming (CP 2009), 424-438,
Lecture Notes in Comput. Sci., 5732, Springer, Berlin, 2009.
(with:
Emmanuel Hebrard,
Barry O'Sullivan,
Igor Razgon)
Many combinatorial problems encountered in practice involve constraints that
require that a set of variables take distinct or equal values.The
ALLDIFFERENT
constraint, in particular, ensures that all variables take distinct values.
Two soft variants of this constraint were proposed in [4],
defined either with respect to a so-called variable or
graph-based cost function. When requiring similarity, as opposed to
diversity, one can consider the dual definition either for the cost or for
the basic constraint itself, that is, ALLEQUAL in our case. Six cost
functions can be defined by exploring every combinations of these
definitions. It is therefore natural to study the complexity of achieving
Arc Consistency and Bound Consistency on them. From our earlier
work on this topic an open problem remained, namely achieving bounds
consistency on the maximisation of the SOFTALLDIFF constraint when considering
the graph-based cost.In this paper we resolve this problem. Therefore, we
give a complete taxonomy of constraints of equality and difference, based on
the alternative objective functions used for the soft variants.
J. Comb. Theory, Ser. B 101(5): 378-381, 2011
(with:
Naonori
Kakimura and
Ken-ichi
Kawarabayashi)
The well-known theorem of Erdös and Pósa says that a graph G has either
k
vertex-disjoint
cycles or a vertex set X of order at most f(k) such that
G\X is a forest.
Starting with this result,
there are many results concerning packing and covering cycles in graph
theory and combinatorial
optimization.
In this paper, we generalize Erdös-Pósa's result to cycles that are
required to go through a set
S of vertices. Given an integer k and a vertex subset S (possibly unbounded
number of vertices)
in a given graph G, we prove that either G has k vertex-disjoint cycles,
each of which contains
at least one vertex of S, or G has a vertex set X of order at most
f(k) =
40k2 log2k such that
G\X has no cycle that intersects S.
Discrete Optimization, 8(1):25-40, 2011.
(with: Ildikó Schlotter)
Conference version:
4nd International Workshop on Parameterized and Exact Computation (IWPEC
2009), 300-311, Lecture Notes in Comput. Sci., 5917, Springer,
Berlin, 2009.
(with:
Ildikó Schlotter)
We study the Hospitals/Residents with Couples problem, a
variant of the classical Stable Marriage problem. This is the extension
of the Hospitals/Residents problem where residents are allowed to form
pairs and submit joint rankings over hospitals. We use the framework of
parameterized complexity, considering the number of couples as a param-
eter. We also apply a local search approach, and examine the possibili-
ties for giving FPT algorithms applicable in this context. Furthermore,
we also investigate the matching problem containing couples that is the
simplied version of the Hospitals/Residents problem modeling the case
when no preferences are given.
Theory of Computing Systems, 48:444-464, 2011.
Conference version:
26th International Symposium on Theoretical Aspects of Computer Science
(STACS 2009), 649-660, 2009.
The way the graph structure of the constraints influences the
complexity of constraint satisfaction problems (CSP) is well
understood for bounded-arity constraints. The situation is less
clear if there is no bound on the arities. In this case the answer
depends also on how the constraints are represented in the input.
We study this question for the truth table representation of
constraints. We introduce a new hypergraph measure adaptive
width and show that CSP with truth tables is polynomial-time
solvable if restricted to a class of hypergraphs with bounded
adaptive width. Conversely,
assuming a conjecture on the complexity of binary CSP,
there is no other polynomial-time solvable case.
Theory of Computing, 6(1):85-112, 2010.
Conference version:
In Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer
Science (FOCS 2007), 169-179, 2007.
It is well-known that constraint satisfaction problems (CSP) can be
solved in time nO(k) if the treewidth of the primal graph of
the instance is at
most k. We show that no algorithm can be significantly better than
this treewidth-based algorithm, even if we restrict the problem
to some special class of primal graphs. Formally, let G
be an arbitrary class of graphs and assume that there is an algorithm
A
solving binary CSP for instances whose primal graph is in G. We
prove that if
the running time of A is
f(G)no(k/log k), where
k is the treewidth of the primal graph G and f is an arbitrary
function, then the Exponential Time Hypothesis fails. We prove the
result also in the more general framework of the homomorphism problem for
bounded-arity relational structures. For this problem, the treewidth of
the core of the left-hand side structure plays the same role as
the treewidth of the primal graph above.
Communications of the ACM, 53(9):99-106, 2010.
(with: Andrei
Bulatov)
In a constraint satisfaction problem (CSP) the goal is to find an assignment
of a given set of variables subject to specified constraints. A global
cardinality constraint is an additional requirement that prescribes how many
variables must be assigned a certain value. We study the complexity of the
problem CCSP(Γ), the CSP with global cardinality constraints that allows
only relations from the set Γ. The main result of this paper characterizes
sets Γ that give rise to problems solvable in polynomial time, and states
that the remaining such problems are NP-complete.
Logical Methods in Computer Science, Vol. 6 (4:4):1-27, 2010.
(with: Andrei
Bulatov)
Conference version:
In Proceedings of the 24th Annual IEEE Symposium on Logic in
Computer Science (LICS 2009), 419-428, 2009.
(with:
Andrei
Bulatov)
In a constraint satisfaction problem (CSP) the goal is to find an
assignment of a given set of variables subject to specified
constraints. A global cardinality constraint is an additional
requirement that prescribes how many variables must be assigned a
certain value. We study the complexity of the problem CCSP(Γ),
the constraint satisfaction problem with global cardinality
constraints that allows only relations from the set Γ. The main
result of this paper characterizes sets Γ that give rise to
problems solvable in polynomial time, and states that the remaining
such problems are NP-complete.
ACM Transactions on Algorithms, 6(2), Article 29, 2010.
Conference version:
In Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete
Algorithms (SODA 2009), 902-911, 2009.
Fractional hypertree width is a hypergraph measure similar to tree
width and hypertree width. Its algorithmic importance comes from the
fact that, as shown in previous work, constraint
satisfaction problems (CSP) and various problems in database theory
are polynomial-time solvable if the input contains a bounded-width
fractional hypertree decomposition of the hypergraph of the
constraints. In this paper, we show that for every w≥1, there
is a polynomial-time algorithm that, given a hypergraph H with
fractional hypertree width at most w, computes a fractional
hypertree decomposition of width O(w3) for
H. This means that
polynomial-time algorithms relying on bounded-width fractional
hypertree decompositions no longer need to be given a decomposition
explicitly in the input, since an appropriate decomposition can be
computed in polynomial time. Therefore, if H is a class of
hypergraphs with bounded fractional hypertree width, then CSP restricted
to instances whose structure is in H is
polynomial-time solvable. This makes bounded fractional hypertree
width the most general known hypergraph property that makes CSP,
Boolean Conjuctive Queries, and Conjunctive Query Containment
polynomial-time solvable.
Algorithmica, 58(1), 170-187, 2010.
(with: Ildikó
Schlotter)
We consider the variant of the classical Stable Marriage problem
where preference lists can be incomplete and may contain ties. In
such a setting, finding a stable matching of maximum size is NP-hard.
We study the parameterized complexity of this problem, where the
parameter can be the number of ties, the maximum or the overall length
of ties. We also investigate the applicability of a local search algorithm
for the problem. Finally, we examine the possibilities for giving an FPT
algorithm or an FPT approximation algorithm for finding an egalitarian
or a minimum regret matching.
International Journal of Computational Geometry and
Applications, 20(2), 147-173, 2010.
(with: Panos
Giannopoulos,
Rolf
Klein,
Christian
Knauer, Martin Kutz)
We prove that computing a geometric minimum-dilation graph on a given set
of points in the plane, using not more than a given number of edges, is an
NP-hard problem, no matter if edge crossings are allowed or forbidden. We
also show that the problem remains NP-hard even when a minimum-dilation
tour or path is sought; not even an FPTAS exists in this case.
Algorithmica, 57(4), 747-768, 2010.
Conference version:
32nd International Workshop on Graph-Theoretic Concepts in Computer Science
(WG 2006),
37-48, Lecture Notes in Comput. Sci., 4271, Springer, Berlin,
2006.
It is known to be NP-hard to decide whether a graph can be made
chordal by the deletion of k vertices. Here we present a uniformly
polynomial-time algorithm for the problem: the running time is
f(k) nc for some constant c not depending on
k and some f depending only on k. For large values of
n, such an
algorithm is much better than
trying all the O(nk) possibilities. Therefore, the chordal
deletion problem parameterized by the number k of vertices to be
deleted is fixed-parameter tractable. This answers an open question
of Cai.
Discrete Applied Mathematics,
157(15):3258-3267, 2009.
(with: Ildikó
Schlotter)
Conference version:
34th International Workshop on Graph-Theoretic Concepts in Computer Science
(WG 2008),
287-289, Lecture Notes in Comput. Sci., 5344, Springer, Berlin,
2008.
(with:
Ildikó
Schlotter)
We investigate the Induced Subgraph Isomorphism problem
with non-standard parametrization, where the parameter is the difference
|V(G)| - |V (H)| with H and G being the smaller and the larger
input graph, respectively. Intuitively, we can interpret this problem as
"cleaning" the graph G, regarded as a pattern containing extra vertices
indicating errors, in order to obtain the graph H representing the original
pattern. We show fixed-parameter tractability of the cases where
both H and G are planar and H is 3-connected, or H is a tree and G is
arbitrary.
Information Processing Letters, 109(20):1161-1166, 2009.
(with: Igor Razgon)
Conference version:
In Proceedings of the 17th European Symposium on Algorithms (ESA 2009),
Lecture Notes in Comput. Sci., 5757, Springer, Berlin, 647-658, 2009.
(with:
Igor Razgon)
The input of the Edge Multicut problem consists of an undirected
graph G and pairs of terminals
{s1,t1},
...,
{sm,tm};
the task is to remove a minimum set of edges such that
si and
ti are disconnected for every 1 ≤ i ≤
m. The parameterized
complexity of the problem, parameterized by the maximum number k
of edges that are allowed to be removed, is currently open. The main
result of the paper is a parameterized 2-approximation algorithm: in
time f(k)nO(1), we can either find a solution of size
2k or correctly conclude that there is no solution of size k.
The proposed algorithm is based on a transformation of the Edge
Multicut problem into a variant of parameterized Max-2-SAT problem,
where the parameter is related to the number of clauses that are
not satisfied. It follows from previous results that the
latter problem can be 2-approximated in a fixed-parameter time; on
the other hand, we show here that it is W[1]-hard. Thus the additional
contribution of the present paper is introducing the first natural
W[1]-hard problem that is constant-ratio fixed-parameter
approximable.
Theoretical Computer Science, 410(44):4471-4479, 2009.
Conference version:
33rd International Colloquium on
Automata, Languages and Programming (ICALP 2006),
656-667, Lecture Notes in Comput. Sci., 4051, Springer, Berlin, 2006.
Matroid theory gives us powerful techniques for understanding
combinatorial optimization problems and for designing polynomial-time
algorithms. However, several natural matroid problems, such as
3-matroid intersection, are NP-hard. Here we investigate these
problems from the parameterized complexity point of view: instead of
the trivial O(nk) time brute force algorithm for finding a
k-element solution, we try to give algorithms with uniformly polynomial
(i.e., f(k) nO(1)) running time. The main result is that if
the ground set of a represented matroid is partitioned into blocks of
size l, then we can determine in f(k,l) nO(1)
randomized time whether there is an independent set that is the union
of k blocks. As consequence, algorithms with similar running time
are obtained for other problems such as finding a k-set
in the intersection of l matroids, or finding k terminals in a
network such
that each of them can be connected simultaneously to the source by
l
disjoint
paths.
Discrete Applied Mathematics, 157(5):1034-1045, 2009.
In the minimum sum edge coloring problem we have to assign positive
integers to the edges of a graph such that adjacent edges receive
different integers and the sum of the assigned numbers is minimal.
We show that the problem is (a) NP-hard for planar bipartite graphs
with maximum degree 3, (b) NP-hard for 3-regular planar graphs,
(c) NP-hard for partial 2-trees, and
(d) APX-hard for bipartite graphs.
Journal of Combinatorial Theory Ser. B, 99(1):218-228, 2009
(with: Martin
Grohe)
A bramble in a graph G is a family of connected subgraphs of G
such that any two of these subgraphs have a nonempty intersection or are
joined by an edge. The order of a bramble is the least number of
vertices required to cover every subgraph in the bramble. Seymour and
Thomas proved that the maximum order of a bramble in a graph
is precisely the tree width of the graph plus one. We prove that every
graph of tree width at least k has a bramble of order
Ω(k1/2/log2k) and size polynomial in
n and k, and that for
every k there is a graph G of tree width Ω(k) such that every
bramble of G of order k1/2+ε has size exponential in
n. To
prove the lower bound, we establish a close connection between linear tree
width and vertex expansion. For the upper bound, we use the connections
between tree width, separators, and concurrent flows.
Discrete Applied Mathematics, 157(1):13-18, 2009
(with: Marcus
Schaefer)
A coloring of a graph is nonrepetitive if the graph contains
no path that has a color pattern of the form xx (where x is a sequence
of colors). We show that determining whether a particular coloring
of a graph is nonrepetitive is coNP-hard, even if the number of colors
is limited to four. The problem becomes fixed-parameter tractable, if
we only exclude colorings xx up to a fixed length k of
x.
SIAM Journal on Computing, 38(4):1382-1410, 2008.
Conference version:
In Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer
Science (FOCS 2005), 63-72, 2005.
We study two pattern matching problems that
are motivated by applications in computational biology.
In the CLOSEST SUBSTRING problem k strings s1,
..., sk are given, and the task is to find a string
s of
length L such that each string si has a consecutive substring
of length L whose distance is at most d from s.
We present
two algorithms that can be efficient for small fixed values of d
and k: for some functions f and g, the algorithms have running
time f(d) nO(log d) and
g(d,k) n^O(loglog k),
respectively. The second algorithm is based on connections with the
extremal combinatorics of hypergraphs.
The CLOSEST SUBSTRING problem is also investigated from the parameterized
complexity point of view. Answering an open question, we show that the
problem is W[1]-hard even if both d and k are parameters. It
follows as a consequence of this hardness result that our algorithms
are optimal in the sense that the exponent of n in the running
time cannot be improved to o(log d) or to o(loglog k)
(modulo some complexity-theoretic assumptions).
CONSENSUS PATTERNS is the variant of the problem where,
instead of the requirement that each si has a substring that is of
distance at most d from
s, we have to select the substrings in such a way that the average
of these k distances is at most δ. By giving an
f(δ)n9 time algorithm, we show that the problem is
fixed-parameter tractable.
Theoretical Computer Science, 401:62-76, 2008.
Given a list L(v) for each vertex v, we say that the graph
G is
L-colorable if there is a proper vertex coloring of G where each
vertex v takes its color from L(v). The graph is uniquely k-list
colorable if there is a list assignment L such that
|L(v)|=k for every
vertex v and the graph has exactly one L-coloring with these lists.
Mahdian and Mahmoodian gave a polynomial-time
characterization of uniquely 2-list colorable graphs. Answering an open
question, we show that uniquely
3-list colorable graphs are unlikely to have such a nice
characterization, since recognizing these graphs is
Σ2p-complete.
Operations Research Letters, 36(1):31-36, 2008.
We show that searching the k-change
neighborhood is W[1]-hard for metric TSP, which means that finding
the best tour in the k-change neighborhood essentially requires
complete search (modulo some complexity-theoretic assumptions).
The Computer Journal, 51(1):60-78, 2008.
Approximation algorithms and parameterized complexity are usually
considered to be two separate ways of dealing with hard algorithmic
problems. In
this paper, our aim is to investigate how these two fields can be
combined to achieve better algorithms than any of the two theories
could offer. We discuss the different ways parameterized
complexity can be extended to approximation algorithms, survey
results of this type, and propose directions for future research.
Theoretical Computer Science, 361(2-3):133-149, 2006
Conference version:
1st
Workshop on Approximation and Online Algorithms (WAOA 2003),
214-226, Lecture Notes in Comput. Sci., 2909, Springer, Berlin, 2004.
[Slides]
The edge multicoloring problem is that given a graph G and integer
demands x(e) for every edge e, assign a set of x(e) colors to
vertex e, such that adjacent edges have disjoint sets of colors.
In the minimum sum edge multicoloring problem the finish
time of an edge is defined to be the highest color assigned to
it. The goal is to minimize the sum of the finish times. The main
result of the paper is a polynomial time approximation scheme for
minimum sum multicoloring the edges of trees.
Discrete Applied Mathematics, 154(6):995-1002, 2006
In the precoloring extension problem we are given a graph with some of
the vertices having a preassigned color and it has to be decided
whether this coloring can be extended to a proper k-coloring of the
graph. Answering an open question of Hujter and Tuza
[Combin. Probab. Comput. 5 (1996) 35-56], we show that the precoloring extension problem is
NP-complete on unit interval graphs.
Computational Complexity, 14(4):308-340, 2006
The sum of a coloring is the sum of the colors assigned
to the vertices (assuming that the colors are the positive
integers). The sum Σ(G) of graph G is the
smallest sum that can be achieved by a proper coloring of
G. The chromatic strength s(G) of G is
the minimum number of colors that is required by a coloring with sum
Σ(G). We determine the complexity of the question 'Is
s(G)≤k?' for every k: it is
coNP-complete for k=2, and
Θ2P-complete for k≥3. We also
study the complexity of the edge coloring version of the problem,
with analogous definitions for the edge sum Σ'(G) and
the chromatic edge strength s'(G). We show that for every
k≥3, it is Θ2P-complete to
decide whether s'(G)≤ k holds. As a first step of the
proof, for every r≥ 3, we present graphs with chromatic
index r and edge strength r+1. Such graphs were
not known before for every r.
Theoretical Computer Science, 351(3):407-424, 2006
Conference version:
1st International Workshop on Parameterized and Exact Computation (IWPEC 2004),
83-95, Lecture Notes in Comput. Sci., 3162, Springer, Berlin, 2004.
[Slides]
In the precoloring extension problem (PrExt) a graph is given with
some of the vertices having a preassigned color and it has to be
decided whether this coloring can be extended to a proper coloring
of the graph with the given number of colors. Two parameterized
versions of the problem are studied in the paper: either the number
of precolored vertices or the number of colors used in the
precoloring is restricted to be at most k. We show that these
problems are polynomial time solvable but W[1]-hard in chordal
graphs. For a graph class F, let F+ke (resp. F+kv) denote
those graphs that can be made to be a member of F by deleting at
most k edges (resp. vertices). We investigate the connection
between PrExt in F and the coloring of F+ke, F+ve graphs.
Answering an open question of Leizhen Cai, we
show that coloring chordal+ke graphs is fixed-parameter tractable.
Theoretical Computer Science, 351(3):394-406, 2006
Conference version:
1st International Workshop on Parameterized and Exact Computation (IWPEC 2004), 71-82, Lecture Notes in Comput. Sci., 3162, Springer, Berlin, 2004.
[Slides]
We consider parameterized problems where some separation property
has to be achieved by deleting as few vertices as possible. The
following five problems are studied: delete k vertices such that
(a) each of the given l terminals is separated from the others,
(b) each of the given l pairs of terminals are separated, (c)
exactly l vertices are cut away from the graph, (d) exactly l connected
vertices are cut away from the graph, (e) the graph is separated
into l components, We show that if both k and l are
parameters, then (a), (b) and (d) are fixed-parameter tractable,
while (c) and (e) are W[1]-hard.
Operations Research Letters, 33(4):382-384, 2005
In the minimum sum coloring problem we have to assign
positive integers to the vertices of a graph in such a way that
neighbors receive different numbers and the sum of the numbers is
minimized. Szkalicki [
SIAM
J. Comput., 29(1):274--287, 1999] has shown that minimum
sum coloring is
NP-hard for interval graphs. Here we present
a simpler proof of this result.
Journal of Graph Theory.
49(4):313-324, 2005
In the edge precoloring extension problem we are given a graph with
some of the edges having a preassigned color and it has to be
decided whether this coloring can be extended to a proper
k-edge-coloring of the graph. In list edge coloring every edge has
a list of available colors, and question is whether there is a
proper edge coloring where every edge receives a color from its list.
We show that both problems are NP-complete on (a) planar, 3-regular
bipartite graphs, (b) bipartite outerplanar graphs, and (c) bipartite
series-parallel graphs. This improves previous results of Easton and
Parker [
Discrete Appl. Math.,113(2-3):167-181, 2001], and Fiala [
J. Graph Theory, 43(2):156-160, 2003].
Computational Complexity, 14(2):153-183, 2005
Conference version:
In Proceedings of 19th Annual IEEE Conference on Computational Complexity,
Amherst, Massachusetts, 139-149, 2004.
[Slides]
[Slides of a longer
talk]
We prove a parameterized analog of Schaefer's Dichotomy
Theorem: we show that for every finite boolean constraint family
F, deciding whether a formula containing constraints from F
has a satisfying assignment of weight exactly k is either
fixed-parameter tractable (FPT) or W[1]-complete. We give a simple
characterization of those constraints that make the problem
fixed-parameter tractable. The special cases when the formula is
restricted to be bounded occurrence, bounded treewidth or planar are
also considered, it turns out that in these cases the problem is in
FPT for every constraint family F.
Periodica Polytechnica Ser. El. Eng. 48(1-2):5-10, 2004.
Discrete Applied Mathematics, 143(1-3):336-341, 2004
We show that the edge disjoint paths problem is
NP-complete in directed or undirected rectangular grids, even if
the union of the supply and the demand graph G+H is Eulerian.
Information Processing Letters, 89(2):85-90, 2004.
Conference version:
3rd Hungarian-Japanese Symposium on Discrete Mathematics and
Its Application, Tokyo, 2002, 164-170
[Slides]
The list edge multicoloring problem is a version of edge coloring
where every edge e has a list of available colors L(e) and an
integer demand x(e). For each e, we have to select x(e)
colors from L(e) such that adjacent edges receive disjoint sets of
colors. Marcotte and Seymour proved a characterization theorem
for list edge multicoloring trees, which can be turned into a
polynomial time algorithm. We present a slightly more general
algorithm that works also on odd cycles. A variant of the method
leads to a randomized polynomial time algorithm for handling even
cycles as well.
-
In Proceedings of the 40th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems
(PODS 2021), 19-29, 2021.
-
In 48th International Colloquium on Automata, Languages, and Programming
(ICALP 2021), 95:1-95:20, 2021.
(with: Govind S. Sankar, Philipp Schepper)
-
In 2nd Symposium on Foundations of Responsible Computing (FORC 2021),
3:1-3:18, 2021.
(with:
Vincent Cohen-Addad, Philip N. Klein, Archer Wheeler, Christopher
Wolfram)
-
In Proceedings of Computational Complexity Conference (CCC 2020),
27:1-27:28, 2020.
(with: Marvin Künneman)
-
In Proceedings of 28th Annual European Symposium on Algorithms (ESA 2020),
71:1-71:19, 2020.
-
In Proceedings of 28th Annual European Symposium on Algorithms (ESA 2020),
72:1-72:25, 2020.
(with: R. B. Sandeep)
-
In Proceedings of 47th International Colloquium on Automata, Languages, and Programming (ICALP
2020), 59:1-59:18, 2020.
(with: Alexander Gök and Matthias Mnich)
-
In Proceedings of the 35th International Symposium on Computational Geometry
(SoCG 2019), 27:1-27:16, 2019.
(with: Vincent
Cohen-Addad,
Éric Colin de Verdière , and
Arnaud de Mesmay)
-
In International Conference on Algorithms and Complexity (CIAC 2019), Lecture Notes in Computer Science
11485,
249-261, 2019.
(with: Alexander
Göke
and
Mathias
Mnich)
-
In Proceedings of Foundations of Software Technology and Theoretical Computer Science (FSTTCS
2019), 8:1-8:20, 2019.
(with: Akanksha Agrawal, Arindam Biswas, Édouard Bonnet, Nick Brettell, Radu Curticapean,
Tillmann Miltzow, Venkatesh Raman, Saket Saurabh)
-
In Proceedings of 30th International Symposium on Algorithms and Computation (ISAAC
2019), 36:1-36:18, 2019.
(with: Sándor Kisfaludi-Ba andTom C. van der Zanden)
-
In proceedings of the 59th IEEE Annual Symposium on Foundations of Computer Science
(FOCS 2018), 474-484, 2018.
(with: Marcin Pilipczuk
and
Michal
Pilipczuk)
-
In proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms
(SODA 2018), 2801-2820, 2018.
(with:
Lin Chen)
-
In 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018),
27:1-27:15, 2018.
(with:
László Egri and
Pawel Rzazewski)
-
In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing
(STOC 2017), 210-223, 2017.
(with:Radu
Curticapean,
Holger Dell)
-
In 25th Annual European Symposium on Algorithms (ESA 2017), 59:1-59:15,
2017.
(with: Marcin
Pilipczuk)
-
34th Symposium on Theoretical Aspects of Computer Science (STACS 2017),
22:1-22:14, 2017.
(with:
Lin Chen,
Deshi Ye, and
Guochuan Zhang)
-
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
(APPROX/RANDOM 2016), 16:1-16:54, 2016.
(with:
Ario Salmasi and
Anastasios
Sidiropoulos)
-
4th Annual European Symposium on Algorithms (ESA 2016), 18:1-18:18,
2016.
(with:
Édouard Bonnet
and
László Egri)
-
In Proceedings of the 57th Annual Symposium on Foundations of Computer Science
(FOCS 2016), 515-524, 2016.
(with:
Fedor Fomin,
Daniel Lokshtanov,
Marcin Pilipczuk,
Michal Pilipczuk, and
Saket Saurabh)
-
43rd International Colloquium on Automata, Languages, and Programming (ICALP
2016), 27:1-27:14, 2016.
(with:
Andreas Feldmann)
-
43rd International Colloquium on Automata, Languages, and Programming (ICALP
2016), 28:1-28:15, 2016.
(with:
Valia Mitsou)
-
42nd International Workshop on Graph-Theoretic Concepts in Computer Science (WG
2016), 233-244, 2016.
(with:
Édouard Bonnet,
Nick Brettell,
and
O-joung Kwon)
-
In Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of
Computing (STOC 2016), 570-583, 2016.
(with: MohammadHossein Bateni,
Erik Demaine, and MohammadTaghi Hajiaghayi)
We present the first polynomial-time approximation scheme
(PTAS), i.e., (1+ε)-approximation algorithm for any constant
ε> 0, for the planar group Steiner tree problem (in which each
group lies on a boundary of a face). This result improves on the best
previous approximation factor of
O(log
n
(loglog
n)
O(1)). We achieve this result via a novel
and powerful technique called
spanner bootstrapping, which allows
one to bootstrap from a superconstant approximation factor (even
superpolynomial in the input size) all the way down to a PTAS. This is in
contrast with the popular existing approach for planar PTASs of constructing
light-weight spanners in one iteration, which notably requires a
constant-factor approximate solution to start from. Spanner bootstrapping
removes one of the main barriers for designing PTASs for problems which have
no known constant-factor approximation (even on planar graphs), and thus can
be used to obtain PTASs for several difficult-to-approximate problems.
Our second major contribution required for the planar group Steiner
tree PTAS is a spanner construction, which reduces the graph to have total
weight within a factor of the optimal solution while approximately
preserving the optimal solution. This is particularly challenging because
group Steiner tree requires deciding which terminal in each group to connect
by the tree, making it much harder than recent previous approaches to
construct spanners for planar TSP by Klein [SIAM J. Computing
2008], subset TSP by Klein [STOC 2006], Steiner tree by Borradaile,
Klein, and Mathieu [ACM Trans. Algorithms 2009], and Steiner forest
by Bateni, Hajiaghayi, and Marx [J. ACM 2011] (and its improvement
to an efficient PTAS by Eisenstat, Klein, and Mathieu [SODA 2012]. The
main conceptual contribution here is realizing that selecting which
terminals may be relevant is essentially a complicated prize-collecting
process: we have to carefully weigh the cost and benefits of reaching or
avoiding certain terminals in the spanner. Via a sequence of involved
prize-collecting procedures, we can construct a spanner that reaches a set
of terminals that is sufficient for an almost-optimal solution.
Our
PTAS for planar group Steiner tree implies the first PTAS for geometric
Euclidean group Steiner tree with obstacles, as well as a (2+)-approximation
algorithm for group TSP with obstacles, improving over the best previous
constant-factor approximation algorithms. By contrast, we show that planar
group Steiner forest, a slight generalization of planar group Steiner tree,
is APX-hard on planar graphs of treewidth 3, even if the groups are pairwise
disjoint and every group is a vertex or an edge.
-
In Proceedings of the 27th
Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2016), 1650-1669,
2016.
(with: Radu
Curticapean)
By now, we have a good understanding of how NP-hard problems become easier
on graphs of bounded treewidth and bounded cliquewidth: for various
problems, matching upper bounds and conditional lower bounds describe
exactly how the running time has to depend on treewidth or cliquewidth. In
particular, Fomin et al. (2009, 2010) have shown a significant difference
between these two parameters: assuming the Exponential-Time Hypothesis
(ETH), the optimal algorithms for problems such as M
ax
C
ut and E
dge D
ominating S
et have
running time
2
O(t)nO(1)
when parameterized by treewidth, but
nO(t) when parameterized by
cliquewidth.
In this paper, we show that a similar phenomenon occurs
also for counting problems. Specifically, we prove that, assuming the
counting version of the Strong Exponential-Time Hypothesis (#SETH), the
problem of counting perfect matchings
• has no (2 ---
ε)knO(1) time algorithm for any
ε > 0 on graphs of treewidth k (but it is known to be
solvable in time 2knO(1) if a tree
decomposition of width k is given), and
• has no
O(n(1-ε)k) time algorithm for any
ε > 0 on graphs of cliquewidth k (but it can be solved in
time O(nk+1) if a k-expression is
given).
A celebrated result of Fisher, Kasteleyn, and Temperley from
the 1960s shows that counting perfect matchings in planar graphs is
polynomial-time solvable. This was later extended by Gallucio and Loebl
(1999), Tesler (2000) and Regge and Zechina (2000) who gave
4k · nO(1) time
algorithms for graphs of genus k. We show that the dependence on the
genus k has to be exponential: assuming #ETH, the counting version of
ETH, there is no 2O(k) ·
nO(1) time algorithm for the problem on graphs
of genus k.
-
In Proceedings of the 32nd International Symposium on Computational Geometry
(SoCG 2016), 52:1-52:16, 2016.
(with: Tillmann Miltzow)
Given a set of n points S in the plane, a triangulation
T of S is a maximal
set of non-crossing segments with endpoints in S. We present an algorithm
that computes the number of triangulations on a given set of n points in
time n(11+ o(1)) √n, significantly improving the previous best
running time of O(2n n2) by Alvarez and Seidel [SoCG 2013]. Our main tool
is identifying separators of size O(√n) of a triangulation in a
canonical way. The definition of the separators are based on the
decomposition of the triangulation into nested layers ("cactus graphs").
Based on the above algorithm, we develop a simple and formal framework to
count other non-crossing straight-line graphs in nO(√n) time. We
demonstrate the usefulness of the framework by applying it to counting
non-crossing Hamilton cycles, spanning trees, perfect matchings, 3-colorable
triangulations, connected graphs, cycle decompositions, quadrangulations,
3-regular graphs, and more.
-
In Proceedings of the 26th ACM-SIAM Symposium on Discrete Algorithms (SODA
2015), 642-661,2015.
(with: Paul
Wollan)
We study the following general disjoint paths problem: given a supply graph
G, terminals T, a demand graph H on the vertices
T,
and an integer k, we seek to find a set of k pairwise vertex-disjoint
valid paths, where we say that a path of the supply graph G is valid if
its endpoints are in T and adjacent in the demand graph H. We study the
fixed-parameter tractability of this family of problems, parameterized by
k, when H is assumed to belong in a fixed hereditary class
H. Our main result is a complete characterization of the
fixed-parameter tractable cases. We show that if H does not
contain every matching and does not contain every skew biclique, then the
H-disjoint paths problem is FPT for H in H, and otherwise the
problem is W[1]-hard.
-
In Proceedings of the 26th ACM-SIAM Symposium on Discrete Algorithms (SODA
2015), 616-629, 2015.
(with: Bart M. P.
Jansen)
We study two fundamental problems related to finding subgraphs: given graphs
G and H, test whether H is isomorphic to a subgraph of
G, or determine the
maximum number of vertex-disjoint H-subgraphs that can be packed in
G. We
investigate these problems when the graph H belongs to a fixed hereditary
family F. Our goal is to study which classes F make the two problems
tractable in one of the following senses: (a) (randomized) polynomial-time
solvable, (b) admits a polynomial (many-one) kernel, or (c) admits a
polynomial Turing kernel.
-
In Proceedings of the 23rd European Symposium on Algorithms (ESA 2015),
Lecture Notes in Computer Science Volume 9294, Springer, 865-877,
2015.
(with: Michal
Pilipczuk)
We study a general family of facility location problems defined on
planar graphs and on the 2-dimensional plane. In these problems, a
subset of k objects has to be selected, satisfying certain packing
(disjointness) and covering constraints. Our main result is showing
that, for each of these problems, the nO(k) time brute force
algorithm of selecting k objects can be improved to
nO(√k) time. The algorithm is based on focusing on the Voronoi
diagram of a hypothetical solution of k objects; this idea was
introduced recently in the design of geometric QPTASs, but was not yet
used for exact algorithms and for planar graphs. As concrete consequences of
our main result, we obtain nO(√k) time algorithms for the
following problems:
d-SCATTERED SET in planar graphs (find $ vertices at pairwise distance
d);
d-DOMINATING SET/(k,d)-CENTER in planar graphs (find $ vertices such that every
vertex is at distance at most $ from these vertices); select k pairwise
disjoint connected vertex sets from a given collection; select k pairwise
disjoint disks in the plane (of possibly different radii) from a given
collection; cover a set of points in the plane by selecting k
disks/axis-parallel squares from a given collection. We complement these
positive results with lower bounds suggesting that some similar, but
slightly more general problems (such as covering points with axis-parallel
rectangles)
do not admit nO(√k) time algorithms.
-
In Proceedings of the 55th Annual Symposium on Foundations of Computer
Science (FOCS 2014), 130-139, 2014.
(with: Radu Curticapean)
For a class C of graphs, #Sub(C) is the counting problem
that, given a graph H from C and an arbitrary graph G, asks for
the number of subgraphs of G isomorphic to H. It is
known that if C has bounded vertex-cover number (equivalently,
the size of the maximum matching in C is bounded), then #Sub(C) is
polynomial-time solvable. We complement this result with a corresponding
lower bound: if C is any recursively enumerable class of
graphs with unbounded vertex-cover number, then #Sub(C) is
#W[1]-hard parameterized by the size of H and hence not
polynomial-time solvable and not even fixed-parameter tractable,
unless FPT is equal to #W[1].
As a first step of the proof, we show that counting k-matchings in
bipartite graphs is #W[1]-hard. Recently, Curticapean [ICALP 2013]
proved the #W[1]-hardness of counting k-matchings in general graphs; our
result strengthens
this statement to bipartite graphs with a considerably simpler proof
and even shows that, assuming the
Exponential Time Hypothesis (ETH), there is no
f(k)no(k/log k)
time algorithm for counting k-matchings in bipartite graphs for
any computable function f. As a consequence, we obtain an
independent and somewhat simpler proof of the classical result of
Flum and Grohe [SICOMP 2004] stating that counting
paths of length k is #W[1]-hard, as well as a similar
almost-tight ETH-based lower bound on the exponent.
-
In Proceedings of the 25th ACM-SIAM Symposium on Discrete Algorithms (SODA
2014), 82-101, 2014.
(with: Sylvain
Guillemot)
Given two permutations σ and π, the PERMUTATION PATTERN problem asks if
σ is
a subpattern of π. We show that the problem can be solved in time
2O(l2 log
l) n, where l=|σ| and n=|π|. In other words, the problem is
fixed-parameter tractable parameterized by the size of the subpattern to be
found.
We introduce a novel type of decompositions for permutations and a
corresponding width measure. We present a linear-time algorithm that either
finds σ as a subpattern of π, or finds a decomposition of π whose width is
bounded by a function of |σ|. Then we show how to solve the
PERMUTATION PATTERN problem in linear time if a bounded-width decomposition is given in
the input.
-
In Proceedings of the 25th ACM-SIAM Symposium on Discrete Algorithms (SODA
2014), 1812-1830, 2014.
(with: Philip N.
Klein)
Given a graph G and a subset S of vertices, the Subset TSP problem asks for
a shortest closed walk in G visiting all vertices of S. The problem can be
solved in time 2knO(1) using the classical dynamic programming algorithms
of Bellman and of Held and Karp, where k=|S| and
n=|V(G)|. Our main
result is showing that the problem can be solved in time
(2O(√k log k+W)nO(1) if
G is a planar
graph with weights that are integers no greater than W. While similar
speedups have been observed for various paramterized problems on planar
graphs, our result cannot be simply obtained as a consequence of bounding
the treewidth of G or invoking bidimensionality theory. Our algorithm
consists of two steps: (1) find a locally optimal solution, and (2) use it
to guide a dynamic program. The proof of correctness of the algorithm
depends on a treewidth bound on a graph obtained by combining an optimal
solution with a locally optimal solution.
-
Proceedings of the 30th Annual Symposium on Computational Geometry (SoCG 2014),
67, 2014.
(with: Anastasios Sidiropoulos)
We are studying
d-dimensional geometric problems that have algorithms
with 1-1/
d appearing in the exponent of the running time, for example,
in the form of 2
n1-1/d or
nk1-1/d. This means that these
algorithms perform somewhat better in low dimensions, but the running
time is almost the same for all large values
d of the dimension. Our
main result is showing that for some of these problems the dependence on
1-1/
d is best possible under a standard complexity assumption. We show
that, assuming the Exponential Time Hypothesis,
-
d-dimensional Euclidean TSP on n points cannot be solved in time
2n1-1/d-ε for any ε>0, and
- the problem of
finding a set of k pairwise nonintersecting d-dimensional unit
balls/axis parallel unit cubes cannot be solved in time
f(k)no(k1-1/d) for any computable function
f.
These
lower bounds essentially match the known algorithms for these problems. To
obtain these results, we first prove lower bounds on the complexity of
Constraint Satisfaction Problems (CSPs) whose constraint graphs are
d-dimensional grids. We state the complexity results on CSPs in a way to
make them convenient starting points forproblem-specific reductions to
particular
d-dimensional geometric problems and to be reusable in the
future for further results of similar flavor.
-
In Proceedings of
31st International Symposium on Theoretical Aspects of Computer Science
(STACS 2014), 542-553, 2014.
(with: Michal
Pilipczuk)
Given two graphs H and G, the SIBGRAPH Subgraph Isomorphism problem asks if
H is
isomorphic to a subgraph of G. While NP-hard in general, algorithms exist
for various parameterized versions of the problem. However, the literature
contains very little guidance on which combinations of parameters can or
cannot be exploited algorithmically. Our goal is to systematically
investigate the possible parameterized algorithms that can exist for
Subgraph Isomorphism. We develop a framework involving 10 relevant
parameters for each of H and G (such as treewidth, pathwidth, genus, maximum
degree, number of vertices, number of components, etc.), and ask if an
algorithm with running time
f1(p1,p2,...,pl)
nf2(pl+1,...,pk)
exists, where each of p1,...,pk is one of the 10 parameters depending only
on H or G. We show that all the questions arising in this framework are
answered by a set of 11 maximal positive results (algorithms) and a set of
17 maximal negative results (hardness proofs); some of these results already
appear in the literature, while others are new in this paper. On the
algorithmic side, our study reveals for example that an unexpected
combination of bounded degree, genus, and feedback vertex set number of
G
gives rise to a highly nontrivial algorithm for Subgraph Isomorphism. On the
hardness side, we present W[1]-hardness proofs under extremely restricted
conditions, such as when H is a bounded-degree tree of constant pathwidth
and G is a planar graph of bounded pathwidth.
-
In Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer
Science (FOCS 2013), 197-206, 2013.
(with:Marek Cygan,
Marcin Pilipczuk,
Michal Pilipczuk)
Full version:
Technical Report, arXiv:1111.1109
Given a graph G and k pairs of vertices
(s1,t1),
...,
(sk,tk), the k-Vertex-Disjoint Paths problem asks
for pairwise
vertex-disjoint paths P1, ..., Pk such that
Pi goes
from si to ti. Schrijver proved that the
k-Vertex-Disjoint Paths problem on planar directed graphs can be
solved in time nO(k)
-
40th International Colloquium on Automata, Languages and Programming (ICALP
2013), Volume 2, 125-136, Lecture Notes in Comput. Sci., 7965, Springer, 2013.
(with: Hubie Chen)
We study the complexity of model checking in quantified
conjunctive logic, that is, the fragment of first-order logic where both
quantifiers maybe used, but conjunction is the only permitted connective. In
particular, we study block-sorted queries, which we define to be prenex
sentences in multi-sorted relational first-order logic where
two variables having the same sort must appear in the same quantifier block. We
establish a complexity classification theorem that describes precisely
the sets of block-sorted queries of bounded arity on which model checking is
fixed-parameter tractable. This theorem strictly generalizes, for the first
time, the corresponding classificationfor existential conjunctive logic
(which is known and due to Grohe) to a logic in which both quantifiers are
present.
-
In Proceedings of the 23rd ACM-SIAM Symposium on Discrete Algorithms (SODA
2012), 68-81, 2012.
(with: Holger Dell)
Kernelization algorithms are polynomial-time reductions from a problem to
itself that guarantee their output to have a size not exceedingsome bound.
For example, d-Set Matching for integers d≥3 is the problem of
finding a matching of size at least k in a given d-uniform hypergraph and
has kernels with O(kd) edges. Recently, Bodlaender et al. [ICALP 2008],
Fortnow and Santhanam [STOC 2008], Dell and Van Melkebeek [STOC 2010]
developed a framework for proving lower bounds on the kernel size for certain
problems, under thecomplexity-theoretic hypothesis that coNP is not
contained in NP/poly. Under the same hypothesis, we show lower bounds for the
kernelizationof d-Set Matching and other packing problems. Our bounds
are tight for d-Set Matching: It does not have kernels with
O(kd-ε) edges for any ε>0 unless the hypothesis fails.
By reduction, this transfers to a bound of
O(kd-1-ε) for the
problem of finding k vertex-disjoint cliques of size d in standard
graphs. It is natural to ask for tight bounds on the kernel sizes of such
graph packing problems. We make first progress in that direction by showing
non-trivial kernelswith O(k2.5) edges for the problem of finding
k
vertex-disjoint paths of three edges each. This does not quite match the
best lowerbound of O(k2-ε) that we can prove. Most of our lower
bound proofs follow a general scheme that we discover: To exclude kernels of
size O(kd-ε) for a problem in d-uniform hypergraphs, one should
reduce from a carefully chosen d-partite problem that is still NP-hard. As
an illustration, weapply this scheme to the vertex cover problem, which
allows us toreplace the number-theoretical construction by Dell and Van
Melkebeek [STOC 2010] with shorter elementary arguments.
-
39th International Colloquium on Automata, Languages and Programming (ICALP
2012), 569-580, Lecture Notes in Comput. Sci., 7391, Springer, 2012.
(with: Philip N.
Klein)
The problem PLANAR k-TERMINAL CUT is as follows: given an
undirected planar graph with edge-costs and with k vertices designated as
terminals, find a minimum-cost set of edges whose removal pairwise
separates the terminals. It was known that the complexity of this problem
is O(n2k-4log n). We show that there is a constant
c such that the
complexity is O(nc√k).
This matches a recent lower bound of
Marx showing that the c√k term in the exponent is best possible up
to the constant c (assuming the Exponential Time Hypothesis).
-
39th International Colloquium on Automata, Languages and Programming (ICALP
2012), 677-688, Lecture Notes in Comput. Sci., 7391, Springer, 2012.
Given a planar graph with k terminal vertices, the PLANAR MULTIWAY
CUT problem asks for a minimum set of edges whose
removal pairwise separates the terminals from each other. A classical
algorithm of Dahlhaus et al. solves the problem
in time nO(k), which was very recently improved to
2O(k)nO(√k) time by Klein and Marx. Here we show the
optimality of the latter algorithm: assuming the Exponential Time
Hypothesis (ETH), there is no
f(k)no(√k)
time
algorithm for PLANAR MULTIWAY CUT. It also follows that the
problem is W[1]-hard, answering an open question of Downey and
Fellows.
-
37th International Workshop on Graph-Theoretic Concepts in Computer Science (WG
2011), 5-10, Lecture Notes in Comput. Sci., 6986, Springer, Berlin, 2011.
The notion of "important separators" and bounding the number of such
separators turned out to be a very useful technique in the design of
fixed-parameter tractable algorithms for multi(way) cut problems. For
example, the recent breakthrough result of Chen et al. on the DIRECTED
FEEDBACK VERTEX SET problem can be also explained using this notion. In my
talk, I will overview combinatorial and algorithmic results that can be
obtained by studying such separators.
-
17th International Conference on
Principles and Practice of Constraint Programming (CP 2011), 160-171,
Lecture Notes in Comput. Sci., 6876, Springer, Berlin, 2011.
(with:
David Cohen,
Martin
Cooper,
Martin Green)
Much work has been done on describing tractable classes of constraint
networks. Most of the known tractable examples are described by either
restricting the structure of the networks, or their language. Indeed, for
both structural or language restrictions very strong dichotomy results have
been proven and in both cases it is likely that all practical examples have
already been discovered. As such it is timely to consider tractability which
cannot be described by language or structural restrictions. This is the
focus of the work here.
In this paper we investigate
a novel reason for tractability: having at least one variable ordering for
which the number of partial solutions to the first n variables is bounded by
a polynomial in n. We show that the presence of sufficient functional
constraints can guarantee this propertyand we investigate the complexity of
finding good variableorderings based on different notions of
functionality. What is more we identify a completely novel reason for
tractability based on so called Turan sets.
-
In Proceedings of the 43rd annual ACM symposium on Theory of computing (STOC
2011), 479-488, 2011.
(with:
Martin Grohe,
Ken-ichi Kawarabayashi,
and
Paul Wollan)
Full version:
Technical Report, arXiv:1011.1827
We show that for every fixed undirected graph H, there is a
O(|V(G)|3) time algorithm that tests, given a graph G, if G contains
H as a
topological subgraph (that is, a subdivision of H is subgraph of
G).
This shows that topological subgraph testing is fixed-parameter tractable,
resolving a longstanding open question of Downey and Fellows from 1992. As a
corollary, for every H we obtain an
O(|V(G)|3) time algorithm that
tests if there is an immersion of H into a given graph G. This answers
another open question raised by Downey and Fellows in 1992.
-
In Proceedings of the 22nd ACM-SIAM Symposium on Discrete Algorithms (SODA
2011), 1028-1049, 2011.
(with:
MohammadHossein Bateni,
Chandra Checkuri,
Alina R. Ene,
MohammadTaghi Hajiaghayi,
Nitish Korula)
In this paper, we reduce PRIZE-COLLECTING STEINER TSP (PCTSP), PRIZE COLLETING
STROLL (PCS), PRIZE-COLLECTING (PCST), PRIZE-COLLETING FOREST (PCSF), and more generally
SUBMODULAR PRIZE-COLLECTING STEINER FOREST (SPCSF), on planar
graphs (and also on bounded-genus graphs) to the corresponding problem on
graphs of bounded treewidth. More precisely, for each of the mentioned
problems, an α-approximation algorithm for the problem on graphs of
bounded treewidth implies an (α+ε)-approximation algorithm
for the problem on planar graphs (and also bounded-genus graphs), for
any constant ε>0. PCS, PCTSP, PCST can be solved
exactly on graphs of bounded treewidth and hence we obtain a PTAS for
these problems on planar graphs and bounded-genus graphs. In contrast, we
show that PCSF is APX-hard to approximate on series-parallel graphs,
which are planar graphs of treewidth at most 2. Apart from ruling out a PTAS
for PCSF on planar graphs and bounded treewidth graphs, this result is
also interesting since it gives the first provable hardness
separation between the approximability of a problem and its
prize-collecting version.
We also show that PCSF is APX-hard on Euclidean
instances.
-
36th International Workshop on Graph-Theoretic Concepts in Computer Science
(WG 2010),
244-255, Lecture Notes in Comput. Sci., 6410, Springer, Berlin,
2010.
(with: Ildikó
Schlotter)
We study the Arc-Preserving Subsequence (APS) prob-
lem with unlimited annotations. Given two arc-annotated sequences P
and T, this problem asks if it is possible to delete characters from
T to
obtain P. Since even the unary version of APS is NP-hard, we used the
framework of parameterized complexity, focusing on a parameterization
of this problem where the parameter is the number of deletions we can
make. We present a linear-time FPT algorithm for a generalization of
APS, applying techniques originally designed to give an FPT algorithm
for Induced Subgraph Isomorphism on interval graphs.
-
In Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer
Science (FOCS 2007), 338-348, 2007.
We show for several planar and geometric problems that the best
knownapproximation schemes are essentially optimal with respect to the
dependence on ε. For example, we show that the
2O(1/ε) n time approximation schemes for planar
MAXIMUM INDEPENDENT SET and for TSP on a metric defined
by a planar graph are essentially optimal: if there is a δ>0 such that
any of these problems admits a
2O(1/ε)1-δnO(1) time
PTAS, then the Exponential Time Hypothesis (ETH) fails. It is known that
MAXIMUM INDEPENDENT SET on unit diskgraphs and the planar logic
problems MPSAT, TMIN, TMAX admit
nO(1/ε) time approximation schemes. We show that they are optimal
in the sense that if there is a δ>0 such that any of these problems
admits a
2(1/ε)O(1)nO(1/ε)1-δ time PTAS,
then ETH fails.
-
In A. Bondy, J. Fonlupt, J.-L. Fouquet, J.-C. Fournier, and
J. Ramirez Alfonsin, editors, Graph Theory in Paris. Proceedings of a
Conference in Memory of Claude Berge, Trends in Mathematics, pages
255--270. Birkhäuser, 2007.
In the precoloring extension problem (PrExt) we are given
a graph with some of the vertices having a preassigned color and it
has to be decided whether this coloring can be extended to a proper
k-coloring of the graph. 1-PrExt is the special case where
every color is assigned to at most one vertex in the precoloring.
Answering an open question of Hujter and Tuza, we
show that the 1-PrExt problem can be solved in polynomial time for
chordal graphs.
-
2nd International Workshop on Parameterized and Exact Computation (IWPEC 2006),
154-165, Lecture Notes in Comput. Sci., 4169, Springer, Berlin, 2006.
We investigate the parameterized complexity of MAXIMUM INDEPENDENT SET and
DOMINATING SET restricted to certain
geometric graphs. We show that DOMINATING SET is W[1]-hard for the
intersection graphs of unit squares, unit disks, and line segments.
For MAXIMUM INDEPENDENT SET, we show that the problem is W[1]-complete for unit segments, but
fixed-parameter tractable if the segments are axis-parallel.
-
In Proceedings of 13th Annual European Symposium on Algorithms (ESA 2005),
Lecture Notes in Comput. Sci., 3669, Springer, Berlin, 448-459, 2005.
[Slides]
An EPTAS (efficient PTAS) is an approximation scheme where ε does
not
appear
in the exponent of n, i.e., the running time is f(ε)
* nc. We use parameterized complexity to investigate the possibility
of improving the known approximation schemes for certain geometric
problems to EPTAS.
Answering an open question of Alber and Fiala, we show
that MAXIMUM INDEPENDENT SET is W[1]-complete for the
intersection graphs of unit disks and axis-parallel
unit squares in the plane. A standard consequence of this result is
that the nO(1/ε) time PTAS of Hunt et
al. for
MAXIMUM INDEPENDENT SET
on
unit disk graphs cannot be improved to an EPTAS. Similar results are
obtained for the problem of covering points with squares.
-
2nd
Workshop on Approximation and Online Algorithms (WAOA 2004),
9-22, Lecture Notes in Comput. Sci., 3351, Springer, Berlin, 2005.
[Slides]
The edge multicoloring problem is that given a graph G and integer
demands x(e) for every edge e, assign a set of x(e) colors to
edge e, such that adjacent edges have disjoint sets of colors.
In the minimum sum edge multicoloring problem the finish
time of an edge is defined to be the highest color assigned to
it. The goal is to minimize the sum of the finish times. The main
result of the paper is a polynomial time approximation scheme for
minimum sum multicoloring the edges of planar graphs and partial
k-trees.
-
Mathematical foundations of computer science (MFCS 2002), 532-542,
Lecture Notes in Comput. Sci., 2420,
Springer, Berlin, 2002.
[Slides]
The multicoloring problem is that given a graph
G and
integer demands
x(v) for every vertex
v, assign a set of
x(v) colors to vertex
v, such that neighboring vertices
have disjoint sets of colors. In the
preemptive sum multicoloring
problem the
finish time of a vertex is defined to be the
highest color assigned to it. The goal is to minimize the sum of the
finish times. The study of this problem is motivated by applications
in scheduling. Answering a question of Halldórsson et al. [
Inform. and
Comput., 180(2):113-129, 2003], we show that the problem is
strongly
NP-hard in binary trees. As a first step toward this
result we prove that list multicoloring of binary trees is
NP-complete.
-
IEEE INFOCOM 2000, 1000-1009.
(with: Dániel
Fogaras)
An efficient and general graph-theoretic model (the
Wavelength-Graph (WG)) has been proposed which enables solving the
static Routing and Wavelength Assignment (RWA) problems in
Multihop Wavelength Routing (WR) Wavelength Division Multiplexing
(WDM) Networks simultaneously, and - as a unique feature - it
optimises the optical layer jointly with electrical one. Based on
the proposed WG model the problem has been formulated as an
Integer Linear Program (ILP), solved by stochastic algorithms
improved by simple heuristics.
The topology of the physical layer, the type of each node (e.g., OADM,
OXC or EXC), the number of available wavelengths per link and the
capacity of each wavelength-channel are assumed given with the
aggregated traffic demand of each node-pair. The output of the
optimisation is the system of wavelengthpaths, lightpaths and
semi-lightpaths.
The objective of the optimisation is to reduce resource usage at upper
(electrical) layers, subject to constrained amount of capacity of
each wavelength and limited number of wavelengths. Although the
problem to be solved is NP-hard, all methods proposed give results
in very short time.
Papers appearing in
edited volumes
-
In Fomin, F.V., et al. (eds.)
Treewidth, Kernels, and Algorithms.
Essays Dedicated to Hans L. Bodlaender on the Occasion of His 60th Birthday.
Lecture Notes in Comput. Sci., vol 12160, pp. 129-144, Springer, 2020.
-
In Bodlaender,
H.L., et al. (eds.) Fellows Festschrift. Lecture Notes in Comput. Sci., vol. 7370, pp.
457-468, Springer, 2012.
(with:Fedor V. Fomin)
We give an update on the status of open problems from the book
"Parameterized Complexity" by Downey and Fellows.
-
In Bodlaender,
H.L., et al. (eds.) Fellows Festschrift. Lecture Notes in Comput. Sci., vol. 7370, pp.
469-496, Springer, 2012.
The progress in parameterized complexity has been very significant in
recent years, with new research questions and directions, such as
kernelization lower bounds, appearing and receiving considerable
attention. This speculative article tries to identify new directions that
might become similar hot topics in the future. First, we point out that
the search for optimality in parameterized complexity already has good
foundations, but lots of interesting work can be still done in this area.
The systematic study of kernelization became a very successful research
direction in recent years. We look at what general conclusions one can
draw from these results and we argue that the systematic study of other
algorithmic techniques should be modeled after the study of
kernelization. In particular, we set up a framework for understanding
which problems can be solved by branching algorithms. Finally, we discuss
that the domain of directed graph problems is a challenging area which
can potentially see significant progress in the following years.
Volume
editing
-
Hans L. Bodlaender, Rod Downey, Fedor V. Fomin, and Dániel Marx (eds.) Lecture Notes in Comput. Sci., vol.
7370, Springer, 2012.
-
Dániel Marx and Peter Rossmanith (eds.) Lecture Notes in Comput. Sci., vol.
7112, Springer, 2012.
-
Manuscript, 2003.
Coloring circular arcs was shown to be NP-complete by
Garey, Johnson, Miller and Papadimitriou [SIAM J. Algebraic
Discrete Methods, 1(2):216--227, 1980]. Here we present a
simpler proof of this result.
-
Parameterized Complexity Newletter, pages 7-8, Vol. 3, 2007.
Thesis
-
PhD thesis, 2004.