Inclusive and Exclusive Vertex Splitting into Specific Graph Classes: NP Hardness and Algorithms
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866914132203143168 |
|---|---|
| author | Gaikwad, Ajinkya Kumar, Hitendra Padmapriya, S. Patra, Praneet Kumar Sanklecha, Harsh Maity, Soumen |
| author_facet | Gaikwad, Ajinkya Kumar, Hitendra Padmapriya, S. Patra, Praneet Kumar Sanklecha, Harsh Maity, Soumen |
| contents | We study a family of graph modification problems called the F-Vertex Splitting problem. Given a graph G, the task is to determine whether G can be transformed into a graph G-prime belonging to a graph class F through a sequence of at most k vertex splits. We investigate this problem for several target graph classes, namely constellations, cycle graphs, linear forests, and bipartite graphs. We analyze both inclusive and exclusive variants of vertex splitting, as introduced by Abu-Khzam and collaborators (ISCO 2018). Our results show that the F-Vertex Splitting problem is polynomial-time solvable when F is a cycle graph or a linear forest, for both variants. In contrast, when F is a constellation or a bipartite graph, the problem is NP-complete for both variants. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_26938 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Inclusive and Exclusive Vertex Splitting into Specific Graph Classes: NP Hardness and Algorithms Gaikwad, Ajinkya Kumar, Hitendra Padmapriya, S. Patra, Praneet Kumar Sanklecha, Harsh Maity, Soumen Data Structures and Algorithms Computational Complexity We study a family of graph modification problems called the F-Vertex Splitting problem. Given a graph G, the task is to determine whether G can be transformed into a graph G-prime belonging to a graph class F through a sequence of at most k vertex splits. We investigate this problem for several target graph classes, namely constellations, cycle graphs, linear forests, and bipartite graphs. We analyze both inclusive and exclusive variants of vertex splitting, as introduced by Abu-Khzam and collaborators (ISCO 2018). Our results show that the F-Vertex Splitting problem is polynomial-time solvable when F is a cycle graph or a linear forest, for both variants. In contrast, when F is a constellation or a bipartite graph, the problem is NP-complete for both variants. |
| title | Inclusive and Exclusive Vertex Splitting into Specific Graph Classes: NP Hardness and Algorithms |
| topic | Data Structures and Algorithms Computational Complexity |
| url | https://arxiv.org/abs/2510.26938 |