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…