27 Search Results for "Kowalik, Łukasz"


Document
An Asymptotically Fast Polynomial Space Algorithm for Hamiltonicity Detection in Sparse Directed Graphs

Authors: Andreas Björklund

Published in: LIPIcs, Volume 187, 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)


Abstract
We present a polynomial space Monte Carlo algorithm that given a directed graph on n vertices and average outdegree δ, detects if the graph has a Hamiltonian cycle in 2^{n-Ω(n/δ)} time. This asymptotic scaling of the savings in the running time matches the fastest known exponential space algorithm by Björklund and Williams ICALP 2019. By comparison, the previously best polynomial space algorithm by Kowalik and Majewski IPEC 2020 guarantees a 2^{n-Ω(n/(2^δ))} time bound. Our algorithm combines for the first time the idea of obtaining a fingerprint of the presence of a Hamiltonian cycle through an inclusion-exclusion summation over the Laplacian of the graph from Björklund, Kaski, and Koutis ICALP 2017, with the idea of sieving for the non-zero terms in an inclusion-exclusion summation by listing solutions to systems of linear equations over ℤ₂ from Björklund and Husfeldt FOCS 2013.

Cite as

Andreas Björklund. An Asymptotically Fast Polynomial Space Algorithm for Hamiltonicity Detection in Sparse Directed Graphs. In 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 187, pp. 15:1-15:12, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)


Copy BibTex To Clipboard

