4 Search Results for "Wiederrecht, Sebastian"

Document
DOI: 10.4230/LIPIcs.STACS.2025.6
Twin-Width One

Authors: Jungho Ahn, Hugo Jacob, Noleen Köhler, Christophe Paul, Amadeus Reinald, and Sebastian Wiederrecht

Published in: LIPIcs, Volume 327, 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)

Abstract
We investigate the structure of graphs of twin-width at most 1, and obtain the following results: - Graphs of twin-width at most 1 are permutation graphs. In particular they have an intersection model and a linear structure. - There is always a 1-contraction sequence closely following a given permutation diagram. - Based on a recursive decomposition theorem, we obtain a simple algorithm running in linear time that produces a 1-contraction sequence of a graph, or guarantees that it has twin-width more than 1. - We characterise distance-hereditary graphs based on their twin-width and deduce a linear time algorithm to compute optimal sequences on this class of graphs.
Cite as

Jungho Ahn, Hugo Jacob, Noleen Köhler, Christophe Paul, Amadeus Reinald, and Sebastian Wiederrecht. Twin-Width One. In 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 327, pp. 6:1-6:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{ahn_et_al:LIPIcs.STACS.2025.6,
  author =	{Ahn, Jungho and Jacob, Hugo and K\"{o}hler, Noleen and Paul, Christophe and Reinald, Amadeus and Wiederrecht, Sebastian},
  title =	{{Twin-Width One}},
  booktitle =	{42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)},
  pages =	{6:1--6:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-365-2},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{327},
  editor =	{Beyersdorff, Olaf and Pilipczuk, Micha{\l} and Pimentel, Elaine and Thắng, Nguy\~{ê}n Kim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2025.6},
  URN =		{urn:nbn:de:0030-drops-228319},
  doi =		{10.4230/LIPIcs.STACS.2025.6},
  annote =	{Keywords: Twin-width, Hereditary graph classes, Intersection model}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2024.114
Delineating Half-Integrality of the Erdős-Pósa Property for Minors: The Case of Surfaces

Authors: Christophe Paul, Evangelos Protopapas, Dimitrios M. Thilikos, and Sebastian Wiederrecht

Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)

Abstract
In 1986 Robertson and Seymour proved a generalization of the seminal result of Erdős and Pósa on the duality of packing and covering cycles: A graph has the Erdős-Pósa property for minors if and only if it is planar. In particular, for every non-planar graph H they gave examples showing that the Erdős-Pósa property does not hold for H. Recently, Liu confirmed a conjecture of Thomas and showed that every graph has the half-integral Erdős-Pósa property for minors. Liu’s proof is non-constructive and to this date, with the exception of a small number of examples, no constructive proof is known. In this paper, we initiate the delineation of the half-integrality of the Erdős-Pósa property for minors. We conjecture that for every graph H, there exists a unique (up to a suitable equivalence relation on graph parameters) graph parameter EP_H such that H has the Erdős-Pósa property in a minor-closed graph class 𝒢 if and only if sup{EP_H(G) ∣ G ∈ 𝒢} is finite. We prove this conjecture for the class ℋ of Kuratowski-connected shallow-vortex minors by showing that, for every non-planar H ∈ ℋ, the parameter EP_H(G) is precisely the maximum order of a Robertson-Seymour counterexample to the Erdős-Pósa property of H which can be found as a minor in G. Our results are constructive and imply, for the first time, parameterized algorithms that find either a packing, or a cover, or one of the Robertson-Seymour counterexamples, certifying the existence of a half-integral packing for the graphs in ℋ.
Cite as

