Thin Tree Verification is coNP-Complete

Alice Moayyedi

An $\hat{I}\pm$-thin tree $T$ of a graph $G$ is a spanning tree such that every cut of $G$ has at most an $\hat{I}\pm$ proportion of its edges in $T$. The Thin Tree Conjecture proposes that there…