Breaking the Exponential Barrier: The First Polynomial-Time Algorithm for the Győri-Lovász Theorem
2026-08-31 • Data Structures and Algorithms
Data Structures and Algorithms
AI summaryⓘ
The authors present the first polynomial-time algorithm for the Győri-Lovász theorem, which says any highly connected graph can be split into several connected parts of chosen sizes. Previously, only non-constructive or exponential-time proofs existed, and it was unknown if an efficient algorithm was possible. By introducing a new idea called flow-essential assignment that combines matching and cut structures, they create an efficient way to actually find these partitions. Their method also works for a stronger directed version of the theorem, even giving near-linear time algorithms for directed acyclic graphs, and extends to weighted cases where previous results were only existential.
Győri-Lovász theoremk-connected graphgraph partitioningpolynomial-time algorithmflow-essential assignmentmatching theorycut structuresdirected acyclic graphs (DAGs)algorithmic graph theoryweighted graph partitioning
Authors
Mohammad T. Hajiaghayi, Mahdi JafariRaviz, Alireza Kaviani, Soheil Mohammadkhani
Abstract
We give the first polynomial-time algorithm, after half a century, for the celebrated Győri-Lovász theorem, which resolved a conjecture of Frank (1975). The theorem, one of the simplest existential theorems to explain, states that every $k$-connected graph can be partitioned into $k$ disjoint connected subgraphs of arbitrary prescribed positive sizes. This is a fundamental structural result with broad applications, such as flexible allocation of connected subnetworks of prescribed sizes in sufficiently connected cloud infrastructures. While Lovász (1977) gave a highly non-constructive proof for a stronger directed version using algebraic topology, Győri's original constructive proof (1976) requires exponential time. Despite more than 50 years of effort, no polynomial-time algorithm was known even for $k>4$. Determining the computational complexity of the Győri-Lovász theorem---whether it admits even a sub-exponential-time algorithm or is computationally hard (in particular, PLS-complete or PPAD)---has remained one of the central open problems in algorithmic graph theory. In this paper, we finally resolve this long-standing problem by a fundamentally new proof of the existential theorem via introducing the novel concept of \emph{flow-essential assignment}, which genuinely marries matching and cut structures and yields the first polynomial-time constructive algorithm for the Győri-Lovász theorem. In fact, we obtain a polynomial-time algorithm for Lovász's stronger directed version, whose proof was non-constructive even for DAGs; for DAGs, we further obtain a near-linear-time algorithm. We also develop polynomial-time algorithms for weighted generalizations where the seminal work of Chen, Kleinberg, Lovász, Rajaraman, Sundaram, and Vetta (JACM'07) on confluent flows established only existential non-constructive results.