Search Results

Documents authored by Gorsky, Maximilian

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
DOI: 10.4230/LIPIcs.CSL.2022.22
Differential Games, Locality, and Model Checking for FO Logic of Graphs

Authors: Jakub Gajarský, Maximilian Gorsky, and Stephan Kreutzer

Published in: LIPIcs, Volume 216, 30th EACSL Annual Conference on Computer Science Logic (CSL 2022)

Abstract
We introduce differential games for FO logic of graphs, a variant of Ehrenfeucht-Fraïssé games in which the game is played on only one graph and the moves of both players are restricted. We prove that these games are strong enough to capture essential information about graphs from graph classes which are interpretable in nowhere dense graph classes. This, together with the newly introduced notion of differential locality and the fact that the restriction of possible moves by the players makes it easy to decide the winner of the game in some cases, leads to a new approach to the FO model checking problem which can be used on various graph classes interpretable in classes of sparse graphs.
Cite as

Jakub Gajarský, Maximilian Gorsky, and Stephan Kreutzer. Differential Games, Locality, and Model Checking for FO Logic of Graphs. In 30th EACSL Annual Conference on Computer Science Logic (CSL 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 216, pp. 22:1-22:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{gajarsky_et_al:LIPIcs.CSL.2022.22,
  author =	{Gajarsk\'{y}, Jakub and Gorsky, Maximilian and Kreutzer, Stephan},
  title =	{{Differential Games, Locality, and Model Checking for FO Logic of Graphs}},
  booktitle =	{30th EACSL Annual Conference on Computer Science Logic (CSL 2022)},
  pages =	{22:1--22:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-218-1},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{216},
  editor =	{Manea, Florin and Simpson, Alex},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2022.22},
  URN =		{urn:nbn:de:0030-drops-157426},
  doi =		{10.4230/LIPIcs.CSL.2022.22},
  annote =	{Keywords: FO model checking, locality, Gaifman’s theorem, EF games}
}
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