A graph is c-closed when every pair of nonadjacent vertices has at most  \(c-1\) common neighbors. In \(c\) -Closed Vertex Deletion, the input is a graph G and an integer k and we ask whether G can be transformed into a c-closed graph by deleting at most k vertices. We study the classic and parameterized complexity of \(c\) -Closed Vertex Deletion. We obtain, for example, NP-hardness for the case that G is bipartite with bounded maximum degree. We also show upper and lower bounds on the size of problem kernels for the parameter k and introduce a new parameter, the number x of vertices in bad pairs, for which we show a problem kernel of size  \(\mathcal {O}(x^3 + x^2\cdot c))\) . Here, a pair of nonadjacent vertices is bad if they have at least c common neighbors. Finally, we show that \(c\) -Closed Vertex Deletion can be solved in polynomial time on unit interval graphs with depth at most  \(c+1\) and that it is fixed-parameter tractable with respect to the neighborhood diversity of G.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

A Complexity Analysis of the c-Closed Vertex Deletion Problem

  • Lisa Lehner,
  • Christian Komusiewicz,
  • Luca Pascal Staus

摘要

A graph is c-closed when every pair of nonadjacent vertices has at most  \(c-1\) common neighbors. In \(c\) -Closed Vertex Deletion, the input is a graph G and an integer k and we ask whether G can be transformed into a c-closed graph by deleting at most k vertices. We study the classic and parameterized complexity of \(c\) -Closed Vertex Deletion. We obtain, for example, NP-hardness for the case that G is bipartite with bounded maximum degree. We also show upper and lower bounds on the size of problem kernels for the parameter k and introduce a new parameter, the number x of vertices in bad pairs, for which we show a problem kernel of size  \(\mathcal {O}(x^3 + x^2\cdot c))\) . Here, a pair of nonadjacent vertices is bad if they have at least c common neighbors. Finally, we show that \(c\) -Closed Vertex Deletion can be solved in polynomial time on unit interval graphs with depth at most  \(c+1\) and that it is fixed-parameter tractable with respect to the neighborhood diversity of G.