DROPS

Document

Track A: Algorithms, Complexity and Games

DOI: 10.4230/LIPIcs.ICALP.2026.51

Well-Quasi-Ordering Eulerian Digraphs: Bounded Carving Width

Authors: Dario Cavallaro, Ken-ichi Kawarabayashi, and Stephan Kreutzer

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

Abstract

We prove that every class of Eulerian directed graphs of bounded carving width (equivalently, of bounded degree and treewidth) is well-quasi-ordered by strong immersion. In fact, we prove a stronger result, namely that every class of Eulerian directed graphs of bounded carving width, where every vertex is additionally labelled from a well-quasi-order, fixes a linear order on its incident edges, and may impose further restrictions on how the immersion is allowed to route paths through it, is well-quasi-ordered by an adequate notion of strong immersion. To this extent, we develop a framework seemingly suited to prove well-quasi-ordering for classes of Eulerian directed graphs by (strong) immersion and present a first meta theorem in that direction. We complement our results by observing that the class of Eulerian directed graphs of unbounded degree is not well-quasi-ordered by strong immersion, even if we assume the treewidth of the class to be at most two. We conclude with a dichotomy result, proving for a very restricted class of Eulerian directed graphs of unbounded degree that it is not well-quasi-ordered by strong immersion, but it is well-quasi-ordered by weak immersion.

Cite as

Dario Cavallaro, Ken-ichi Kawarabayashi, and Stephan Kreutzer. Well-Quasi-Ordering Eulerian Digraphs: Bounded Carving Width. In 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 374, pp. 51:1-51:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{cavallaro_et_al:LIPIcs.ICALP.2026.51,
  author =	{Cavallaro, Dario and Kawarabayashi, Ken-ichi and Kreutzer, Stephan},
  title =	{{Well-Quasi-Ordering Eulerian Digraphs: Bounded Carving Width}},
  booktitle =	{53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)},
  pages =	{51:1--51:19},
  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.51},
  URN =		{urn:nbn:de:0030-drops-264404},
  doi =		{10.4230/LIPIcs.ICALP.2026.51},
  annote =	{Keywords: algorithmic graph theory, structural graph theory, digraphs, immersions, well-quasi ordering}
}

Search Results

Documents authored by Cavallaro, Dario

Well-Quasi-Ordering Eulerian Digraphs: Bounded Carving Width

Abstract

Cite as

Thanks for your feedback!

Could not send message