Finding d-Cuts in Graphs of Bounded Diameter, Graphs of Bounded Radius and H-Free Graphs
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866911191323901952 |
|---|---|
| author | Lucke, Felicia Momeni, Ali Paulusma, Daniël Smith, Siani |
| author_facet | Lucke, Felicia Momeni, Ali Paulusma, Daniël Smith, Siani |
| contents | The d-Cut problem is to decide if a graph has an edge cut such that each vertex has at most d neighbours at the opposite side of the cut. If $d=1$, we obtain the intensively studied Matching Cut problem. The d-Cut problem has been studied as well, but a systematic study for special graph classes was lacking. We initiate such a study and consider classes of bounded diameter, bounded radius and $H$-free graphs. We prove that for all $d\geq 2$, d-Cut is polynomial-time solvable for graphs of diameter 2, $(P_3+P_4)$-free graphs and $P_5$-free graphs. These results extend known results for $d=1$. However, we also prove several NP-hardness results for d-Cut that contrast known polynomial-time results for $d=1$. Our results lead to full dichotomies for bounded diameter and bounded radius and to almost-complete dichotomies for H-free graphs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2404_11389 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Finding d-Cuts in Graphs of Bounded Diameter, Graphs of Bounded Radius and H-Free Graphs Lucke, Felicia Momeni, Ali Paulusma, Daniël Smith, Siani Combinatorics Computational Complexity Discrete Mathematics Data Structures and Algorithms The d-Cut problem is to decide if a graph has an edge cut such that each vertex has at most d neighbours at the opposite side of the cut. If $d=1$, we obtain the intensively studied Matching Cut problem. The d-Cut problem has been studied as well, but a systematic study for special graph classes was lacking. We initiate such a study and consider classes of bounded diameter, bounded radius and $H$-free graphs. We prove that for all $d\geq 2$, d-Cut is polynomial-time solvable for graphs of diameter 2, $(P_3+P_4)$-free graphs and $P_5$-free graphs. These results extend known results for $d=1$. However, we also prove several NP-hardness results for d-Cut that contrast known polynomial-time results for $d=1$. Our results lead to full dichotomies for bounded diameter and bounded radius and to almost-complete dichotomies for H-free graphs. |
| title | Finding d-Cuts in Graphs of Bounded Diameter, Graphs of Bounded Radius and H-Free Graphs |
| topic | Combinatorics Computational Complexity Discrete Mathematics Data Structures and Algorithms |
| url | https://arxiv.org/abs/2404.11389 |