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

1 Introduction

• The first polynomial-time algorithm partitions every k-connected graph into k disjoint connected subgraphs of arbitrary prescribed positive sizes.This resolves the open case for arbitrary k, whereas previous exact algorithms covered only restricted values or graph classes.Source: §1 · pp. 3–4
• Győri’s constructive proof [Győ76] is exponential because connectivity-preserving cascades can be arbitrarily long and exponentially numerous, while Lovász’s proof [Lov77] is non-constructive and algebraic-topological.These proof styles helped motivate questions about PLS-completeness and PPAD membership, although the new polynomial-time algorithms do not strictly rule out PLS-completeness.Source: §1 · pp. 3–4
• The framework extends Lovász’s stronger directed theorem, gives a near-linear-time algorithm for DAGs, and handles weighted demands with nonuniform capacities.The weighted result makes the previously non-constructive confluent-flow existential theorem constructive, even with exponentially large weights.Source: §1 · pp. 4–5, §1.1 · p. 5

1.1 Our Results

• The algorithm introduces a flow-essential assignment that assigns each vertex to an essential terminal while exactly saturating prescribed capacities.Essential terminals are characterized both by maximum vertex-disjoint paths and by the terminals in the tightest minimum cut; the assignment is found using maximum-flow computations and bipartite matching.Source: §1.1 · pp. 5–8
• The directed formulation assumes k-T-connectivity and partitions vertices into terminal-rooted parts whose sizes match the prescribed nonnegative capacities.Each non-terminal vertex in a part has a directed path to its terminal within that part.Source: §1.1 · p. 5
• The construction overcomes failed connectivity invariants by repeatedly deleting edges until a forced contraction becomes available, while preserving a valid assignment witness.Terminal removal, contraction, and witness-preserving edge deletion empty the graph in at most |V| + |E| steps; reversing contractions yields disjoint arborescences.Source: §1.1 · pp. 5, 6, 8, Figure 1 · p. 6
• Under the Flow-Essential Assignment Condition, a polynomial-time algorithm constructs terminal-rooted parts of exactly the prescribed sizes.The condition strictly generalizes k-T-connectivity, so Theorem 1 follows as a special case.Source: §1.1 · p. 8
• The weighted generalization partitions a k-T-connected directed graph into terminal-connected parts whose weights exceed capacities by at most w_max − 1, and the unweighted theorem is a special case.The additive violation is unavoidable, and the weighted result underlies the confluent-flow existence theorem of Chen et al..Source: §1.1 · p. 11
• The Flow-Essential Split-Assignment Condition distributes each vertex’s weight integrally among essential terminals under capacity upper bounds, and witnesses can be found by maximum flow or minimum-cost flow.In a k-T-connected graph, every terminal is essential for every vertex, so any capacity-respecting split is a witness when total capacity covers total weight.Source: §1.1 · p. 12
• To handle exponentially large binary weights, the algorithm computes a minimum-potential witness directly by one minimum-cost-flow computation, guaranteeing a non-critical edge without exponentially many unit cycle shifts.Cycle shifts preserve split-assignment feasibility and reduce potential; minimum potential therefore implies that some secondary edge is removable.Source: §1.1 · p. 13
• When terminal-to-pre-terminal matching fails, rounding removes a minimal Hall-deficient terminal set and its neighboring pre-terminals while preserving the restricted witness’s essentiality.The proof uses temporary replacement terminals and tight minimum cuts, and rounding is the only operation that can create the additive capacity violation.Source: §1.1 · p. 13
• The full weighted algorithm runs in polynomial time, while on k-T-connected DAGs contractions alone yield an O(m log n)-time partitioning algorithm, including the weighted setting.In DAGs, k-T-connectivity is equivalent to every non-terminal having out-degree at least k; a heap implementation repeatedly contracts suitable pre-terminals.Source: §1.1 · pp. 13–14

2 Preliminaries

• 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.Source: §2 · p. 14
• By Menger’s theorem [Men27], terminal connectivity equals the minimum separator size among cuts separating v from the terminal set T.A separator blocks every directed path from v to T before it reaches the left side of the cut.Source: §2 · p. 15

2.1 Union, Intersection, and the Tightest Min-Cut

• Union and intersection preserve valid cuts and satisfy the modular identity |S_C1|+|S_C2|=|S_C1∪C2|+|S_C1∩C2|.Consequently, minimum cuts are closed under both operations and retain size κ_G(v).Source: §2.1 · pp. 15–17
• Intersecting all minimum cuts yields a tightest minimum cut whose left side is contained in every other minimum cut’s left side, while every other right side is contained in its right side.This canonical cut also contains any terminal appearing in another minimum cut’s separator.Source: §2.1 · p. 17

3 Flow-Essential Assignment

• A terminal is flow-essential for v exactly when deleting it lowers v’s terminal connectivity by one, equivalently when it lies in the separator of v’s tightest minimum cut.This equivalence connects path-based essentiality with minimum-cut structure and supports later terminal deletions and contraction steps.Source: §3 · p. 17
• All essential terminals for one vertex can be found with one maximum-flow computation on an O(n)-vertex, O(n+m)-edge network and linear postprocessing in O((n+m)1+o(1)) time [VCK+23].The construction uses vertex splitting to encode vertex-disjoint paths, while reverse-residual reachability identifies the tightest minimum cut and its essential terminals.Source: §3 · pp. 18–19

3.1 Flow-Essential Assignment Condition

• The unweighted Flow-Essential Assignment Condition assigns every non-terminal to an essential terminal while enforcing each terminal’s exact capacity, marrying matching and cut structures for the contraction algorithm.A witnessing assignment is the object maintained by the unweighted contraction algorithm.Source: §3.1 · p. 20

3.2 Flow-Essential Split-Assignment Condition

• Weighted split-assignments let each vertex send its full weight among terminals essential for it, while each terminal respects capacity; a minimum-cost flow yields an optimal witness or proves none exists.The algorithm runs in O((nk)1+o(1) log(nwmax) log n) time and remains polynomial even when weights are exponentially large.Source: §3.2 · pp. 21–22

4 The Polynomial-Time Algorithm

• Theorem 1 gives a polynomial-time algorithm that partitions a k-T-connected directed graph into terminal-rooted connected parts with prescribed sizes.For nonnegative capacities c_1,...,c_k summing to |V\T|, each part V_i contains t_i, has size c_i+1, and G[V_i] is connected to t_i.Source: §4 · p. 23
• Theorem 2 extends the algorithm to every instance satisfying the Flow-Essential Assignment Condition, which k-T-connectivity implies because every terminal is essential for every nonterminal.The same prescribed-size, terminal-rooted connected partition is produced in polynomial time.Source: §4 · p. 23

4.1 GLPartition Algorithm

• GLPartition recursively removes zero-capacity terminals, contracts out-degree-one pre-terminals, or removes an edge after updating the witnessing assignment.The assignment witness is maintained throughout recursion, preserving the condition needed for subsequent calls.Source: §4.1 · pp. 23–24
• ShiftAssignment combines a pre-terminal-to-terminal matching with reassignment cycles to preserve the condition and eventually expose a removable non-critical edge.Each cycle shifts labeled vertices between terminals without changing capacities, while the number of critical assignments decreases after every shift.Source: §4.1 · pp. 24–25

4.2 Correctness of the Algorithm

• The correctness proof shows GLPartition terminates in polynomial time and returns the required partition, with at most |V(G)| + |E(G)| recursive calls.A maximum-flow computation first finds the witnessing assignment, while structural lemmas validate terminal deletion, pre-terminal contraction, and non-critical-edge removal.Source: §4.2 · pp. 25, 26, 28
• Hall-deficient terminals are non-essential outside their pre-terminal neighborhood, enabling rerouting through a matching that avoids any chosen deficient terminal.Minimality gives a matching saturating the neighborhood and all but one deficient terminal; replacing final path edges preserves disjointness and terminal distinctness.Source: §4.2 · pp. 28–29
• Under the Flow-Essential Assignment Condition with positive capacities, a matching from pre-terminals to terminals exists.A minimal Hall-deficient terminal set would force every assigned vertex for those terminals into its pre-terminal neighborhood, contradicting Hall deficiency.Source: §4.2 · pp. 29–30
• Critical secondary edges imply essentiality of their matching terminals, so reassignment cycles preserve essential assignments and capacities.A critical edge reduces connectivity by one; rerouting through its matching edge contradicts non-essentiality of the corresponding terminal.Source: §4.2 · pp. 30–31
• At most k|V\T| cycle shifts occur before ShiftAssignment finds a removable non-critical edge.Each shift preserves the Flow-Essential Assignment Condition and strictly decreases a potential bounded between 0 and k|V\T|.Source: §4.2 · pp. 31–32

