A Complexity Analysis of the c-Closed Vertex Deletion Problem
摘要
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.