pith. sign in

arxiv: 2410.00568 · v5 · submitted 2024-10-01 · 💻 cs.DS · cs.DM

Approximation of Spanning Tree Congestion using Hereditary Bisection

Petr Kolman This is my paper

Pith reviewed 2026-05-23 20:15 UTC · model grok-4.3

classification 💻 cs.DS cs.DM
keywords spanning tree congestionhereditary bisectionapproximation algorithmgraph bisection widthedge congestionspanning tree
0
0 comments X

The pith

Spanning tree congestion is at least Omega of hereditary bisection width divided by maximum degree, yielding an O(Delta log to the 3/2 n) approximation.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper proves that the minimum possible maximum edge congestion over all spanning trees of G is at least a constant times the hereditary bisection width hb(G) divided by the maximum degree Delta. It then builds on this relation an algorithm that returns a spanning tree whose congestion is at most O(Delta times the square root of log cubed n) times the optimum. A reader would care because the only previously known guarantee was a trivial factor of n/2 that holds for every graph, so the new ratio is exponentially better once Delta is bounded by a polylog of n. The hereditary bisection width is the largest bisection width that appears in any subgraph of G.

Core claim

We prove that for every graph G, STC(G) is at least Omega(hb(G)/Delta) where hb(G) is the hereditary bisection width, and we give an O(Delta log^{3/2} n)-approximation algorithm for the spanning tree congestion problem.

What carries the argument

Hereditary bisection width hb(G), defined as the maximum bisection width over all subgraphs of G, which supplies the lower bound on congestion after scaling by 1/Delta.

If this is right

  • For any graph whose maximum degree is polylogarithmic in n the new algorithm improves exponentially on the trivial n/2 approximation.
  • The lower bound itself is presented as a tool of independent interest for analyzing spanning tree congestion.
  • The algorithm produces a spanning tree whose congestion is guaranteed to be within the stated factor of the minimum possible congestion.
  • The result applies directly to all graphs and gives a polylogarithmic approximation whenever Delta is polylogarithmic.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • If hereditary bisection width itself admits a fast approximation algorithm, the same framework could produce a practical heuristic for moderate-size instances.
  • The same cut-based lower bound may transfer to other problems that embed graphs into trees while controlling load on edges.
  • One could test whether the Omega(hb/Delta) relation remains tight when restricted to planar graphs or expanders, which the paper does not address.
  • The technique might combine with existing separators to improve the log factor in the approximation ratio.

Load-bearing premise

The hereditary bisection width can be related to the congestion of any spanning tree through a multiplicative factor of only Delta without hidden structural losses that would break the approximation ratio.

What would settle it

A concrete graph family in which every spanning tree has maximum congestion o(hb(G)/Delta), or an instance where the constructed tree exceeds the claimed O(Delta log^{3/2} n) factor.

read the original abstract

The Spanning Tree Congestion (STC) problem is the following NP-hard problem: given a graph $G$, construct a spanning tree $T$ of $G$ minimizing its maximum edge congestion where the congestion of an edge $e\in T$ is the number of edges $uv$ in $G$ such that the unique path between $u$ and $v$ in $T$ passes through $e$; the optimal value for a given graph $G$ is denoted $STC(G)$. It is known that every spanning tree is an $n/2$-approximation for the STP problem. A long-standing problem is to design a better approximation algorithm. Our contribution towards this goal is an $O(\Delta\cdot\log^{3/2}n)$-approximation algorithm where $\Delta$ is the maximum degree in $G$ and $n$ the number of vertices. For graphs with a maximum degree bounded by a polylog of the number of vertices, this is an exponential improvement over the previous best approximation. Our main tool for the algorithm is a new lower bound on the spanning tree congestion which is of independent interest. Denoting by $hb(G)$ the hereditary bisection of $G$ which is the maximum bisection width over all subgraphs of $G$, we prove that for every graph $G$, $STC(G)\geq \Omega(hb(G)/\Delta)$.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 0 minor

Summary. The paper claims to prove that STC(G) ≥ Ω(hb(G)/Δ) for every graph G, where hb(G) denotes hereditary bisection width, and to obtain an O(Δ log^{3/2} n)-approximation algorithm for the spanning tree congestion problem, improving on the known n/2-approximation (especially for polylog-bounded Δ).

Significance. If the lower bound and algorithm analysis hold without hidden logarithmic or structural losses, the work supplies both a new combinatorial tool (the hb-based lower bound) and a substantial improvement in approximation ratio for low-degree graphs.

major comments (1)
  1. [Abstract] Abstract (main tool paragraph): the claimed relation STC(G) ≥ Ω(hb(G)/Δ) is load-bearing for both the lower bound and the subsequent approximation ratio; without the full proof it is impossible to verify whether the Δ factor absorbs all congestion losses or whether additional log or structural factors appear that would invalidate the stated O(Δ log^{3/2} n) guarantee.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their review. We address the single major comment below, confirming that the full proof appears in the manuscript and supports the stated bounds without additional hidden factors.

read point-by-point responses

  1. Referee: [Abstract] Abstract (main tool paragraph): the claimed relation STC(G) ≥ Ω(hb(G)/Δ) is load-bearing for both the lower bound and the subsequent approximation ratio; without the full proof it is impossible to verify whether the Δ factor absorbs all congestion losses or whether additional log or structural factors appear that would invalidate the stated O(Δ log^{3/2} n) guarantee.

    Authors: The complete proof of STC(G) ≥ Ω(hb(G)/Δ) is given in Section 3. It proceeds by relating the hereditary bisection width directly to the minimum congestion over all spanning trees, with the Δ factor arising from a per-vertex degree argument that absorbs all congestion contributions from the bisection cuts; the analysis introduces no extra logarithmic or structural multiplicative terms. Section 4 then invokes this bound inside a recursive partitioning procedure whose depth and width analysis yields precisely the O(Δ log^{3/2} n) guarantee, with every constant and logarithmic factor tracked explicitly. revision: no

