论文标题
关于删除到$ \ MATHCAL {h} $的参数化复杂性 - 免费的强组件
On the Parameterized Complexity of Deletion to $\mathcal{H}$-free Strong Components
论文作者
论文摘要
{\ sc定向反馈顶点集（DFVS）}是一个基本的计算问题，在参数化的复杂性上已广泛关注。在本文中，我们启动了广泛概括的研究，即{\ sc $ {\ cal h} $ - 免费的SCC删除}问题。在这里，给出了一个digraph $ d $，一个整数$ k $，目的是确定是否有一组尺寸的顶点$ k $，其删除的删除留下了一个digraph，其中每个强的组件都不包括固定有限族$ {\ cal h} $中的图形。当$ {\ cal h} $仅包含单个弧形的挖掘物时，此问题恰好是DFV。 我们的主要结果是证明，如果$ {\ cal h} $仅包含根源图，或者如果$ {\ cal h} $包含至少一个有向路径，则此问题可通过删除集的大小来固定参数参数。除了概括DFV的固定参数障碍性结果外，我们的结果还推广了Göke等人的最新结果。 [CIAC 2019]对于{\ sc 1-out-regular顶点删除}和{\ sc有界尺寸强大的组件顶点删除}问题。此外，我们为上述两个问题设计了算法，它们的运行时间更好，并且与{\ sc dfvs}的最佳界限匹配，而无需使用Göke等人所做的重型删除阴影的重型机械。 [CIAC 2019]。
{\sc Directed Feedback Vertex Set (DFVS)} is a fundamental computational problem that has received extensive attention in parameterized complexity. In this paper, we initiate the study of a wide generalization, the {\sc ${\cal H}$-free SCC Deletion} problem. Here, one is given a digraph $D$, an integer $k$ and the objective is to decide whether there is a vertex set of size at most $k$ whose deletion leaves a digraph where every strong component excludes graphs in the fixed finite family ${\cal H}$ as (not necessarily induced) subgraphs. When ${\cal H}$ comprises only the digraph with a single arc, then this problem is precisely DFVS. Our main result is a proof that this problem is fixed-parameter tractable parameterized by the size of the deletion set if ${\cal H}$ only contains rooted graphs or if ${\cal H}$ contains at least one directed path. Along with generalizing the fixed-parameter tractability result for DFVS, our result also generalizes the recent results of Göke et al. [CIAC 2019] for the {\sc 1-Out-Regular Vertex Deletion} and {\sc Bounded Size Strong Component Vertex Deletion} problems. Moreover, we design algorithms for the two above mentioned problems, whose running times are better and match with the best bounds for {\sc DFVS}, without using the heavy machinery of shadow removal as is done by Göke et al. [CIAC 2019].
