{"id":"openai-math/A-polynomial-time-construction-of-strong-thin-trees","pdf":"https://github.com/openai/math/blob/main/preprints/A-polynomial-time-construction-of-strong-thin-trees-September-23-2026/paper.pdf","url":"https://github.com/openai/math/tree/main/preprints/A-polynomial-time-construction-of-strong-thin-trees-September-23-2026","tags":["graph-theory","spanning-trees","combinatorics"],"score":0,"title":"A polynomial-time construction of strong thin trees","domain":"Combinatorics","family":"174","origin":"ai-generated","source":"openai-math","authors":["OpenAI"],"reviews":0,"subject":"math.CO","summary":"We give a deterministic polynomial-time construction of strong thin trees. Given a finite k -edge-connected loopless multigraph on at least one vertex, the algorithm constructs a spanning tree meeting every cut in at most a $`C/k`$ fraction of its edges, for a universal constant C . The running time is polynomial in the binary input length, including when parallel-edge multiplicities are encoded in binary.","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-09-23","reactions":{},"formalized":false,"family_title":"Deterministic construction of strong thin spanning trees"}