Circularity Check

0 steps flagged

No significant circularity identified

full rationale

The abstract presents a new lower bound STC(G) ≥ Ω(hb(G)/Δ) and an O(Δ log^{3/2} n)-approximation algorithm as independent contributions. No equations, definitions, or steps are supplied that would reduce the claimed bound or ratio to a fitted parameter, self-citation chain, or input by construction. The derivation chain cannot be shown to collapse internally from the given material, satisfying the default expectation of no circularity.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

Abstract-only review; no free parameters, invented entities, or non-standard axioms are visible. The lower bound is presented as a new relation between two graph quantities.

axioms (1)
  • standard math Standard facts from graph theory on spanning trees, cuts, and maximum degree
    Invoked to relate bisection width to congestion.

pith-pipeline@v0.9.0 · 5781 in / 1143 out tokens · 25721 ms · 2026-05-23T20:15:55.401362+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

10 extracted references · 10 canonical work pages

  1. [1]

    Vazirani

    Sanjeev Arora, Satish Rao, and Umesh V. Vazirani. Expander flows, geometric em- beddings and graph partitioning.J. ACM, 56(2):5:1–5:37, 2009. Preliminary version inProc. of the 40th Annual ACM Symposium on Theory of Computing (STOC), 2004.doi:10.1145/1502793.1502794

    work page doi:10.1145/1502793.1502794 2009

  2. [2]

    Sunil Chandran, Yun Kuen Cheung, and Davis Issac

    L. Sunil Chandran, Yun Kuen Cheung, and Davis Issac. Spanning tree congestion and computation of generalized Gy¨ ori-Lov´ asz partition. InProc. of 45th International Colloquium on Automata, Languages, and Programming (ICALP), volume 107 of LIPIcs, pages 32:1–32:14. Schloss Dagstuhl - Leibniz-Zentrum f¨ ur Informatik, 2018. doi:10.4230/LIPICS.ICALP.2018.32

    work page doi:10.4230/lipics.icalp.2018.32 2018

  3. [3]

    Sur les assemblages de lignes.Journal f¨ ur die reine und angewandte Mathematik, 70:185–190, 1869

    Camille Jordan. Sur les assemblages de lignes.Journal f¨ ur die reine und angewandte Mathematik, 70:185–190, 1869

    work page

  4. [4]

    Klein, Serge A

    Philip N. Klein, Serge A. Plotkin, and Satish Rao. Excluded minors, network decomposition, and multicommodity flow. InProc. of the Twenty-Fifth Annual ACM Symposium on Theory of Computing (STOC), pages 682–690, 1993.doi: 10.1145/167088.167261

    work page doi:10.1145/167088.167261 1993

  5. [5]

    Approximating spanning tree congestion on graphs with polylog degree

    Petr Kolman. Approximating spanning tree congestion on graphs with polylog degree. InProc. of International Workshop on Combinatorial Algorithms (IWOCA), pages 497–508, 2024.doi:10.1007/978-3-031-63021-7_38

    work page doi:10.1007/978-3-031-63021-7_38 2024

  6. [6]

    Approximation of Spanning Tree Congestion Using Hereditary Bisec- tion

    Petr Kolman. Approximation of Spanning Tree Congestion Using Hereditary Bisec- tion. InProc. of 42nd International Symposium on Theoretical Aspects of Computer Science (STACS), volume 327 ofLeibniz International Proceedings in Informatics (LIPIcs), pages 63:1–63:6. Schloss Dagstuhl – Leibniz-Zentrum f¨ ur Informatik, 2025. doi:10.4230/LIPIcs.STACS.2025.63

    work page doi:10.4230/lipics.stacs.2025.63 2025

  7. [7]

    Crossing number, pair-crossing number, and ex- pansion.Journal of Combinatorial Theory, Series B, 92(1):99–113, 2004.doi: 10.1016/j.jctb.2003.09.002

    Petr Kolman and Jiˇ r´ ı Matouˇ sek. Crossing number, pair-crossing number, and ex- pansion.Journal of Combinatorial Theory, Series B, 92(1):99–113, 2004.doi: 10.1016/j.jctb.2003.09.002

    work page doi:10.1016/j.jctb.2003.09.002 2004

  8. [8]

    Parameterized spanning tree congestion, 2024

    Michael Lampis, Valia Mitsou, Edouard Nemery, Yota Otachi, Manolis Vasilakis, and Daniel Vaz. Parameterized spanning tree congestion, 2024. URL:https://arxiv. org/abs/2410.08314,arXiv:2410.08314

    work page arXiv 2024

  9. [9]

    Better hardness results for the minimum spanning tree congestion problem.Algorithmica, pages 1–18, 2024

    Huong Luu and Marek Chrobak. Better hardness results for the minimum spanning tree congestion problem.Algorithmica, pages 1–18, 2024. Preliminary version inProc. of 17th International Conference and Workshops on Algorithms and Computation (WALCOM), 2023.doi:10.1007/s00453-024-01278-5

    work page doi:10.1007/s00453-024-01278-5 2024

  10. [10]

    A survey on spanning tree congestion

    Yota Otachi. A survey on spanning tree congestion. InTreewidth, Kernels, and Algorithms: Essays Dedicated to Hans L. Bodlaender on the Occasion of His 60th Birthday, volume 12160 ofLecture Notes in Computer Science, pages 165–172, 2020. doi:10.1007/978-3-030-42071-0_12. 7

    work page doi:10.1007/978-3-030-42071-0_12 2020