论文标题
通过边缘收缩减少图形横向
Reducing graph transversals via edge contractions
论文作者
论文摘要
对于图形不变$π$，鉴于图$ g $和两个正整数$ k，d $的收缩（$π$）问题，决定是否可以收缩$ g $ g $的最多$ k $ edges，以获取$π$至少下降至$ d $的图表。 Galby等。 [ISAAC 2019，MFCS 2019]最近研究了$π$的案例，是最低占主导地位的大小。我们专注于定义的图形不变式，该基集的最小大小，该基集击中了根据固定的封存关系，将$ {\ cal H} $中的所有图形出现。我们证明了$ {\ cal h} $的图表下的某些假设下的共同成绩结果，这尤其暗示着即使对于固定的$ k = 1 $，当$π$是最小反馈顶点设置或奇数周期的最小反馈的大小时，收缩（$π$）即使是co-np-hard。相比之下，我们表明，当$π$是最小顶点盖的大小时，问题在XP参数为$ D $中。
For a graph invariant $π$, the Contraction($π$) problem consists in, given a graph $G$ and two positive integers $k,d$, deciding whether one can contract at most $k$ edges of $G$ to obtain a graph in which $π$ has dropped by at least $d$. Galby et al. [ISAAC 2019, MFCS 2019] recently studied the case where $π$ is the size of a minimum dominating set. We focus on graph invariants defined as the minimum size of a vertex set that hits all the occurrences of graphs in a collection ${\cal H}$ according to a fixed containment relation. We prove co-NP-hardness results under some assumptions on the graphs in ${\cal H}$, which in particular imply that Contraction($π$) is co-NP-hard even for fixed $k=d=1$ when $π$ is the size of a minimum feedback vertex set or an odd cycle transversal. In sharp contrast, we show that when $π$ is the size of a minimum vertex cover, the problem is in XP parameterized by $d$.
