PaperlayerView exact revision on arXiv

Source-linked AI summary

Breaking the Exponential Barrier: The First Polynomial-Time Algorithm for the Győri-Lovász Theorem

Mohammad T. Hajiaghayi, Mahdi JafariRaviz, Alireza Kaviani, Soheil Mohammadkhani

arXiv:2608.30945v1cs.DSmath.CO

TL;DR

The paper addresses the absence of polynomial-time constructive algorithms for the Győri–Lovász theorem and related directed and weighted results. It introduces flow-essential assignments, combining matching and cut structures, and proves polynomial-time constructions for the theorem and its extensions. The weighted guarantee has an additive w_max−1 capacity violation, which is unavoidable.

  • Problem

    The Győri–Lovász theorem had existential proofs but no polynomial-time algorithm for the general case, while related weighted results were non-constructive.

  • Method

    The paper maintains a polynomial-time checkable flow-essential assignment that combines essential-terminal cuts with exact capacity assignments and supports incremental contractions.

  • Results

    The paper gives the first polynomial-time algorithm for the Győri–Lovász theorem and polynomial-time constructive algorithms for the directed and weighted generalizations.

  • Takeaways & Limitations

    Matching and cut structures together provide a constructive route past the exponential barrier for prescribed connected partitions and related confluent-flow results.

  • Takeaways & Limitations

    In the weighted setting, each part may exceed its capacity by at most w_max−1, and this additive violation is unavoidable.

Abstract

from arXiv · show

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.

1 Introduction

The paper turns the long-standing existential Győri–Lovász theorem into a polynomial-time construction by combining matching and cut structures through flow-essential assignments. The framework also yields constructive directed and weighted extensions.

  • Problem: The Győri–Lovász theorem partitions every k-connected graph into k disjoint connected subgraphs with prescribed positive sizes, but prior constructive methods required exponential time.The stronger directed theorem had a highly non-constructive topological proof, and no polynomial-time algorithm was known for general instances or fixed k≥5.
  • Approach: The algorithm maintains a flow-essential assignment while incrementally contracting edges that permanently assign vertices to rooted parts.The invariant is designed to be both strong enough to guarantee a valid contraction and efficiently checkable.
  • Extensions: The framework extends to weighted generalizations, providing constructive polynomial-time algorithms where earlier confluent-flow results were existential and non-constructive.The weighted guarantee permits each part’s total weight to exceed its capacity by at most w_max−1.
  • Approach: Flow-essential assignments combine bottleneck information from cuts with exact capacity requirements through bipartite matching between vertices and essential terminals.A terminal is essential when removing it decreases a vertex’s terminal connectivity; equivalently, it lies in the tightest minimum cut.
  • Results: Theorem 1 gives a polynomial-time algorithm for partitioning a k-T-connected directed graph into rooted connected parts with prescribed sizes.Each part contains its designated terminal, has size c_i+1, and induces a subgraph connected to that terminal.
  • Algorithm: The Flow-Essential Assignment Condition is checkable in polynomial time using maximum-flow computations for essential terminals followed by one bipartite maximum-flow computation for the assignment.The condition is maintained throughout the construction until the full partition is obtained.

2 Preliminaries

This section defines terminal connectivity and directed cuts, then establishes that minimum cuts are closed under union and intersection. Their intersection yields a canonical tightest minimum cut whose terminal separator structure supports later arguments.

  • Terminal connectivity: Terminal connectivity κ_G(v) is the maximum number of vertex-disjoint paths from non-terminal v to distinct terminals, and k-T-connectivity requires κ_G(v)=k for every non-terminal.Standard k-vertex-connectivity implies k-T-connectivity for any terminal set of size k.
  • Cuts and separators: A cut separating v from T partitions vertices into left side L, separator S, and right side R, with separator size defining the cut size.The separator blocks directed paths from v on the right to T on the left or separator.
  • Cuts and separators: Menger’s theorem equates κ_G(v) with the minimum separator size among cuts separating v from T.Thus terminal connectivity can be characterized either by disjoint paths or by minimum cuts.
  • Union and intersection of cuts: Union and intersection preserve valid cuts separating v from T, and their separator sizes satisfy an exact modular identity.The identity is |S_C1| + |S_C2| = |S_C1∪C2| + |S_C1∩C2|.
  • The tightest minimum cut: Consequently, the union and intersection of two minimum cuts are also minimum cuts, enabling a canonical tightest minimum cut formed by intersecting all minimum cuts.The tightest cut has the smallest left side and is contained on the left by every other minimum cut.
  • The tightest minimum cut: Every terminal appearing in the separator of any minimum cut also lies in the separator of the tightest minimum cut.The tightest cut therefore captures all terminals that can occur in minimum-cut separators.

3 Flow-Essential Assignment