Christophe Paul, Evangelos Protopapas, Dimitrios M. Thilikos, and Sebastian Wiederrecht. Delineating Half-Integrality of the Erdős-Pósa Property for Minors: The Case of Surfaces. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 114:1-114:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{paul_et_al:LIPIcs.ICALP.2024.114,
  author =	{Paul, Christophe and Protopapas, Evangelos and Thilikos, Dimitrios M. and Wiederrecht, Sebastian},
  title =	{{Delineating Half-Integrality of the Erd\H{o}s-P\'{o}sa Property for Minors: The Case of Surfaces}},
  booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
  pages =	{114:1--114:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-322-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{297},
  editor =	{Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.114},
  URN =		{urn:nbn:de:0030-drops-202576},
  doi =		{10.4230/LIPIcs.ICALP.2024.114},
  annote =	{Keywords: Erd\H{o}s-P\'{o}sa property, Erd\H{o}s-P\'{o}sa pair, Graph parameters, Graph minors, Universal obstruction, Surface containment}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2023.26
Dynamic Programming on Bipartite Tree Decompositions

Authors: Lars Jaffke, Laure Morelle, Ignasi Sau, and Dimitrios M. Thilikos

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

Abstract
We revisit a graph width parameter that we dub bipartite treewidth, along with its associated graph decomposition that we call bipartite tree decomposition. Bipartite treewidth can be seen as a common generalization of treewidth and the odd cycle transversal number. Intuitively, a bipartite tree decomposition is a tree decomposition whose bags induce almost bipartite graphs and whose adhesions contain at most one vertex from the bipartite part of any other bag, while the width of such decomposition measures how far the bags are from being bipartite. Adapted from a tree decomposition originally defined by Demaine, Hajiaghayi, and Kawarabayashi [SODA 2010] and explicitly defined by Tazari [Theor. Comput. Sci. 2012], bipartite treewidth appears to play a crucial role for solving problems related to odd-minors, which have recently attracted considerable attention. As a first step toward a theory for solving these problems efficiently, the main goal of this paper is to develop dynamic programming techniques to solve problems on graphs of small bipartite treewidth. For such graphs, we provide a number of para-NP-completeness results, FPT-algorithms, and XP-algorithms, as well as several open problems. In particular, we show that K_t-Subgraph-Cover, Weighted Vertex Cover/Independent Set, Odd Cycle Transversal, and Maximum Weighted Cut are FPT parameterized by bipartite treewidth. We also provide the following complexity dichotomy when H is a 2-connected graph, for each of the H-Subgraph-Packing, H-Induced-Packing, H-Scattered-Packing, and H-Odd-Minor-Packing problems: if H is bipartite, then the problem is para-NP-complete parameterized by bipartite treewidth while, if H is non-bipartite, then the problem is solvable in XP-time. Beyond bipartite treewidth, we define 1-ℋ-treewidth by replacing the bipartite graph class by any graph class ℋ. Most of the technology developed here also works for this more general parameter.
Cite as

Lars Jaffke, Laure Morelle, Ignasi Sau, and Dimitrios M. Thilikos. Dynamic Programming on Bipartite Tree Decompositions. In 18th International Symposium on Parameterized and Exact Computation (IPEC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 285, pp. 26:1-26:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{jaffke_et_al:LIPIcs.IPEC.2023.26,
  author =	{Jaffke, Lars and Morelle, Laure and Sau, Ignasi and Thilikos, Dimitrios M.},
  title =	{{Dynamic Programming on Bipartite Tree Decompositions}},
  booktitle =	{18th International Symposium on Parameterized and Exact Computation (IPEC 2023)},
  pages =	{26:1--26:22},
  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.26},
  URN =		{urn:nbn:de:0030-drops-194455},
  doi =		{10.4230/LIPIcs.IPEC.2023.26},
  annote =	{Keywords: tree decomposition, bipartite graphs, dynamic programming, odd-minors, packing, maximum cut, vertex cover, independent set, odd cycle transversal}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2018.143
Congestion-Free Rerouting of Flows on DAGs

Authors: Saeed Akhoondian Amiri, Szymon Dudycz, Stefan Schmid, and Sebastian Wiederrecht

Published in: LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)

Abstract
Changing a given configuration in a graph into another one is known as a reconfiguration problem. Such problems have recently received much interest in the context of algorithmic graph theory. We initiate the theoretical study of the following reconfiguration problem: How to reroute k unsplittable flows of a certain demand in a capacitated network from their current paths to their respective new paths, in a congestion-free manner? This problem finds immediate applications, e.g., in traffic engineering in computer networks. We show that the problem is generally NP-hard already for k=2 flows, which motivates us to study rerouting on a most basic class of flow graphs, namely DAGs. Interestingly, we find that for general k, deciding whether an unsplittable multi-commodity flow rerouting schedule exists, is NP-hard even on DAGs. Our main contribution is a polynomial-time (fixed parameter tractable) algorithm to solve the route update problem for a bounded number of flows on DAGs. At the heart of our algorithm lies a novel decomposition of the flow network that allows us to express and resolve reconfiguration dependencies among flows.
Cite as

Saeed Akhoondian Amiri, Szymon Dudycz, Stefan Schmid, and Sebastian Wiederrecht. Congestion-Free Rerouting of Flows on DAGs. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 143:1-143:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{akhoondianamiri_et_al:LIPIcs.ICALP.2018.143,
  author =	{Akhoondian Amiri, Saeed and Dudycz, Szymon and Schmid, Stefan and Wiederrecht, Sebastian},
  title =	{{Congestion-Free Rerouting of Flows on DAGs}},
  booktitle =	{45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)},
  pages =	{143:1--143:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-076-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{107},
  editor =	{Chatzigiannakis, Ioannis and Kaklamanis, Christos and Marx, D\'{a}niel and Sannella, Donald},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.143},
  URN =		{urn:nbn:de:0030-drops-91471},
  doi =		{10.4230/LIPIcs.ICALP.2018.143},
  annote =	{Keywords: Unsplittable Flows, Reconfiguration, DAGs, FPT, NP-Hardness}
}
  • Refine by Author
  • 3 Wiederrecht, Sebastian
  • 2 Paul, Christophe
  • 2 Thilikos, Dimitrios M.
  • 1 Ahn, Jungho
  • 1 Akhoondian Amiri, Saeed
  • Show More...

  • Refine by Classification

  • Refine by Keyword
  • 1 DAGs
  • 1 Erdős-Pósa pair
  • 1 Erdős-Pósa property
  • 1 FPT
  • 1 Graph minors
  • Show More...

  • Refine by Type
  • 4 document

  • Refine by Publication Year
  • 1 2018
  • 1 2023
  • 1 2024
  • 1 2025

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-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact