Złożoność parametryzowana i algorytmy wykładnicze
(Parameterized
Complexity and exponentialtime algorithms)
Grant N N206 567140 funded by National Science Centre from 04.2011 to 04.2014
Publications  People involved  Guests
Most important publications of the project
 Marek Cygan, Jesper Nederlof, Marcin Pilipczuk, Michal Pilipczuk, Johan
M. M. van Rooij, Jakub Onufry Wojtaszczyk, Solving Connectivity Problems
Parameterized by Treewidth in Single Exponential Time.
Proceedings of the 52nd IEEE Annual Symposium on Foundations of Computer Science (FOCS 2011), 150159, 2011.
[arXiv] [Publisher's version]Abstract: For the vast majority of local graph problems standard dynamic programming techniques give c^{tw} V^{O(1)} algorithms, where tw is the treewidth of the input graph. On the other hand, for problems with a global requirement (usually connectivity) the bestknown algorithms were naive dynamic programming schemes running in at least tw^{tw} time.
We breach this gap by introducing a technique we dubbed Cut&Count that allows to produce c^{tw} V^{O(1)} Monte Carlo algorithms for most connectivitytype problems, including Hamiltonian Path, Feedback Vertex Set and Connected Dominating Set, consequently answering the question raised by Lokshtanov, Marx and Saurabh [SODA'11] in a surprising way. We also show that (under reasonable complexity assumptions) the gap cannot be breached for some problems for which Cut&Count does not work, like CYCLE PACKING.
The constant c we obtain is in all cases small (at most 4 for undirected problems and at most 6 for directed ones), and in several cases we are able to show that improving those constants would cause the Strong Exponential Time Hypothesis to fail.
Our results have numerous consequences in various fields, like FPT algorithms, exact and approximate algorithms on planar and Hminorfree graphs and algorithms on graphs of bounded degree. In all these fields we are able to improve the bestknown results for some problems.  Rajesh Chitnis, Marek Cygan, MohammadTaghi Hajiaghayi,
Marcin Pilipczuk, Michał Pilipczuk. Designing FPT algorithms for cut
problems using randomized contractions.
Proceedings of the 53rd IEEE Annual Symposium on Foundations of Computer Science (FOCS 2012), 460469.
[arXiv] [Publisher's version]Abstract: We introduce a new technique for designing fixedparameter algorithms for cut problems, namely randomized contractions. We apply our framework to obtain the first FPT algorithm for the Unique Label Cover problem and new FPT algorithms with exponential speed up for the Steiner Cut and Node Multiway CutUncut problems. More precisely, we show the following:
 We prove that the parameterized version of the Unique Label Cover problem, which is the base of the Unique Games Conjecture, can be solved in 2^{O(k^2\log \Sigma)}n^4\log n deterministic time (even in the stronger, vertexdeletion variant) where k is the number of unsatisfied edges and \Sigma is the size of the alphabet. As a consequence, we show that one can in polynomial time solve instances of Unique Games where the number of edges allowed not to be satisfied is upper bounded by O(\sqrt{\log n}) to optimality, which improves over the trivial O(1) upper bound.
 We prove that the Steiner Cut problem can be solved in 2^{O(k^2\log k)}n^4\log n deterministic time and \tilde{O}(2^{O(k^2\log k)}n^2) randomized time where k is the size of the cutset. This result improves the double exponential running time of the recent work of Kawarabayashi and Thorup (FOCS'11).
 We show how to combine considering `cut' and `uncut' constraints at the same time. More precisely, we define a robust problem Node Multiway CutUncut that can serve as an abstraction of introducing uncut constraints, and show that it admits an algorithm running in 2^{O(k^2\log k)}n^4\log n deterministic time where k is the size of the cutset. To the best of our knowledge, the only known way of tackling uncut constraints was via the approach of Marx, O'Sullivan and Razgon (STACS'10), which yields algorithms with double exponential running time.
An interesting aspect of our technique is that, unlike important separators, it can handle real weights. 
Andreas Björklund, Petteri Kaski, Łukasz Kowalik, Counting thin
subgraphs via packings faster than meetinthemiddle time,
To appear at ACMSIAM Symposium on Discrete Algorithms (SODA 2014),
[arXiv]Abstract: Vassilevska and Williams (STOC 2009) showed how to count simple paths on $k$ vertices and matchings on $k/2$ edges in an $n$vertex graph in time $n^{k/2+O(1)}$. In the same year, two different algorithms with the same runtime were given by Koutis and Williams (ICALP 2009), and Bj\"orklund \emph{et al.} (ESA 2009), via $n^{st/2+O(1)}$time algorithms for counting $t$tuples of pairwise disjoint sets drawn from a given family of $s$sized subsets of an $n$element universe. Shortly afterwards, Alon and Gutner (TALG 2010) showed that these problems have $\Omega(n^{\lfloor st/2\rfloor})$ and $\Omega(n^{\lfloor k/2\rfloor})$ lower bounds when counting by color coding. Here we show that one can do better, namely, we show that the "meetinthemiddle" exponent $st/2$ can be beaten and give an algorithm that counts in time $n^{0.4547 st + O(1)}$ for $t$ a multiple of three. This implies algorithms for counting occurrences of a fixed subgraph on $k$ vertices and pathwidth $p\ll k$ in an $n$vertex graph in $n^{0.4547 k+2p+O(1)}$ time, improving on the three mentioned algorithms for paths and matchings, and circumventing the colorcoding lower bound.

Andreas Björklund, Petteri Kaski, Łukasz Kowalik, Probably Optimal Graph Motifs,
Proc. 30th Symposium on Theoretical Aspects of Computer Science (STACS 2013),
LIPIcs, 2031, 2013.
[arXiv] [Publisher's version]Abstract: We show an O*(2^{k})time polynomial space algorithm for the ksized Graph Motif problem. We also introduce a new optimization variant of the problem, called Closest Graph Motif and solve it within the same time bound. The Closest Graph Motif problem encompasses several previously studied optimization variants, like Maximum Graph Motif, MinSubstitute, and MinAdd.
Moreover, we provide a piece of evidence that our result might be essentially tight: the existence of an O((2ε)^{k})time algorithm for the Graph Motif problem implies an O((2ε')^{n})time algorithm for Set Cover. 
Marek Cygan, Marcin Pilipczuk, Michał Pilipczuk.
Known algorithms for
EDGE CLIQUE COVER are probably optimal.
Proceedings of the 24th Annual ACMSIAM Symposium on Discrete Algorithms, SODA 2013, 10441053.
[arXiv] [Publisher's version]Abstract: In the EDGE CLIQUE COVER (ECC) problem, given a graph G and an integer k, we ask whether the edges of G can be covered with k complete subgraphs of G or, equivalently, whether G admits an intersection model on kelement universe. Gramm et al. [JEA 2008] have shown a set of simple rules that reduce the number of vertices of G to 2^{k}, and no algorithm is known with significantly better running time bound than a bruteforce search on this reduced instance. In this paper we show that the approach of Gramm et al. is essentially optimal: we present a polynomial time algorithm that reduces an arbitrary 3CNFSAT formula with n variables and m clauses to an equivalent ECC instance (G,k) with k = O(log n) and V(G) = O(n + m). Consequently, there is no 2^{2o(k)}poly(n) time algorithm for the ECC problem, unless the Exponential Time Hypothesis fails. To the best of our knowledge, these are the first results for a natural, fixedparameter tractable problem, and proving that a doublyexponential dependency on the parameter is essentially necessary.

Marek Cygan, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk.
The planar directed kVertexDisjoint Paths problem is fixedparameter
tractable.
Acceped to FOCS 2013.
[arXiv]Abstract: Given a graph G and k pairs of vertices (s_1,t_1), ..., (s_k,t_k), the kVertexDisjoint Paths problem asks for pairwise vertexdisjoint paths P_1, ..., P_k such that P_i goes from s_i to t_i. Schrijver [SICOMP'94] proved that the kVertexDisjoint Paths problem on planar directed graphs can be solved in time n^{O(k)}. We give an algorithm with running time 2^{2^{O(k^2)}} n^{O(1)} for the problem, that is, we show the fixedparameter tractability of the problem.
Remaining publications:

Marek Cygan, Łukasz Kowalik, Channel Assignment via Fast Zeta Transform,
Information Processing Letters, Vol. 111, No. 15, 2011, 727730.
[arXiv] [Publisher's version]Abstract: We show an O*((l+1)^n)time algorithm for the channel assignment problem, where l is the maximum edge weight. This improves on the previous O*((l+2)^n)time algorithm by Kral, as well as algorithms for important special cases, like L(2,1)labelling. For the latter problem, our algorithm works in O*(3^n) time. The progress is achieved by applying the fast zeta transform in combination with the inclusionexclusion principle.
 Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk and Jakub Wojtaszczyk, On Multiway Cut parameterized above lower bounds
Proc. 6th International Symposium on Parameterized and Exact Computation (IPEC 2011), LNCS 7112, 112, 2011.
Journal version accepted to ACM Transactions on Computation Theory.
[arXiv] [Publisher's version]  Marek Cygan, Fedor Fomin and Erik Jan Van Leeuwen,
Parameterized Complexity of Firefighting Revisited
Proc. 6th International Symposium on Parameterized and Exact Computation (IPEC 2011),
LNCS 7112, 1326, 2011.
[arXiv] [Publisher's version]  Marek Cygan, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, Ildikó
Schlotter, Parameterized Complexity of Eulerian Deletion Problems,
Proc. 37th International Workshop on GraphTheoretic Concepts in Computer Science (WG 2011),
Journal version accepted to Algorithmica.
LNCS 6986, 131142, 2011.
[Publisher's version]  Marek Cygan, Marcin Pilipczuk. Split
Vertex Deletion meets Vertex Cover: New fixedparameter and exact
exponentialtime algorithms.
Information Processing Letters 113(56), 179182, 2013.  Łukasz Kowalik, Marcin Pilipczuk, Karol Suchan. Towards optimal kernel for connected vertex cover in planar graphs. Discrete Applied Mathematics, Discr. Appl. Math., Vol. 161, 11541161, 2013.
 Marek Cygan, Daniel Lokshtanov, Marcin Pilipczuk, Michał
Pilipczuk, Saket Saurabh. On
Cutwidth Parameterized by Vertex Cover.
Algorithmica, to appear, 2012  Stefan Kratsch, Marcin Pilipczuk, Michał Pilipczuk, Magnus
Wahlström. FixedParameter
Tractability of Multicut in Directed Acyclic Graphs.
Proceedings of Automata, Languages, and Programming  39th International Colloquium (ICALP 2012), Lecture Notes in Computer Science 7391, 581593.  Marek Cygan, Stefan Kratsch, Marcin Pilipczuk, Michał Pilipczuk,
Magnus Wahlström. Clique Cover and
Graph Separation: New Incompressibility Results.
Proceedings of Automata, Languages, and Programming  39th International Colloquium (ICALP 2012), Lecture Notes in Computer Science 7391, 254265.  Rajesh Hemant Chitnis, Marek Cygan, Mohammad Taghi Hajiaghayi,
Dániel Marx: Directed Subset
Feedback Vertex Set Is FixedParameter Tractable.
Proceedings of Automata, Languages, and Programming  39th International Colloquium (ICALP 2012), 230241  Marek Cygan, Guy Kortsarz, Zeev Nutov. Steiner Forest Orientation
Problems.
SIAM J. Discrete Math., 27(3), 1503–1513. (11 pages)
[Publisher's version]
Conference version: Proceedings of 20th Annual European Symposium on Algorithms (ESA 2012), 2012, 361372  Marek Cygan, Deterministic
Parameterized Connected Vertex Cover.
Proc. of 13th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2012), 95106  Stefan Kratsch, Marcin Pilipczuk, Ashutosh Rai, Venkatesh Raman.
Kernel Lower Bounds Using Conondeterminism: Finding Induced Hereditary Subgraphs. Proc. of 13th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2012), Lecture Notes in Computer Science 7357, 364375.  Marcin Pilipczuk, Michał Pilipczuk. Finding a maximum induced degenerate
subgraph faster than 2^n.
Proc. 7th International Symposium on Parameterized and Exact Computation (IPEC 2012), Lecture Notes in Computer Science 7535, 312.  Marek Cygan, Marcin Pilipczuk, Michał Pilipczuk. On Group Feedback Vertex Set Parameterized
by the Size of the Cutset.
Proceedings of WG 2012, Lecture Notes in Computer Science 7551, 194205.  Marek Cygan, Marcin Pilipczuk, Michał Pilipczuk, Jakub Onufry
Wojtaszczyk. Sitting Closer to
Friends Than Enemies, Revisited.
Proceedings of MFCS 2012, Lecture Notes in Computer Science 7464, 296307.  Fedor Fomin, Stefan Kratsch, Marcin Pilipczuk, Michał Pilipczuk,
Yngve Villanger. Tight bounds for
Parameterized Complexity of Cluster Editing.
Proc. 30th Symposium on Theoretical Aspects of Computer Science (STACS 2013), LIPIcs, Vol. 20, 3243.  Łukasz Kowalik, Nonblocker in Hminor free graphs: kernelization meets
discharging
Proc. 7th International Symposium on Parameterized and Exact Computation (IPEC 2012),
LNCS 7535, 6172, 2012.
[arXiv] [Publisher's version] [slides]  Adam Bouland, Anuj Dawar, Eryk Kopczynski,
On Tractable Parameterizations of Graph Isomorphism
Proc. 7th International Symposium on Parameterized and Exact Computation (IPEC 2012),
LNCS 7535, 218230, 2012.
[Publisher's version]  Łukasz Kowalik, Marcin Mucha, A 9k kernel for nonseparating independent set in planar
graphs,
Proc. 38th International Workshop on GraphTheoretic Concepts in Computer Science (WG 2012),
LNCS 7551, 160171, 2012.
[arXiv] [Publisher's version] [slides]  Marek Cygan, Marcin Pilipczuk,
Faster exponentialtime algorithms in graphs of bounded average
degree
Accepted for ICALP 2013.
[arXiv]
People involved
 Marek Cygan
 Łukasz Kowalik
 Eryk Kopczyński
 Marcin Mucha
 Marcin Pilipczuk
 Michał Pilipczuk
 Jakub Wojtaszczyk
Guests hosted
 Anudhyan Boral (Institute of Mathematical Sciences, India)
 Matthias Mnich (MPI Saarbrucken, Germany)
 Marcin Kamiński (Bruxelles, Belgium)
 Petteri Kaski (Aalto University, Finland)
 Stefan Kratsch (Utrecht University, The Nederlands)
 Daniel Lokshtanov (UCSD, USA)
 Saket Saurabh (Institute of Mathematical Sciences, India)
 Magnus Wahlström (MPI Saarbrucken, Germany)