Search Results

Documents authored by Seweryn, Michał T.

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}
}
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