2025/11/17 by Lisa Lehner, Christian Komusiewicz, Lehner, Lisa +3
Biochemistry, Genetics and Molecular Biology · Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Genome Rearrangement Algorithms
paper · pdf · doi:10.48550/arxiv.2511.13301
openalex publication_date 2025/11/17 · openalex created_date 2025/11/19 · openalex updated_date 2026/07/28
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(x3 + x2⋅ 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.