4.3 Proof of Lemma 4.12

• For each shifted vertex vi, the new assignment ti is essential, ei is no longer critical, and every other critical edge transfers back, so ξvi(ti) < ξvi(ϕ(vi)).Lemma 4.13 establishes that ei is not critical for assigning vi to ti, while Lemma 4.14 transfers every edge critical for ti to the original assignment.Source: §4.3 · pp. 32–33
• A directed cycle in the assignment relation yields a shifted assignment with no self-loops and distinct reassigned vertices.Every terminal has in-degree one, so the relation contains a cycle of length at least two; shifting along it assigns each v_i from t_i−1 to t_i.Source: §4.3 · p. 36
• The shifted assignment preserves capacity constraints and satisfies the Flow-Essential Assignment Condition.Each reassigned vertex remains assigned to an essential terminal, while every cycle terminal loses and gains exactly one vertex.Source: §4.3 · p. 36
• The cycle shift strictly decreases the potential Φ, completing the proof of Lemma 4.12.Critical-edge inclusions show the shifted assignment improves the potential while assignments outside the cycle remain unchanged.Source: §4.3 · p. 36

5 Generalized Polynomial-Time Algorithm for Weighted Graphs

• The weighted algorithm also solves unweighted instances faster by finding a minimum-potential flow-essential split-assignment in one minimum-cost-flow computation.This replaces repeated cycle shifts for potential optimization while preserving the underlying flow-essential framework.Source: §5 · p. 37
• The weighted theorem gives a polynomial-time algorithm that partitions every k-T-connected directed graph into terminal-rooted connected parts, with each part exceeding capacity by at most w_max −1.The additive error is necessary when a single non-terminal has weight k while all terminal capacities are one; this bound is guaranteed by the weighted Győri–Lovász theorem [CKL+07].Source: §5 · p. 37

5.2 Correctness of the Weighted Algorithm

• Under the Flow-Essential Split-Assignment Condition, minimum-cost flow and cycle-shift arguments find removable edges, while reductions preserve the condition and valid weighted partitions.A minimum-potential assignment exists because the condition is feasible; if every candidate edge were critical, a directed reassignment cycle would lower the potential, yielding a contradiction.Source: §5 · p. 37, §5.1 · p. 39, §5.2 · p. 41

5.1 GLWeightedPartition Algorithm

• Algorithm 4 extends the unweighted procedure with rounding: it removes zero-capacity terminals, contracts out-degree-one pre-terminals, deletes a removable edge via matching, or rounds a Hall-deficient terminal set.When matching fails, RoundAndRemove forms connected terminal-pre-terminal parts and recurses on the residual instance; this is the only source of the additive w_max −1 error.Source: §5.1 · pp. 38–39

5.2 Correctness of the Weighted Algorithm

• The rounding proof preserves terminal essentiality by replacing removed terminals with their pre-terminal neighborhood, maintaining terminal connectivity, and then removing those temporary terminals one at a time.Restricting the original flow-essential split-assignment yields a valid witness on the smaller instance because positive weight remains assigned only to essential terminals and capacities cannot increase.Source: §5.2 · pp. 43–44
• GLWeightedPartition is correct by induction: each recursive case removes zero-capacity terminals, contracts degree-one pre-terminals, deletes removable edges, or rounds a Hall-deficient terminal set while preserving a valid weighted partition.The rounding case forms connected parts for the removed terminals, and the remaining instance retains the Flow-Essential Split-Assignment Condition.Source: §5.2 · p. 45
• The recursion has at most |V(G)| + |E(G)| calls, and all matching, removable-edge, and RoundAndRemove operations are polynomial, establishing polynomial-time solvability.Each recursive call decreases the graph size measure, while a minimal Hall-deficient set is found using at most |T|^2 matching tests.Source: §5.2 · p. 45

