A polynomial-time construction of strong thin trees
There is an absolute constant such that, given a finite -edge-connected loopless multigraph on at least one vertex and an integer , a deterministic algorithm returns a spanning tree satisfying for all in time polynomial in the total binary input length, whether edges are listed explicitly or multiplicities are encoded in binary (with the empty tree returned for a one-vertex graph).
The proof of Theorem 1.1 for both explicit and binary-multiplicity models is complete, with all iteration counts, product bounds, and bit-complexity estimates rigorously established.
“Theorem 1.1 (Algorithmic strong thin trees). There is an absolute constant C with the following property. Given a finite k-edge-connected multigraph G on at least one vertex and an integer k ≥ 1, a deterministic algorithm returns a spanning tree T satisfying |δT (S)| ≤ C/k |δG(S)| (∅ ̸= S ⊊ V (G)) (1.1) in time polynomial in the total binary input length, whether edges are listed explicitly or multiplicities are encoded in binary. For a one-vertex graph the answer is the empty tree.” · Show in paper