@InProceedings{bjorklund:LIPIcs.STACS.2021.15,
  author =	{Bj\"{o}rklund, Andreas},
  title =	{{An Asymptotically Fast Polynomial Space Algorithm for Hamiltonicity Detection in Sparse Directed Graphs}},
  booktitle =	{38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)},
  pages =	{15:1--15:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-180-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{187},
  editor =	{Bl\"{a}ser, Markus and Monmege, Benjamin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2021.15},
  URN =		{urn:nbn:de:0030-drops-136601},
  doi =		{10.4230/LIPIcs.STACS.2021.15},
  annote =	{Keywords: Hamiltonian cycle, directed graph, worst case analysis algorithm}
}
Document
The Asymmetric Travelling Salesman Problem In Sparse Digraphs

Authors: Łukasz Kowalik and Konrad Majewski

Published in: LIPIcs, Volume 180, 15th International Symposium on Parameterized and Exact Computation (IPEC 2020)


Abstract
Asymmetric Travelling Salesman Problem (ATSP) and its special case Directed Hamiltonicity are among the most fundamental problems in computer science. The dynamic programming algorithm running in time 𝒪^*(2ⁿ) developed almost 60 years ago by Bellman, Held and Karp, is still the state of the art for both of these problems. In this work we focus on sparse digraphs. First, we recall known approaches for Undirected Hamiltonicity and TSP in sparse graphs and we analyse their consequences for Directed Hamiltonicity and ATSP in sparse digraphs, either by adapting the algorithm, or by using reductions. In this way, we get a number of running time upper bounds for a few classes of sparse digraphs, including 𝒪^*(2^(n/3)) for digraphs with both out- and indegree bounded by 2, and 𝒪^*(3^(n/2)) for digraphs with outdegree bounded by 3. Our main results are focused on digraphs of bounded average outdegree d. The baseline for ATSP here is a simple enumeration of cycle covers which can be done in time bounded by 𝒪^*(μ(d)ⁿ) for a function μ(d) ≤ (⌈d⌉!)^(1/⌈d⌉). One can also observe that Directed Hamiltonicity can be solved in randomized time 𝒪^*((2-2^(-d))ⁿ) and polynomial space, by adapting a recent result of Björklund [ISAAC 2018] stated originally for Undirected Hamiltonicity in sparse bipartite graphs. We present two new deterministic algorithms for ATSP: the first running in time 𝒪(2^(0.441(d-1)n)) and polynomial space, and the second in exponential space with running time of 𝒪^*(τ(d)^(n/2)) for a function τ(d) ≤ d.

Cite as

Łukasz Kowalik and Konrad Majewski. The Asymmetric Travelling Salesman Problem In Sparse Digraphs. In 15th International Symposium on Parameterized and Exact Computation (IPEC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 180, pp. 23:1-23:18, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)


Copy BibTex To Clipboard

@InProceedings{kowalik_et_al:LIPIcs.IPEC.2020.23,
  author =	{Kowalik, {\L}ukasz and Majewski, Konrad},
  title =	{{The Asymmetric Travelling Salesman Problem In Sparse Digraphs}},
  booktitle =	{15th International Symposium on Parameterized and Exact Computation (IPEC 2020)},
  pages =	{23:1--23:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-172-6},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{180},
  editor =	{Cao, Yixin and Pilipczuk, Marcin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2020.23},
  URN =		{urn:nbn:de:0030-drops-133269},
  doi =		{10.4230/LIPIcs.IPEC.2020.23},
  annote =	{Keywords: asymmetric traveling salesman problem, Hamiltonian cycle, sparse graphs, exponential algorithm}
}
Document
The PACE 2020 Parameterized Algorithms and Computational Experiments Challenge: Treedepth

Authors: Łukasz Kowalik, Marcin Mucha, Wojciech Nadara, Marcin Pilipczuk, Manuel Sorge, and Piotr Wygocki

Published in: LIPIcs, Volume 180, 15th International Symposium on Parameterized and Exact Computation (IPEC 2020)


Abstract
This year’s Parameterized Algorithms and Computational Experiments challenge (PACE 2020) was devoted to the problem of computing the treedepth of a given graph. Altogether 51 participants from 20 teams, 12 countries and 3 continents submitted their implementations to the competition. In this report, we describe the setup of the challenge, the selection of benchmark instances and the ranking of the participating teams. We also briefly discuss the approaches used in the submitted solvers and the differences in their performance on our benchmark dataset.

Cite as

Łukasz Kowalik, Marcin Mucha, Wojciech Nadara, Marcin Pilipczuk, Manuel Sorge, and Piotr Wygocki. The PACE 2020 Parameterized Algorithms and Computational Experiments Challenge: Treedepth. In 15th International Symposium on Parameterized and Exact Computation (IPEC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 180, pp. 37:1-37:18, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)


Copy BibTex To Clipboard

@InProceedings{kowalik_et_al:LIPIcs.IPEC.2020.37,
  author =	{Kowalik, {\L}ukasz and Mucha, Marcin and Nadara, Wojciech and Pilipczuk, Marcin and Sorge, Manuel and Wygocki, Piotr},
  title =	{{The PACE 2020 Parameterized Algorithms and Computational Experiments Challenge: Treedepth}},
  booktitle =	{15th International Symposium on Parameterized and Exact Computation (IPEC 2020)},
  pages =	{37:1--37:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-172-6},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{180},
  editor =	{Cao, Yixin and Pilipczuk, Marcin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2020.37},
  URN =		{urn:nbn:de:0030-drops-133404},
  doi =		{10.4230/LIPIcs.IPEC.2020.37},
  annote =	{Keywords: computing treedepth, contest, implementation challenge, FPT}
}
Document
Many Visits TSP Revisited

Authors: Łukasz Kowalik, Shaohua Li, Wojciech Nadara, Marcin Smulewicz, and Magnus Wahlström

Published in: LIPIcs, Volume 173, 28th Annual European Symposium on Algorithms (ESA 2020)


Abstract
We study the Many Visits TSP problem, where given a number k(v) for each of n cities and pairwise (possibly asymmetric) integer distances, one has to find an optimal tour that visits each city v exactly k(v) times. The currently fastest algorithm is due to Berger, Kozma, Mnich and Vincze [SODA 2019, TALG 2020] and runs in time and space O*(5ⁿ). They also show a polynomial space algorithm running in time O(16^{n+o(n)}). In this work, we show three main results: - A randomized polynomial space algorithm in time O*(2^n D), where D is the maximum distance between two cities. By using standard methods, this results in a (1+ε)-approximation in time O*(2ⁿε^{-1}). Improving the constant 2 in these results would be a major breakthrough, as it would result in improving the O*(2ⁿ)-time algorithm for Directed Hamiltonian Cycle, which is a 50 years old open problem. - A tight analysis of Berger et al.’s exponential space algorithm, resulting in an O*(4ⁿ) running time bound. - A new polynomial space algorithm, running in time O(7.88ⁿ).

Cite as

Łukasz Kowalik, Shaohua Li, Wojciech Nadara, Marcin Smulewicz, and Magnus Wahlström. Many Visits TSP Revisited. In 28th Annual European Symposium on Algorithms (ESA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 173, pp. 66:1-66:22, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)


Copy BibTex To Clipboard

@InProceedings{kowalik_et_al:LIPIcs.ESA.2020.66,
  author =	{Kowalik, {\L}ukasz and Li, Shaohua and Nadara, Wojciech and Smulewicz, Marcin and Wahlstr\"{o}m, Magnus},
  title =	{{Many Visits TSP Revisited}},
  booktitle =	{28th Annual European Symposium on Algorithms (ESA 2020)},
  pages =	{66:1--66:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-162-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{173},
  editor =	{Grandoni, Fabrizio and Herman, Grzegorz and Sanders, Peter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2020.66},
  URN =		{urn:nbn:de:0030-drops-129329},
  doi =		{10.4230/LIPIcs.ESA.2020.66},
  annote =	{Keywords: many visits traveling salesman problem, exponential algorithm}
}
Document
Fine-Grained Complexity of k-OPT in Bounded-Degree Graphs for Solving TSP

Authors: Édouard Bonnet, Yoichi Iwata, Bart M. P. Jansen, and Łukasz Kowalik

Published in: LIPIcs, Volume 144, 27th Annual European Symposium on Algorithms (ESA 2019)


Abstract
The Traveling Salesman Problem asks to find a minimum-weight Hamiltonian cycle in an edge-weighted complete graph. Local search is a widely-employed strategy for finding good solutions to TSP. A popular neighborhood operator for local search is k-opt, which turns a Hamiltonian cycle C into a new Hamiltonian cycle C' by replacing k edges. We analyze the problem of determining whether the weight of a given cycle can be decreased by a k-opt move. Earlier work has shown that (i) assuming the Exponential Time Hypothesis, there is no algorithm that can detect whether or not a given Hamiltonian cycle C in an n-vertex input can be improved by a k-opt move in time f(k) n^o(k / log k) for any function f, while (ii) it is possible to improve on the brute-force running time of O(n^k) and save linear factors in the exponent. Modern TSP heuristics are very successful at identifying the most promising edges to be used in k-opt moves, and experiments show that very good global solutions can already be reached using only the top-O(1) most promising edges incident to each vertex. This leads to the following question: can improving k-opt moves be found efficiently in graphs of bounded degree? We answer this question in various regimes, presenting new algorithms and conditional lower bounds. We show that the aforementioned ETH lower bound also holds for graphs of maximum degree three, but that in bounded-degree graphs the best improving k-move can be found in time O(n^((23/135+epsilon_k)k)), where lim_{k -> infty} epsilon_k = 0. This improves upon the best-known bounds for general graphs. Due to its practical importance, we devote special attention to the range of k in which improving k-moves in bounded-degree graphs can be found in quasi-linear time. For k <= 7, we give quasi-linear time algorithms for general weights. For k=8 we obtain a quasi-linear time algorithm when the weights are bounded by O(polylog n). On the other hand, based on established fine-grained complexity hypotheses about the impossibility of detecting a triangle in edge-linear time, we prove that the k = 9 case does not admit quasi-linear time algorithms. Hence we fully characterize the values of k for which quasi-linear time algorithms exist for polylogarithmic weights on bounded-degree graphs.

Cite as

Édouard Bonnet, Yoichi Iwata, Bart M. P. Jansen, and Łukasz Kowalik. Fine-Grained Complexity of k-OPT in Bounded-Degree Graphs for Solving TSP. In 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 144, pp. 23:1-23:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)


Copy BibTex To Clipboard

@InProceedings{bonnet_et_al:LIPIcs.ESA.2019.23,
  author =	{Bonnet, \'{E}douard and Iwata, Yoichi and Jansen, Bart M. P. and Kowalik, {\L}ukasz},
  title =	{{Fine-Grained Complexity of k-OPT in Bounded-Degree Graphs for Solving TSP}},
  booktitle =	{27th Annual European Symposium on Algorithms (ESA 2019)},
  pages =	{23:1--23:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-124-5},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{144},
  editor =	{Bender, Michael A. and Svensson, Ola and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2019.23},
  URN =		{urn:nbn:de:0030-drops-111444},
  doi =		{10.4230/LIPIcs.ESA.2019.23},
  annote =	{Keywords: traveling salesman problem, k-OPT, bounded degree}
}
Document
Reducing the Domination Number of Graphs via Edge Contractions

Authors: Esther Galby, Paloma T. Lima, and Bernard Ries

Published in: LIPIcs, Volume 138, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)


Abstract
In this paper, we study the following problem: given a connected graph G, can we reduce the domination number of G by at least one using k edge contractions, for some fixed integer k >= 0? We show that for k <= 2, the problem is coNP-hard. We further prove that for k=1, the problem is W[1]-hard parameterized by the size of a minimum dominating set plus the mim-width of the input graph, and that it remains NP-hard when restricted to P_9-free graphs, bipartite graphs and {C_3,...,C_{l}}-free graphs for any l >= 3. Finally, we show that for any k >= 1, the problem is polynomial-time solvable for P_5-free graphs and that it can be solved in FPT-time and XP-time when parameterized by tree-width and mim-width, respectively.

Cite as

Esther Galby, Paloma T. Lima, and Bernard Ries. Reducing the Domination Number of Graphs via Edge Contractions. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 41:1-41:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)


Copy BibTex To Clipboard

@InProceedings{galby_et_al:LIPIcs.MFCS.2019.41,
  author =	{Galby, Esther and Lima, Paloma T. and Ries, Bernard},
  title =	{{Reducing the Domination Number of Graphs via Edge Contractions}},
  booktitle =	{44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)},
  pages =	{41:1--41:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-117-7},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{138},
  editor =	{Rossmanith, Peter and Heggernes, Pinar and Katoen, Joost-Pieter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2019.41},
  URN =		{urn:nbn:de:0030-drops-109856},
  doi =		{10.4230/LIPIcs.MFCS.2019.41},
  annote =	{Keywords: domination number, blocker problem, graph classes}
}
Document
A Complexity Dichotomy for Critical Values of the b-Chromatic Number of Graphs

Authors: Lars Jaffke and Paloma T. Lima

Published in: LIPIcs, Volume 138, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)


