DROPS

Document

Track A: Algorithms, Complexity and Games

DOI: 10.4230/LIPIcs.ICALP.2026.129

Thin Trees for near Minimum Cuts

Authors: Nathan Klein, Neil Olver, and Zi Song Yeoh

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

Abstract

The strong thin tree conjecture states that every k-edge-connected graph G contains an O(1/k)-thin spanning tree, meaning a spanning tree which contains at most an O(1/k) fraction of the edges across each cut in G. This conjecture is still open despite significant effort; the best current result by Anari and Oveis Gharan shows the existence of an O(polylog log n/k)-thin tree. In this work, we demonstrate that the conjecture is true if one only requires thinness for the set of η-near minimum cuts of the graph for η = 1/40, in other words, for the set of cuts with fewer than (1+1/40)k edges. Our approach constructs such a tree in polynomial time. To show this, we utilize the structure of near minimum cuts, and in particular the polygon representation of Benczúr and Goemans, to reduce to the previously solved problem of finding a spanning tree that is O(1/k)-thin for all sets in a laminar family.

Cite as

Nathan Klein, Neil Olver, and Zi Song Yeoh. Thin Trees for near Minimum Cuts. In 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 374, pp. 129:1-129:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{klein_et_al:LIPIcs.ICALP.2026.129,
  author =	{Klein, Nathan and Olver, Neil and Yeoh, Zi Song},
  title =	{{Thin Trees for near Minimum Cuts}},
  booktitle =	{53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)},
  pages =	{129:1--129:18},
  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.129},
  URN =		{urn:nbn:de:0030-drops-265180},
  doi =		{10.4230/LIPIcs.ICALP.2026.129},
  annote =	{Keywords: Graph Theory, Thin Trees, Polygon Representation, Near Minimum Cuts}
}

Search Results

Documents authored by Yeoh, Zi Song

Thin Trees for near Minimum Cuts

Abstract

Cite as

Thanks for your feedback!

Could not send message