Search Results

Documents authored by Wiederrecht, Sebastian

Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2026.64
Odd-Cycle-Packing-Treewidth: On the Maximum Independent Set Problem in Odd-Minor-Free Graph Classes

Authors: Mujin Choi, Maximilian Gorsky, Gunwoo Kim, Caleb McFarland, and Sebastian Wiederrecht

Published in: LIPIcs, Volume 374, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)

Abstract
We introduce the tree-decomposition-based graph parameter Odd-Cycle-Packing-treewidth (OCP-tw) as a width parameter that asks to decompose a given graph into pieces of bounded odd cycle packing number. The parameter OCP-tw is monotone under the odd-minor-relation and we provide an analogue to the celebrated Grid Theorem of Robertson and Seymour for OCP-tw. That is, we identify two infinite families of grid-like graphs whose presence as odd-minors implies large OCP-tw and prove that their absence implies bounded OCP-tw. This structural result is constructive and implies a 2^poly(k) poly(n)-time parameterized poly(k)-approximation algorithm for OCP-tw. Moreover, we show that the (weighted) Maximum Independent Set problem (MIS) can be solved in polynomial time on graphs of bounded OCP-tw. Finally, we lift the concept of OCP-tw to a parameter for matrices of integer programs. To this end, we show that our strategy can be applied to efficiently solve integer programs whose matrices have entries in {-1,0,1} and can be "tree-decomposed" into totally Δ-modular matrices with at most two non-zero entries per row.
Cite as

Mujin Choi, Maximilian Gorsky, Gunwoo Kim, Caleb McFarland, and Sebastian Wiederrecht. Odd-Cycle-Packing-Treewidth: On the Maximum Independent Set Problem in Odd-Minor-Free Graph Classes. In 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 374, pp. 64:1-64:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{choi_et_al:LIPIcs.ICALP.2026.64,
  author =	{Choi, Mujin and Gorsky, Maximilian and Kim, Gunwoo and McFarland, Caleb and Wiederrecht, Sebastian},
  title =	{{Odd-Cycle-Packing-Treewidth: On the Maximum Independent Set Problem in Odd-Minor-Free Graph Classes}},
  booktitle =	{53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)},
  pages =	{64:1--64:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-428-4},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{374},
  editor =	{Bhattacharya, Sayan and Nanongkai, Danupon and Benedikt, Michael and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2026.64},
  URN =		{urn:nbn:de:0030-drops-264533},
  doi =		{10.4230/LIPIcs.ICALP.2026.64},
  annote =	{Keywords: Odd-minor, treewidth, parameterized algorithm, graph minor, structural graph theory, Odd-Cycle-Packing-treewidth, Maximum Independent Set problem}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2026.99
Quickly Excluding an Annotated Planar Graph

Authors: Maximilian Gorsky, Evangelos Protopapas, and Sebastian Wiederrecht

Published in: LIPIcs, Volume 374, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)

Abstract
We provide proofs certifying that the structure theorem for vertex sets of bounded bidimensionality holds with polynomial bounds. The bidimensionality of vertex sets is a common generalisation of both treewidth and the face-cover-number of vertex sets in planar graphs. As such, it plays a crucial role in extensions of Courcelle’s Theorem to H-minor-free graphs. Recently, bidimensionality and similar parameters have emerged as key for extensions of known parameterized algorithms for problems defined on a terminal set R. A prominent example for such a problem is Steiner Tree, which admits efficient algorithms on planar graphs whenever R can be covered with few faces. Key to the algorithmic applications of bidimensionality is a structure theorem that explains how a graph G can be decomposed into pieces where the behaviour of R is highly controlled. One may see this structure theorem as a rooted analogue of Robertson and Seymour’s celebrated Grid Theorem. Combining recent advances in obtaining polynomial bounds in the Graph Minors framework with new techniques for handling annotated vertex sets, we show that all parameters in the structure theorem above admit polynomial bounds. As an application, we also provide a sketch showing how our techniques imply polynomial bounds for the structure theorem for graphs excluding an apex minor.
Cite as

Maximilian Gorsky, Evangelos Protopapas, and Sebastian Wiederrecht. Quickly Excluding an Annotated Planar Graph. In 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 374, pp. 99:1-99:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{gorsky_et_al:LIPIcs.ICALP.2026.99,
  author =	{Gorsky, Maximilian and Protopapas, Evangelos and Wiederrecht, Sebastian},
  title =	{{Quickly Excluding an Annotated Planar Graph}},
  booktitle =	{53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)},
  pages =	{99:1--99:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-428-4},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{374},
  editor =	{Bhattacharya, Sayan and Nanongkai, Danupon and Benedikt, Michael and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2026.99},
  URN =		{urn:nbn:de:0030-drops-264880},
  doi =		{10.4230/LIPIcs.ICALP.2026.99},
  annote =	{Keywords: Structural Graph Theory, Graph Minors, Annotated Graphs, Rooted Minors, Colorful Minors, Bidimensionality}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2026.100
