On the Extension Theorem for Packing Steiner Forests

Jinghan A Zeng · 2026

Read On the Extension Theorem for Packing Steiner Forests by Jinghan A Zeng (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-16956.txt.

Introduction

Zeng studies the packing of edge disjoint Steiner forests in graphs. The input gives a multigraph and a set of vertex subsets, each of which must stay connected in every forest. Lau had claimed that 30k edge connectivity of each subset suffices to pack k forests. His proof rests on an Extension Theorem. Zeng shows that theorem has a gap, by giving a counterexample. He then repairs the proof: 32k edge connectivity suffices in general. With more care, 31k suffices when k is at least eight.

Catalog record

CREATORJinghan A Zeng
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE77486
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2603.16956

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

On the Extension Theorem for Packing Steiner Forests Jinghan A Zeng Abstract We consider the problem of packing edge-disjoint Steiner forests in a graph. The input consists of a multi-graph G = ( V , E ) G=(V,E) and a collection of h h vertex subsets 𝒮 = { S 1 , S 2 , … , S h } \mathcal{S}=\{S_{1},S_{2},\ldots,S_{h}\} . A Steiner forest for 𝒮 \mathcal{S} , also called an 𝒮 \mathcal{S} -forest, is a forest of G G in which each S i S_{i} is connected. In the case where h = 1 h=1 , this is the Steiner Tree packing problem. Kriesell’s conjecture postulates that 2 ​ k 2k -edge-connectivity of S 1 S_{1} is sufficient to find k k edge-disjoint S 1 S_{1} -trees. Lau [ 6 ] showed that 24 ​ k 24k -edge-connectivity suffices for the Steiner Tree packing problem, which was improved to 6.5 ​ k 6.5k by West and Wu [ 9 ] and 5 ​ k + 4 5k+4 by Devos, McDonald and Pivotto [ 2 ] . In his thesis, Lau [ 6 ] asserts that for the Steiner Forest problem, if each S i S_{i} is 30 ​ k 30k -edge-connected in G G , then there exist k k edge-disjoint 𝒮 \mathcal{S} -forests. However, Lau’s proof relies on an intermediate theorem called the Extension Theorem, which in this paper we will demonstrate has a gap by providing a counterexample to Lau’s Extension Theorem. Furthermore, we will resolve this gap by correcting Lau’s proof to show that 36 ​ k 36k -edge-connectivity of each S i S_{i} suffices to pack k k 𝒮 \mathcal{S} -forests. More careful analysis yields that 35 ​ k 35k -edge-connectivity of each S i S_{i} is sufficient when k ≥ 8 k\geq 8 . 1 Introduction Let G=(V,E) be a multigraph without self-loops. The well-known theorem of Tutte and Nash-Williams gives a min-max characterization for the maximum number of edge-disjoint spanning trees of G . This was later seen as a special case of packing disjoint bases in a matroid via the work of Edmonds. See [ 8 ] . A simple and useful corollary of the Tutte-Nash-Williams theorem is that if G is 2k -edge-connected then G has at least k edge-disjoint spanning trees. Kriesell considered the problem of packing Steiner trees. Given G and a set of terminal vertices S\subset V we call a subgraph (V_{H},E_{H}) of G an S -tree if it connects S (a minimal subgraph connecting S would a tree). Kriesell conjectured that if S is 2k -edge-connected in G then there exist k edge-disjoint S -trees in G [ 3 ] . This conjecture is still open, however much progress has been achieved starting with the important work of Lau [ 4 , 6 ] . Lau showed that it suffices for S to be 24k -edge-connected to guarantee k -edge-disjoint S -trees. West and Wu [ 9 ] showed that 6.5k -edge-connectivity suffices. Devos, McDonald and Pivotto further improved this bound to (5k+4) [ 2 ] . We now consider the problem of packing Steiner forests which is a further generalization. Let \mathcal{S}=\{S_{1},S_{2},\ldots,S_{h}\} be a collection of vertex-disjoint subsets. An \mathcal{S} -forest is a subgraph of G in which each S_{i} is connected (a minimal such subgraph will be a forest). Kriesell’s conjecture admits a natural extension to this setting: if each S_{i} is 2k -edge-connected then G has k -edge-disjoint \mathcal{S} -forests. The Steiner forest packing question was motivated initially by integer decomposition results [ 1 ] who showed that the packing conjecture is true if G is Eulerian. Lau [ 5 , 6 ] asserted that if each S_{i} is 30k -edge-connected then G admits k -edge-disjoint \mathcal{S} -forests. For this he relied on an extension theorem that builds on his work on packing Steiner trees. However, we will demonstrate that there is a gap in this extension theorem by providing a counterexample to the theorem. Furthermore, we will also remedy the gap in Lau’s proof to obtain the following result: Theorem 1.1 . Let \mathcal{S}=\{S_{1},S_{2},\ldots,S_{h}\} be a collection of vertex-disjoint subsets in a multigraph G . If each S_{i} is 36k -edge-connected, then there exist k edge disjoint \mathcal{S} -forests in G . We note that the main point of our paper will be to show that Qk edge connectivity for some constant Q suffices for the Steiner Forest packing problem, so we will show that 36k -edge-connectivity suffices for simplicity. However, more careful analysis shows that 35k -edge-connectivity suffices when k\geq 8 . We also show some better bounds for when t is small, that is, 9k -edge-connectivity suffices when t=2 or t=3 , and for t>3 , (2t+3)k+Ct^{2} -edge-connectivity suffices for some constant C . 2 Preliminaries We begin this section with some basic definitions. A set S\subseteq V(G) on a graph is said to be k -edge-connected if after the deletion of any k-1 edges on G , we have that S is still connected. By Menger’s Theorem, S being k -edge-connected is equivalent to being able to find k edge-disjoint paths between any two vertices in S . An S -subgraph is a subgraph H of G such that S is connected in H . An (S_{1},S_{2}...S_{t}) -subgraph is a subgraph H of G such that for any i\in[t] , S_{i} is connected in H . A minimal S -subgraph is referred to as a Steiner tree , a minimal (S_{1},S_{2}...S_{t}) -subgraph is referred to as a Steiner forest . To find k disjoint Steiner Forests in a graph, both Lau’s approach and our approach involve packing Steiner Trees on some S_{i} , recursively packing Steiner Forests on the rest of the graph, and merging the two together to find a packing of k Steiner Forests. To formalize this idea, we will need to define notions of balancing and an extension , which we do below. Definition 2.1 . Given a graph G and a vertex v with a subpartition P_{1}\sqcup P_{2}...\sqcup P_{k}\subseteq E(v) into k parts where each part is allowed to be empty, we say that a collection of k edge-disjoint subgraphs H_{1},H_{2},...,H_{k} extend v if all of the following criteria are true. 1. For all i , P_{i}\subseteq E(H_{i}) . 2. For all i , v is not a cut vertex of H_{i} . We will define an operation called the edge-union which uses the idea of an extension to "merge" two graphs together. We will prove a lemma that we will use frequently throughout the proof of the Extension Theorem, which provides motivation for how we define an extension. Take a graph G , and take some edge cut that splits the graph into components C_{1} and C_{2} . We form two graphs G_{1} and G_{2} , where G_{1} is formed by taking G and contracting C_{2} into a single vertex v_{2} . Similarly, we form G_{2} by taking G and contracting C_{1} into a single vertex v_{1} . Note that by construction, E(v_{1})=E(v_{2}) , since both edge sets are the (C_{1},C_{2}) -cut of G . Take some set S\subseteq V(G) , and denote S_{1}=S\cap G_{1} and S_{2}=S\cap G_{2} . Suppose that we can find

Read the complete text