{"ID":2855475,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2510.12050","arxiv_id":"2510.12050","title":"Thin Trees via $k$-Respecting Cut Identities","abstract":"Thin spanning trees lie at the intersection of graph theory, approximation algorithms, and combinatorial optimization. They are central to the long-standing \\emph{thin tree conjecture}, which asks whether every $k$-edge-connected graph contains an $O(1/k)$-thin tree, and they underpin algorithmic breakthroughs such as the $O(\\log n/\\log\\log n)$-approximation for ATSP. Yet even the basic algorithmic task of \\emph{verifying} that a given tree is thin has remained elusive: checking thinness requires reasoning about exponentially many cuts, and no efficient certificates have been known. We introduce a new machinery of \\emph{$k$-respecting cut identities}, which express the weight of every cut that crosses a spanning tree in at most $k$ edges as a simple function of pairwise ($2$-respecting) cuts. This yields a tree-local oracle that, after $O(n^2)$ preprocessing, evaluates such cuts in $O_k(1)$ time. Building on this oracle, we give the first procedure to compute the exact $k$-thinness certificate $Θ_k(T)$ of any spanning tree for fixed $k$ in time $\\tilde O(n^2+n^k)$, outputting both the certificate value and a witnessing cut. Beyond general graphs, our framework yields sharper guarantees in structured settings. In planar graphs, duality with cycles and dual girth imply that every spanning tree admits a verifiable certificate $Θ_k(T)\\le k/λ$ (hence $O(1/λ)$ for constant $k$). In graphs embedded on a surface of genus $γ$, refined counting gives certified (per-cut) bounds $O((\\log n+γ)/λ)$ via the same ensemble coverage.","short_abstract":"Thin spanning trees lie at the intersection of graph theory, approximation algorithms, and combinatorial optimization. They are central to the long-standing \\emph{thin tree conjecture}, which asks whether every $k$-edge-connected graph contains an $O(1/k)$-thin tree, and they underpin algorithmic breakthroughs such as...","url_abs":"https://arxiv.org/abs/2510.12050","url_pdf":"https://arxiv.org/pdf/2510.12050v1","authors":"[\"Mohit Daga\"]","published":"2025-10-14T01:21:14Z","proceeding":"cs.DS","tasks":"[\"cs.DS\",\"cs.DM\",\"math.CO\"]","methods":"[]","has_code":false}