Aktualne trendy w algorytmach parametryzowanych i wykładniczych
(Current trends in parameterized and exponentialtime algorithms)
Grant 2013/09/B/ST6/03136 funded by National Science Centre from 21.03.2014 to 20.03.2017
Publications  People involved  Guests
Selected publications of the project
 Marek Cygan, Daniel Lokshtanov, Marcin Pilipczuk, Michal
Pilipczuk, Saket Saurabh Minimum bisection is fixed parameter tractable
Proc. Symposium on Theory of Computing (STOC 2014)
[arXiv] [Publisher's version]Abstract: In the classic Minimum Bisection problem we are given as input a graph $G$ and an integer $k$. The task is to determine whether there is a partition of $V(G)$ into two parts $A$ and $B$ such that $AB \leq 1$ and there are at most $k$ edges with one endpoint in $A$ and the other in $B$. In this paper we give an algorithm for Minimum Bisection with running time $O(2^{O(k^{3})}n^3 \log^3 n)$. This is the first fixed parameter tractable algorithm for Minimum Bisection. At the core of our algorithm lies a new decomposition theorem that states that every graph $G$ can be decomposed by small separators into parts where each part is "highly connected" in the following sense: any cut of bounded size can separate only a limited number of vertices from each part of the decomposition. Our techniques generalize to the weighted setting, where we seek for a bisection of minimum weight among solutions that contain at most $k$ edges.
 Fedor V. Fomin, Daniel Lokshtanov, Dániel Marx, Marcin
Pilipczuk, Michal Pilipczuk, Saket Saurabh Subexponential Parameterized
Algorithms for Planar and ApexMinorFree Graphs via Low Treewidth Pattern
Covering
Proc. 57th Annual Symposium on Foundations of Computer Science, FOCS 2016
[arXiv] [Publisher's version]Abstract: We prove the following theorem. Given a planar graph $G$ and an integer $k$, it is possible in polynomial time to randomly sample a subset $A$ of vertices of $G$ with the following properties: (i) $A$ induces a subgraph of $G$ of treewidth $\mathcal{O}(\sqrt{k}\log k)$, and (ii) for every connected subgraph $H$ of $G$ on at most $k$ vertices, the probability that $A$ covers the whole vertex set of $H$ is at least $(2^{\mathcal{O}(\sqrt{k}\log^2 k)}\cdot n^{\mathcal{O}(1)})^{1}$, where $n$ is the number of vertices of $G$. Together with standard dynamic programming techniques for graphs of bounded treewidth, this result gives a versatile technique for obtaining (randomized) subexponential parameterized algorithms for problems on planar graphs, usually with running time bound $2^{\mathcal{O}(\sqrt{k} \log^2 k)} n^{\mathcal{O}(1)}$. The technique can be applied to problems expressible as searching for a small, connected pattern with a prescribed property in a large host graph, examples of such problems include Directed $k$Path, Weighted $k$Path, Vertex Cover Local Search, and Subgraph Isomorphism, among others. Up to this point, it was open whether these problems can be solved in subexponential parameterized time on planar graphs, because they are not amenable to the classic technique of bidimensionality. Furthermore, all our results hold in fact on any class of graphs that exclude a fixed apex graph as a minor, in particular on graphs embeddable in any fixed surface.
 Marek Cygan, Fedor V. Fomin, Alexander Golovnev, Alexander
S. Kulikov, Ivan Mihajlin, Jakub W. Pachocki, Arkadiusz Socala Tight
Lower Bounds on Graph Embedding Problems
Accepted to J. ACM. Conference version at SODA'16.
[arXiv]Abstract: We prove the following theorem. Given a planar graph $G$ and an integer $k$, it is possible in polynomial time to randomly sample a subset $A$ of vertices of $G$ with the following properties: (i) $A$ induces a subgraph of $G$ of treewidth $\mathcal{O}(\sqrt{k}\log k)$, and (ii) for every connected subgraph $H$ of $G$ on at most $k$ vertices, the probability that $A$ covers the whole vertex set of $H$ is at least $(2^{\mathcal{O}(\sqrt{k}\log^2 k)}\cdot n^{\mathcal{O}(1)})^{1}$, where $n$ is the number of vertices of $G$. Together with standard dynamic programming techniques for graphs of bounded treewidth, this result gives a versatile technique for obtaining (randomized) subexponential parameterized algorithms for problems on planar graphs, usually with running time bound $2^{\mathcal{O}(\sqrt{k} \log^2 k)} n^{\mathcal{O}(1)}$. The technique can be applied to problems expressible as searching for a small, connected pattern with a prescribed property in a large host graph, examples of such problems include Directed $k$Path, Weighted $k$Path, Vertex Cover Local Search, and Subgraph Isomorphism, among others. Up to this point, it was open whether these problems can be solved in subexponential parameterized time on planar graphs, because they are not amenable to the classic technique of bidimensionality. Furthermore, all our results hold in fact on any class of graphs that exclude a fixed apex graph as a minor, in particular on graphs embeddable in any fixed surface.
 Arkadiusz Socala, Tight lower bound for the channel
assignment problem.
ACM Transactions on Algorithms, Vol. 12, 2016, pp. 48:148:19
[DOI] [arXiv]
Conference version: Proceedings of the TwentySixth Annual ACMSIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, CA, USA, January 46, 2015
[Publisher's version]Abstract: We study the complexity of the Channel Assignment problem. A major open problem asks whether Channel Assignment admits an O(c^n)time algorithm, for a constant c independent of the weights on the edges. We answer this question in the negative i.e. we show that there is no 2^o(nlogn)time algorithm solving Channel Assignment unless the Exponential Time Hypothesis fails. Note that the currently best known algorithm works in time O*(n!)=2^O(nlogn) so our lower bound is tight.

Andreas Björklund, Vikram Kamat, Łukasz Kowalik and Meirav Zehavi, Spotting Trees with Few Leaves
SIAM Journal on Discrete Mathematics, 2017, Vol. 31, No. 2 : pp. 687713.
[DOI] [arXiv] [talk]
Conference version: Proc. ICALP 2015, pp. 243255.
[BibTeX] [DOI] [slides]
Remaining publications:

Hardness of approximation for strip packing, Anna Adamaszek,
Tomasz Kociumaka, Marcin Pilipczuk, Michal Pilipczuk
To appear in ACM Transactions on Computation Theory (TOCT).
[arxiv] 
Improving TSP tours using dynamic programming over tree
decomposition, Marek Cygan, Łukasz Kowalik and Arkadiusz Socala.
Manuscript.
[arXiv] 
Approximation and Parameterized Complexity of Minimax Approval
Voting, Marek Cygan, Lukasz Kowalik, Arkadiusz Socala, Krzysztof Sornat
Proceedings of the 31st AAAI Conference on Artificial Intelligence (AAAI'17), pp. 459465, AAAI Press, 2017.
[DOI] [arXiv] 
On the finegrained complexity of rainbow coloring, Łukasz
Kowalik, Juho Lauri and Arkadiusz Socala
ESA 2016.
[arXiv] [DOI] 
On finding rainbow and colorful paths, Łukasz Kowalik and Juho Lauri
Theor. Comput. Sci. 628: 110114 (2016)
[Publisher's version] 
Linear kernels for outbranching problems in sparse
digraphs, Marthe Bonamy, Łukasz Kowalik, Michal Pilipczuk and Arkadiusz Socala
IPEC'15. Journal version accepted to Algorithmica.

Engineering Motif Search for Large Graphs,
Andreas Björklund, Petteri Kaski, Łukasz Kowalik, Juho Lauri
Proc. 17th Workshop on Algorithm Engineering and Experiments, ALENEX 2015, SIAM, 2015, pp. 104118.
[PDF] [Publisher's version] 
A 13kkernel for Planar Feedback Vertex Set via Region
Decomposition, Marthe Bonamy, Łukasz Kowalik
Theor. Comput. Sci. 645: 2540 (2016)
[arXiv] [DOI]
Conference version: A 14kkernel for Planar Feedback Vertex Set via Region Decomposition Proc. 9th International Symposium on Parameterized and Exact Computation, IPEC'14, LNCS vol 8894, Springer, 97109, 2014.
[slides] 
Fast Witness
Extraction Using a Decision Oracle, Andreas Björklund, Petteri Kaski
and Łukasz Kowalik
Proc. 22th Annual European Symposium on Algorithms (ESA 2014), LNCS 8737, 2014, pp. 149160.
[Publisher's version] [BibTeX entry] [slides] 
Assigning channels via the
meetinthemiddle approach, Łukasz Kowalik and Arkadiusz Socala,
Algorithmica 74(4): 14351452 (2016) (open access).
[arXiv] [PDF] [DOI]
Conference version: Proc. 14th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2014), LNCS 8503, 2014, pp. 282293.
[Publisher's version]Abstract: We study the complexity of the CHANNEL ASSIGNMENT problem. By applying the meetinthemiddle approach we get an algorithm for the $\ell$bounded CHANNEL ASSIGNMENT (when the edge weights are bounded by $\ell$) running in time $O^*((2\sqrt{\ell+1})^n)$. This is the first algorithm which breaks the $(O(\ell))^n$ barrier. We extend this algorithm to the counting variant, at the cost of slightly higher polynomial factor. A major open problem asks whether CHANNEL ASSIGNMENT admits a $O(c^n)$time algorithm, for a constant $c$ independent of $\ell$. We consider a similar question for GENERALIZED TCOLORING, a CSP problem that generalizes CHANNEL ASSIGNMENT. We show that GENERALIZED TCOLORING does not admit a $2^{2^{o\left(\sqrt{n}\right)}} {\rm poly}(r)$time algorithm, where $r$ is the size of the instance.
People involved
 Marek Cygan
 Marcin Jakub Kamiński
 Łukasz Kowalik (PI)
 Marcin Pilipczuk
 Arkadiusz Socała
Guests hosted
 Marthe Bonamy (LIRMM, France)
 Juho Lauri (Tampere, Finland)