Connected Partitions via Connected Dominating Sets
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_ | 1866912377387089920 |
|---|---|
| author | Niklanovits, Aikaterini Simonov, Kirill Verma, Shaily Zeif, Ziena |
| author_facet | Niklanovits, Aikaterini Simonov, Kirill Verma, Shaily Zeif, Ziena |
| contents | The classical theorem due to Győri and Lovász states that any $k$-connected graph $G$ admits a partition into $k$ connected subgraphs, where each subgraph has a prescribed size and contains a prescribed vertex, as long as the total size of target subgraphs is equal to the size of $G$. However, this result is notoriously evasive in terms of efficient constructions, and it is still unknown whether such a partition can be computed in polynomial time, even for $k = 5$.
We make progress towards an efficient constructive version of the Győri--Lovász theorem by considering a natural strengthening of the $k$-connectivity requirement. Specifically, we show that the desired connected partition can be found in polynomial time, if $G$ contains $k$ disjoint connected dominating sets. As a consequence of this result, we give several efficient approximate and exact constructive versions of the original Győri--Lovász theorem:
1. On general graphs, a Győri--Lovász partition with $k$ parts can be computed in polynomial time when the input graph has connectivity $Ω(k \cdot \log^2 n)$;
2. On convex bipartite graphs, connectivity of $4k$ is sufficient;
3. On biconvex graphs and interval graphs, connectivity of $k$ is sufficient, meaning that our algorithm gives a ``true'' constructive version of the theorem on these graph classes. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2503_13112 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Connected Partitions via Connected Dominating Sets Niklanovits, Aikaterini Simonov, Kirill Verma, Shaily Zeif, Ziena Combinatorics Data Structures and Algorithms The classical theorem due to Győri and Lovász states that any $k$-connected graph $G$ admits a partition into $k$ connected subgraphs, where each subgraph has a prescribed size and contains a prescribed vertex, as long as the total size of target subgraphs is equal to the size of $G$. However, this result is notoriously evasive in terms of efficient constructions, and it is still unknown whether such a partition can be computed in polynomial time, even for $k = 5$. We make progress towards an efficient constructive version of the Győri--Lovász theorem by considering a natural strengthening of the $k$-connectivity requirement. Specifically, we show that the desired connected partition can be found in polynomial time, if $G$ contains $k$ disjoint connected dominating sets. As a consequence of this result, we give several efficient approximate and exact constructive versions of the original Győri--Lovász theorem: 1. On general graphs, a Győri--Lovász partition with $k$ parts can be computed in polynomial time when the input graph has connectivity $Ω(k \cdot \log^2 n)$; 2. On convex bipartite graphs, connectivity of $4k$ is sufficient; 3. On biconvex graphs and interval graphs, connectivity of $k$ is sufficient, meaning that our algorithm gives a ``true'' constructive version of the theorem on these graph classes. |
| title | Connected Partitions via Connected Dominating Sets |
| topic | Combinatorics Data Structures and Algorithms |
| url | https://arxiv.org/abs/2503.13112 |