Search Results

Documents authored by van Leeuwen, Erik Jan

Document
DOI: 10.4230/LIPIcs.SoCG.2024.67
Separator Theorem and Algorithms for Planar Hyperbolic Graphs

Authors: Sándor Kisfaludi-Bak, Jana Masaříková, Erik Jan van Leeuwen, Bartosz Walczak, and Karol Węgrzycki

Published in: LIPIcs, Volume 293, 40th International Symposium on Computational Geometry (SoCG 2024)

Abstract
The hyperbolicity of a graph, informally, measures how close a graph is (metrically) to a tree. Hence, it is intuitively similar to treewidth, but the measures are formally incomparable. Motivated by the broad study of algorithms and separators on planar graphs and their relation to treewidth, we initiate the study of planar graphs of bounded hyperbolicity. Our main technical contribution is a novel balanced separator theorem for planar δ-hyperbolic graphs that is substantially stronger than the classic planar separator theorem. For any fixed δ ⩾ 0, we can find a small balanced separator that induces either a single geodesic (shortest) path or a single geodesic cycle in the graph. An important advantage of our separator is that the union of our separator (vertex set Z) with any subset of the connected components of G - Z induces again a planar δ-hyperbolic graph, which would not be guaranteed with an arbitrary separator. Our construction runs in near-linear time and guarantees that the size of the separator is poly(δ) ⋅ log n. As an application of our separator theorem and its strong properties, we obtain two novel approximation schemes on planar δ-hyperbolic graphs. We prove that both Maximum Independent Set and the Traveling Salesperson problem have a near-linear time FPTAS for any constant δ, running in n polylog(n) ⋅ 2^𝒪(δ²) ⋅ ε^{-𝒪(δ)} time. We also show that our approximation scheme for Maximum Independent Set has essentially the best possible running time under the Exponential Time Hypothesis (ETH). This immediately follows from our third contribution: we prove that Maximum Independent Set has no n^{o(δ)}-time algorithm on planar δ-hyperbolic graphs, unless ETH fails.
Cite as

