论文标题
使用边缘收缩和顶点删除来减少独立数和集团数字
Using Edge Contractions and Vertex Deletions to Reduce the Independence Number and the Clique Number
论文作者
论文摘要
我们考虑以下问题：对于给定的图G和两个整数K和D，我们可以在最多k时应用固定的图操作以将给定的图参数$π$减少至少d吗？我们表明，当参数是独立性数字，并且图形操作是顶点删除或边缘收缩时，即使对于固定的d = 1，并且仅限于弦图时，该问题是NP-HARD。我们还给出了两分图的多项式时间算法时，当操作是边缘收缩时，参数为独立数，d是固定的。此外，当参数是集团数字时，我们完成了无H-Free图的复杂性二分法，并且通过证明此问题为NP-HARD（$ C_3+P_1 $） - 即使对于固定d = 1，则操作是边缘收缩。我们的结果回答了[Diner等人，理论计算机科学，第746页，第746页。 49-72（2012）]。
We consider the following problem: for a given graph G and two integers k and d, can we apply a fixed graph operation at most k times in order to reduce a given graph parameter $π$ by at least d? We show that this problem is NP-hard when the parameter is the independence number and the graph operation is vertex deletion or edge contraction, even for fixed d=1 and when restricted to chordal graphs. We also give a polynomial time algorithm for bipartite graphs when the operation is edge contraction, the parameter is the independence number and d is fixed. Further, we complete the complexity dichotomy on H-free graphs when the parameter is the clique number and the operation is edge contraction by showing that this problem is NP-hard in ($C_3+P_1$)-free graphs even for fixed d=1. Our results answer several open questions stated in [Diner et al., Theoretical Computer Science, 746, p. 49-72 (2012)].