Abstract
A b-coloring of a graph G is a proper coloring of its vertices such that each color class contains a vertex that has at least one neighbor in all the other color classes. The b-Coloring problem asks whether a graph G has a b-coloring with k colors. The b-chromatic number of a graph G, denoted by chi_b(G), is the maximum number k such that G admits a b-coloring with k colors. We consider the complexity of the b-Coloring problem, whenever the value of k is close to one of two upper bounds on chi_b(G): The maximum degree Delta(G) plus one, and the m-degree, denoted by m(G), which is defined as the maximum number i such that G has i vertices of degree at least i-1. We obtain a dichotomy result for all fixed k in N when k is close to one of the two above mentioned upper bounds. Concretely, we show that if k in {Delta(G) + 1 - p, m(G) - p}, the problem is polynomial-time solvable whenever p in {0, 1} and, even when k = 3, it is NP-complete whenever p >= 2. We furthermore consider parameterizations of the b-Coloring problem that involve the maximum degree Delta(G) of the input graph G and give two FPT-algorithms. First, we show that deciding whether a graph G has a b-coloring with m(G) colors is FPT parameterized by Delta(G). Second, we show that b-Coloring{} is FPT parameterized by Delta(G) + l_k(G), where l_k(G) denotes the number of vertices of degree at least k.

