Let d and k be two given integers, and let G be a graph. Can we reduce the independence number of G by at least d via at most k graph operations from some fixed set S? This problem belongs to a class of so-called blocker problems. It is known to be co-NP-hard even if S consists of either an edge contraction or a vertex deletion. We further investigate its computational complexity under these two settings: - we give a sufficient condition on a graph class for the vertex deletion variant to be co-NP-hard even if d = k = 1; - in addition we prove that the vertex deletion variant is co-NP-hard for triangle-free graphs even if d = k = 1; - we prove that the edge contraction variant is NP-hard for bipartite graphs but linear-time solvable for trees. By combining our new results with known ones we are able to give full complexity classifications for both variants restricted to H-free graphs.
展开▼
机译：假设D和K是两个给定的整数，让G是图形。我们可以通过一些固定集s的大多数K图形操作来减少G至少D的独立号码吗？这个问题属于一类所谓的阻塞问题。即使S由边缘收缩或顶点缺失组成，也已知是CO-NP - 硬。我们进一步调查了它在这两个设置下的计算复杂性： - 即使d = k = 1，我们在viptex删除变体的图表类上给出了足够的条件。 - 另外，我们证明了顶点删除变体是三角形图的CO-NP - 即使d = k = 1也是如此; - 我们证明了边缘收缩变体为二分的图形，但是树木的线性时间可解决。通过将我们的新结果与已知的结果相结合，我们能够为两个限制的变体提供完整的复杂性分类，限制为自由图形图。
展开▼
