{
  "id": "2503.13112",
  "version": "v2",
  "published": "2025-03-17T12:34:42.000Z",
  "updated": "2025-05-15T14:07:16.000Z",
  "title": "Connected Partitions via Connected Dominating Sets",
  "authors": [
    "Aikaterini Niklanovits",
    "Kirill Simonov",
    "Shaily Verma",
    "Ziena Zeif"
  ],
  "categories": [
    "math.CO",
    "cs.DS"
  ],
  "abstract": "The classical theorem due to Gy\\H{o}ri and Lov\\'{a}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\\H{o}ri--Lov\\'{a}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\\H{o}ri--Lov\\'{a}sz theorem: 1. On general graphs, a Gy\\H{o}ri--Lov\\'{a}sz partition with $k$ parts can be computed in polynomial time when the input graph has connectivity $\\Omega(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.",
  "revisions": [
    {
      "version": "v2",
      "updated": "2025-05-15T14:07:16.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "connected partition",
      "polynomial time",
      "convex bipartite graphs",
      "connectivity requirement",
      "efficient constructive version"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}