Cite as

Lars Jaffke and Paloma T. Lima. A Complexity Dichotomy for Critical Values of the b-Chromatic Number of Graphs. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 34:1-34:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)


Copy BibTex To Clipboard

@InProceedings{jaffke_et_al:LIPIcs.MFCS.2019.34,
  author =	{Jaffke, Lars and Lima, Paloma T.},
  title =	{{A Complexity Dichotomy for Critical Values of the b-Chromatic Number of Graphs}},
  booktitle =	{44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)},
  pages =	{34:1--34:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-117-7},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{138},
  editor =	{Rossmanith, Peter and Heggernes, Pinar and Katoen, Joost-Pieter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2019.34},
  URN =		{urn:nbn:de:0030-drops-109784},
  doi =		{10.4230/LIPIcs.MFCS.2019.34},
  annote =	{Keywords: b-Coloring, b-Chromatic Number}
}
Document
Parameterized Complexity of Fair Vertex Evaluation Problems

Authors: Dušan Knop, Tomáš Masařík, and Tomáš Toufar

Published in: LIPIcs, Volume 138, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)


Abstract
A prototypical graph problem is centered around a graph-theoretic property for a set of vertices and a solution to it is a set of vertices for which the desired property holds. The task is to decide whether, in the given graph, there exists a solution of a certain quality, where we use size as a quality measure. In this work, we are changing the measure to the fair measure (cf. Lin and Sahni [Li-Shin Lin and Sartaj Sahni, 1989]). The fair measure of a set of vertices S is (at most) k if the number of neighbors in the set S of any vertex (in the input graph) does not exceed k. One possible way to study graph problems is by defining the property in a certain logic. For a given objective, an evaluation problem is to find a set (of vertices) that simultaneously minimizes the assumed measure and satisfies an appropriate formula. More formally, we study the {MSO} Fair Vertex Evaluation, where the graph-theoretic property is described by an {MSO} formula. In the presented paper we show that there is an FPT algorithm for the {MSO} Fair Vertex Evaluation problem for formulas with one free variable parameterized by the twin cover number of the input graph and the size of the formula. One may define an extended variant of {MSO} Fair Vertex Evaluation for formulas with l free variables; here we measure a maximum number of neighbors in each of the l sets. However, such variant is {W[1]}-hard for parameter l even on graphs with twin cover one. Furthermore, we study the Fair Vertex Cover (Fair VC) problem. Fair VC is among the simplest problems with respect to the demanded property (i.e., the rest forms an edgeless graph). On the negative side, Fair VC is {W[1]}-hard when parameterized by both treedepth and feedback vertex set of the input graph. On the positive side, we provide an FPT algorithm for the parameter modular width.

