Thin Trees via $k$-Respecting Cut Identities
Fuente:
arXiv
Guardado en:
| Autor principal: | |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866915553115897856 |
|---|---|
| author | Daga, Mohit |
| author_facet | Daga, Mohit |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_12050 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Thin Trees via $k$-Respecting Cut Identities Daga, Mohit Data Structures and Algorithms Discrete Mathematics Combinatorics 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. |
| title | Thin Trees via $k$-Respecting Cut Identities |
| topic | Data Structures and Algorithms Discrete Mathematics Combinatorics |
| url | https://arxiv.org/abs/2510.12050 |