5.3 Running Time Analysis

• Algorithm 4 runs in O(n k m^2+o(1) + m(nk)^1+o(1) log(n w_max) log n) time, with at most m edge-removing calls contributing to the total cost.Source: §5.3 · pp. 45–46

6 Improved Algorithm for DAGs

• Theorem 5 gives an O(m log n)-time algorithm that partitions a k-T-connected DAG into terminal-rooted connected parts satisfying the weighted capacity guarantees.The unweighted problem follows as a special case, yielding parts of prescribed sizes.Source: §6 · p. 47

6.1 GLDAGPartition Algorithm

• GLDAGPartition repeatedly contracts the earliest available pre-terminal into an active terminal using canonical-order heaps, updating residual capacities and inserting new in-neighbors.The contraction preserves k-T-connectivity because the selected pre-terminal has no common predecessor with its terminal; heap operations yield O(m log n) time.Source: §6.1 · pp. 48–49

6.2 Correctness of the Algorithm

• Correctness follows from the DAG characterization that k-T-connectivity is equivalent to every non-terminal having out-degree at least k, together with safe earliest-pre-terminal contractions.The algorithm terminates with a partition whose parts are connected to their terminals and whose assigned weights satisfy the required capacity bound.Source: §6.2 · pp. 50–52

Flow-Essential Assignment

• The Flow-Essential Assignment Condition suffices for a valid partition even when the graph is not k-T-connected, enabling contractions without disrupting the inductive connectivity structure.This relaxation is central to the polynomial-time algorithm.Source: A Relaxed Conditions for the… · p. 54

Relaxed Connectivity Conditions

• In the unweighted setting, k-T-connectivity implies compact connectivity, which implies local connectivity, and Theorem 7 establishes the Győri–Lovász conclusion under either weaker condition.These conditions count non-terminal vertices rather than total weight; the hierarchy is shown in Figure 19 and compact-to-local implication follows from Lemma A.10.Source: A Relaxed Conditions for the… · p. 54

Contraction and Algorithms

• Compact connectivity may lack any contraction-preserving edge, yet every such instance satisfies the Flow-Essential Assignment Condition and admits a polynomial-time partitioning algorithm by Theorem 2.This contrast demonstrates the greater flexibility of the Flow-Essential Assignment Condition.Source: A Relaxed Conditions for the… · p. 54

Definitions

• A vertex is locally connected to a terminal subset T′ when |T′| internally vertex-disjoint paths link it to distinct terminals in T′.Pre-terminals are conventionally treated as having arbitrarily many paths to their associated terminal.Source: §A.1 · pp. 54–55
• The local connectivity condition requires every terminal subset T′ to have a local connected set whose size is at least the terminals’ total capacity, with capacities summing to n−k.The local connected set L(T′) consists of all non-terminal vertices locally connected to T′.Source: §A.1 · p. 55

Connectivity implication

• k-T-connectivity implies the local connectivity condition for every nonnegative capacity assignment, so local connectivity is a relaxation of k-T-connectivity.For each terminal subset, restricting k vertex-disjoint paths from any non-terminal to T yields the required paths, making every non-terminal locally connected to that subset.Source: §A.1 · p. 55

Theorem 7

• Under the local connectivity condition, the graph admits a partition into k connected parts, each containing its designated terminal t_i and exactly c_ti non-terminals.The capacities sum to |V\T|, and each induced part is connected to its designated terminal.Source: §A.1 · p. 55

Algorithmic status

• The constructive proof of this partition theorem adapts Győri [Győ76] and Hoyer and Thomas [HT16] but remains exponential-time, even for small k.The authors conjecture a reduction by deleting zero-capacity terminals or contracting suitable pre-terminals, while warning that checking local connectivity may be hard when k is unfixed.Source: §A.1 · pp. 55–56