Cite as

Dušan Knop, Tomáš Masařík, and Tomáš Toufar. Parameterized Complexity of Fair Vertex Evaluation Problems. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 33:1-33:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)


Copy BibTex To Clipboard

@InProceedings{knop_et_al:LIPIcs.MFCS.2019.33,
  author =	{Knop, Du\v{s}an and Masa\v{r}{\'\i}k, Tom\'{a}\v{s} and Toufar, Tom\'{a}\v{s}},
  title =	{{Parameterized Complexity of Fair Vertex Evaluation Problems}},
  booktitle =	{44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)},
  pages =	{33:1--33:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-117-7},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{138},
  editor =	{Rossmanith, Peter and Heggernes, Pinar and Katoen, Joost-Pieter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2019.33},
  URN =		{urn:nbn:de:0030-drops-109775},
  doi =		{10.4230/LIPIcs.MFCS.2019.33},
  annote =	{Keywords: Fair objective, metatheorem, fair vertex cover, twin cover, modular width}
}
Document
Faster FPT Algorithm for 5-Path Vertex Cover

Authors: Radovan Červený and Ondřej Suchý

Published in: LIPIcs, Volume 138, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)


Abstract
The problem of d-Path Vertex Cover, d-PVC lies in determining a subset F of vertices of a given graph G=(V,E) such that G \ F does not contain a path on d vertices. The paths we aim to cover need not to be induced. It is known that the d-PVC problem is NP-complete for any d >= 2. When parameterized by the size of the solution k, 5-PVC has direct trivial algorithm with O(5^kn^{O(1)}) running time and, since d-PVC is a special case of d-Hitting Set, an algorithm running in O(4.0755^kn^{O(1)}) time is known. In this paper we present an iterative compression algorithm that solves the 5-PVC problem in O(4^kn^{O(1)}) time.

Cite as

Radovan Červený and Ondřej Suchý. Faster FPT Algorithm for 5-Path Vertex Cover. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 32:1-32:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)


Copy BibTex To Clipboard

@InProceedings{cerveny_et_al:LIPIcs.MFCS.2019.32,
  author =	{\v{C}erven\'{y}, Radovan and Such\'{y}, Ond\v{r}ej},
  title =	{{Faster FPT Algorithm for 5-Path Vertex Cover}},
  booktitle =	{44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)},
  pages =	{32:1--32:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-117-7},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{138},
  editor =	{Rossmanith, Peter and Heggernes, Pinar and Katoen, Joost-Pieter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2019.32},
  URN =		{urn:nbn:de:0030-drops-109761},
  doi =		{10.4230/LIPIcs.MFCS.2019.32},
  annote =	{Keywords: graph algorithms, Hitting Set, iterative compression, parameterized complexity, d-Path Vertex Cover}
}
Document
Measuring what Matters: A Hybrid Approach to Dynamic Programming with Treewidth

Authors: Eduard Eiben, Robert Ganian, Thekla Hamm, and O-joung Kwon

Published in: LIPIcs, Volume 138, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)


Abstract
We develop a framework for applying treewidth-based dynamic programming on graphs with "hybrid structure", i.e., with parts that may not have small treewidth but instead possess other structural properties. Informally, this is achieved by defining a refinement of treewidth which only considers parts of the graph that do not belong to a pre-specified tractable graph class. Our approach allows us to not only generalize existing fixed-parameter algorithms exploiting treewidth, but also fixed-parameter algorithms which use the size of a modulator as their parameter. As the flagship application of our framework, we obtain a parameter that combines treewidth and rank-width to obtain fixed-parameter algorithms for Chromatic Number, Hamiltonian Cycle, and Max-Cut.

