On the Complexity of Claw-Free Vertex Splitting
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866908570330595328 |
|---|---|
| author | Abu-Khzam, Faisal N. Thoumi, Sergio |
| author_facet | Abu-Khzam, Faisal N. Thoumi, Sergio |
| contents | Vertex splitting consists of taking a vertex $v$ in a graph and replacing it with two non-adjacent vertices whose combined neighborhoods is the neighborhood of $v$. The split is said to be exclusive when these neighborhoods are disjoint. In the Claw-Free (Exclusive) Vertex Splitting problem, we are given a graph $G$ and an integer $k$, and we are asked if we can perform at most $k$ (exclusive) vertex splits to obtain a claw-free graph. We consider the complexity of Claw-Free Exclusive Vertex Splitting and prove it to be NP-complete in general, while admitting a polynomial-time algorithm when the input graph has maximum degree 4. This result settles an open problem posed in [Firbas \& Sorge, ISAAC 2024]. We also show that our results can be generalized to $K_{1,c}$-Free Vertex Splitting for all $c \geq 3$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_06044 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | On the Complexity of Claw-Free Vertex Splitting Abu-Khzam, Faisal N. Thoumi, Sergio Computational Complexity Vertex splitting consists of taking a vertex $v$ in a graph and replacing it with two non-adjacent vertices whose combined neighborhoods is the neighborhood of $v$. The split is said to be exclusive when these neighborhoods are disjoint. In the Claw-Free (Exclusive) Vertex Splitting problem, we are given a graph $G$ and an integer $k$, and we are asked if we can perform at most $k$ (exclusive) vertex splits to obtain a claw-free graph. We consider the complexity of Claw-Free Exclusive Vertex Splitting and prove it to be NP-complete in general, while admitting a polynomial-time algorithm when the input graph has maximum degree 4. This result settles an open problem posed in [Firbas \& Sorge, ISAAC 2024]. We also show that our results can be generalized to $K_{1,c}$-Free Vertex Splitting for all $c \geq 3$. |
| title | On the Complexity of Claw-Free Vertex Splitting |
| topic | Computational Complexity |
| url | https://arxiv.org/abs/2506.06044 |