论文标题
通过收缩和删除减少图形参数
Reducing Graph Parameters by Contractions and Deletions
论文作者
论文摘要
我们考虑以下问题：对于给定的图形$ g $和两个整数$ k $和$ d $，我们是否可以在最多使用$ k $ times的固定图操作，以将给定的图参数$π$减少至少$ d $？我们表明，当参数是独立数字，并且图形操作是顶点删除或边缘收缩时，即使对于固定的$ d = 1 $，并且限制在弦弦图时，则此问题是NP-HARD。当操作为边缘收缩时，我们给出了两分图的多项式时间算法，参数为独立数，$ d $是固定的。此外，当参数为集团数字时，我们完成了$ h $ free图的复杂性二分法，并且通过证明此问题为$（C_3+P_1）$ - 即使固定$ d = 1 $，操作是边缘收缩。当操作是边缘删除，并且参数是色数时，我们确定了Cographs和完整多部分图上相关问题的计算复杂性。我们的结果回答了[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 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$. When the operation is edge deletion and the parameter is the chromatic number, we determine the computational complexity of the associated problem on cographs and complete multipartite graphs. Our results answer several open questions stated in [Diner et al., Theoretical Computer Science, 746, p. 49-72 (2012)].
