Finding $d$-Cuts in Probe $H$-Free Graphs
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866916764448718848 |
|---|---|
| author | Dabrowski, Konrad K. Eagling-Vose, Tala Johnson, Matthew Paesani, Giacomo Paulusma, Daniël |
| author_facet | Dabrowski, Konrad K. Eagling-Vose, Tala Johnson, Matthew Paesani, Giacomo Paulusma, Daniël |
| contents | For an integer $d\geq 1$, the $d$-Cut problem is that of deciding whether a graph has an edge cut in which each vertex is adjacent to at most $d$ vertices on the opposite side of the cut. The $1$-Cut problem is the well-known Matching Cut problem. The $d$-Cut problem has been extensively studied for $H$-free graphs. We extend these results to the probe graph model, where we do not know all the edges of the input graph. For a graph $H$, a partitioned probe $H$-free graph $(G,P,N)$ consists of a graph $G=(V,E)$, together with a set $P\subseteq V$ of probes and an independent set $N=V\setminus P$ of non-probes such that we can change $G$ into an $H$-free graph by adding zero or more edges between vertices in $N$. For every graph $H$ and every integer $d\geq 1$, we completely determine the complexity of $d$-Cut on partitioned probe $H$-free graphs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_22351 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Finding $d$-Cuts in Probe $H$-Free Graphs Dabrowski, Konrad K. Eagling-Vose, Tala Johnson, Matthew Paesani, Giacomo Paulusma, Daniël Data Structures and Algorithms Computational Complexity Discrete Mathematics Combinatorics For an integer $d\geq 1$, the $d$-Cut problem is that of deciding whether a graph has an edge cut in which each vertex is adjacent to at most $d$ vertices on the opposite side of the cut. The $1$-Cut problem is the well-known Matching Cut problem. The $d$-Cut problem has been extensively studied for $H$-free graphs. We extend these results to the probe graph model, where we do not know all the edges of the input graph. For a graph $H$, a partitioned probe $H$-free graph $(G,P,N)$ consists of a graph $G=(V,E)$, together with a set $P\subseteq V$ of probes and an independent set $N=V\setminus P$ of non-probes such that we can change $G$ into an $H$-free graph by adding zero or more edges between vertices in $N$. For every graph $H$ and every integer $d\geq 1$, we completely determine the complexity of $d$-Cut on partitioned probe $H$-free graphs. |
| title | Finding $d$-Cuts in Probe $H$-Free Graphs |
| topic | Data Structures and Algorithms Computational Complexity Discrete Mathematics Combinatorics |
| url | https://arxiv.org/abs/2505.22351 |