Grant Optimality in Parameterized Complexity wass funded by the
Polish National Science Center (NCN). It started in October 2014, and concluded September 2017. The investigators in the grant were Michał Pilipczuk (PI) and Marcin Wrochna.
The following list contains works supported by the grant. Preprints of all the works are available on arxiv.
Florian Barbero, Christophe Paul, Michał Pilipczuk,
Strong immersion is a well-quasi-ordering for semi-complete digraphs,
unpublished, available at [arxiv], Show abstract
We prove that the strong immersion order is a well-quasi-ordering on the class of semi-complete digraphs,
thereby generalizing the result of Chudnovsky and Seymour that this holds for tournaments.
Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk,
On subexponential parameterized algorithms for Steiner Tree and Directed Subset TSP on planar graphs,
unpublished, available at [arxiv], Show abstract
We give a subexponential parameterized algorithm with running time
exp(O(k1/2· log k))· poly(n) for the Subset TSP problem on directed planar graphs. We also show that the Steiner Tree problem on planar graphs
does not admit a 2o(|T|) · poly(n)-time algorithm under ETH, but admits an algorithm with running time nO(sqrt{|T|}); here, T is the terminal set.
The combination of these two results refutes the existence of a parameter-nonincreasing polynomial kernel for Steiner Tree on planar graphs.
Thus, our results essentially completely resolve the question of the complexity of the parameterization by the number of terminals for planar Steiner Tree, which was open for several years.
Bart M. P. Jansen, Marcin Pilipczuk, Marcin Wrochna,
Turing kernelization for finding long paths in graph classes excluding a topological minor,
IPEC 2017, available at [arxiv], Show abstract
We prove that the problem of finding a simple path on k vertices, parameterized by k, admits a Turing kernel
on any class characterized by excluding a fixed topological minor. This generalizes previous results of Jansen that this holds for planar graphs and for classes with constant maximum degree.
Marthe Bonamy, Łukasz Kowalik, Jesper Nederlof, Michał Pilipczuk, Arkadiusz Socała, Marcin Wrochna,
On Directed Feedback Vertex Set parameterized by treewidth,
unpublished, available at [arxiv], Show abstract
We study the Directed Feedback Vertex Set problem parameterized by the treewidth of the undirected graph obtained
by forgetting the orientation of arcs in the input. We prove that for treewidth t there is a semi-standard dynamic programming routine working in time O*(2O(t log t)), which is tight under ETH,
but on planar digraphs of treewidth t one can obtain running time O*(2O(t)).
Daniel Lokshtanov, Michał Pilipczuk, Saket Saurabh,
Below all subsets for Minimal Connected Dominating Set,
unpublished, available at [arxiv], Show abstract
We prove that the number of minimal connected dominating sets in an n-vertex graph is at most O(2(1-eps)n) for some miniscule, but positive constant eps.
Marthe Bonamy, Łukasz Kowalik, Michał Pilipczuk, Arkadiusz Socała, Marcin Wrochna,
Tight lower bounds for the complexity of multicoloring,
ESA 2017, available at [arxiv], Show abstract
In the Multicoloring problem we are given a graph G and integers a>b. The goal is to assign to each vertex
exactly b colors out of a palette of a colors so that adjacent vertices receive disjoint color subsets. Multicoloring has close connections to the fractional chromatic number and graph homomorphisms,
where the target graph is a Kneser graph. We prove that the classic algorithm that solves the Multicoloring problem in time O*((b+1)n) is essentially optimal: under the Exponential Time
Hypothesis, there is no algorithm with running time 2o(n· log b).
Michał Pilipczuk, Erik Jan van Leeuwen, Andreas Wiese,
Approximation and parameterized algorithms for geometric independent set with shrinking,
MFCS 2017, available at [arxiv], Show abstract
We consider the geometric Independent Set problem for weighted rectangles: given a family
of weighted axis-parallel rectangles in the plane, find a maximum-weight subset of pairwise non-overlapping rectangles. Since the problem is hard both in the parameterized and
the approximation setting, we investigate the shrinking model: rectangles in the solution only need to be non-overlapping after shrinking them slightly, but the performance of the algorithm
is still compared to the optimum without shrinking. For this model, we show that there is an EPTAS and an FPT algorithm; the latter is for the setting of looking for a maximum-weight solution with
cardinality k, where k is the parameter. This improves a PTAS previously known for the shrinking model. Furthermore, we investigate kernelization in the shrinking model, and using this methodology
we derive subexponential parameterized algorithms for several important subcases of the problem.
Anna Adamaszek, Tomasz Kociumaka, Marcin Pilipczuk, Michał Pilipczuk,
Hardness of approximation for strip packing,
ACM Transactions on Computation Theory (TOCT), available at [arxiv], Show abstract
In the Strip Packing problem, a set of rectangular objects has to be packed into a bin of fixed width,
and the goal is to minimize the overall height of the packing. Recently, it was observed that the classic hardness of 3/2-approximation can be broken if we assume that the width of the bin
is given in unary, and the problem admits a 4/3+eps approximation algorithm. This raised the question whether in this setting also a quasi-polynomial approximation scheme (QPTAS) can be designed,
similarly as for other geometric packing problems of similar flavor. We give a negative answer to this question, by proving that it is NP-hard to approximate Strip Packing within factor 12/11-eps.
Florian Barbero, Christophe Paul, Michał Pilipczuk,
Exploring the complexity of layout parameters in tournaments and semi-complete digraphs,
ICALP 2017, available at [arxiv], Show abstract
We study the the cutwidth parameter in semi-complete digraph, which intuitively is the measure of how well
we can linearly order a semi-complete digraph so that only few arcs are going backward at every point of the ordering. Our main result is that
the problem of computing the cutwidth of a semi-complete digraph admits a quadratic Turing kernel, despite not admitting a classic polynomial kernel under standard complexity theoretic assumptions. We also show that this problem is NP-hard and that known parameterized algorithms for it are almost tight under ETH.
Archontia C. Giannopoulou, Michał Pilipczuk, Jean-Florent Raymond, Dimitrios M. Thilikos, Marcin Wrochna,
Linear kernels for edge deletion problems to immersion-closed graph classes,
ICALP 2017, available at [arxiv], Show abstract
We study the general class of edge modification problems defined as follows: Given a graph G and integer k,
remove at most k edges from G in order to obtain a graph from a fixed immersion-closed graph class. This is the edge-deletion counterpart
of the F-Deletion problem studied by Fomin et al., where the goal is to delete k vertices to obtain a graph from a fixed minor-closed graph class. We prove that
whenever one of the forbidden immersions characterizing the graph class is planar subcubic, then the problem admits a linear kernel, a single-exponential FPT algorithm, and a constant-factor approximation.
This mirrors exactly the results of Fomin et al. for F-Deletion when one of the forbidden minors is planar.
However, in our setting we always obtain a linear kernel, while in the setting of F-Deletion the polynomial upper bound on the kernel size provably has to depend on the target graph class.
Fedor V. Fomin, Daniel Lokshtanov, Michał Pilipczuk, Saket Saurabh, Marcin Wrochna,
Fully polynomial-time parameterized computations for graphs and matrices of low treewidth,
SODA 2017, available at [arxiv], Show abstract
We study algorithms working on graphs and matrices that run in time poly(k) · n or poly(k) · n log n on a graph/matrix of treewidth k and size n. Such algorithm can be efficiently employed already on inputs with moderate values of the treewidth, while they can turn out to be faster than general-purpose algorithms with high polynomial dependence on n in case the treewidth is low. We provide an approximation algorithm for treewidth that is suitable for this class of running times, as well as we design such algorithms for several fundamental problems, including Maximum Matching, Minimum Cut, and solving systems of linear equations.
Fedor V. Fomin, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, Saket Saurabh,
Subexponential parameterized algorithms for planar and apex-minor-free graphs via low treewidth pattern covering,
FOCS 2016, available at [arxiv], Show abstract
We prove that every planar graph on n vertices admits a family
of vertex subsets of size exp(O(k1/2· log2 k))· poly(n) with the following property: each vertex subset from F induces a subgraph of treewidth
O(k1/2· log k), and every connected subset of vertices of size k is entirely contain in some vertex subset from F. This basic tool enables us to
derive a number of subexponential parameterized algorithms for problems on planar graphs that can be described as searching for a small pattern with a prescribed property.
Archontia C. Giannopoulou, Michał Pilipczuk, Jean-Florent Raymond, Dimitrios M. Thilikos, Marcin Wrochna,
Cutwidth: obstructions and algorithmic aspects,
IPEC 2016, available at [arxiv], Show abstract
We prove that immersion obstructions to graphs of cutwidth at most k have sizes single-exponential in k.
As a by-product, we develop a new, simpler exact FPT algorithm for computing the cutwidth of a graph.
Marcin Pilipczuk, Michał Pilipczuk, Marcin Wrochna,
Edge Bipartization faster than 2k,
IPEC 2016, journal version in Algorithmica, available at [arxiv], Show abstract
We prove that the Edge Bipartization problem (remove at most k edges to make the given graph bipartite) can be solved in time 1.977k· poly(n), which improves upon a decade-old algorithm with running time 2k· poly(n). The main ingredient of the new approach is to use polynomial-time solvable relaxation of the problem in the form of a Valued CSP, a technique recently proposed by Wahlström.
Ivan Bliznets, Marek Cygan, Paweł Komosa, Michał Pilipczuk,
Hardness of approximation for H-free edge modification problems,
APPROX 2016, available at [arxiv], Show abstract
We explore the approximation complexity of edge modification problems related to H-free graphs, that is,
graphs excluding H as an induced subgraph. We show that, with a few curious exceptions, for almost all graphs H the problem is very hard to approximate. To prove the hardness,
we use intuitions and techniques borrowed from the parameterized literature on these problems, in particular from the known lower bounds on polynomial kernelization and subexponential complexity.
Marek Cygan, Daniel Lokshtanov, Marcin Pilipczuk, Michał Pilipczuk, Saket Saurabh,
Lower bounds for approximation schemes for Closest String,
SWAT 2016, available at [arxiv], Show abstract
We prove that the Closest String problem, one of the central NP-hard string problems motivated by machine learning and computational biology, does not admit an EPTAS unless FPT=W[1]. Our hardness reduction also shows that the existence of a PTAS with running time no(1/eps) would contradict ETH.
Michał Pilipczuk, Marcin Wrochna,
On space efficiency of algorithms working on structural decompositions of graphs,
STACS 2016, journal version accepted to ACM Transactions on Computation Theory, available at [arxiv], Show abstract
The starting point of our investigations is the question whether algorithms working on tree decompositions of graphs can be implemented to run in polynomial space while not sacrificing the time complexity much. We prove that this question is tightly connected to the question whether the Longest Common Subsequence problem can be solved by an algorithm working simultaneously in XP time and FPT space. We also investigate the parameter tree-depth, and prove a completeness result for computations on low tree-depth decompositions of graphs. Together with earlier results of Allender et al. for pathwidth and treewidth, this uncovers a hierarchy of complexity classes for nondeterministic machines with different access to the working space, which resembles the classic inequalities between treewidth, pathwidth, and tree-depth.
Ivan Bliznets, Marek Cygan, Paweł Komosa, Lukáš Mach, Michał Pilipczuk,
Lower bounds for the parameterized complexity of Minimum Fill-in and other completion problems,
SODA 2016, available at [arxiv], Show abstract
We adress the problem of finding matching lower bounds for a number of completion problems related to subclasses of chordal graphs, which can be solved in subexponential FPT time. We show that a combination of ETH and PCP tools provides better lower bounds than previously known, however still not tight. Then, we introduce a new conjecture about the hardness of approximation of the Minimum Bisection problem, and prove that under this conjecture (almost) tight lower bounds can be provided.
Pål Grønås Drange, Michał Pilipczuk,
A polynomial kernel for Trivially Perfect Editing,
ESA 2015, available at [arxiv], Show abstract
We prove that the problem of editing (adding or removing) edges to obtain a trivially perfect graph admits a kernel with O(k7) vertices. We complement this result by showing that the problem cannot be solved in subexponential FPT time unless the ETH fails.
Dániel Marx, Michał Pilipczuk,
Optimal parameterized algorithms for planar facility location problems using Voronoi diagrams,
ESA 2015, available at [arxiv], Show abstract
We provide a general methodology for designing parameterized algorithms with running time of the form nO(k) for a large family of packing and covering problems on planar graphs and in the Euclidean plane. The crux of the approach is to exploit short balanced separators of the Voronoi diagram induced by the (unknown) solution. The study is complemented by a number of lower bounds based on ETH and SETH showing that the algorithms yielded by our technique (probably) cannot be improved upon.
Ariel Gabizon, Daniel Lokshtanov, Michał Pilipczuk,
Fast algorithms for parameterized problems with relaxed disjointness constraints,
ESA 2015, available at [arxiv], Show abstract
We investigate parameterized problems for which gradually relaxing the disjointness condition results in a gradual shift of time complexity of the problem. We provide a derandomization of the main technique used in this approach, which was introduced by Abasi et al., using the concept of representative sets for multisets. We also apply the methodology to several problems, including providing an elegant exact exponential-time algorithm for finding spanning trees of small maximum degree.
Marek Cygan, Marcin Pilipczuk, Michał Pilipczuk, Erik Jan van Leeuwen, Marcin Wrochna,
Polynomial kernelization for removing induced claws and diamonds,
WG 2015, journal version in Theory of Computing Systems, available at [arxiv], Show abstract
We prove that the edge deletion problem to {claw,diamond}-free graphs, i.e., the class of graphs that do not admit induced claws or diamonds, admits a polynomial kernel. Moreover, the problem cannot be solved in subexponential FPT time unless the ETH fails. This is the first step towards the investigation of the existence of a polynomial kernel for claw-free edge deletion.
|