Breaking the Exponential Barrier: The First Polynomial-Time Algorithm for the Győri-Lovász Theorem
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.
Related
- On the exponential ergodicity of the McKean-Vlasov SDE depending on a polynomial interaction
- Exponential Convergence of the Sinkhorn Algorithm for the Schrödinger Bridge with Regime Switching
- Breaking the Infinite Barrier in the 1/3--2/3 Conjecture
- Korovkin type theorems for operators acting on functions of polynomial and exponential growth on [0,∞)
- Combining Exponential and Polynomial Convergence Rates for Accelerated Extremum Seeking: A High-Order Lie Bracket Approach
BibTeX
@misc{hajiaghayi2026breaking,
title = {{Breaking the Exponential Barrier: The First Polynomial-Time Algorithm for the Győri-Lovász Theorem}},
author = {Mohammad T. Hajiaghayi and Mahdi JafariRaviz and Alireza Kaviani and Soheil Mohammadkhani},
howpublished = {arXiv},
year = {2026},
month = aug,
doi = {10.48550/arxiv.2608.30945},
eprint = {2608.30945},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2608.30945},
}
RIS
TY - UNPB
TI - Breaking the Exponential Barrier: The First Polynomial-Time Algorithm for the Győri-Lovász Theorem
AU - Mohammad T. Hajiaghayi
AU - Mahdi JafariRaviz
AU - Alireza Kaviani
AU - Soheil Mohammadkhani
PY - 2026
DA - 2026/08/31
PB - arXiv
DO - 10.48550/arxiv.2608.30945
UR - https://arxiv.org/abs/2608.30945
AB - 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.
ER -