2026-07-22T19:33:56Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:16450 2024-03-06T10:57:31Z ddc:004 open_access

Faster Cut-Equivalent Trees in Simple Graphs Zhang, Tianyi graph algorithms minimum cuts max-flow Let G = (V, E) be an undirected connected simple graph on n vertices. A cut-equivalent tree of G is an edge-weighted tree on the same vertex set V, such that for any pair of vertices s, t ∈ V, the minimum (s, t)-cut in the tree is also a minimum (s, t)-cut in G, and these two cuts have the same cut value. In a recent paper [Abboud, Krauthgamer and Trabelsi, STOC 2021], the authors propose the first subcubic time algorithm for constructing a cut-equivalent tree. More specifically, their algorithm has Õ(n^{2.5}) running time. Later on, this running time was significantly improved to n^{2+o(1)} by two independent works [Abboud, Krauthgamer and Trabelsi, FOCS 2021] and [Li, Panigrahi, Saranurak, FOCS 2021], and then to (m+n^{1.9})^{1+o(1)} by [Abboud, Krauthgamer and Trabelsi, SODA 2022]. In this paper, we improve the running time to Õ(n²) graphs if near-linear time max-flow algorithms exist, or Õ(n^{17/8}) using the currently fastest max-flow algorithm. Although our algorithm is slower than previous works, the runtime bound becomes better by a sub-polynomial factor in dense simple graphs when assuming near-linear time max-flow algorithms. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Tianyi Zhang 2022 Is Part Of LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2022.109 urn:nbn:de:0030-drops-164507 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.109 eng https://creativecommons.org/licenses/by/4.0/legalcode