论文标题
s-club群集顶点删除在间隔和分节良好的和弦图上
s-Club Cluster Vertex Deletion on Interval and Well-Partitioned Chordal Graphs
论文作者
论文摘要
在本文中，我们研究了\ textsc {$ s $ -club clubl cluster顶点删除}的计算复杂性。给定图形，\ textsc {$ s $ -club clubl cluster顶点删除（$ s $ -CVD）}旨在从图中删除最小数量的顶点，以使所得图的每个连接组件最多在$ s $中都具有直径。当$ s = 1 $时，相应的问题通常被称为\ sloppy \ textsc {cluster vertex deletion（cvd）}。我们为\ emph {Interval Graphs}上的\ textsc {$ s $ -cvd}提供更快的算法。对于每个$ s \ geq 1 $，我们给出一个$ o（n（n+m））$ - \ textsc {$ s $ cvd}的时间算法在带有$ n $ dertices和$ m $ edges的间隔图上。在$ s = 1 $的情况下，我们的算法比$ o（n^3）$ - cao \ etal的时间算法（theor.comput。sci。，2018）和$ s \ geq 2 $有了略有的改进，它显着改善了总体的运行时间$ \ weft（o \ weft（o \ weft（o \ weft）n^4^4^4^4^4^4^4^4^4^\ right） 我们还提供了一个多项式时间算法来求解\ emph {cvd} {cvd} {分区良好的和弦图}，这是一个由ahn \ etal（\ textsc {wg 2020}）引入的图形类，作为在缩小构造图形以及在串联图上缩小复杂性差异的工具，并且是完善图形的工具。我们的算法依赖于最佳解决方案的表征，并在\ textsc {加权两部分顶点盖}的多个实例上求解。这概括了cao \ etal（理论comput。Sci。，2018）的结果。 我们还表明，对于任何整数$ s \ geq 2 $，\ textsc {$ s $ -cvd}都是分区良好的和弦图上的np-hard。
In this paper, we study the computational complexity of \textsc{$s$-Club Cluster Vertex Deletion}. Given a graph, \textsc{$s$-Club Cluster Vertex Deletion ($s$-CVD)} aims to delete the minimum number of vertices from the graph so that each connected component of the resulting graph has a diameter at most $s$. When $s=1$, the corresponding problem is popularly known as \sloppy \textsc{Cluster Vertex Deletion (CVD)}. We provide a faster algorithm for \textsc{$s$-CVD} on \emph{interval graphs}. For each $s\geq 1$, we give an $O(n(n+m))$-time algorithm for \textsc{$s$-CVD} on interval graphs with $n$ vertices and $m$ edges. In the case of $s=1$, our algorithm is a slight improvement over the $O(n^3)$-time algorithm of Cao \etal (Theor. Comput. Sci., 2018) and for $s \geq 2$, it significantly improves the state-of-the-art running time $\left(O\left(n^4\right)\right)$. We also give a polynomial-time algorithm to solve \textsc{CVD} on \emph{well-partitioned chordal graphs}, a graph class introduced by Ahn \etal (\textsc{WG 2020}) as a tool for narrowing down complexity gaps for problems that are hard on chordal graphs, and easy on split graphs. Our algorithm relies on a characterisation of the optimal solution and on solving polynomially many instances of the \textsc{Weighted Bipartite Vertex Cover}. This generalises a result of Cao \etal (Theor. Comput. Sci., 2018) on split graphs. We also show that for any even integer $s\geq 2$, \textsc{$s$-CVD} is NP-hard on well-partitioned chordal graphs.
