细树验证是coNP完全的

本文探讨了验证图中生成树“细度”的计算复杂性。细树猜想是图论中一个重要的未解决问题，并且能够有效地构建细树对于解决非对称旅行商问题（ATSP）等问题的近似算法具有重要意义。本文的主要贡献是证明了验证树的细度是coNP难的，这意味着确定给定树是否满足细度标准在计算上可能很困难。这一结果对与细树猜想和相关优化问题相关的算法的开发具有影响。

• •证明了验证树的细度是coNP难的。
• •这一结果对与细树猜想相关问题的计算复杂性有影响。
• •这些发现影响了相关优化问题（如ATSP）的算法开发。