摘要
双宽度是一个图参数，对于解释许多图类的一阶模型检查的固定参数可处理性至关重要。尽管其算法重要性显著，计算双宽度的难度仍然较高：即使是识别双宽度最多为四的图也是 NP-hard，并且目前尚无基于双宽度本身的固定参数近似算法。
最近的一种方法集中在开发计算或近似双宽度的固定参数算法，参数化方式不同于双宽度。我们的第一个结果表明，当以树深度作为参数时，近似双宽度是固定参数可处理的，这打破了之前所有可处理参数化均基于删除距离的长期障碍。
证明过程通过有向双宽度展开，为这一变体可能在算法上更易处理提供了首个建设性证据。
作为我们的第二个主要结果，我们展示了在顶点完整性方面，精确计算双宽度也是固定参数可处理的。这构成了计算最优收缩序列的首个非平凡参数化算法。
博主点评： 双宽度的计算难度长期以来一直是图论中的一大难题，这项研究通过引入树深度和顶点完整性提供了新的思路，展示了如何克服传统参数化算法的局限性。这样的进展不仅有助于理论研究，也可能为实际应用中的图处理提供新的解决方案。