论文标题
关于$ S $ -Club群集边缘删除问题的参数化复杂性
On the Parameterized Complexity of the $s$-Club Cluster Edge Deletion Problem
论文作者
论文摘要
我们研究了$ s $ -club群集边缘删除问题的参数化复杂性：给定图形$ g $和两个整数$ s \ ge 2 $和$ k \ ge 1 $，是否有可能从$ g $中删除最多$ k $的边缘，以便最多可产生的图形的每个连接组件在最多$ $ s $？当$ s = 2 $时，已知该问题已经是NP-HARD。我们证明，当通过$ s $和输入图的树宽参数化时，它将接受固定参数可拖动算法。
We study the parameterized complexity of the $s$-Club Cluster Edge Deletion problem: Given a graph $G$ and two integers $s \ge 2$ and $k \ge 1$, is it possible to remove at most $k$ edges from $G$ such that each connected component of the resulting graph has diameter at most $s$? This problem is known to be NP-hard already when $s = 2$. We prove that it admits a fixed-parameter tractable algorithm when parameterized by $s$ and the treewidth of the input graph.