Cite as

Eduard Eiben, Robert Ganian, Thekla Hamm, and O-joung Kwon. Measuring what Matters: A Hybrid Approach to Dynamic Programming with Treewidth. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 42:1-42:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)


Copy BibTex To Clipboard

@InProceedings{eiben_et_al:LIPIcs.MFCS.2019.42,
  author =	{Eiben, Eduard and Ganian, Robert and Hamm, Thekla and Kwon, O-joung},
  title =	{{Measuring what Matters: A Hybrid Approach to Dynamic Programming with Treewidth}},
  booktitle =	{44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)},
  pages =	{42:1--42:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-117-7},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{138},
  editor =	{Rossmanith, Peter and Heggernes, Pinar and Katoen, Joost-Pieter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2019.42},
  URN =		{urn:nbn:de:0030-drops-109867},
  doi =		{10.4230/LIPIcs.MFCS.2019.42},
  annote =	{Keywords: Parameterized complexity, treewidth, rank-width, fixed-parameter algorithms}
}
Document
Enumeration of Preferred Extensions in Almost Oriented Digraphs

Authors: Serge Gaspers and Ray Li

Published in: LIPIcs, Volume 138, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)


Abstract
In this paper, we present enumeration algorithms to list all preferred extensions of an argumentation framework. This task is equivalent to enumerating all maximal semikernels of a directed graph. For directed graphs on n vertices, all preferred extensions can be enumerated in O^*(3^{n/3}) time and there are directed graphs with Omega(3^{n/3}) preferred extensions. We give faster enumeration algorithms for directed graphs with at most 0.8004 * n vertices occurring in 2-cycles. In particular, for oriented graphs (digraphs with no 2-cycles) one of our algorithms runs in time O(1.2321^n), and we show that there are oriented graphs with Omega(3^{n/6}) > Omega(1.2009^n) preferred extensions. A combination of three algorithms leads to the fastest enumeration times for various proportions of the number of vertices in 2-cycles. The most innovative one is a new 2-stage sampling algorithm, combined with a new parameterized enumeration algorithm, analyzed with a combination of the recent monotone local search technique (STOC 2016) and an extension thereof (ICALP 2017).

Cite as

Serge Gaspers and Ray Li. Enumeration of Preferred Extensions in Almost Oriented Digraphs. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 74:1-74:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)


Copy BibTex To Clipboard

@InProceedings{gaspers_et_al:LIPIcs.MFCS.2019.74,
  author =	{Gaspers, Serge and Li, Ray},
  title =	{{Enumeration of Preferred Extensions in Almost Oriented Digraphs}},
  booktitle =	{44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)},
  pages =	{74:1--74:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-117-7},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{138},
  editor =	{Rossmanith, Peter and Heggernes, Pinar and Katoen, Joost-Pieter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2019.74},
  URN =		{urn:nbn:de:0030-drops-110188},
  doi =		{10.4230/LIPIcs.MFCS.2019.74},
  annote =	{Keywords: abstract argumentation, exact algorithms, exponential time algorithms, parameterized algorithms, enumeration algorithms, semikernels in digraphs}
}
Document
Parameterized Complexity of Conflict-Free Matchings and Paths

Authors: Akanksha Agrawal, Pallavi Jain, Lawqueen Kanesh, and Saket Saurabh

Published in: LIPIcs, Volume 138, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)


Abstract
An input to a conflict-free variant of a classical problem Gamma, called Conflict-Free Gamma, consists of an instance I of Gamma coupled with a graph H, called the conflict graph. A solution to Conflict-Free Gamma in (I,H) is a solution to I in Gamma, which is also an independent set in H. In this paper, we study conflict-free variants of Maximum Matching and Shortest Path, which we call Conflict-Free Matching (CF-Matching) and Conflict-Free Shortest Path (CF-SP), respectively. We show that both CF-Matching and CF-SP are W[1]-hard, when parameterized by the solution size. Moreover, W[1]-hardness for CF-Matching holds even when the input graph where we want to find a matching is itself a matching, and W[1]-hardness for CF-SP holds for conflict graph being a unit-interval graph. Next, we study these problems with restriction on the conflict graphs. We give FPT algorithms for CF-Matching when the conflict graph is chordal. Also, we give FPT algorithms for both CF-Matching and CF-SP, when the conflict graph is d-degenerate. Finally, we design FPT algorithms for variants of CF-Matching and CF-SP, where the conflicting conditions are given by a (representable) matroid.

