{"id":"arxiv/2608.30945","url":"https://arxiv.org/abs/2608.30945","tags":["cs.DS","math.CO"],"score":0,"title":"Breaking the Exponential Barrier: The First Polynomial-Time Algorithm for the Győri-Lovász Theorem","domain":"cs.DS","source":"arxiv","authors":["Mohammad T. Hajiaghayi","Mahdi JafariRaviz","Alireza Kaviani","Soheil Mohammadkhani"],"reviews":0,"subject":"cs.DS","summary":"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…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-08-31","reactions":{}}