For a graph invariant $\pi$, the Contraction($\pi$) 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 $\pi$ has dropped by at least $d$. Galby et al. [ISAAC 2019, MFCS 2019] recently studied the case where $\pi$ 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($\pi$) is co-NP-hard even for fixed $k=d=1$ when $\pi$ is the size of a minimum feedback vertex set or an odd cycle transversal. In sharp contrast, we show that when $\pi$ is the size of a minimum vertex cover, the problem is in XP parameterized by $d$.
翻译:对于一个变差值 $\ pion 美元, 合同问题( $\ pi$) 的问题在于, 给一个G$ 和两个正整数 $, 美元, 确定一个人是否可以在最多K$的边距以美元表示, 以获得一个美元表示, 美元至少下跌了美元。 Galby et al. [ISAAC 2019, MFCS 2019] 等最近研究了一个情况, 美元为最小支配值的大小 。 我们关注一个图形的变差体, 其定义为根据固定控制关系点击收藏中所有图表出现的最小大小 $_ cal H} 的顶点 。 我们证明, 在一些假设中, 美元为$- NP- 硬度的结果是 。 这特别意味着, 美元( $\ pip$) 即使固定的 美元= d= 1美元, 当美元是最小的回馈数或奇怪的周期反向值的大小时, 。 鲜明的对比是, 当 美元为 X 的 美元 的 。