Definition

• A vertex is compact-connected to terminal t when k internally vertex-disjoint paths reach the terminals, with only t allowed to receive multiple paths.Pre-terminals are conventionally compact-connected to their associated terminal, and C(t) contains all vertices compact-connected to t.Source: §A.2 · p. 56

Characterization

• The compact connectivity condition is equivalent, by Hall’s theorem, to assigning every non-terminal vertex to a compact-connected terminal with prescribed capacities.This condition lies between k-T-connectivity and local connectivity: k-T-connectivity implies compact connectivity, which implies local connectivity.Source: §A.2 · pp. 56–57

Partitioning

• Compact connectivity implies a partition into connected terminal-rooted parts of the prescribed sizes, and the partition can be computed in polynomial time.The implication follows through local connectivity and Theorem 7; equivalently, compact connectivity yields the Flow-Essential Assignment Condition used by Algorithm 2.Source: §A.2 · pp. 58, 60

Recognition

• Polynomial-time recognition computes compact-connected pairs using maximum flows, then tests a bipartite assignment network with O(nk) arcs.The procedure uses one maximum-flow computation for each non-terminal–terminal pair, followed by one additional maximum-flow computation.Source: §A.2 · pp. 58–59

Limitation

• Compact connectivity is not always preserved by contract/remove operations, even though it supports the desired partitioning algorithm.There are instances with nine terminals, every pre-terminal of out-degree two, and every edge critical to compact connectivity.Source: §A.2 · pp. 60–61

• For every forcing vertex v_e, the only compact-connected terminal is the one targeted by its edge e, and every witness uses e.Source: §A.2 · p. 62
• Assigning each pre-terminal to a terminal out-neighbor and each forcing vertex to its unique target yields a witness assigning every non-terminal exactly once, so the graph satisfies the compact connectivity condition.Source: §A.2 · p. 62
• If an edge leaves a forcing vertex, deleting it reduces that vertex to eight out-neighbors, preventing the nine internally vertex-disjoint paths required for compact connectivity.Source: §A.2 · p. 62
• If an edge joins a pre-terminal to a terminal, deleting it destroys the corresponding forcing vertex’s sole compact connection without creating another, so every edge is critical.Source: §A.2 · p. 62

The incremental extension theorem

• Theorem 8 considers pairwise disjoint terminal-containing sets with |V_i \ {t_i}| = n_i, where n_i ≤ c_ti for all i and n_1 < c_t1, and yields sets with |V′_1 \ {t_1}| = n_1 + 1 while the other counts remain n_i.Source: B The Győri–Lovász theorem under local… · p. 62

Configuration framework

• The proof tracks valid configurations through reservoirs and cascades, assigning recursively defined ranks that must strictly increase along each cascade.Bridges are unallocated-to-reservoir edges whose ranks are determined by the minimum rank of the target reservoirs.Source: B The Győri–Lovász theorem under local… · p. 63

Monotone constructive process

• Local updates preserve validity and strictly increase the lexicographic potential ρ, so repeated cascade extensions and bridge shifts terminate.Each coordinate ρ_r is at most |V|, while the update procedures implement the two local rules that enlarge the potential.Source: B The Győri–Lovász theorem under local… · pp. 64–65

Termination and completion

• If no local update applies, the local connectivity condition forces an edge from an unallocated vertex into V_1, completing the incremental extension.Otherwise, the argument constructs a terminal set whose local connectivity is contradicted by the cascade endpoints separating all relevant paths.Source: B The Győri–Lovász theorem under local… · pp. 65–67

From incremental extension to Győri–Lovász

• Applying Theorem 8 repeatedly from singleton terminal parts assigns exactly c_t non-terminals to each terminal and produces the partition required by Theorem 7.Each application adds exactly one non-terminal, and after Σ_{t∈T} c_t = |V\T| applications all vertices are assigned with the prescribed sizes.Source: B The Győri–Lovász theorem under local… · p. 67