Sándor Kisfaludi-Bak, Jana Masaříková, Erik Jan van Leeuwen, Bartosz Walczak, and Karol Węgrzycki. Separator Theorem and Algorithms for Planar Hyperbolic Graphs. In 40th International Symposium on Computational Geometry (SoCG 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 293, pp. 67:1-67:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{kisfaludibak_et_al:LIPIcs.SoCG.2024.67,
  author =	{Kisfaludi-Bak, S\'{a}ndor and Masa\v{r}{\'\i}kov\'{a}, Jana and van Leeuwen, Erik Jan and Walczak, Bartosz and W\k{e}grzycki, Karol},
  title =	{{Separator Theorem and Algorithms for Planar Hyperbolic Graphs}},
  booktitle =	{40th International Symposium on Computational Geometry (SoCG 2024)},
  pages =	{67:1--67:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-316-4},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{293},
  editor =	{Mulzer, Wolfgang and Phillips, Jeff M.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2024.67},
  URN =		{urn:nbn:de:0030-drops-200126},
  doi =		{10.4230/LIPIcs.SoCG.2024.67},
  annote =	{Keywords: Hyperbolic metric, Planar Graphs, r-Division, Approximation Algorithms}
}
Document
DOI: 10.4230/LIPIcs.SWAT.2024.29
Edge Multiway Cut and Node Multiway Cut Are Hard for Planar Subcubic Graphs

Authors: Matthew Johnson, Barnaby Martin, Sukanya Pandey, Daniël Paulusma, Siani Smith, and Erik Jan van Leeuwen

Published in: LIPIcs, Volume 294, 19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024)

Abstract
It is known that the weighted version of Edge Multiway Cut (also known as Multiterminal Cut) is NP-complete on planar graphs of maximum degree 3. In contrast, for the unweighted version, NP-completeness is only known for planar graphs of maximum degree 11. In fact, the complexity of unweighted Edge Multiway Cut was open for graphs of maximum degree 3 for over twenty years. We prove that the unweighted version is NP-complete even for planar graphs of maximum degree 3. As weighted Edge Multiway Cut is polynomial-time solvable for graphs of maximum degree at most 2, we have now closed the complexity gap. We also prove that (unweighted) Node Multiway Cut (both with and without deletable terminals) is NP-complete for planar graphs of maximum degree 3. By combining our results with known results, we can apply two meta-classifications on graph containment from the literature. This yields full dichotomies for all three problems on H-topological-minor-free graphs and, should H be finite, on H-subgraph-free graphs as well. Previously, such dichotomies were only implied for H-minor-free graphs.
Cite as

Matthew Johnson, Barnaby Martin, Sukanya Pandey, Daniël Paulusma, Siani Smith, and Erik Jan van Leeuwen. Edge Multiway Cut and Node Multiway Cut Are Hard for Planar Subcubic Graphs. In 19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 294, pp. 29:1-29:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{johnson_et_al:LIPIcs.SWAT.2024.29,
  author =	{Johnson, Matthew and Martin, Barnaby and Pandey, Sukanya and Paulusma, Dani\"{e}l and Smith, Siani and van Leeuwen, Erik Jan},
  title =	{{Edge Multiway Cut and Node Multiway Cut Are Hard for Planar Subcubic Graphs}},
  booktitle =	{19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024)},
  pages =	{29:1--29:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-318-8},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{294},
  editor =	{Bodlaender, Hans L.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2024.29},
  URN =		{urn:nbn:de:0030-drops-200699},
  doi =		{10.4230/LIPIcs.SWAT.2024.29},
  annote =	{Keywords: multiway cut, planar subcubic graph, complexity dichotomy, graph containment}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2023.6
The Parameterised Complexity Of Integer Multicommodity Flow

Authors: Hans L. Bodlaender, Isja Mannens, Jelle J. Oostveen, Sukanya Pandey, and Erik Jan van Leeuwen

Published in: LIPIcs, Volume 285, 18th International Symposium on Parameterized and Exact Computation (IPEC 2023)

Abstract
The Integer Multicommodity Flow problem has been studied extensively in the literature. However, from a parameterised perspective, mostly special cases, such as the Disjoint Path problem, have been considered. Therefore, we investigate the parameterised complexity of the general Integer Multicommodity Flow problem. We show that the decision version of this problem on directed graphs for a constant number of commodities, when the capacities are given in unary, is XNLP-complete with pathwidth as parameter and XALP-complete with treewidth as parameter. When the capacities are given in binary, the problem is NP-complete even for graphs of pathwidth at most 13. We give related results for undirected graphs. These results imply that the problem is unlikely to be fixed-parameter tractable by these parameters. In contrast, we show that the problem does become fixed-parameter tractable when weighted tree partition width (a variant of tree partition width for edge weighted graphs) is used as parameter.
Cite as

Hans L. Bodlaender, Isja Mannens, Jelle J. Oostveen, Sukanya Pandey, and Erik Jan van Leeuwen. The Parameterised Complexity Of Integer Multicommodity Flow. In 18th International Symposium on Parameterized and Exact Computation (IPEC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 285, pp. 6:1-6:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{bodlaender_et_al:LIPIcs.IPEC.2023.6,
  author =	{Bodlaender, Hans L. and Mannens, Isja and Oostveen, Jelle J. and Pandey, Sukanya and van Leeuwen, Erik Jan},
  title =	{{The Parameterised Complexity Of Integer Multicommodity Flow}},
  booktitle =	{18th International Symposium on Parameterized and Exact Computation (IPEC 2023)},
  pages =	{6:1--6:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-305-8},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{285},
  editor =	{Misra, Neeldhara and Wahlstr\"{o}m, Magnus},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2023.6},
  URN =		{urn:nbn:de:0030-drops-194250},
  doi =		{10.4230/LIPIcs.IPEC.2023.6},
  annote =	{Keywords: multicommodity flow, parameterised complexity, XNLP-completeness, XALP-completeness}
}
Document
DOI: 10.4230/LIPIcs.ESA.2023.18
Space-Efficient Parameterized Algorithms on Graphs of Low Shrubdepth

Authors: Benjamin Bergougnoux, Vera Chekan, Robert Ganian, Mamadou Moustapha Kanté, Matthias Mnich, Sang-il Oum, Michał Pilipczuk, and Erik Jan van Leeuwen

Published in: LIPIcs, Volume 274, 31st Annual European Symposium on Algorithms (ESA 2023)

Abstract
Dynamic programming on various graph decompositions is one of the most fundamental techniques used in parameterized complexity. Unfortunately, even if we consider concepts as simple as path or tree decompositions, such dynamic programming uses space that is exponential in the decomposition’s width, and there are good reasons to believe that this is necessary. However, it has been shown that in graphs of low treedepth it is possible to design algorithms which achieve polynomial space complexity without requiring worse time complexity than their counterparts working on tree decompositions of bounded width. Here, treedepth is a graph parameter that, intuitively speaking, takes into account both the depth and the width of a tree decomposition of the graph, rather than the width alone. Motivated by the above, we consider graphs that admit clique expressions with bounded depth and label count, or equivalently, graphs of low shrubdepth. Here, shrubdepth is a bounded-depth analogue of cliquewidth, in the same way as treedepth is a bounded-depth analogue of treewidth. We show that also in this setting, bounding the depth of the decomposition is a deciding factor for improving the space complexity. More precisely, we prove that on n-vertex graphs equipped with a tree-model (a decomposition notion underlying shrubdepth) of depth d and using k labels, - Independent Set can be solved in time 2^𝒪(dk) ⋅ n^𝒪(1) using 𝒪(dk²log n) space; - Max Cut can be solved in time n^𝒪(dk) using 𝒪(dk log n) space; and - Dominating Set can be solved in time 2^𝒪(dk) ⋅ n^𝒪(1) using n^𝒪(1) space via a randomized algorithm. We also establish a lower bound, conditional on a certain assumption about the complexity of Longest Common Subsequence, which shows that at least in the case of Independent Set the exponent of the parametric factor in the time complexity has to grow with d if one wishes to keep the space complexity polynomial.
Cite as

Benjamin Bergougnoux, Vera Chekan, Robert Ganian, Mamadou Moustapha Kanté, Matthias Mnich, Sang-il Oum, Michał Pilipczuk, and Erik Jan van Leeuwen. Space-Efficient Parameterized Algorithms on Graphs of Low Shrubdepth. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 18:1-18:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{bergougnoux_et_al:LIPIcs.ESA.2023.18,
  author =	{Bergougnoux, Benjamin and Chekan, Vera and Ganian, Robert and Kant\'{e}, Mamadou Moustapha and Mnich, Matthias and Oum, Sang-il and Pilipczuk, Micha{\l} and van Leeuwen, Erik Jan},
  title =	{{Space-Efficient Parameterized Algorithms on Graphs of Low Shrubdepth}},
  booktitle =	{31st Annual European Symposium on Algorithms (ESA 2023)},
  pages =	{18:1--18:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-295-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{274},
  editor =	{G{\o}rtz, Inge Li and Farach-Colton, Martin and Puglisi, Simon J. 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.2023.18},
  URN =		{urn:nbn:de:0030-drops-186710},
  doi =		{10.4230/LIPIcs.ESA.2023.18},
  annote =	{Keywords: Parameterized complexity, shrubdepth, space complexity, algebraic methods}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2023.57
Complexity Framework for Forbidden Subgraphs III: When Problems Are Tractable on Subcubic Graphs

Authors: Matthew Johnson, Barnaby Martin, Sukanya Pandey, Daniël Paulusma, Siani Smith, and Erik Jan van Leeuwen

Published in: LIPIcs, Volume 272, 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)

Abstract
For any finite set ℋ = {H_1,…,H_p} of graphs, a graph is ℋ-subgraph-free if it does not contain any of H_1,…,H_p as a subgraph. In recent work, meta-classifications have been studied: these show that if graph problems satisfy certain prescribed conditions, their complexity can be classified on classes of ℋ-subgraph-free graphs. We continue this work and focus on problems that have polynomial-time solutions on classes that have bounded treewidth or maximum degree at most 3 and examine their complexity on H-subgraph-free graph classes where H is a connected graph. With this approach, we obtain comprehensive classifications for (Independent) Feedback Vertex Set, Connected Vertex Cover, Colouring and Matching Cut. This resolves a number of open problems. We highlight that, to establish that Independent Feedback Vertex Set belongs to this collection of problems, we first show that it can be solved in polynomial time on graphs of maximum degree 3. We demonstrate that, with the exception of the complete graph on four vertices, each graph in this class has a minimum size feedback vertex set that is also an independent set.
Cite as

Matthew Johnson, Barnaby Martin, Sukanya Pandey, Daniël Paulusma, Siani Smith, and Erik Jan van Leeuwen. Complexity Framework for Forbidden Subgraphs III: When Problems Are Tractable on Subcubic Graphs. In 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 272, pp. 57:1-57:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{johnson_et_al:LIPIcs.MFCS.2023.57,
  author =	{Johnson, Matthew and Martin, Barnaby and Pandey, Sukanya and Paulusma, Dani\"{e}l and Smith, Siani and van Leeuwen, Erik Jan},
  title =	{{Complexity Framework for Forbidden Subgraphs III: When Problems Are Tractable on Subcubic Graphs}},
  booktitle =	{48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)},
  pages =	{57:1--57:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-292-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{272},
  editor =	{Leroux, J\'{e}r\^{o}me and Lombardy, Sylvain and Peleg, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2023.57},
  URN =		{urn:nbn:de:0030-drops-185914},
  doi =		{10.4230/LIPIcs.MFCS.2023.57},
  annote =	{Keywords: forbidden subgraphs, independent feedback vertex set, treewidth}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2022.24
Parameterized Complexity of Streaming Diameter and Connectivity Problems

Authors: Jelle J. Oostveen and Erik Jan van Leeuwen

Published in: LIPIcs, Volume 249, 17th International Symposium on Parameterized and Exact Computation (IPEC 2022)

Abstract
We initiate the investigation of the parameterized complexity of Diameter and Connectivity in the streaming paradigm. On the positive end, we show that knowing a vertex cover of size k allows for algorithms in the Adjacency List (AL) streaming model whose number of passes is constant and memory is 𝒪(log n) for any fixed k. Underlying these algorithms is a method to execute a breadth-first search in 𝒪(k) passes and 𝒪(k log n) bits of memory. On the negative end, we show that many other parameters lead to lower bounds in the AL model, where Ω(n/p) bits of memory is needed for any p-pass algorithm even for constant parameter values. In particular, this holds for graphs with a known modulator (deletion set) of constant size to a graph that has no induced subgraph isomorphic to a fixed graph H, for most H. For some cases, we can also show one-pass, Ω(n log n) bits of memory lower bounds. We also prove a much stronger Ω(n²/p) lower bound for Diameter on bipartite graphs. Finally, using the insights we developed into streaming parameterized graph exploration algorithms, we show a new streaming kernelization algorithm for computing a vertex cover of size k. This yields a kernel of 2k vertices (with 𝒪(k²) edges) produced as a stream in poly(k) passes and only 𝒪(k log n) bits of memory.
Cite as

Jelle J. Oostveen and Erik Jan van Leeuwen. Parameterized Complexity of Streaming Diameter and Connectivity Problems. In 17th International Symposium on Parameterized and Exact Computation (IPEC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 249, pp. 24:1-24:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{oostveen_et_al:LIPIcs.IPEC.2022.24,
  author =	{Oostveen, Jelle J. and van Leeuwen, Erik Jan},
  title =	{{Parameterized Complexity of Streaming Diameter and Connectivity Problems}},
  booktitle =	{17th International Symposium on Parameterized and Exact Computation (IPEC 2022)},
  pages =	{24:1--24:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-260-0},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{249},
  editor =	{Dell, Holger and Nederlof, Jesper},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2022.24},
  URN =		{urn:nbn:de:0030-drops-173808},
  doi =		{10.4230/LIPIcs.IPEC.2022.24},
  annote =	{Keywords: Stream, Streaming, Graphs, Parameter, Complexity, Diameter, Connectivity, Vertex Cover, Disjointness, Permutation}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2020.63
Algorithms for the Rainbow Vertex Coloring Problem on Graph Classes

Authors: Paloma T. Lima, Erik Jan van Leeuwen, and Marieke van der Wegen

Published in: LIPIcs, Volume 170, 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)

Abstract
Given a vertex-colored graph, we say a path is a rainbow vertex path if all its internal vertices have distinct colors. The graph is rainbow vertex-connected if there is a rainbow vertex path between every pair of its vertices. In the Rainbow Vertex Coloring (RVC) problem we want to decide whether the vertices of a given graph can be colored with at most k colors so that the graph becomes rainbow vertex-connected. This problem is known to be NP-complete even in very restricted scenarios, and very few efficient algorithms are known for it. In this work, we give polynomial-time algorithms for RVC on permutation graphs, powers of trees and split strongly chordal graphs. The algorithm for the latter class also works for the strong variant of the problem, where the rainbow vertex paths between each vertex pair must be shortest paths. We complement the polynomial-time solvability results for split strongly chordal graphs by showing that, for any fixed p ≥ 3 both variants of the problem become NP-complete when restricted to split (S₃,…,S_p)-free graphs, where S_q denotes the q-sun graph.
Cite as

Paloma T. Lima, Erik Jan van Leeuwen, and Marieke van der Wegen. Algorithms for the Rainbow Vertex Coloring Problem on Graph Classes. In 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 170, pp. 63:1-63:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{lima_et_al:LIPIcs.MFCS.2020.63,
  author =	{Lima, Paloma T. and van Leeuwen, Erik Jan and van der Wegen, Marieke},
  title =	{{Algorithms for the Rainbow Vertex Coloring Problem on Graph Classes}},
  booktitle =	{45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)},
  pages =	{63:1--63:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-159-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{170},
  editor =	{Esparza, Javier and Kr\'{a}l', Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2020.63},
  URN =		{urn:nbn:de:0030-drops-127331},
  doi =		{10.4230/LIPIcs.MFCS.2020.63},
  annote =	{Keywords: rainbow vertex coloring, permutation graphs, powers of trees}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2019.23
Subexponential-Time Algorithms for Finding Large Induced Sparse Subgraphs

Authors: Jana Novotná, Karolina Okrasa, Michał Pilipczuk, Paweł Rzążewski, Erik Jan van Leeuwen, and Bartosz Walczak

Published in: LIPIcs, Volume 148, 14th International Symposium on Parameterized and Exact Computation (IPEC 2019)

Abstract
Let C and D be hereditary graph classes. Consider the following problem: given a graph G in D, find a largest, in terms of the number of vertices, induced subgraph of G that belongs to C. We prove that it can be solved in 2^{o(n)} time, where n is the number of vertices of G, if the following conditions are satisfied: - the graphs in C are sparse, i.e., they have linearly many edges in terms of the number of vertices; - the graphs in D admit balanced separators of size governed by their density, e.g., O(Delta) or O(sqrt{m}), where Delta and m denote the maximum degree and the number of edges, respectively; and - the considered problem admits a single-exponential fixed-parameter algorithm when parameterized by the treewidth of the input graph. This leads, for example, to the following corollaries for specific classes C and D: - a largest induced forest in a P_t-free graph can be found in 2^{O~(n^{2/3})} time, for every fixed t; and - a largest induced planar graph in a string graph can be found in 2^{O~(n^{3/4})} time.
Cite as

Jana Novotná, Karolina Okrasa, Michał Pilipczuk, Paweł Rzążewski, Erik Jan van Leeuwen, and Bartosz Walczak. Subexponential-Time Algorithms for Finding Large Induced Sparse Subgraphs. In 14th International Symposium on Parameterized and Exact Computation (IPEC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 148, pp. 23:1-23:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{novotna_et_al:LIPIcs.IPEC.2019.23,
  author =	{Novotn\'{a}, Jana and Okrasa, Karolina and Pilipczuk, Micha{\l} and Rz\k{a}\.{z}ewski, Pawe{\l} and van Leeuwen, Erik Jan and Walczak, Bartosz},
  title =	{{Subexponential-Time Algorithms for Finding Large Induced Sparse Subgraphs}},
  booktitle =	{14th International Symposium on Parameterized and Exact Computation (IPEC 2019)},
  pages =	{23:1--23:11},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-129-0},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{148},
  editor =	{Jansen, Bart M. P. and Telle, Jan Arne},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2019.23},
  URN =		{urn:nbn:de:0030-drops-114845},
  doi =		{10.4230/LIPIcs.IPEC.2019.23},
  annote =	{Keywords: subexponential algorithm, feedback vertex set, P\underlinet-free graphs, string graphs}
}
Document
DOI: 10.4230/LIPIcs.ESA.2019.26
On Geometric Set Cover for Orthants

Authors: Karl Bringmann, Sándor Kisfaludi-Bak, Michał Pilipczuk, and Erik Jan van Leeuwen

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

Abstract
We study SET COVER for orthants: Given a set of points in a d-dimensional Euclidean space and a set of orthants of the form (-infty,p_1] x ... x (-infty,p_d], select a minimum number of orthants so that every point is contained in at least one selected orthant. This problem draws its motivation from applications in multi-objective optimization problems. While for d=2 the problem can be solved in polynomial time, for d>2 no algorithm is known that avoids the enumeration of all size-k subsets of the input to test whether there is a set cover of size k. Our contribution is a precise understanding of the complexity of this problem in any dimension d >= 3, when k is considered a parameter: - For d=3, we give an algorithm with runtime n^O(sqrt{k}), thus avoiding exhaustive enumeration. - For d=3, we prove a tight lower bound of n^Omega(sqrt{k}) (assuming ETH). - For d >=slant 4, we prove a tight lower bound of n^Omega(k) (assuming ETH). Here n is the size of the set of points plus the size of the set of orthants. The first statement comes as a corollary of a more general result: an algorithm for SET COVER for half-spaces in dimension 3. In particular, we show that given a set of points U in R^3, a set of half-spaces D in R^3, and an integer k, one can decide whether U can be covered by the union of at most k half-spaces from D in time |D|^O(sqrt{k})* |U|^O(1). We also study approximation for SET COVER for orthants. While in dimension 3 a PTAS can be inferred from existing results, we show that in dimension 4 and larger, there is no 1.05-approximation algorithm with runtime f(k)* n^o(k) for any computable f, where k is the optimum.
Cite as

Karl Bringmann, Sándor Kisfaludi-Bak, Michał Pilipczuk, and Erik Jan van Leeuwen. On Geometric Set Cover for Orthants. In 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 144, pp. 26:1-26:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{bringmann_et_al:LIPIcs.ESA.2019.26,
  author =	{Bringmann, Karl and Kisfaludi-Bak, S\'{a}ndor and Pilipczuk, Micha{\l} and van Leeuwen, Erik Jan},
  title =	{{On Geometric Set Cover for Orthants}},
  booktitle =	{27th Annual European Symposium on Algorithms (ESA 2019)},
  pages =	{26:1--26:18},
  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.26},
  URN =		{urn:nbn:de:0030-drops-111476},
  doi =		{10.4230/LIPIcs.ESA.2019.26},
  annote =	{Keywords: Set Cover, parameterized complexity, algorithms, Exponential Time Hypothesis}
}
Document
DOI: 10.4230/LIPIcs.STACS.2019.39
A Deterministic Polynomial Kernel for Odd Cycle Transversal and Vertex Multiway Cut in Planar Graphs

Authors: Bart M. P. Jansen, Marcin Pilipczuk, and Erik Jan van Leeuwen

Published in: LIPIcs, Volume 126, 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)

Abstract
We show that Odd Cycle Transversal and Vertex Multiway Cut admit deterministic polynomial kernels when restricted to planar graphs and parameterized by the solution size. This answers a question of Saurabh. On the way to these results, we provide an efficient sparsification routine in the flavor of the sparsification routine used for the Steiner Tree problem in planar graphs (FOCS 2014). It differs from the previous work because it preserves the existence of low-cost subgraphs that are not necessarily Steiner trees in the original plane graph, but structures that turn into (supergraphs of) Steiner trees after adding all edges between pairs of vertices that lie on a common face. We also show connections between Vertex Multiway Cut and the Vertex Planarization problem, where the existence of a polynomial kernel remains an important open problem.
Cite as

Bart M. P. Jansen, Marcin Pilipczuk, and Erik Jan van Leeuwen. A Deterministic Polynomial Kernel for Odd Cycle Transversal and Vertex Multiway Cut in Planar Graphs. In 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 126, pp. 39:1-39:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{jansen_et_al:LIPIcs.STACS.2019.39,
  author =	{Jansen, Bart M. P. and Pilipczuk, Marcin and van Leeuwen, Erik Jan},
  title =	{{A Deterministic Polynomial Kernel for Odd Cycle Transversal and Vertex Multiway Cut in Planar Graphs}},
  booktitle =	{36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)},
  pages =	{39:1--39:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-100-9},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{126},
  editor =	{Niedermeier, Rolf and Paul, Christophe},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2019.39},
  URN =		{urn:nbn:de:0030-drops-102783},
  doi =		{10.4230/LIPIcs.STACS.2019.39},
  annote =	{Keywords: planar graphs, kernelization, odd cycle transversal, multiway cut}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2018.83
Rainbow Vertex Coloring Bipartite Graphs and Chordal Graphs

Authors: Pinar Heggernes, Davis Issac, Juho Lauri, Paloma T. Lima, and Erik Jan van Leeuwen

Published in: LIPIcs, Volume 117, 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)

Abstract
Given a graph with colors on its vertices, a path is called a rainbow vertex path if all its internal vertices have distinct colors. We say that the graph is rainbow vertex-connected if there is a rainbow vertex path between every pair of its vertices. We study the problem of deciding whether the vertices of a given graph can be colored with at most k colors so that the graph becomes rainbow vertex-connected. Although edge-colorings have been studied extensively under similar constraints, there are significantly fewer results on the vertex variant that we consider. In particular, its complexity on structured graph classes was explicitly posed as an open question. We show that the problem remains NP-complete even on bipartite apex graphs and on split graphs. The former can be seen as a first step in the direction of studying the complexity of rainbow coloring on sparse graphs, an open problem which has attracted attention but limited progress. We also give hardness of approximation results for both bipartite and split graphs. To complement the negative results, we show that bipartite permutation graphs, interval graphs, and block graphs can be rainbow vertex-connected optimally in polynomial time.
Cite as

Pinar Heggernes, Davis Issac, Juho Lauri, Paloma T. Lima, and Erik Jan van Leeuwen. Rainbow Vertex Coloring Bipartite Graphs and Chordal Graphs. In 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 117, pp. 83:1-83:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{heggernes_et_al:LIPIcs.MFCS.2018.83,
  author =	{Heggernes, Pinar and Issac, Davis and Lauri, Juho and Lima, Paloma T. and van Leeuwen, Erik Jan},
  title =	{{Rainbow Vertex Coloring Bipartite Graphs and Chordal Graphs}},
  booktitle =	{43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)},
  pages =	{83:1--83:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-086-6},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{117},
  editor =	{Potapov, Igor and Spirakis, Paul and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2018.83},
  URN =		{urn:nbn:de:0030-drops-96657},
  doi =		{10.4230/LIPIcs.MFCS.2018.83},
  annote =	{Keywords: Rainbow coloring, graph classes, polynomial-time algorithms, approximation algorithms}
}
Document
DOI: 10.4230/LIPIcs.ESA.2018.51
Solving Partition Problems Almost Always Requires Pushing Many Vertices Around

Authors: Iyad Kanj, Christian Komusiewicz, Manuel Sorge, and Erik Jan van Leeuwen

Published in: LIPIcs, Volume 112, 26th Annual European Symposium on Algorithms (ESA 2018)

Abstract
A fundamental graph problem is to recognize whether the vertex set of a graph G can be bipartitioned into sets A and B such that G[A] and G[B] satisfy properties Pi_A and Pi_B, respectively. This so-called (Pi_A,Pi_B)-Recognition problem generalizes amongst others the recognition of 3-colorable, bipartite, split, and monopolar graphs. A powerful algorithmic technique that can be used to obtain fixed-parameter algorithms for many cases of (Pi_A,Pi_B)-Recognition, as well as several other problems, is the pushing process. For bipartition problems, the process starts with an "almost correct" bipartition (A',B'), and pushes appropriate vertices from A' to B' and vice versa to eventually arrive at a correct bipartition. In this paper, we study whether (Pi_A,Pi_B)-Recognition problems for which the pushing process yields fixed-parameter algorithms also admit polynomial problem kernels. In our study, we focus on the first level above triviality, where Pi_A is the set of P_3-free graphs (disjoint unions of cliques, or cluster graphs), the parameter is the number of clusters in the cluster graph G[A], and Pi_B is characterized by a set H of connected forbidden induced subgraphs. We prove that, under the assumption that NP not subseteq coNP/poly, (Pi_A,Pi_B)-Recognition admits a polynomial kernel if and only if H contains a graph of order at most 2. In both the kernelization and the lower bound results, we make crucial use of the pushing process.
Cite as

Iyad Kanj, Christian Komusiewicz, Manuel Sorge, and Erik Jan van Leeuwen. Solving Partition Problems Almost Always Requires Pushing Many Vertices Around. In 26th Annual European Symposium on Algorithms (ESA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 112, pp. 51:1-51:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{kanj_et_al:LIPIcs.ESA.2018.51,
  author =	{Kanj, Iyad and Komusiewicz, Christian and Sorge, Manuel and van Leeuwen, Erik Jan},
  title =	{{Solving Partition Problems Almost Always Requires Pushing Many Vertices Around}},
  booktitle =	{26th Annual European Symposium on Algorithms (ESA 2018)},
  pages =	{51:1--51:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-081-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{112},
  editor =	{Azar, Yossi and Bast, Hannah 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.2018.51},
  URN =		{urn:nbn:de:0030-drops-95140},
  doi =		{10.4230/LIPIcs.ESA.2018.51},
  annote =	{Keywords: Fixed-parameter algorithms, Kernelization, Vertex-partition problems, Reduction rules, Cross-composition}
}
Document
DOI: 10.4230/LIPIcs.ESA.2018.61
Disconnected Cuts in Claw-free Graphs

Authors: Barnaby Martin, Daniël Paulusma, and Erik Jan van Leeuwen

Published in: LIPIcs, Volume 112, 26th Annual European Symposium on Algorithms (ESA 2018)

Abstract
A disconnected cut of a connected graph is a vertex cut that itself also induces a disconnected subgraph. The corresponding decision problem is called Disconnected Cut. It is known that Disconnected Cut is NP-hard on general graphs, while polynomial-time algorithms exist for several graph classes. However, the complexity of the problem on claw-free graphs remained an open question. Its connection to the complexity of the problem to contract a claw-free graph to the 4-vertex cycle C_4 led Ito et al. (TCS 2011) to explicitly ask to resolve this open question. We prove that Disconnected Cut is polynomial-time solvable on claw-free graphs, answering the question of Ito et al. The basis for our result is a decomposition theorem for claw-free graphs of diameter 2, which we believe is of independent interest and builds on the research line initiated by Chudnovsky and Seymour (JCTB 2007-2012) and Hermelin et al. (ICALP 2011). On our way to exploit this decomposition theorem, we characterize how disconnected cuts interact with certain cobipartite subgraphs, and prove two further algorithmic results, namely that Disconnected Cut is polynomial-time solvable on circular-arc graphs and line graphs.
Cite as

Barnaby Martin, Daniël Paulusma, and Erik Jan van Leeuwen. Disconnected Cuts in Claw-free Graphs. In 26th Annual European Symposium on Algorithms (ESA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 112, pp. 61:1-61:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{martin_et_al:LIPIcs.ESA.2018.61,
  author =	{Martin, Barnaby and Paulusma, Dani\"{e}l and van Leeuwen, Erik Jan},
  title =	{{Disconnected Cuts in Claw-free Graphs}},
  booktitle =	{26th Annual European Symposium on Algorithms (ESA 2018)},
  pages =	{61:1--61:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-081-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{112},
  editor =	{Azar, Yossi and Bast, Hannah 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.2018.61},
  URN =		{urn:nbn:de:0030-drops-95249},
  doi =		{10.4230/LIPIcs.ESA.2018.61},
  annote =	{Keywords: disconnected cut, surjective homomorphism, biclique cover, claw-freeness}
}
Document
DOI: 10.4230/LIPIcs.ESA.2018.65
Quasi-Polynomial Time Approximation Schemes for Packing and Covering Problems in Planar Graphs

Authors: Michal Pilipczuk, Erik Jan van Leeuwen, and Andreas Wiese

Published in: LIPIcs, Volume 112, 26th Annual European Symposium on Algorithms (ESA 2018)

Abstract
We consider two optimization problems in planar graphs. In {Maximum Weight Independent Set of Objects} we are given a graph G and a family D of {objects}, each being a connected subgraph of G with a prescribed weight, and the task is to find a maximum-weight subfamily of D consisting of pairwise disjoint objects. In {Minimum Weight Distance Set Cover} we are given an edge-weighted graph G, two sets D,C of vertices of G, where vertices of D have prescribed weights, and a nonnegative radius r. The task is to find a minimum-weight subset of D such that every vertex of C is at distance at most r from some selected vertex. Via simple reductions, these two problems generalize a number of geometric optimization tasks, notably {Maximum Weight Independent Set} for polygons in the plane and {Weighted Geometric Set Cover} for unit disks and unit squares. We present {quasi-polynomial time approximation schemes} (QPTASs) for both of the above problems in planar graphs: given an accuracy parameter epsilon>0 we can compute a solution whose weight is within multiplicative factor of (1+epsilon) from the optimum in time 2^{poly(1/epsilon,log |D|)}* n^{O(1)}, where n is the number of vertices of the input graph. Our main technical contribution is to transfer the techniques used for recursive approximation schemes for geometric problems due to Adamaszek, Har-Peled, and Wiese [Adamaszek and Wiese, 2013; Adamaszek and Wiese, 2014; Sariel Har-Peled, 2014] to the setting of planar graphs. In particular, this yields a purely combinatorial viewpoint on these methods.
Cite as

Michal Pilipczuk, Erik Jan van Leeuwen, and Andreas Wiese. Quasi-Polynomial Time Approximation Schemes for Packing and Covering Problems in Planar Graphs. In 26th Annual European Symposium on Algorithms (ESA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 112, pp. 65:1-65:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{pilipczuk_et_al:LIPIcs.ESA.2018.65,
  author =	{Pilipczuk, Michal and van Leeuwen, Erik Jan and Wiese, Andreas},
  title =	{{Quasi-Polynomial Time Approximation Schemes for Packing and Covering Problems in Planar Graphs}},
  booktitle =	{26th Annual European Symposium on Algorithms (ESA 2018)},
  pages =	{65:1--65:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-081-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{112},
  editor =	{Azar, Yossi and Bast, Hannah 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.2018.65},
  URN =		{urn:nbn:de:0030-drops-95282},
  doi =		{10.4230/LIPIcs.ESA.2018.65},
  annote =	{Keywords: QPTAS, planar graphs, Voronoi diagram}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2017.42
Approximation and Parameterized Algorithms for Geometric Independent Set with Shrinking

Authors: Michal Pilipczuk, Erik Jan van Leeuwen, and Andreas Wiese

Published in: LIPIcs, Volume 83, 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)

Abstract
Consider the Maximum Weight Independent Set problem for rectangles: given a family of weighted axis-parallel rectangles in the plane, find a maximum-weight subset of non-overlapping rectangles. The problem is notoriously hard both in the approximation and in the parameterized setting. The best known polynomial-time approximation algorithms achieve super-constant approximation ratios [Chalermsook & Chuzhoy, Proc. SODA 2009; Chan & Har-Peled, Discrete & Comp. Geometry, 2012], even though there is a (1+epsilon)-approximation running in quasi-polynomial time [Adamaszek & Wiese, Proc. FOCS 2013; Chuzhoy & Ene, Proc. FOCS 2016]. When parameterized by the target size of the solution, the problem is W[1]-hard even in the unweighted setting [Marx, ESA 2005]. To achieve tractability, we study the following shrinking model: one is allowed to shrink each input rectangle by a multiplicative factor 1-delta for some fixed delta > 0, but the performance is still compared against the optimal solution for the original, non-shrunk instance. We prove that in this regime, the problem admits an EPTAS with running time f(epsilon,delta) n^{O(1)}, and an FPT algorithm with running time f(k,delta) n^{O(1)}, in the setting where a maximum-weight solution of size at most k is to be computed. This improves and significantly simplifies a PTAS given earlier for this problem [Adamaszek, Chalermsook & Wiese, Proc. APPROX/RANDOM 2015], and provides the first parameterized results for the shrinking model. Furthermore, we explore kernelization in the shrinking model, by giving efficient kernelization procedures for several variants of the problem when the input rectangles are squares.
Cite as

Michal Pilipczuk, Erik Jan van Leeuwen, and Andreas Wiese. Approximation and Parameterized Algorithms for Geometric Independent Set with Shrinking. In 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 83, pp. 42:1-42:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{pilipczuk_et_al:LIPIcs.MFCS.2017.42,
  author =	{Pilipczuk, Michal and van Leeuwen, Erik Jan and Wiese, Andreas},
  title =	{{Approximation and Parameterized Algorithms for Geometric Independent Set with Shrinking}},
  booktitle =	{42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)},
  pages =	{42:1--42:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-046-0},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{83},
  editor =	{Larsen, Kim G. and Bodlaender, Hans L. and Raskin, Jean-Francois},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2017.42},
  URN =		{urn:nbn:de:0030-drops-80917},
  doi =		{10.4230/LIPIcs.MFCS.2017.42},
  annote =	{Keywords: Combinatorial optimization, Approximation algorithms, Fixed-parameter algorithms}
}
Document
DOI: 10.4230/LIPIcs.STACS.2016.55
Polynomial Kernels for Deletion to Classes of Acyclic Digraphs

Authors: Matthias Mnich and Erik Jan van Leeuwen

Published in: LIPIcs, Volume 47, 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016)

Abstract
We consider the problem to find a set X of vertices (or arcs) with |X| <= k in a given digraph G such that D = G-X is an acyclic digraph. In its generality, this is DIRECTED FEEDBACK VERTEX SET or DIRECTED FEEDBACK ARC SET respectively. The existence of a polynomial kernel for these problems is a notorious open problem in the field of kernelization, and little progress has been made. In this paper, we consider both deletion problems with an additional restriction on D, namely that D must be an out-forest, an out-tree, or a (directed) pumpkin. Our main results show that for each of these three restrictions the vertex deletion problem remains NP-hard, but we can obtain a kernel with k^{O(1)} vertices on general digraphs G. We also show that, in contrast to the vertex deletion problem, the arc deletion problem with each of the above restrictions can be solved in polynomial time.
Cite as

Matthias Mnich and Erik Jan van Leeuwen. Polynomial Kernels for Deletion to Classes of Acyclic Digraphs. In 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 47, pp. 55:1-55:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{mnich_et_al:LIPIcs.STACS.2016.55,
  author =	{Mnich, Matthias and van Leeuwen, Erik Jan},
  title =	{{Polynomial Kernels for Deletion to Classes of Acyclic Digraphs}},
  booktitle =	{33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016)},
  pages =	{55:1--55:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-001-9},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{47},
  editor =	{Ollinger, Nicolas and Vollmer, Heribert},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2016.55},
  URN =		{urn:nbn:de:0030-drops-57569},
  doi =		{10.4230/LIPIcs.STACS.2016.55},
  annote =	{Keywords: directed feedback vertex/arc set, parameterized algorithms, kernels}
}
Document
DOI: 10.4230/LIPIcs.STACS.2015.157
Parameterized Complexity Dichotomy for Steiner Multicut

Authors: Karl Bringmann, Danny Hermelin, Matthias Mnich, and Erik Jan van Leeuwen

Published in: LIPIcs, Volume 30, 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)

Abstract
We consider the Steiner Multicut problem, which asks, given an undirected graph G, a collection T = \{T_{1},...,T_{t}}, T_i \subseteq V(G), of terminal sets of size at most p, and an integer k, whether there is a set S of at most k edges or nodes such that of each set T_{i} at least one pair of terminals is in different connected components of G \ S. This problem generalizes several well-studied graph cut problems, in particular the Multicut problem, which corresponds to the case p = 2. The Multicut problem was recently shown to be fixed-parameter tractable for parameter k [Marx and Razgon, Bousquet et al., STOC 2011]. The question whether this result generalizes to Steiner Multicut motivates the present work. We answer the question that motivated this work, and in fact provide a dichotomy of the parameterized complexity of Steiner Multicut on general graphs. That is, for any combination of k, t, p, and the treewidth tw(G) as constant, parameter, or unbounded, and for all versions of the problem (edge deletion and node deletion with and without deletable terminals), we prove either that the problem is fixed-parameter tractable or that the problem is hard (W[1]-hard or even (para-)NP-complete). Among the many results in the paper, we highlight that: - The edge deletion version of Steiner Multicut is fixed-parameter tractable for parameter k+t on general graphs (but has no polynomial kernel, even on trees). - In contrast, both node deletion versions of Steiner Multicut are W[1]-hard for the parameter k+t on general graphs. - All versions of Steiner Multicut are W[1]-hard for the parameter k, even when p=3 and the graph is a tree plus one node. Since we allow k, t, p, and tw(G) to be any constants, our characterization includes a dichotomy for Steiner Multicut on trees (for tw(G) = 1) as well as a polynomial time versus NP-hardness dichotomy (by restricting k,t,p,tw(G) to constant or unbounded).
Cite as

Karl Bringmann, Danny Hermelin, Matthias Mnich, and Erik Jan van Leeuwen. Parameterized Complexity Dichotomy for Steiner Multicut. In 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 30, pp. 157-170, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{bringmann_et_al:LIPIcs.STACS.2015.157,
  author =	{Bringmann, Karl and Hermelin, Danny and Mnich, Matthias and van Leeuwen, Erik Jan},
  title =	{{Parameterized Complexity Dichotomy for Steiner Multicut}},
  booktitle =	{32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)},
  pages =	{157--170},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-78-1},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{30},
  editor =	{Mayr, Ernst W. and Ollinger, Nicolas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2015.157},
  URN =		{urn:nbn:de:0030-drops-49115},
  doi =		{10.4230/LIPIcs.STACS.2015.157},
  annote =	{Keywords: graph cut problems, Steiner cut, fixed-parameter tractability}
}
Document
DOI: 10.4230/LIPIcs.STACS.2013.353
Subexponential-Time Parameterized Algorithm for Steiner Tree on Planar Graphs

Authors: Marcin Pilipczuk, Michal Pilipczuk, Piotr Sankowski, and Erik Jan van Leeuwen

Published in: LIPIcs, Volume 20, 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)

Abstract
The well-known bidimensionality theory provides a method for designing fast, subexponential-time parameterized algorithms for a vast number of NP-hard problems on sparse graph classes such as planar graphs, bounded genus graphs, or, more generally, graphs with a fixed excluded minor. However, in order to apply the bidimensionality framework the considered problem needs to fulfill a special density property. Some well-known problems do not have this property, unfortunately, with probably the most prominent and important example being the Steiner Tree problem. Hence the question whether a subexponential-time parameterized algorithm for Steiner Tree on planar graphs exists has remained open. In this paper, we answer this question positively and develop an algorithm running in O(2^{O((k log k)^{2/3})}n) time and polynomial space, where k is the size of the Steiner tree and n is the number of vertices of the graph. Our algorithm does not rely on tools from bidimensionality theory or graph minors theory, apart from Baker's classical approach. Instead, we introduce new tools and concepts to the study of the parameterized complexity of problems on sparse graphs.
Cite as

Marcin Pilipczuk, Michal Pilipczuk, Piotr Sankowski, and Erik Jan van Leeuwen. Subexponential-Time Parameterized Algorithm for Steiner Tree on Planar Graphs. In 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 20, pp. 353-364, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)

Copy BibTex To Clipboard

@InProceedings{pilipczuk_et_al:LIPIcs.STACS.2013.353,
  author =	{Pilipczuk, Marcin and Pilipczuk, Michal and Sankowski, Piotr and van Leeuwen, Erik Jan},
  title =	{{Subexponential-Time Parameterized Algorithm for Steiner Tree on Planar Graphs}},
  booktitle =	{30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)},
  pages =	{353--364},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-50-7},
  ISSN =	{1868-8969},
  year =	{2013},
  volume =	{20},
  editor =	{Portier, Natacha and Wilke, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2013.353},
  URN =		{urn:nbn:de:0030-drops-39471},
  doi =		{10.4230/LIPIcs.STACS.2013.353},
  annote =	{Keywords: planar graph, Steiner tree, subexponential-time algorithms}
}
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
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact