# Lukasz Kowalik

homepage

Main menu: Home | Papers | Teaching | Projects |

## Złożoność parametryzowana i algorytmy wykładnicze (Parameterized Complexity and exponential-time algorithms)

Grant N N206 567140 funded by National Science Centre from 04.2011 to 04.2014

### Most important publications of the project

1. 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), 150-159, 2011.
[arXiv] [Publisher's version]

Abstract: For the vast majority of local graph problems standard dynamic programming techniques give ctw |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 best-known algorithms were naive dynamic programming schemes running in at least twtw time.
We breach this gap by introducing a technique we dubbed Cut&Count that allows to produce ctw |V|O(1) Monte Carlo algorithms for most connectivity-type 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 H-minor-free graphs and algorithms on graphs of bounded degree. In all these fields we are able to improve the best-known results for some problems.

2. 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), 460-469.
[arXiv] [Publisher's version]

Abstract: We introduce a new technique for designing fixed-parameter 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 Cut-Uncut 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, vertex-deletion 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 Cut-Uncut 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.

3. Andreas Björklund, Petteri Kaski, Łukasz Kowalik, Counting thin subgraphs via packings faster than meet-in-the-middle time,
To appear at ACM-SIAM 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 "meet-in-the-middle" 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 color-coding lower bound.

4. Andreas Björklund, Petteri Kaski, Łukasz Kowalik, Probably Optimal Graph Motifs,
Proc. 30th Symposium on Theoretical Aspects of Computer Science (STACS 2013),
LIPIcs, 20-31, 2013.
[arXiv] [Publisher's version]

Abstract: We show an O*(2k)-time polynomial space algorithm for the k-sized 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, Min-Substitute, and Min-Add.
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.

5. Marek Cygan, Marcin Pilipczuk, Michał Pilipczuk. Known algorithms for EDGE CLIQUE COVER are probably optimal.
Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013, 1044-1053.
[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 k-element universe. Gramm et al. [JEA 2008] have shown a set of simple rules that reduce the number of vertices of G to 2k, and no algorithm is known with significantly better running time bound than a brute-force 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 3-CNF-SAT 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 22o(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, fixed-parameter tractable problem, and proving that a doubly-exponential dependency on the parameter is essentially necessary.

6. Marek Cygan, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk. The planar directed k-Vertex-Disjoint Paths problem is fixed-parameter 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 k-Vertex-Disjoint Paths problem asks for pairwise vertex-disjoint paths P_1, ..., P_k such that P_i goes from s_i to t_i. Schrijver [SICOMP'94] proved that the k-Vertex-Disjoint 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 fixed-parameter tractability of the problem.

### Remaining publications:

1. Marek Cygan, Łukasz Kowalik, Channel Assignment via Fast Zeta Transform,
Information Processing Letters, Vol. 111, No. 15, 2011, 727-730.
[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 inclusion-exclusion principle.

2. 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, 1-12, 2011.
Journal version accepted to ACM Transactions on Computation Theory.
[arXiv] [Publisher's version]
3. 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, 13-26, 2011.
[arXiv] [Publisher's version]
4. Marek Cygan, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, Ildikó Schlotter, Parameterized Complexity of Eulerian Deletion Problems,
Proc. 37th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2011),
Journal version accepted to Algorithmica.
LNCS 6986, 131-142, 2011.
[Publisher's version]
5. Marek Cygan, Marcin Pilipczuk. Split Vertex Deletion meets Vertex Cover: New fixed-parameter and exact exponential-time algorithms.
Information Processing Letters 113(5-6), 179-182, 2013.
6. Łukasz Kowalik, Marcin Pilipczuk, Karol Suchan. Towards optimal kernel for connected vertex cover in planar graphs. Discrete Applied Mathematics, Discr. Appl. Math., Vol. 161, 1154-1161, 2013.
7. Marek Cygan, Daniel Lokshtanov, Marcin Pilipczuk, Michał Pilipczuk, Saket Saurabh. On Cutwidth Parameterized by Vertex Cover.
Algorithmica, to appear, 2012
8. Stefan Kratsch, Marcin Pilipczuk, Michał Pilipczuk, Magnus Wahlström. Fixed-Parameter Tractability of Multicut in Directed Acyclic Graphs.
Proceedings of Automata, Languages, and Programming - 39th International Colloquium (ICALP 2012), Lecture Notes in Computer Science 7391, 581-593.
9. 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, 254-265.
10. Rajesh Hemant Chitnis, Marek Cygan, Mohammad Taghi Hajiaghayi, Dániel Marx: Directed Subset Feedback Vertex Set Is Fixed-Parameter Tractable.
Proceedings of Automata, Languages, and Programming - 39th International Colloquium (ICALP 2012), 230-241
11. 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, 361-372
12. Marek Cygan, Deterministic Parameterized Connected Vertex Cover.
Proc. of 13th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2012), 95-106
13. Stefan Kratsch, Marcin Pilipczuk, Ashutosh Rai, Venkatesh Raman.
Kernel Lower Bounds Using Co-nondeterminism: Finding Induced Hereditary Subgraphs. Proc. of 13th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2012), Lecture Notes in Computer Science 7357, 364-375.
14. 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, 3-12.
15. 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, 194-205.
16. 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, 296-307.
17. 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, 32-43.
18. Łukasz Kowalik, Nonblocker in H-minor free graphs: kernelization meets discharging
Proc. 7th International Symposium on Parameterized and Exact Computation (IPEC 2012),
LNCS 7535, 61-72, 2012.
[arXiv] [Publisher's version] [slides]
19. 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, 218-230, 2012.
[Publisher's version]
20. Łukasz Kowalik, Marcin Mucha, A 9k kernel for nonseparating independent set in planar graphs,
Proc. 38th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2012),
LNCS 7551, 160-171, 2012.
[arXiv] [Publisher's version] [slides]
21. Marek Cygan, Marcin Pilipczuk, Faster exponential-time 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)