Cite as

Akanksha Agrawal, Pallavi Jain, Lawqueen Kanesh, and Saket Saurabh. Parameterized Complexity of Conflict-Free Matchings and Paths. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 35:1-35:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)


Copy BibTex To Clipboard

@InProceedings{agrawal_et_al:LIPIcs.MFCS.2019.35,
  author =	{Agrawal, Akanksha and Jain, Pallavi and Kanesh, Lawqueen and Saurabh, Saket},
  title =	{{Parameterized Complexity of Conflict-Free Matchings and Paths}},
  booktitle =	{44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)},
  pages =	{35:1--35:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-117-7},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{138},
  editor =	{Rossmanith, Peter and Heggernes, Pinar and Katoen, Joost-Pieter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2019.35},
  URN =		{urn:nbn:de:0030-drops-109798},
  doi =		{10.4230/LIPIcs.MFCS.2019.35},
  annote =	{Keywords: Conflict-free, Matching, Shortest Path, FPT algorithm, W\lbrack1\rbrack-hard, Matroid}
}
Document
Parameterization of Tensor Network Contraction

Authors: Bryan O'Gorman

Published in: LIPIcs, Volume 135, 14th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2019)


Abstract
We present a conceptually clear and algorithmically useful framework for parameterizing the costs of tensor network contraction. Our framework is completely general, applying to tensor networks with arbitrary bond dimensions, open legs, and hyperedges. The fundamental objects of our framework are rooted and unrooted contraction trees, which represent classes of contraction orders. Properties of a contraction tree correspond directly and precisely to the time and space costs of tensor network contraction. The properties of rooted contraction trees give the costs of parallelized contraction algorithms. We show how contraction trees relate to existing tree-like objects in the graph theory literature, bringing to bear a wide range of graph algorithms and tools to tensor network contraction. Independent of tensor networks, we show that the edge congestion of a graph is almost equal to the branchwidth of its line graph.

Cite as

Bryan O'Gorman. Parameterization of Tensor Network Contraction. In 14th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 135, pp. 10:1-10:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)


Copy BibTex To Clipboard

@InProceedings{ogorman:LIPIcs.TQC.2019.10,
  author =	{O'Gorman, Bryan},
  title =	{{Parameterization of Tensor Network Contraction}},
  booktitle =	{14th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2019)},
  pages =	{10:1--10:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-112-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{135},
  editor =	{van Dam, Wim and Man\v{c}inska, Laura},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2019.10},
  URN =		{urn:nbn:de:0030-drops-104025},
  doi =		{10.4230/LIPIcs.TQC.2019.10},
  annote =	{Keywords: tensor networks, parameterized complexity, tree embedding, congestion}
}
Document
Tight Lower Bounds for List Edge Coloring

Authors: Lukasz Kowalik and Arkadiusz Socala

Published in: LIPIcs, Volume 101, 16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018)


Abstract
The fastest algorithms for edge coloring run in time 2^m n^{O(1)}, where m and n are the number of edges and vertices of the input graph, respectively. For dense graphs, this bound becomes 2^{Theta(n^2)}. This is a somewhat unique situation, since most of the studied graph problems admit algorithms running in time 2^{O(n log n)}. It is a notorious open problem to either show an algorithm for edge coloring running in time 2^{o(n^2)} or to refute it, assuming the Exponential Time Hypothesis (ETH) or other well established assumptions. We notice that the same question can be asked for list edge coloring, a well-studied generalization of edge coloring where every edge comes with a set (often called a list) of allowed colors. Our main result states that list edge coloring for simple graphs does not admit an algorithm running in time 2^{o(n^2)}, unless ETH fails. Interestingly, the algorithm for edge coloring running in time 2^m n^{O(1)} generalizes to the list version without any asymptotic slow-down. Thus, our lower bound is essentially tight. This also means that in order to design an algorithm running in time 2^{o(n^2)} for edge coloring, one has to exploit its special features compared to the list version.

Cite as

Lukasz Kowalik and Arkadiusz Socala. Tight Lower Bounds for List Edge Coloring. In 16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 101, pp. 28:1-28:12, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)


Copy BibTex To Clipboard

@InProceedings{kowalik_et_al:LIPIcs.SWAT.2018.28,
  author =	{Kowalik, Lukasz and Socala, Arkadiusz},
  title =	{{Tight Lower Bounds for List Edge Coloring}},
  booktitle =	{16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018)},
  pages =	{28:1--28:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-068-2},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{101},
  editor =	{Eppstein, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2018.28},
  URN =		{urn:nbn:de:0030-drops-88540},
  doi =		{10.4230/LIPIcs.SWAT.2018.28},
  annote =	{Keywords: list edge coloring, complexity, ETH lower bound}
}
Document
Tight Lower Bounds for the Complexity of Multicoloring

Authors: Marthe Bonamy, Lukasz Kowalik, Michal Pilipczuk, Arkadiusz Socala, and Marcin Wrochna

Published in: LIPIcs, Volume 87, 25th Annual European Symposium on Algorithms (ESA 2017)


Abstract
In the multicoloring problem, also known as (a:b)-coloring or b-fold coloring, we are given a graph G and a set of a colors, and the task is to assign a subset of b colors to each vertex of G so that adjacent vertices receive disjoint color subsets. This natural generalization of the classic coloring problem (the b=1 case) is equivalent to finding a homomorphism to the Kneser graph KG_{a,b}, and gives relaxations approaching the fractional chromatic number. We study the complexity of determining whether a graph has an (a:b)-coloring. Our main result is that this problem does not admit an algorithm with running time f(b) * 2^{o(log b) n}, for any computable f(b), unless the Exponential Time Hypothesis (ETH) fails. A (b+1)^n * poly(n)-time algorithm due to Nederlof [2008] shows that this is tight. A direct corollary of our result is that the graph homomorphism problem does not admit a 2^O(n+h) algorithm unless ETH fails, even if the target graph is required to be a Kneser graph. This refines the understanding given by the recent lower bound of Cygan et al. [SODA 2016]. The crucial ingredient in our hardness reduction is the usage of detecting matrices of Lindström [Canad. Math. Bull., 1965], which is a combinatorial tool that, to the best of our knowledge, has not yet been used for proving complexity lower bounds. As a side result, we prove that the running time of the algorithms of Abasi et al. [MFCS 2014] and of Gabizon et al. [ESA 2015] for the r-monomial detection problem are optimal under ETH.

Cite as

Marthe Bonamy, Lukasz Kowalik, Michal Pilipczuk, Arkadiusz Socala, and Marcin Wrochna. Tight Lower Bounds for the Complexity of Multicoloring. In 25th Annual European Symposium on Algorithms (ESA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 87, pp. 18:1-18:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2017)


Copy BibTex To Clipboard

@InProceedings{bonamy_et_al:LIPIcs.ESA.2017.18,
  author =	{Bonamy, Marthe and Kowalik, Lukasz and Pilipczuk, Michal and Socala, Arkadiusz and Wrochna, Marcin},
  title =	{{Tight Lower Bounds for the Complexity of Multicoloring}},
  booktitle =	{25th Annual European Symposium on Algorithms (ESA 2017)},
  pages =	{18:1--18:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-049-1},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{87},
  editor =	{Pruhs, Kirk and Sohler, Christian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2017.18},
  URN =		{urn:nbn:de:0030-drops-78527},
  doi =		{10.4230/LIPIcs.ESA.2017.18},
  annote =	{Keywords: multicoloring, Kneser graph homomorphism, ETH lower bound}
}
  • Refine by Author
  • 7 Kowalik, Lukasz
  • 5 Socala, Arkadiusz
  • 4 Kowalik, Łukasz
  • 3 Saurabh, Saket
  • 2 Björklund, Andreas
  • Show More...

  • Refine by Classification
  • 8 Theory of computation → Parameterized complexity and exact algorithms
  • 7 Theory of computation → Graph algorithms analysis
  • 3 Theory of computation → Fixed parameter tractability
  • 2 Mathematics of computing → Graph coloring
  • 1 Computing methodologies → Knowledge representation and reasoning
  • Show More...

  • Refine by Keyword
  • 4 parameterized complexity
  • 4 treewidth
  • 3 FPT algorithm
  • 2 ETH lower bound
  • 2 FPT
  • Show More...

  • Refine by Type
  • 27 document

  • Refine by Publication Year
  • 9 2019
  • 8 2015
  • 3 2020
  • 2 2017
  • 1 2008
  • Show More...

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail