A Complexity Analysis of the c-Closed Vertex Deletion Problem
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911270158991360 |
|---|---|
| author | Lehner, Lisa Komusiewicz, Christian Staus, Luca Pascal |
| author_facet | Lehner, Lisa Komusiewicz, Christian Staus, Luca Pascal |
| contents | 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$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_13301 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A Complexity Analysis of the c-Closed Vertex Deletion Problem Lehner, Lisa Komusiewicz, Christian Staus, Luca Pascal Data Structures and Algorithms Computational Complexity 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$. |
| title | A Complexity Analysis of the c-Closed Vertex Deletion Problem |
| topic | Data Structures and Algorithms Computational Complexity |
| url | https://arxiv.org/abs/2511.13301 |