摘要
我们研究有界密度顶点删除（BDVD）的参数化复杂性：给定一个图 $G$、一个整数预算 $k$ 以及一个目标密度 $\tau_\rho$，任务是确定通过删除至多 $k$ 个顶点，$G$ 的最稠密子图的密度（即边数除以顶点数）是否可以降低到不超过 $\tau_\rho$。我们主要关注与树宽相关的结构图参数，因为 Bazgan 等人留下的关于树宽的 BDVD 参数化复杂性的问题尚未解决。我们通过展示与各种参数（包括树深和反馈顶点数）相关的 W[1]-难度来解决这个问题。这些结果表明，树宽的 W[1]-难度也得到了证实。
对于大于树深和反馈顶点数的参数，我们获得了正面结果，即我们证明 BDVD 在最大叶子数或顶点完整性参数下是固定参数可解的。在目标密度 $\tau_\rho$ 是固定常数的假设下，BDVD 的参数化复杂性格局发生了显著变化，即使对于比树宽更小的参数（如团宽），也存在固定参数可解的算法。总的来说，我们的结果为有界密度顶点删除提供了更精细的复杂性格局，清晰地区分了在结构参数化下可解和不可解的参数区域。
博主点评： 本文通过揭示有界密度顶点删除问题的复杂性，提供了对图论中重要问题的深刻见解，特别是在结构参数化方面的贡献，值得关注！