The paper defines flow-essentiality through terminal connectivity and minimum cuts, then uses capacitated assignments and flow computations to make the condition algorithmically testable, including weighted split-assignments.

  • Flow-essential terminals: A terminal is flow-essential for v when deleting it reduces v’s terminal connectivity by exactly 1, equivalently forcing it into every maximum disjoint-path family.The same concept is characterized through tightest minimum-cut separators.
  • Flow-essential terminals: Essential terminals are exactly the terminals in the separator of v’s tightest minimum cut.This cut characterization supports terminal deletion and critical-edge arguments later in the algorithm.
  • Computing essential terminals: One maximum-flow computation finds all essential terminals for a vertex in O((n + m)1+o(1)) time, followed by linear-time residual-graph processing.The construction uses vertex splitting, unit capacities outside v, and residual reachability to identify the separator.
  • Flow-essential assignment: A flow-essential assignment maps every non-terminal to an essential terminal while giving each terminal exactly its prescribed capacity.This condition combines the assignment or matching requirement with the cut-based essentiality requirement.
  • Weighted generalization: In the weighted setting, a split-assignment lets each vertex divide its weight among essential terminals, while terminal capacities and costs are enforced by a bipartite flow network.Minimum-cost flow either produces an optimal witness or certifies that no witness exists, in polynomial time.

4 The Polynomial-Time Algorithm

The polynomial-time algorithm constructs the partition recursively by contractions and assignment updates while preserving the Flow-Essential Assignment Condition. Its correctness and polynomial running time follow from progress operations, cycle-based reassignment, and bounded recursion.

  • Main theorem: Theorem 1 gives a polynomial-time partition algorithm for k-T-connected directed graphs with prescribed part sizes and terminal-rooted connectivity.Each part contains its terminal, has size c_i + 1, and induces a subgraph connected to that terminal.
  • Main theorem: The algorithm relaxes k-T-connectivity to the Flow-Essential Assignment Condition, which still guarantees a polynomial-time partition with the prescribed terminal-rooted sizes.The original theorem follows because every terminal is essential for every non-terminal in a k-T-connected graph.
  • Algorithm: GLPartition recursively removes zero-capacity terminals, contracts out-degree-one pre-terminals, or removes a suitable edge after updating the assignment.The input assignment is maintained as a witness throughout recursive execution.
  • Assignment updates: ShiftAssignment builds a matching and a reassignment graph, then shifts assignments along a directed cycle to reduce the number of critical edges while preserving feasibility.The reassignment graph has in-degree one at every vertex, ensuring a directed cycle exists.
  • Correctness and complexity: Each recursive call decreases |V(G)| + |E(G)|, yielding at most |V(G)| + |E(G)| calls and therefore polynomial running time.Each step is polynomial time by the cited lemma, and the resulting partition satisfies the theorem’s size and connectivity requirements.

5 Generalized Polynomial-Time Algorithm for Weighted Graphs

The weighted algorithm extends the flow-essential framework to capacitated, weighted partitions, using contractions, minimum-cost flow, and recursive handling of Hall-deficient sets. It runs in polynomial time, with additive capacity error at most w_max−1 arising only from rounding.

  • Algorithm and guarantee: The weighted algorithm partitions flow-essential instances into connected terminal-rooted parts in polynomial time.It relaxes k-T-connectivity to the Flow-Essential Split-Assignment Condition, where vertex weights may be split among essential terminals within capacities.
  • Algorithm and guarantee: The algorithm incrementally contracts edges, removes zero-capacity terminals, contracts degree-one pre-terminals, deletes suitable edges, and rounds Hall-deficient terminal sets.These four operations preserve the relevant invariant or reduce the instance for recursive processing.
  • Algorithm and guarantee: A minimum-potential flow-essential split-assignment found by one minimum-cost-flow computation yields a removable edge even when weights are exponentially large.This avoids relying on a potential function that is not polynomially bounded in the input size.
  • Recursive rounding: The RoundAndRemove step matches all but one terminal in an inclusion-minimal Hall-deficient set to neighboring pre-terminals, completes those parts, and recurses on the residual instance.The removed set includes the deficient terminals and their pre-terminal neighborhood; remaining vertices send no weight to the removed terminals.
  • Capacity guarantee: The only additive capacity error is w_max−1, because each rounded terminal receives at most one non-terminal of weight at most w_max.The resulting part can therefore exceed its capacity by at most w_max−1.
  • Running time: Algorithm 4 runs in O(nk m^2+o(1) + m(nk)^1+o(1) log(nw_max) log n) time.There are at most |V(G)|+|E(G)| recursive calls, and the stated bound covers condition checks and all four operations.

6 Improved Algorithm for DAGs

For k-T-connected DAGs, the paper gives a direct weighted partition algorithm based on canonical topological order and heap-guided contractions. It achieves O(m log n) time while preserving connectivity and capacity guarantees.

  • Theorem and result: Weighted Győri–Lovász partitioning on k-T-connected DAGs admits an O(m log n)-time algorithm.The algorithm returns connected parts containing their designated terminals and satisfying the theorem’s capacity bounds.
  • Corollary: In the unweighted case, the DAG algorithm yields parts of exactly prescribed sizes, with |V_i| = c_i + 1 for every terminal.Unit weights make the weighted capacity guarantee exact after summing the capacities.
  • Algorithm design: Canonical topological order places all non-terminals before the terminals, whose order is fixed as t1 ≺ t2 ≺ ··· ≺ tk.Each heap stores pre-terminals adjacent to a current part and returns the earliest one under this order.
  • Algorithm design: The algorithm repeatedly contracts the earliest available pre-terminal into an active terminal while preserving the out-degree characterization of k-T-connectivity.In a DAG, k-T-connectivity is equivalent to every non-terminal having out-degree at least k.
  • Algorithm design: Each contraction adds the pre-terminal to its terminal’s part, decreases residual capacity by its weight, marks the vertex used, and inserts its in-neighbors into the corresponding heap.Saturated terminals are removed from the active set and are no longer enlarged.
  • Running time: The O(m log n) running time follows because each edge causes at most one heap insertion and each heap entry is extracted at most once.Binary-heap operations dominate the O(n+m) initialization cost.

A Relaxed Conditions for the Győri–Lovász Theorem

The paper strengthens the theorem’s sufficient condition: valid connected partitions exist under the Flow-Essential Assignment Condition, even when k-T-connectivity is not preserved.

  • Relaxed conditions: The Flow-Essential Assignment Condition is sufficient for a valid terminal-rooted connected partition, even without k-T-connectivity.This weaker invariant enables contractions that may destroy direct k-T-connectivity while retaining the structure needed for induction.
  • Relaxed conditions: The appendix introduces local and compact connectivity as further relaxations, with k-T-connectivity implying compact connectivity and compact connectivity implying local connectivity.The paper states that the Győri–Lovász conclusion holds under either relaxed condition.
  • Path definition: Internally vertex-disjoint paths may share their starting vertex and may end at the same terminal.This definition differs from standard vertex-disjoint paths by permitting repeated terminal endpoints.

A.1 Local Connectivity Condition

Local connectivity requires every terminal subset to have enough vertices that can reach it through internally vertex-disjoint paths. This condition relaxes k-T-connectivity while still guaranteeing a prescribed connected partition.

  • A vertex is locally connected to T′ when it has |T′| internally vertex-disjoint paths to vertices of T′.
  • The local connectivity condition requires every terminal subset T′ to have at least the total capacity of its terminals in locally connected vertices.
  • k-T-connectivity implies local connectivity because disjoint paths to all terminals restrict to disjoint paths for every terminal subset.
  • Under local connectivity, the directed Győri–Lovász conclusion gives a partition with prescribed terminal assignments, capacities, and terminal-connected induced subgraphs.
  • The proof adapts Győri’s and Hoyer–Thomas’s constructive cascade framework, but the resulting procedure is exponential even for small k.

A.2 Compact Connectivity Condition

Compact connectivity strengthens local connectivity by assigning vertices to terminals through specialized disjoint-path structures. It remains sufficient for the Győri–Lovász partition and can be recognized and handled in polynomial time.

  • A vertex is compact-connected to terminal t when k internally vertex-disjoint paths reach the terminals, with every other terminal receiving at most one path.
  • By Hall’s Marriage Theorem, compact connectivity is equivalent to a capacity-respecting assignment of every non-terminal vertex to a compact-connected terminal.
  • Compact connectivity lies between standard k-T-connectivity and local connectivity: k-T-connectivity implies it, and it implies local connectivity.
  • Compact connectivity implies a prescribed connected partition, and Algorithm 2 constructs such a partition in polynomial time.
  • Polynomial-time recognition uses maximum-flow computations for vertex–terminal pairs followed by one bipartite-network maximum-flow computation with O(nk) edges.
  • Compact connectivity is not always preserved by contractions or edge removals, motivating the more flexible Flow-Essential Assignment Condition.
  • There are compactly connected instances with k=9 in which every edge is critical, so no edge-removal step preserves compact connectivity.

B The Győri–Lovász theorem under local connectivity

The proof extends the cascade framework to directed graphs under local connectivity and uses validity-preserving updates to enlarge a deficient terminal component. Lexicographic progress forces termination at the required partition.

  • The Győri–Lovász theorem under local connectivity: When no further update applies, local connectivity guarantees an edge from the unallocated set into the first part, completing the allocation.
  • The Győri–Lovász theorem under local connectivity: Reservoirs record vertices that still reach their terminal after deleting a cascade vertex, exposing dependencies used by cascade updates.
  • The Győri–Lovász theorem under local connectivity: A configuration combines prescribed connected vertex sets with one cascade in each part other than the distinguished first part.
  • The Győri–Lovász theorem under local connectivity: Cascade vertices receive recursively defined ranks, and valid configurations require ranks to increase strictly along each cascade.
  • The Győri–Lovász theorem under local connectivity: Local modifications preserve validity and strictly increase the reservoir-count vector lexicographically, ensuring termination because every coordinate is at most |V|.
  • The Győri–Lovász theorem under local connectivity: CascadeExtension and BridgeShift either enlarge this lexicographic potential or move vertices toward the distinguished first part.
  • The Győri–Lovász theorem under local connectivity: After |V\T| allocations, every terminal receives exactly its capacity and the resulting sets form the required partition.
Loading 2608.30945v1…