Lukasz Kowalik

homepage

Main menu: Home | Papers | Teaching | Projects |

Aktualne trendy w algorytmach parametryzowanych i wykładniczych
(Current trends in parameterized and exponential-time 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

  1. 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 $||A|-|B|| \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.

  2. Fedor V. Fomin, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, Saket Saurabh Subexponential Parameterized Algorithms for Planar and Apex-Minor-Free 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.

  3. 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.

  4. Arkadiusz Socala, Tight lower bound for the channel assignment problem.
    ACM Transactions on Algorithms, Vol. 12, 2016, pp. 48:1-48:19
    [DOI] [arXiv]
    Conference version: Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, CA, USA, January 4-6, 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.

  5. 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. 687-713.
    [DOI] [arXiv] [talk]
    Conference version: Proc. ICALP 2015, pp. 243-255.
    [BibTeX] [DOI] [slides]

Remaining publications:

  1. Hardness of approximation for strip packing, Anna Adamaszek, Tomasz Kociumaka, Marcin Pilipczuk, Michal Pilipczuk
    To appear in ACM Transactions on Computation Theory (TOCT).
    [arxiv]
  2. Improving TSP tours using dynamic programming over tree decomposition, Marek Cygan, Łukasz Kowalik and Arkadiusz Socala.
    Manuscript.
    [arXiv]
  3. 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. 459--465, AAAI Press, 2017.
    [DOI] [arXiv]
  4. On the fine-grained complexity of rainbow coloring, Łukasz Kowalik, Juho Lauri and Arkadiusz Socala
    ESA 2016.
    [arXiv] [DOI]
  5. On finding rainbow and colorful paths, Łukasz Kowalik and Juho Lauri
    Theor. Comput. Sci. 628: 110-114 (2016)
    [Publisher's version]
  6. Linear kernels for outbranching problems in sparse digraphs, Marthe Bonamy, Łukasz Kowalik, Michal Pilipczuk and Arkadiusz Socala
    IPEC'15. Journal version accepted to Algorithmica.
  7. 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. 104-118.
    [PDF] [Publisher's version]
  8. A 13k-kernel for Planar Feedback Vertex Set via Region Decomposition, Marthe Bonamy, Łukasz Kowalik
    Theor. Comput. Sci. 645: 25-40 (2016)
    [arXiv] [DOI]
    Conference version: A 14k-kernel for Planar Feedback Vertex Set via Region Decomposition Proc. 9th International Symposium on Parameterized and Exact Computation, IPEC'14, LNCS vol 8894, Springer, 97-109, 2014.
    [slides]
  9. 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. 149-160.
    [Publisher's version] [BibTeX entry] [slides]
  10. Assigning channels via the meet-in-the-middle approach, Łukasz Kowalik and Arkadiusz Socala,
    Algorithmica 74(4): 1435-1452 (2016) (open access).
    [arXiv] [PDF] [DOI]
    Conference version: Proc. 14th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2014), LNCS 8503, 2014, pp. 282-293.
    [Publisher's version]

    Abstract: We study the complexity of the CHANNEL ASSIGNMENT problem. By applying the meet-in-the-middle 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 T-COLORING, a CSP problem that generalizes CHANNEL ASSIGNMENT. We show that GENERALIZED T-COLORING 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

Guests hosted