A Complexity Analysis of the c-Closed Vertex Deletion Problem

Abstract

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 $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$.