The Price of Homogeneity Is Polynomial

Authors: Maximilian Gorsky, Michał T. Seweryn, and Sebastian Wiederrecht

Published in: LIPIcs, Volume 374, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)

Abstract
We provide explicit and polynomial bounds for the Homogeneous Wall Lemma which occurred for the first time implicitly in the 13th entry of Robertson and Seymour’s Graph Minors Series [JCTB 1990] and has since become a cornerstone in the algorithmic theory of graph minors. A wall where each brick is assigned a set of colours is said to be homogeneous if each brick is assigned the same set of colours. The Homogeneous Wall Lemma says that there exists a function h that, given non-negative integers q and k and an h(q,k)-wall W where each brick is assigned a, possibly empty, subset of {1,…,q} contains a k-wall W' as a subgraph such that, if one assigns to each brick B of W' the union of the sets assigned to the bricks of W in its interior, then W' is homogeneous. It is well-known that h(q,k) ∈ k^𝒪(q). The Homogeneous Wall Lemma plays a key role in most applications of the Irrelevant Vertex Technique where an exponential dependency of h on q usually causes non-uniform dependencies on meta-parameters at best and additional exponential blow-ups at worst. By proving that h(q,k) ∈ 𝒪(q⁴⋅ k⁶), we provide a positive answer to a problem raised by Sau, Stamoulis, and Thilikos [ICALP 2020].
Cite as

Maximilian Gorsky, Michał T. Seweryn, and Sebastian Wiederrecht. The Price of Homogeneity Is Polynomial. In 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 374, pp. 100:1-100:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{gorsky_et_al:LIPIcs.ICALP.2026.100,
  author =	{Gorsky, Maximilian and Seweryn, Micha{\l} T. and Wiederrecht, Sebastian},
  title =	{{The Price of Homogeneity Is Polynomial}},
  booktitle =	{53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)},
  pages =	{100:1--100:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-428-4},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{374},
  editor =	{Bhattacharya, Sayan and Nanongkai, Danupon and Benedikt, Michael and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2026.100},
  URN =		{urn:nbn:de:0030-drops-264891},
  doi =		{10.4230/LIPIcs.ICALP.2026.100},
  annote =	{Keywords: Graph Minors, Grid Graph, Wall Graph, Homogeneous Wall, Colored Graph, Annotated Graph, Structural Graph Theory, Irrelevant Vertex Technique}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2026.149
Colorful Minors

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

Published in: LIPIcs, Volume 374, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)

Abstract
We introduce the notion of colorful minors, which generalizes the classical concept of rooted minors in graphs. A q-colorful graph is defined as a pair (G, χ), where G is a graph and χ assigns to each vertex a (possibly empty) subset of at most q colors. The colorful minor relation enhances the classical minor relation by merging color sets at contracted edges and allowing the removal of colors from vertices. This framework naturally models algorithmic problems involving graphs with (possibly overlapping) annotated vertex sets. We develop a structural theory for colorful minors by establishing three core theorems characterizing ℋ-colorful minor-free graphs, where ℋ consists either of a clique or a grid with all vertices assigned all colors, or of grids with colors segregated and ordered on the outer face. Our results reveal that when exclusion is imposed not only on graphs but also to the way colors are distributed in them, a more refined structural landscape appears. Leveraging our structural insights, we provide a complete classification - parameterized by the number q of colors - of all colorful graphs that exhibit the Erdős–Pósa property with respect to colorful minors. On the algorithmic side, we deduce that colorful minor testing is fixed-parameter tractable. Together with the fact that the colorful minor relation forms a well-quasi-order, this implies that every colorful minor-monotone parameter on colorful graphs admits a fixed-parameter algorithm. Furthermore, we derive two algorithmic meta-theorems (AMTs) whose structural conditions are linked to extensions of treewidth and Hadwiger number on colorful graphs. Our results suggest how known AMTs can be extended to incorporate not only the structure of the input graph but also the way the colored vertices are distributed in it.
Cite as

Evangelos Protopapas, Dimitrios M. Thilikos, and Sebastian Wiederrecht. Colorful Minors. In 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 374, pp. 149:1-149:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{protopapas_et_al:LIPIcs.ICALP.2026.149,
  author =	{Protopapas, Evangelos and Thilikos, Dimitrios M. and Wiederrecht, Sebastian},
  title =	{{Colorful Minors}},
  booktitle =	{53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)},
  pages =	{149:1--149:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-428-4},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{374},
  editor =	{Bhattacharya, Sayan and Nanongkai, Danupon and Benedikt, Michael and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2026.149},
  URN =		{urn:nbn:de:0030-drops-265380},
  doi =		{10.4230/LIPIcs.ICALP.2026.149},
  annote =	{Keywords: Graph Minors, Colorful Minors, Annotated Graphs, Rooted Minors, Erd\H{o}s-P\'{o}sa property, Structural Graph Theory, Obstruction sets, Algorithmic Meta-Theorems, Bidimensionality}
}
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.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}
}
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact