# Hypergraphic LP Relaxations for Steiner Trees

Deeparnab Chakrabarty  Jochen Könemann  David Pritchard

(University of Waterloo 111Supported by NSERC grant no. 288340 and by an Early
Research Award. Email: (deepc, jochen, dagpritc @uwaterloo.ca))

###### Abstract

We investigate hypergraphic LP relaxations for the Steiner tree problem,
primarily the partition LP relaxation introduced by Könemann et al. [Math.
Programming, 2009]. Specifically, we are interested in proving upper bounds on
the integrality gap of this LP, and studying its relation to other linear
relaxations. Our results are the following.

Structural results: We extend the technique of uncrossing, usually applied to
families of sets, to families of partitions. As a consequence we show that any
basic feasible solution to the partition LP formulation has sparse support.
Although the number of variables could be exponential, the number of positive
variables is at most the number of terminals.

Relations with other relaxations: We show the equivalence of the partition LP
relaxation with other known hypergraphic relaxations. We also show that these
hypergraphic relaxations are equivalent to the well studied bidirected cut
relaxation, if the instance is quasibipartite.

Integrality gap upper bounds: We show an upper bound of $\sqrt{3}\doteq 1.729$
on the integrality gap of these hypergraph relaxations in general graphs. In
the special case of uniformly quasibipartite instances, we show an improved
upper bound of $73/60\doteq 1.216$. By our equivalence theorem, the latter
result implies an improved upper bound for the bidirected cut relaxation as
well.

##  1 Introduction

In the Steiner tree problem, we are given an undirected graph $G=(V,E)$, non-
negative costs $c_{e}$ for all edges $e\in E$, and a set of terminal vertices
$R\subseteq V$. The goal is to find a minimum-cost tree $T$ spanning $R$, and
possibly some Steiner vertices from $V\setminus R$. We can assume that the
graph is complete and that the costs induce a metric. The problem takes a
central place in the theory of combinatorial optimization and has numerous
practical applications. Since the Steiner tree problem is
$\mathsf{NP}$-hard222Chlebík and Chlebíková show that no
$(96/95-\epsilon)$-approximation algorithm can exist for any positive
$\epsilon$ unless $\mathsf{P}$=$\mathsf{NP}$ [5]. we are interested in
approximation algorithms for it. The best published approximation algorithm
for the Steiner tree problem is due to Robins and Zelikovsky [29], which for
any fixed $\epsilon>0$, achieves a performance ratio of $1+\frac{\ln
3}{2}+\epsilon\doteq 1.55$ in polynomial time; an improvement is currently in
press [3], see also Remark 1.1.

In this paper, we study linear programming (LP) relaxations for the Steiner
tree problem, and their properties. Numerous such formulations are known
(e.g., see [1, 7, 8, 10, 11, 18, 24, 25, 35, 36]), and their study has led to
impressive running time improvements for integer programming based methods.
Despite the significant body of work in this area, none of the known
relaxations is known to exhibit an integrality gap provably
smaller333Achieving an integrality gap of $2$ is relatively easy for most
relaxations by showing that the minimum spanning tree restricted on the
terminals is within a factor $2$ of the LP. than $2$. The integrality gap of a
relaxation is the maximum ratio of the cost of integral and fractional optima,
over all instances. It is commonly regarded as a measure of strength of a
formulation. One of the contributions of this paper are improved bounds on the
integrality gap for a number of Steiner tree LP relaxations.

A Steiner tree relaxation of particular interest is the bidirected cut
relaxation [11, 36] (precise definitions will follow in Section 1.2). This
relaxation has a flow formulation using $O(|E||R|)$ variables and constraints,
which is much more compact than the other relaxations we study. Also, it is
also widely believed to have an integrality gap significantly smaller than $2$
(e.g., see [4, 28, 34]). The largest lower bound on the integrality gap known
is $8/7$ (by Martin Skutella, reported in [23]), and Chakrabarty et al. [4]
prove an upper bound of $4/3$ in so called quasi-bipartite instances (where
Steiner vertices form an independent set).

Another class of formulations are the so called hypergraphic LP relaxations
for the Steiner tree problem. These relaxations are inspired by the
observation that the minimum Steiner tree problem can be encoded as a minimum
cost hyper-spanning tree (see Section 1.2.2) of a certain hypergraph on the
terminals. They are known to be stronger than the bidirected cut relaxation
[26], and it is therefore natural to try to use them to get better
approximation algorithms, by drawing on the large corpus of known LP
techniques. In this paper, we focus on one hypergraphic LP in particular: the
partition LP of Könemann et al. [23].

###  1.1 Our Results and Techniques

There are three classes of results in this paper: structural results,
equivalence results, and integrality gap upper bounds.

Structural results, Section 2: We extend the powerful technique of uncrossing,
traditionally applied to families of sets, to families of partitions. Set
uncrossing has been very successful in obtaining exact and approximate
algorithms for a variety of problems (for instance, [13, 21, 31]). Using
partition uncrossing, we show that any basic feasible solution to the
partition LP has at most $(|R|-1)$ positive variables (even though it can have
an exponentially large number of variables and constraints).

Equivalence results, Section 3: In addition to the partition LP, two other
hypergraphic LPs have been studied before: one based on _subtour elimination_
due to Warme [35], and a _directed hypergraph relaxation_ of Polzin and
Vahdati Daneshmand [26]; these two are known to be equivalent [26]. We prove
that in fact _all three hypergraphic relaxations are equivalent_ (that is,
they have the same objective value for any Steiner tree instance). We give two
proofs (for completeness and to demonstrate our new techniques), one showing
the equivalence of the partition LP and the subtour LP via partition
uncrossing, and one showing the equivalence of the partition LP to the
directed LP via hypergraph orientation results of Frank et al. [14].

We also show that, on quasibipartite instances, the hypergraphic and the
bidirected cut LP relaxations are equivalent. We find this surprising for the
following reasons. Firstly, some instances are known where the hypergraph
relaxations is strictly stronger than the bidirected cut relaxation [26].
Secondly, the bidirected cut relaxations seems to resist uncrossing
techniques; e.g. even in quasi-bipartite graphs extreme points for bidirected
cut can have as many as $\Omega(|V|^{2})$ positive variables [27, Sec. 4.9].
Thirdly, the known approaches to exploiting the bidirected cut relaxation
(mostly primal-dual and local search algorithms [28, 4]) are very different
from the combinatorial hypergraphic algorithms for the Steiner tree problem
(almost all of them employ greedy strategies). In short, there is no
qualitative similarity to suggest why the two relaxations should be
equivalent! We believe a better understanding of the bidirected cut relaxation
is important because it is central in theory _and_ practical for
implementation.

Improved integrality gap upper bounds, Section 4: For _uniformly
quasibipartite instances_ (quasibipartite instances where for each Steiner
vertex, all incident edges have the same cost), we show that the integrality
gap of the hypergraphic LP relaxations is upper bounded by $73/60\doteq
1.216$. Our proof uses the approximation algorithm of Gröpl et al. [20] which
achieves the same ratio with respect to the (integral) optimum. We show, via a
simple dual fitting argument, that this ratio is also valid with respect to
the LP value. To the best of our knowledge this is the only nontrivial class
of instances where the best currently known approximation ratio and
integrality gap upper bound are the same.

For general graphs, we give simple upper bounds of $2\sqrt{2}-1\doteq 1.83$
and $\sqrt{3}\doteq 1.729$ on the integrality gap of the hypergraph
relaxation. Call a graph gainless if the minimum spanning tree of the
terminals is the optimal Steiner tree. To obtain these integrality gap upper
bounds, we use the following key property of the hypergraphic relaxation which
was implicit in [23]: on gainless instances (instances where the optimum
terminal spanning tree is the optimal Steiner tree), the LP value equals the
minimum spanning tree and the integrality gap is 1. Such a theorem was known
for quasibipartite instances and the bidirected cut relaxation (implicitly in
[28], explicitly in [4]); we extend techniques of [4] to obtain improved
integrality gaps on all instances.

######  Remark 1.1.

The recent independent work of Byrka et al. [3], which gives an improved
approximation for Steiner trees in general graphs, also shows an integrality
gap bound of $1.55$ on the hypergraphic directed cut LP. This is stronger than
our integrality gap bounds and was obtained prior to the completion of our
paper; yet we include our bounds because they are obtained using fairly
different methods which might be of independent interest in certain settings.

The proof in [3] can be easily modified to show an integrality gap upper bound
of $1.28$ in quasibipartite instances. Then using our equivalence result, we
get an integrality gap upper bound of $1.28$ for the bidirected cut relaxation
on quasibipartite instances, improving the previous best of $4/3$.

###  1.2 Bidirected Cut and Hypergraphic Relaxations

####  1.2.1 The Bidirected Cut Relaxation

The first bidirected LP was given by Edmonds [11] as an exact formulation for
the spanning tree problem. Wong [36] later extended this to obtain the
bidirected cut relaxation for the Steiner tree problem, and gave a dual ascent
heuristic based on the relaxation. For this relaxation, introduce two arcs
$(u,v)$ and $(v,u)$ for each edge $uv\in E$, and let both of their costs be
$c_{uv}$. Fix an arbitrary terminal $r\in R$ as the root. Call a subset
$U\subseteq V$ valid if it contains a terminal but not the root, and let
$\mathrm{valid}(V)$ be the family of all valid sets. Clearly, the in-tree
rooted at $r$ (the directed tree with all vertices but the root having out-
degree exactly $1$) of a Steiner tree $T$ must have at least one arc with tail
in $U$ and head outside $U$, for all valid $U$. This leads to the bidirected
cut relaxation ($\mathcal{B}$) (shown in Figure 1 on page 1 with dual) which
has a variable for each arc $a\in A$, and a constraint for every valid set
$U$. Here and later, $\delta^{\mathrm{out}}(U)$ denotes the set of arcs in $A$
whose tail is in $U$ and whose head lies in $V\setminus U$. When there are no
Steiner vertices, Edmonds’ work [11] implies this relaxation is exact.

$\displaystyle\min\sum_{a\in A}c_{a}x_{a}:\quad$ $\displaystyle
x\in\mathbf{R}^{A}_{\geq 0}$ ($\mathcal{B}$)
$\displaystyle\sum_{a\in\delta^{\mathrm{out}}(U)}x_{a}\geq 1,\quad$
$\displaystyle\forall U\in{\mathrm{valid}(V)}$ (1)

$\displaystyle\max\sum_{U}z_{U}:\quad$ $\displaystyle
z\in\mathbf{R}^{\mathrm{valid}(V)}_{\geq 0}$ ($\mathcal{B}_{D}$)
$\displaystyle\sum_{U:a\in\delta^{\mathrm{out}}(U)}z_{U}\leq c_{a},\quad$
$\displaystyle\forall a\in A$ (2)

Figure 1: The bidirected cut relaxation ($\mathcal{B}$) and its dual
($\mathcal{B}_{D}$).

Goemans & Myung [18] made significant progress in understanding the LP, by
showing that the bidirected cut LP has the same value independent of which
terminal is chosen as the root, and by showing that a whole “catalogue” of
very different-looking LPs also has the same value; later Goemans [17] showed
that if the graph is series-parallel, the relaxation is exact. Rajagopalan and
Vazirani [28] were the first to show a non-trivial integrality gap upper bound
of $3/2$ on quasibipartite graphs; this was subsequently improved to $4/3$ by
Chakrabarty et al. [4], who gave another alternate formulation for
($\mathcal{B}$).

####  1.2.2 Hypergraphic Relaxations

Given a Steiner tree $T$, a _full component_ of $T$ is a maximal subtree of
$T$ all of whose leaves are terminals and all of whose internal nodes are
Steiner nodes. The edge set of any Steiner tree can be partitioned in a unique
way into full components by splitting at internal terminals; see Figure 2 on
page 2 for an example.

Figure 2: Black nodes are terminals and white nodes are Steiner nodes. Left: a
Steiner tree for this instance. Middle: the Steiner tree’s edges are
partitioned into full components; there are four full components. Right: the
hyperedges corresponding to these full components.

Let $\mathcal{K}$ be the set of all nonempty subsets of terminals
(_hyperedges_). We associate with each $K\in\mathcal{K}$ a fixed full
component spanning the terminals in $K$, and let $C_{K}$ be its cost444We
choose the minimum cost full component if there are many. If there is no full
component spanning $K$, we let $C_{K}$ be infinity. Such a minimum cost
component can be found in polynomial time, if $|K|$ is a constant.. The
problem of finding a minimum-cost Steiner tree spanning $R$ now reduces to
that of finding a minimum-cost hyper-spanning tree in the hypergraph
$(R,\mathcal{K})$.

Spanning trees in (normal) graphs are well understood and there are many
different exact LP relaxations for this problem. These exact LP relaxations
for spanning trees in graphs inspire the hypergraphic relaxations for the
Steiner tree problem. Such relaxations have a variable $x_{K}$ for
every555Observe that there could be exponentially many hyperedges. This
computational issue is circumvented by considering hyperedges of size at most
$r$, for some constant $r$. By a result of Borchers and Du [2], this leads to
only a $(1+\Theta(1/\log r))$ factor increase in the optimal Steiner tree
cost. $K\in\mathcal{K}$, and the different relaxations are based on the
constraints used to capture a hyper-spanning tree, just as constraints on
edges are used to capture a spanning tree in a graph.

The oldest hypergraphic LP relaxation is the subtour LP introduced by Warme
[35] which is inspired by Edmonds’ subtour elimination LP relaxation [12] for
the spanning tree polytope. This LP relaxation uses the fact that there are no
hypercycles in a hyper-spanning tree, and that it is spanning. More formally,
let $\rho(X):=\max(0,|X|-1)$ be the rank of a set $X$ of vertices. Then a sub-
hypergraph $(R,\mathcal{K}^{\prime})$ is a hyper-spanning tree iff
$\sum_{K\in\mathcal{K}^{\prime}}\rho(K)=\rho(R)$ and
$\sum_{K\in\mathcal{K}^{\prime}}\rho(K\cap S)\leq\rho(S)$ for every subset $S$
of $R$. The corresponding LP relaxation, denoted below as ($\mathcal{S}$), is
called the subtour elimination LP relaxation.

$\displaystyle\min\Big{\\{}\sum_{K\in\mathcal{K}}C_{K}x_{K}:~{}$
$\displaystyle x\in\mathbf{R}^{\mathcal{K}}_{\geq
0},~{}\sum_{K\in\mathcal{K}}x_{K}\rho(K)=\rho(R),$ ($\mathcal{S}$)
$\displaystyle\sum_{K\in\mathcal{K}}x_{K}\rho(K\cap S)\leq\rho(S),~{}\forall
S\subset R\Big{\\}}$

Warme showed that if the maximum hyperedge size $r$ is bounded by a constant,
the LP can be solved in polynomial time.

The next hypergraphic LP introduced for Steiner tree was a directed hypergraph
formulation ($\mathcal{D}$), introduced by Polzin and Vahdati Daneshmand [26],
and inspired by the bidirected cut relaxation. Given a full component $K$ and
a terminal $i\in K$, let $K^{i}$ denote the arborescence obtained by directing
all the edges of $K$ towards $i$. Think of this as directing the hyperedge $K$
towards $i$ to get the directed hyperedge $K^{i}$. Vertex $i$ is called the
_head_ of $K^{i}$ while the terminals in $K\setminus i$ are the _tails_ of
$K$. The cost of each directed hyperedge $K^{i}$ is the cost of the
corresponding undirected hyperedge $K$. In the directed hypergraph
formulation, there is a variable $x_{K^{i}}$ for every directed hyperedge
$K^{i}$. As in the bidirected cut relaxation, there is a vertex $r\in R$ which
is a root, and as described above, a subset $U\subseteq R$ of terminals is
valid if it does not contain the root but contains at least one vertex in $R$.
We let $\Delta^{\mbox{\scriptsize{$\mathrm{out}$}}}(U)$ be the set of directed
full components coming out of $U$, that is all $K^{i}$ such that $U\cap
K\neq\varnothing$ but $i\notin U$. Let $\overrightarrow{\mathcal{K}}$ be the
set of all directed hyperedges. We show the directed hypergraph relaxation and
its dual in Figure 3.

$\displaystyle\min\Big{\\{}\sum_{K\in\mathcal{K},i\in K}C_{K}x_{K^{i}}:$
$\displaystyle\,\,x\in\mathbf{R}^{\overrightarrow{\mathcal{K}}}_{\geq 0}$
($\mathcal{D}$)
$\displaystyle\sum_{K^{i}\in\Delta^{\mbox{\scriptsize{$\mathrm{out}$}}}(U)}x_{K^{i}}\geq
1,\quad$ $\displaystyle\forall\mbox{ valid }~{}U\subseteq R\Big{\\}}$ (3)

$\displaystyle\max\Big{\\{}\sum_{U}z_{U}:~{}~{}~{}~{}\quad$ $\displaystyle
z\in\mathbf{R}^{\textrm{valid}(R)}_{\geq 0}\\!\\!\\!\\!$ ($\mathcal{D}_{D}$)
$\displaystyle\sum_{U:K\cap U\neq\varnothing,i\notin U}z_{U}\leq C_{K},\quad$
$\displaystyle\forall K\in\mathcal{K},\forall i\in K\Big{\\}}$ (4)

Figure 3: The directed hypergraph relaxation ($\mathcal{D}$) and its dual
($\mathcal{D}_{D}$).

Polzin & Vahdati Daneshmand [26] showed that
$\mathop{\mathrm{OPT}}\eqref{eq:LP-
PUDir}=\mathop{\mathrm{OPT}}\eqref{eq:LP-S}$. Moreover they observed that this
directed hypergraphic relaxation strengthens the bidirected cut relaxation.

######  Lemma 1.2 ([26]).

For any instance, $\mathop{\mathrm{OPT}}\eqref{eq:LP-
PUDir}\geq\mathop{\mathrm{OPT}}\eqref{eq:LP-B}$.

###### Proof sketch..

It suffices to show that any solution $x$ of ($\mathcal{D}$) can be converted
to a feasible solution $x^{\prime}$ of ($\mathcal{B}$) of the same cost. For
each arc $a$, let $x^{\prime}_{a}$ be the sum of $x_{K^{i}}$ over all directed
full components $K^{i}$ that (when viewed as an arborescence) contain $a$. Now
for any valid subset $U$ of $V$, it is not hard to see that every directed
full component leaving $R\cap U$ has at least one arc leaving $U$, hence
$\sum_{a\in\delta^{\mathrm{out}}(U)}{x^{\prime}}_{a}\geq\sum_{K^{i}\in\Delta^{\mbox{\scriptsize{$\mathrm{out}$}}}(R\cap
U)}x_{K^{i}}\geq 1$ and $x^{\prime}$ is feasible as needed. ∎

See [26] for an example where the strict inequality
$\mathop{\mathrm{OPT}}\eqref{eq:LP-
PUDir}>\mathop{\mathrm{OPT}}\eqref{eq:LP-B}$ holds.

Könemann et al. [23], inspired by the work of Chopra [6], described a
partition-based relaxation which captures that given any partition of the
terminals, any hyper-spanning tree must have sufficiently many “cross
hyperedges”. More formally, a partition, $\pi$, is a collection of pairwise
disjoint nonempty terminal sets $(\pi_{1},\ldots,\pi_{q})$ whose union equals
$R$. The number of parts $q$ of $\pi$ is referred to as the partition’s rank
and denoted as $r(\pi)$. Let $\Pi_{R}$ be the set of all partitions of $R$.
Given a partition $\pi=\\{\pi_{1},\ldots,\pi_{q}\\}$, define the rank
contribution $\mathtt{rc}_{K}^{\pi}$ of hyperedge $K\in\mathcal{K}$ for $\pi$
as the rank reduction of $\pi$ obtained by merging the parts of $\pi$ that are
touched by $K$; i.e.,
$\mathtt{rc}_{K}^{\pi}:=|\\{i\,:\,K\cap\pi_{i}\neq\varnothing\\}|-1.$ Then a
hyper-spanning tree $(R,\mathcal{K}^{\prime})$ must satisfy
$\sum_{K\in\mathcal{K}^{\prime}}\mathtt{rc}^{\pi}_{K}\geq r(\pi)-1$. The
partition based LP of [23] and its dual are given in Figure 4 on page 4.

$\displaystyle\min\Big{\\{}\sum_{K\in\mathcal{K}}C_{K}x_{K}:\quad$
$\displaystyle x\in\mathbf{R}^{\mathcal{K}}_{\geq 0}\\!\\!\\!$ ($\mathcal{P}$)
$\displaystyle\sum_{K\in\mathcal{K}}x_{K}\mathtt{rc}_{K}^{\pi}\geq
r(\pi)-1,\quad$ $\displaystyle\forall\pi\in\Pi_{R}\Big{\\}}$ (5)

$\displaystyle\max\Big{\\{}\sum_{\pi}(r(\pi)-1)\cdot y_{\pi}:\quad$
$\displaystyle y\in\mathbf{R}^{\Pi_{R}}_{\geq 0}$ ($\mathcal{P}_{D}$)
$\displaystyle\sum_{\pi\in\Pi_{R}}y_{\pi}\mathtt{rc}_{K}^{\pi}\leq
C_{K},\quad$ $\displaystyle\forall K\in\mathcal{K}\Big{\\}}$ (6)

Figure 4: The unbounded partition relaxation ($\mathcal{P}$) and its dual
($\mathcal{P}_{D}$).

The feasible region of ($\mathcal{P}$) is _unbounded_ , since if $x$ is a
feasible solution for ($\mathcal{P}$) then so is any $x^{\prime}\geq x$. We
obtain a _bounded_ partition LP relaxation, denoted by
($\mathcal{P}^{\prime}$) and shown below, by adding a valid equality
constraint to the LP.

$\displaystyle\min\Big{\\{}\sum_{K\in\mathcal{K}}C_{K}x_{K}:x\in\eqref{eq:LP-
PU},\sum_{K\in\mathcal{K}}x_{K}(|K|-1)=|R|-1\Big{\\}}$
($\mathcal{P}^{\prime}$)

####  1.2.3 Discussion of Computational Issues

The bidirected cut relaxation is very attractive from a perspective of
computational implementation. Although the formulation given in Section 1.2.1
has an exponential number of constraints, an equivalent compact flow
formulation with $O(|E||R|)$ variables and constraints is well-known.

What is known regarding solving the hypergraphic LPs? They are good enough to
get theoretical results but less attractive in practice, as we now explain.
Using a separation oracle, Warme showed [35] that for any chosen family
$\mathcal{K}$ of full components, the subtour LP can be optimized in time
$\textrm{poly}(|V|,|\mathcal{K}|)$. For the common _$r$ -restricted setting_
of $\mathcal{K}$ to be all possible full components of size at most $r$ for
constant $r$, we have $\mathcal{K}\leq\tbinom{|R|}{r}$. This is polynomial for
any fixed $r$, and the relative error caused by this choice of $r$ is at most
the _$r$ -Steiner ratio_ $\rho_{r}=1+\Theta(1/\log r)$ [2]. But this is not so
practical: to get relative error $1+\epsilon$, we apply the ellipsoid
algorithm to an LP with $|R|^{\exp(\Theta(1/\epsilon))}$ variables!

In the _unrestricted setting_ where $\mathcal{K}$ contains all possible full
components without regard to size, it is an open problem to optimize any of
the hypergraphic LPs exactly in polynomial time. We make some progress here:
in quasibipartite instances, the proof method of our hypergraphic-bidirected
equivalence theorem (Section 3.3) implies that one can exactly compute the LP
optimal value, and a dual optimal solution. Regarding this open problem, we
note that the $r$-restricted LP optimum is at most $\rho_{r}$ times the
unrestricted optimum, and wonder whether there might be some advantage gained
by using the fact that the hypergraphic LPs have sparse optima.

We reiterate our feeling that it is important to obtain practical algorithms
and understand the bidirected cut relaxation as well as possible, e.g. we know
now that it has an integrality gap of at most 1.28 on quasi-bipartite
instances, but obtaining such a bound directly could give new insights.

####  1.2.4 Other Related Work

In the special case of $r$-restricted instances for $r=3$, the partition
hypergraphic LP is essentially a special case of an LP introduced by Vande
Vate [33] for matroid matching, which is totally dual half-integral [16].
Additional facts about the hypergraphic relaxations appear in the thesis of
the third author [27], e.g. a combinatorial “gainless tree formulation” for
the LPs similar in flavour to the “1-tree bound” for the Held-Karp TSP
relaxation.

##  2 Uncrossing Partitions

In this section we are interested in uncrossing a minimal set of tight
partitions that uniquely define a basic feasible solution to ($\mathcal{P}$).
We start with a few preliminaries necessary to state our result formally.

###  2.1 Preliminaries

We introduce some needed well-known properties of partitions that arise in
combinatorial lattice theory [32].

######  Definition 2.1.

We say that a partition $\pi^{\prime}$ _refines_ another partition $\pi$ if
each part of $\pi^{\prime}$ is contained in some part of $\pi$. We also say
$\pi$ coarsens $\pi^{\prime}$. Two partitions _cross_ if neither refines the
other. A family of partitions forms a _chain_ if no pair of them cross.
Equivalently, a chain is any family $\pi^{1},\pi^{2},\dotsc,\pi^{t}$ such that
$\pi^{i}$ refines $\pi^{i-1}$ for each $1<i\leq t$.

The family $\Pi_{R}$ of all partitions of $R$ forms a _lattice_ with a _meet
operator_ $\wedge:\Pi_{R}^{2}\to\Pi_{R}$ and a _join operator_
$\vee:\Pi_{R}^{2}\to\Pi_{R}$. The meet $\pi\wedge\pi^{\prime}$ is the coarsest
partition that refines both $\pi$ and $\pi^{\prime}$, and the join
$\pi\vee\pi^{\prime}$ is the most refined partition that coarsens both $\pi$
and $\pi^{\prime}$. See Figure 5 on page 5 for an illustration.

######  Definition 2.2 (Meet of partitions).

Let the parts of $\pi$ be $\pi_{1},\dotsc,\pi_{t}$ and let the parts of
$\pi^{\prime}$ be $\pi^{\prime}_{1},\dotsc,\pi^{\prime}_{u}$. Then the parts
of the meet $\pi\wedge\pi^{\prime}$ are the nonempty intersections of parts of
$\pi$ with parts of $\pi^{\prime}$,

$\pi\wedge\pi^{\prime}=\\{\pi_{i}\cap\pi^{\prime}_{j}\mid 1\leq i\leq t,1\leq
j\leq u\textrm{ and }\pi_{i}\cap\pi^{\prime}_{j}\neq\varnothing\\}.$

Given a graph $G$ and a partition $\pi$ of $V(G)$, we say that $G$ _induces_
$\pi$ if the parts of $\pi$ are the vertex sets of the connected components of
$G$.

######  Definition 2.3 (Join of partitions).

Let $(R,E)$ be a graph that induces $\pi$, and let $(R,E^{\prime})$ be a graph
that induces $\pi^{\prime}$. Then the graph $(R,E\cup E^{\prime})$ induces
$\pi\vee\pi^{\prime}$.

(a)

(b)

(c)

Figure 5: Illustrations of some partitions. The black dots are the terminal
set $R$. (a): two partitions; neither refines the other. (b): the meet of the
partitions from (a). (c): the join of the partitions from (a).

Given a feasible solution $x$ to ($\mathcal{P}$), a partition $\pi$ is _tight_
if $\sum_{K\in\mathcal{K}}x_{K}\mathtt{rc}^{\pi}_{K}=r(\pi)-1$. Let
$\mathop{{\tt tight}}(x)$ be the set of all tight partitions. We are
interested in uncrossing this set of partitions. More precisely, we wish to
find a cross-free set of partitions (chain) which uniquely defines $x$. One
way would be to prove the following.

######  Property 2.4.

If two crossing partitions $\pi$ and $\pi^{\prime}$ are in $\mathop{{\tt
tight}}(x)$, then so are $\pi\wedge\pi^{\prime}$ and $\pi\vee\pi^{\prime}$.

This type of property is already well-used [9, 13, 21, 31] for sets (with
meets and joins replaced by unions and intersections respectively), and the
standard approach is the following. The typical proof considers the
constraints in ($\mathcal{P}$) corresponding to $\pi$ and $\pi^{\prime}$ and
uses the “supermodularity” of the RHS and the “submodularity” of the
coefficients in the LHS. In particular, if the following is true,

$\displaystyle\forall\pi,\pi^{\prime}:~{}r(\pi\vee\pi^{\prime})+r(\pi\wedge\pi^{\prime})$
$\displaystyle~{}~{}~{}\geq~{}~{}~{}r(\pi)+r(\pi^{\prime})$ (7)
$\displaystyle\forall
K,\pi,\pi^{\prime}:~{}\mathtt{rc}_{K}^{\pi}+\mathtt{rc}_{K}^{\pi^{\prime}}$
$\displaystyle~{}~{}~{}\geq~{}~{}~{}\mathtt{rc}_{K}^{\pi\vee\pi^{\prime}}+\mathtt{rc}_{K}^{\pi\wedge\pi^{\prime}}$
(8)

then Property 2.4 can be proved easily by writing a string of
inequalities.666In this hypothetical scenario we get
$r(\pi)+r(\pi^{\prime})-2=\sum_{K}x_{K}(\mathtt{rc}_{K}^{\pi}+\mathtt{rc}_{K}^{\pi^{\prime}})\geq\sum_{K}x_{K}(\mathtt{rc}_{K}^{\pi\wedge\pi^{\prime}}+\mathtt{rc}_{K}^{\pi\vee\pi^{\prime}})\geq
r(\pi\wedge\pi^{\prime})+r(\pi\vee\pi^{\prime})-2\geq
r(\pi)+r(\pi^{\prime})-2$; thus the inequalities hold with equality, and the
middle one shows $\pi\wedge\pi^{\prime}$ and $\pi\vee\pi^{\prime}$ are tight.

Inequality (7) is indeed true (see, for example, [32]), but unfortunately
inequality (8) is not true in general, as the following example shows.

######  Example 2.5.

Let $R=\\{1,2,3,4\\}$, $\pi=\\{\\{1,2\\},\\{3,4\\}\\}$ and
$\pi^{\prime}=\\{\\{1,3\\},\\{2,4\\}\\}.$ Let $K$ denote the full component
$\\{1,2,3,4\\}$. Then
$\mathtt{rc}_{K}^{\pi}+\mathtt{rc}_{K}^{\pi^{\prime}}=1+1<0+3=\mathtt{rc}_{K}^{\pi\vee\pi^{\prime}}+\mathtt{rc}_{K}^{\pi\wedge\pi^{\prime}}.$

Nevertheless, Property 2.4 is true; its correct proof is given in Section 2.2
and depends on a simple though subtle extension of the usual approach. The
crux of the insight needed to fix the approach is not to consider _pairs_ of
constraints in ($\mathcal{P}$), but rather multi-sets which may contain more
than two inequalities. Using this uncrossing result, we can prove the
following theorem (details are given in Section 2.3). Here, we let
$\underline{\pi}$ denote $\\{R\\}$, the unique partition with (minimal) rank
1; later we use $\overline{\pi}$ to denote $\\{\\{r\\}\mid r\in R\\}$, the
unique partition with (maximal) rank $|R|$.

######  Theorem 1.

Let $x^{*}$ be a basic feasible solution of ($\mathcal{P}$), and let
$\mathcal{C}$ be an inclusion-wise maximal chain in $\mathop{{\tt
tight}}(x^{*})\backslash\underline{\pi}$. Then $x^{*}$ is uniquely defined by

$\sum_{K\in\mathcal{K}}\mathtt{rc}_{K}^{\pi}x^{*}_{K}=r(\pi)-1\quad\forall\pi\in\mathcal{C}.$
(9)

Any chain of distinct partitions of $R$ that does not contain
$\underline{\pi}$ has size at most $|R|-1$, and this is an upper bound on the
rank of the system in (9). Elementary linear programming theory immediately
yields the following corollary.

######  Corollary 2.6.

Any basic solution $x^{*}$ of ($\mathcal{P}$) has at most $|R|-1$ non-zero
coordinates.

###  2.2 Partition Uncrossing Inequalities

We start with the following definition.

######  Definition 2.7.

Let $\pi\in\Pi_{R}$ be a partition and let $S\subset R$. Define the _merged
partition_ $m(\pi,S)$ to be the most refined partition that coarsens $\pi$ and
contains all of $S$ in a single part. See Figure 6 on page 6 for an example.
Informally, $m(\pi,S)$ is obtained by merging all parts of $\pi$ which
intersect $S$. Formally, $m(\pi,S)$ equals the set of parts
$\\{\\{\pi_{j}\\}_{j:\pi_{j}\cap S=\varnothing},\bigcup_{j:\pi_{j}\cap
S\neq\varnothing}\pi_{j}\\}$.

Figure 6: Illustration of merging. The left figure shows a (solid) partition
$\pi$ along with a (dashed) set $S$. The right figure shows the merged
partition $m(\pi,S)$.

We will use the following straightforward fact later:

$\mathtt{rc}_{K}^{\pi}=r(\pi)-r(m(\pi,K)).$ (10)

We now state the (true) inequalities which replace the false inequality (8).
Later, we show how one uses these to obtain partition uncrossing, e.g. to
prove Property 2.4.

######  Lemma 2.8 (Partition Uncrossing Inequalities).

Let $\pi,\pi^{\prime}\in\Pi_{R}$ and let the parts of $\pi$ be
$\pi_{1},\pi_{2},\dotsc,\pi_{r(\pi)}$.

$\displaystyle r(\pi)\left[r(\pi^{\prime})-1\right]+\left[r(\pi)-1\right]$
$\displaystyle=$
$\displaystyle\left[r(\pi\wedge\pi^{\prime})-1\right]+\sum_{i=1}^{r(\pi)}\left[r(m(\pi^{\prime},\pi_{i}))-1\right]$
(11) $\displaystyle\forall K\in\mathcal{K}:\quad
r(\pi)\Bigl{[}\mathtt{rc}_{K}^{\pi^{\prime}}\Bigr{]}+\Bigl{[}\mathtt{rc}_{K}^{\pi}\Bigr{]}$
$\displaystyle\geq$
$\displaystyle\Bigl{[}\mathtt{rc}_{K}^{\pi\wedge\pi^{\prime}}\Bigr{]}+\sum_{i=1}^{r(\pi)}\Bigl{[}\mathtt{rc}_{K}^{m(\pi^{\prime},\pi_{i})}\Bigr{]}$
(12)

Before giving the proof of the above lemma, let us first show how it can be
used to prove the statement Property 2.4.

Proof of Property 2.4. Since $\pi$ and $\pi^{\prime}$ are tight,

$\displaystyle
r(\pi)[r(\pi^{\prime})-1]+[r(\pi)-1]=r(\pi)\Bigl{[}\sum_{K}x_{K}\mathtt{rc}_{K}^{\pi^{\prime}}\Bigr{]}+\Bigl{[}\sum_{K}x_{K}\mathtt{rc}_{K}^{\pi}\Bigr{]}=\sum_{K}x_{K}\biggl{(}r(\pi)\Bigl{[}\mathtt{rc}_{K}^{\pi^{\prime}}\Bigr{]}+\Bigl{[}\mathtt{rc}_{K}^{\pi}\Bigr{]}\biggr{)}$
$\displaystyle\geq\sum_{K}x_{K}\biggl{(}\Bigl{[}\mathtt{rc}_{K}^{\pi\wedge\pi^{\prime}}\Bigr{]}+\sum_{i=1}^{r(\pi)}\Bigl{[}\mathtt{rc}_{K}^{m(\pi^{\prime},\pi_{i})}\Bigr{]}\biggr{)}=\sum_{K}x_{K}\Bigl{[}\mathtt{rc}_{K}^{\pi\wedge\pi^{\prime}}\Bigr{]}+\sum_{i=1}^{r(\pi)}\sum_{K}x_{K}\Bigl{[}\mathtt{rc}_{K}^{m(\pi^{\prime},\pi_{i})}\Bigr{]}$
$\displaystyle\geq\left[r(\pi\wedge\pi^{\prime})-1\right]+\sum_{i=1}^{r(\pi)}\left[r(m(\pi^{\prime},\pi_{i}))-1\right]=r(\pi)\left[r(\pi^{\prime})-1\right]+\left[r(\pi)-1\right]$

where the first inequality follows from (12) and the second from (5) (as $x$
is feasible); the last equality is (11). Since the first and last terms are
equal, all the inequalities are equalities, in particular our application of
(5) shows that $\pi\wedge\pi^{\prime}$ and each $m(\pi^{\prime},\pi_{i})$ is
tight. Iterating the latter fact, we see that $m(\dotsb
m(m(\pi^{\prime},\pi_{1}),\pi_{2}),\dotsb)=\pi\vee\pi^{\prime}$ is also tight.
$\square$

To prove the inequalities in Lemma 2.8 we need the following lemma that
relates the rank of sets and the rank contribution of partitions. Recall
$\rho(X):=\max(0,|X|-1)$.

######  Lemma 2.9.

For a partition $\pi=\\{\pi_{1},\dotsc,\pi_{t}\\}$ of $R$, where $t=r(\pi)$,
and for any $K\subseteq R$, we have

$\rho(K)=\mathtt{rc}_{K}^{\pi}+\sum_{i=1}^{t}\rho(K\cap\pi_{i}).$

###### Proof.

By definition, $K\cap\pi_{i}\neq\varnothing$ for exactly
$1+\mathtt{rc}_{K}^{\pi}$ values of $i$. Also, $\rho(K\cap\pi_{i})=0$ for all
other $i$. Hence

$\sum_{i=1}^{t}\rho(K\cap\pi_{i})=\sum_{i:K\cap\pi_{i}\neq\varnothing}(|K\cap\pi_{i}|-1)=\left(\sum_{i:K\cap\pi_{i}\neq\varnothing}|K\cap\pi_{i}|\right)-(\mathtt{rc}_{K}^{\pi}+1).$
(13)

Observe that
$\sum_{i:K\cap\pi_{i}\neq\varnothing}|K\cap\pi_{i}|=|K|=\rho(K)+1$; using this
fact together with Equation (13) we obtain

$\sum_{i=1}^{t}\rho(K\cap\pi_{i})=\left(\sum_{i:K\cap\pi_{i}\neq\varnothing}|K\cap\pi_{i}|\right)-(\mathtt{rc}_{K}^{\pi}+1)=\rho(K)-1+(\mathtt{rc}_{K}^{\pi}+1).$

Rearranging, the proof of Lemma 2.9 is complete. ∎

Proof of Lemma 2.8. First, we argue that
$\pi\wedge\pi^{\prime}=\overline{\pi}$ holds without loss of generality. In
the general case, for each part $p$ of $\pi\wedge\pi^{\prime}$ with $|p|\geq
2$, contract $p$ into one pseudo-vertex and define the new $K$ to include the
pseudo-vertex corresponding to $p$ if and only if $K\cap p\neq\varnothing$.
This contraction does not affect the value of any of the terms in Equations
(12) and (11), so is without loss of generality. After contraction, for any
part $\pi_{i}$ of $\pi$ and part $\pi^{\prime}_{j}$ of $\pi^{\prime}$, we have
$|\pi_{i}\cap\pi^{\prime}_{j}|\leq 1$, so indeed
$\pi\wedge\pi^{\prime}=\overline{\pi}$.

###### Proof of Equation (11).

Fix $i$. Since $|\pi_{i}\cap\pi^{\prime}_{j}|\leq 1$ for all $j$, the rank
contribution $\mathtt{rc}_{\pi_{i}}^{\pi^{\prime}}$ is equal to $|\pi_{i}|-1.$
Then using Equation (10) we know that
$r(m(\pi^{\prime},\pi_{i}))=r(\pi^{\prime})-|\pi_{i}|+1$. Thus adding over all
$i$, the right-hand side of Equation (11) is equal to

$|R|-1+\sum_{i=1}^{r(\pi)}(r(\pi^{\prime})-|\pi_{i}|)=|R|-1+r(\pi)r(\pi^{\prime})-|R|$

and this is precisely the left-hand side of Equation (11). ∎

###### Proof of Equation (12).

Fix $i$. Since $|\pi_{i}\cap\pi^{\prime}_{j}|\leq 1$ for all $j$, we have

$\mathtt{rc}_{K}^{\pi^{\prime}}-\mathtt{rc}_{K}^{m(\pi^{\prime},\pi_{i})}\geq\rho(\pi_{i}\cap
K)$ (14)

because, when we merge the parts of $\pi^{\prime}$ intersecting $\pi_{i}$, we
make $K$ span at least $\rho(\pi_{i}\cap K)$ fewer parts. Note that the
inequality could be strict if both $\pi_{i}$ and $K$ intersect a part of
$\pi^{\prime}$ without having a common vertex in that part.

Adding the right-hand side of Equation (14) over all $i$ gives

$\sum_{i=1}^{r(\pi)}(\mathtt{rc}_{K}^{\pi^{\prime}}-\mathtt{rc}_{K}^{m(\pi^{\prime},\pi_{i})})\geq\sum_{i=1}^{r(\pi)}\rho(\pi_{i}\cap
K)=\rho(K)-\mathtt{rc}_{K}^{\pi}.$ (15)

where the last equality follows from Lemma 2.9. To finish the proof we observe
$\rho(K)=\mathtt{rc}_{K}^{\pi\wedge\pi^{\prime}}$, since
$\pi\wedge\pi^{\prime}=\overline{\pi}$. ∎

This completes the proof of Lemma 2.8. $\hfill\Box$

###  2.3 Sparsity of Basic Feasible Solutions: Proof of Theorem 1

###### Proof.

Let $\mathop{{\tt supp}}(x^{*})$ be the full components $K$ with
$x^{*}_{K}>0$. Consider the constraint submatrix with rows corresponding to
the tight partitions and columns corresponding to the full components in
$\mathop{{\tt supp}}(x^{*})$. Since $x^{*}$ is a basic feasible solution, any
full-rank subset of rows uniquely defines $x^{*}$. We now show that any
maximal chain $\mathcal{C}$ in $\mathop{{\tt tight}}(x^{*})$ corresponds to
such a subset.

Let ${\tt row}(\pi)\in\mathbf{R}^{\mathop{{\tt supp}}(x^{*})}$ denote the row
corresponding to partition $\pi$ of this matrix, i.e., ${\tt
row}(\pi)_{K}=\mathtt{rc}^{\pi}_{K}$, and given a collection $\mathcal{R}$ of
partitions (rows), let $\mathop{{\tt span}}(\mathcal{R})$ denote the linear
span of the rows in $\mathcal{R}$. We now prove that for any tight partition
$\pi\notin\mathcal{C}$, we have ${\tt row}(\pi)\in\mathop{{\tt
span}}(\mathcal{C})$; this will complete the proof of the theorem.

For sake of contradiction, suppose ${\tt row}(\pi)\not\in\mathop{{\tt
span}}(\mathcal{C})$. Choose $\pi$ to be the counterexample partition with
smallest rank $r(\pi)$. Firstly, since $\mathcal{C}$ is maximal, $\pi$ must
cross some partition $\sigma$ in $\mathcal{C}$. Choose $\sigma$ to be the most
refined partition in $\mathcal{C}$ which crosses $\pi$. Let the parts of
$\sigma$ be $(\sigma_{1},\ldots,\sigma_{t})$. The following claim uses the
partition uncrossing inequalities to derive a linear dependence between the
rows corresponding to $\sigma,\pi$ and the partitions formed by merging parts
of $\sigma$ with $\pi$.

######  Claim 2.10.

We have ${\tt row}(\sigma)+|r(\sigma)|\cdot{\tt row}(\pi)={\tt
row}(\pi\wedge\sigma)+\sum_{i=1}^{t}{\tt row}(m(\pi,\sigma_{i}))$.

###### Proof.

Since $\sigma$ and $\pi$ are both tight partitions, the proof of Property 2.4
shows that the partition inequality (12) holds with equality for all
$K\in\mathop{{\tt supp}}(x^{*})$, $\pi$ and $\sigma$, implying the claim. ∎

Let $\mathtt{cp}_{\pi}(\sigma)$ be the parts of $\sigma$ which intersect at
least two parts of $\pi$; i.e., merging the parts of $\pi$ that intersect
$\sigma_{i}$, for any $\sigma_{i}\in\mathtt{cp}_{\pi}(\sigma)$, decreases the
rank of $\pi$. Formally,

$\mathtt{cp}_{\pi}(\sigma):=\\{\sigma_{i}\in\sigma:~{}~{}m(\pi,\sigma_{i})\neq\pi\\}$

Note that one can modify Claim 2.10 by subtracting
$(r(\sigma)-|\mathtt{cp}_{\pi}(\sigma)|){\tt row}(\pi)$ from both sides to get

${\tt row}(\sigma)+|\mathtt{cp}_{\pi}(\sigma)|\cdot{\tt row}(\pi)={\tt
row}(\pi\wedge\sigma)+\sum_{\sigma_{i}\in\mathtt{cp}_{\pi}(\sigma)}{\tt
row}(m(\pi,\sigma_{i}))$ (16)

Now if ${\tt row}(\pi)\notin\mathop{{\tt span}}(\mathcal{C})$, we must have
either ${\tt row}(\pi\wedge\sigma)$ is not in $\mathop{{\tt
span}}(\mathcal{C})$ or ${\tt row}(m(\pi,\sigma_{i}))$ is not in $\mathop{{\tt
span}}(\mathcal{C})$ for some $i$. We show that either case leads to the
needed contradiction, which will prove the theorem.

Case 1:

${\tt row}(\pi\wedge\sigma)\notin\mathop{{\tt span}}(\mathcal{C})$. Note there
is $\sigma^{\prime}\in\mathcal{C}$ which crosses $\pi\wedge\sigma$, since
$\pi\wedge\sigma$ is not in the maximal chain $\mathcal{C}$. Since
$\sigma^{\prime},\sigma\in\mathcal{C}$ and by considering the refinement
order, it is easy to see that $\sigma^{\prime}$ (strictly) refines $\sigma$
and $\sigma^{\prime}$ crosses $\pi$. This contradicts our choice of $\sigma$
as the most refined partition in $\mathcal{C}$ crossing $\pi$, since
$\sigma^{\prime}$ was also a candidate.

Case 2:

${\tt row}(m(\pi,\sigma_{i}))\not\in\mathop{{\tt span}}(\mathcal{C})$. Note
$m(\pi,\sigma_{i})$ is also tight. Since
$\sigma_{i}\in\mathtt{cp}_{\pi}(\sigma)$, $m(\pi,\sigma_{i})$ has smaller rank
than $\pi$. This contradicts our choice of $\pi$.

This completes the proof of Theorem 1. ∎

##  3 Equivalence of Formulations

In this section we describe our equivalence results. A summary of the known
and new results is given in Figure 7 on page 7.

$\mathop{\mathrm{OPT}}\eqref{eq:LP-S}$$\mathop{\mathrm{OPT}}$($\mathcal{P}$)$\mathop{\mathrm{OPT}}$($\mathcal{P}^{\prime}$)$\mathop{\mathrm{OPT}}$($\mathcal{D}$)$\mathop{\mathrm{OPT}}$($\mathcal{B}$)$=$[Thm.
2]$=$[Thm. 4]$=$[26]$=$[Appendix A]$\geq$[Lemma 1.2],[26]$\leq$in quasi-
bipartite [Thm. 5] Figure 7: Summary of relations among various LP relaxations

As we mentioned in the introduction, we give a redundant set of proofs for
completeness and to demonstrate novel techniques. The proof that
($\mathcal{P}$) and ($\mathcal{D}$) have the same value, which appears in
Appendix A, is a consequence of hypergraph orientation results of Frank et al.
[14].

###  3.1 Bounded and Unbounded Partition Relaxations

######  Theorem 2.

The LPs ($\mathcal{P}^{\prime}$) and ($\mathcal{P}$) have the same optimal
value.

We actually prove a stronger statement.

######  Definition 3.1.

The collection $\mathcal{K}$ of hyperedges is _down-closed_ if whenever
$S\in\mathcal{K}$ and $\varnothing\neq T\subset S$, then $T\in\mathcal{K}.$
For down-closed $\mathcal{K}$, the cost function
$C:\mathcal{K}\to\mathbf{R}_{+}$ is _non-decreasing_ if $C_{S}\leq C_{T}$
whenever $S\subset T$.

######  Theorem 3.

If the set of hyperedges is down-closed and the cost function is non-
decreasing, then ($\mathcal{P}^{\prime}$) and ($\mathcal{P}$) have the same
optimal value.

Theorem 3 implies Theorem 2 since the hypergraph and cost function derived
from instances of the Steiner tree problem are down-closed and non-decreasing
(e.g. $C_{\\{k\\}}=0$ for every $k\in R$; we remark that the variables
$x_{\\{k\\}}$ act just as placeholders). Our proof of Theorem 2 relies on the
following operation which we call shrinking.

######  Definition 3.2.

Given an assignment $x:\mathcal{K}\to\mathbf{R}_{+}$ to the full components,
suppose $x_{K}>0$ for some $K$. The operation ${\tt
Shrink}(x,K,K^{\prime},\delta)$, where $K^{\prime}\subseteq K$,
$|K^{\prime}|=|K|-1$ and $0<\delta\leq x_{K}$, changes $x$ to $x^{\prime}$ by
decreasing $x^{\prime}_{K}:=x_{K}-\delta$ and increasing
$x^{\prime}_{K^{\prime}}:=x_{K^{\prime}}+\delta$.

Note that shrinking is defined only for down-closed hypergraphs. Also note
that on performing a shrinking operation, the cost of the solution cannot
increase, if the cost function is non-decreasing. The theorem is proved by
taking the optimum solution to ($\mathcal{P}$) which minimizes the sum
$\sum_{K\in\mathcal{K}}x_{K}|K|$, and then showing that this must satisfy the
equality in ($\mathcal{P}^{\prime}$), or a shrinking operation can be
performed. Now we give the details.

###### Proof of Theorem 3.

It suffices to exhibit an optimum solution of ($\mathcal{P}$) which satisfies
the equality in ($\mathcal{P}^{\prime}$). Let $x$ be an optimal solution to
($\mathcal{P}$) which minimizes the sum $\sum_{K\in\mathcal{K}}x_{K}|K|$.

######  Claim 3.3.

For every $K$ with $x_{K}>0$ and for every $r\in K$, there exists a tight
partition (w.r.t. $x$) $\pi$ such that the part of $\pi$ containing $r$
contains no other vertex of $K$.

###### Proof.

Let $K^{\prime}=K\setminus\\{r\\}$. If the above is not true, then this
implies that for every tight partition $\pi$, we have
$\mathtt{rc}_{K}^{\pi}=\mathtt{rc}_{K^{\prime}}^{\pi}$. We now claim that
there is a $\delta>0$ such that we can perform ${\tt
Shrink}(x,K,K^{\prime},\delta)$ while retaining feasibility in
($\mathcal{P}$). This is a contradiction since the shrink operation strictly
reduces $\sum_{K}|K|x_{K}$ and doesn’t increase cost. Specifically, take

$\delta:=\min\\{x_{K},\min_{\pi:\mathtt{rc}_{K^{\prime}}^{\pi}\neq\mathtt{rc}_{K}^{\pi}}\sum_{K}\mathtt{rc}_{K}^{\pi}x_{K}-r(\pi)+1\\}$

which is positive since for tight partitions we have
$\mathtt{rc}_{K}^{\pi}=\mathtt{rc}_{K^{\prime}}^{\pi}$. ∎

Let $\mathop{{\tt tight}}(x)$ be the set of tight partitions, and
$\pi^{*}:=\bigwedge\\{\pi\mid\pi\in\mathop{{\tt tight}}(x)\\}$ the meet of all
tight partitions. By Property 2.4, $\pi^{*}$ is tight. By Claim 3.3, for any
$K$ with $x_{K}>0$, we have $\mathtt{rc}_{K}^{\pi^{*}}=|K|-1$. Thus,
$r(\pi^{*})-1=\sum_{K\in\mathcal{K}}x_{K}\mathtt{rc}_{K}^{\pi^{*}}=\sum_{K\in\mathcal{K}}x_{K}(|K|-1)\geq
r(\overline{\pi})-1$. But since $\overline{\pi}$ is the unique maximal-rank
partition, this implies $\pi^{*}=\overline{\pi}$. Thus $\overline{\pi}$ is
tight. This implies $x\in\eqref{eq:LP-P2}$. ∎

###  3.2 Partition and Subtour Elimination Relaxations

######  Theorem 4.

The feasible regions of ($\mathcal{P}^{\prime}$) and ($\mathcal{S}$) are the
same.

###### Proof.

Let $x$ be any feasible solution to the LP ($\mathcal{S}$). Note that the
equality constraint of ($\mathcal{P}^{\prime}$) is the same as that of
($\mathcal{S}$). We now show that $x$ satisfies (5). Fix a partition
$\pi=\\{\pi_{1},\dotsc,\pi_{t}\\}$, so $t=r(\pi)$. For each $1\leq i\leq t$,
subtract the inequality constraint in ($\mathcal{S}$) with $S=\pi_{i}$, from
the equality constraint in ($\mathcal{S}$) to obtain

$\sum_{K\in\mathcal{K}}x_{K}\Bigl{(}\rho(K)-\sum_{i=1}^{t}\rho(K\cap\pi_{i})\Bigr{)}\geq\rho(R)-\sum_{i=1}^{t}\rho(\pi_{i}).$
(17)

From Lemma 2.9,
$\rho(K)-\sum_{i=1}^{t}\rho(K\cap\pi_{i})=\mathtt{rc}_{K}^{\pi}$. We also have
$\rho(R)-\sum_{i=1}^{t}\rho(\pi_{i})=|R|-1-(|R|-r(\pi))=r(\pi)-1$. Thus $x$ is
a feasible solution to the LP ($\mathcal{P}^{\prime}$).

Now, let $x$ be a feasible solution to ($\mathcal{P}^{\prime}$) and it
suffices to show that it satisfies the inequality constraints of
($\mathcal{S}$). Fix a set $S\subset R$. Note when $S=\varnothing$ that
inequality constraint is vacuously true so we may assume $S\neq\varnothing$.
Let $R\backslash S=\\{r_{1},\dotsc,r_{u}\\}$. Consider the partition
$\pi=\\{\\{r_{1}\\},\dotsc,\\{r_{u}\\},S\\}$. Subtract (5) for this $\pi$ from
the equality constraint in ($\mathcal{P}^{\prime}$), to obtain

$\sum_{K\in\mathcal{K}}x_{K}(\rho(K)-\mathtt{rc}_{K}^{\pi})\leq\rho(R)-r(\pi)+1.$
(18)

Using Lemma 2.9 and the fact that $\rho(K\cap\\{r_{j}\\})=0$ (the set is
either empty or a singleton), we get $\rho(K)-\mathtt{rc}_{K}^{\pi}=\rho(K\cap
S)$. Finally, as $\rho(R)-r(\pi)+1=|R|-1-(|R\backslash S|+1)+1=\rho(S),$ the
inequality (18) is the same as the constraint needed. Thus $x$ is a feasible
solution to ($\mathcal{S}$), proving the theorem. ∎

###  3.3 Partition and Bidirected Cut Relaxations in Quasibipartite Instances

######  Theorem 5.

On quasibipartite Steiner tree instances,
$\mathop{\mathrm{OPT}}\eqref{eq:LP-B}\geq\mathop{\mathrm{OPT}}\eqref{eq:LP-
PUDir}$.

To prove Theorem 5, we look at the duals of the two LPs and we show
$\mathop{\mathrm{OPT}}\eqref{eq:LP-
BD}\geq\mathop{\mathrm{OPT}}\eqref{eq:LP-A}$ in quasibipartite instances.
Recall that the support of a solution to ($\mathcal{D}_{D}$) is the family of
sets with positive $z_{U}$. A family of sets is called _laminar_ if for any
two of its sets $A,B$ we have $A\subseteq B,B\subseteq A$, or $A\cap
B=\varnothing$.

######  Lemma 3.4.

There exists an optimal solution to ($\mathcal{D}_{D}$) whose support is a
laminar family of sets.

###### Proof.

Choose an optimal solution $z$ to ($\mathcal{D}_{D}$) which maximizes
$\sum_{U}z_{U}|U|^{2}$ among all optimal solutions. We claim that the support
of this solution is laminar. Suppose not and there exists $U$ and $U^{\prime}$
with $U\cap U^{\prime}\neq\varnothing$ and $z_{U}>0$ and $z_{U^{\prime}}>0$.
Define $z^{\prime}$ to be the same as $z$ except
$z^{\prime}_{U}=z_{U}-\delta$,
$z^{\prime}_{U^{\prime}}=z_{U^{\prime}}-\delta$, $z^{\prime}_{U\cup
U^{\prime}}=z_{U\cup U^{\prime}}+\delta$ and $z^{\prime}_{U\cap
U^{\prime}}=z_{U\cap U^{\prime}}+\delta$; we will show for small $\delta>0$,
$z^{\prime}$ is feasible. Note that $U\cap U^{\prime}$ is not empty and $U\cup
U^{\prime}$ doesn’t contain $r$, and the objective value remains unchanged.
Also note that for any $K$ and $i\in K$, if $z_{U\cup U^{\prime}}$ or
$z_{U\cap U^{\prime}}$ appears in the summand of a constraint, then at least
one of $z_{U}$ or $z_{U^{\prime}}$ also appears. If both $z_{U\cup
U^{\prime}}$ and $z_{U\cap U^{\prime}}$ appears, then both $z_{U}$ and
$z_{U^{\prime}}$ appears. Thus $z^{\prime}$ is an optimal solution and
$\sum_{U}z^{\prime}_{U}|U|^{2}>\sum_{U}z_{U}|U|^{2}$, contradicting the choice
of $z$. ∎

######  Lemma 3.5.

For quasibipartite instances, given a solution of ($\mathcal{D}_{D}$) with
laminar support, we can get a feasible solution to ($\mathcal{B}_{D}$) of the
same value.

###### Proof.

This lemma is the heart of the theorem, and is a little technical to prove. We
first give a sketch of how we convert a feasible solution $z$ of
($\mathcal{D}_{D}$) into a feasible solution to ($\mathcal{B}_{D}$) of the
same value.

Comparing ($\mathcal{D}_{D}$) and ($\mathcal{B}_{D}$) one first notes that the
former has a variable for every valid subset of the terminals, while the
latter assigns values to all valid subsets of the entire vertex set. We say
that an edge $uv$ is _satisfied_ for a candidate solution $z$, if both a)
$\sum_{U:u\in U,v\notin U}z_{U}\leq c_{uv}$ and b) $\sum_{U:v\in U,u\notin
U}z_{U}\leq c_{uv}$ hold; $z$ is then feasible for ($\mathcal{B}_{D}$) if all
edges are satisfied.

Let $z$ be a feasible solution to ($\mathcal{D}_{D}$). One easily verifies
that all terminal-terminal edges are satisfied. On the other hand, terminal-
Steiner edges may initially not be satisfied. To see this consider the Steiner
vertex $v$ and its neighbours depicted in Figure 3.3 on page 3.3 below.
Initially, none of the sets in $z$’s support contains $v$, and the load on the
edges incident to $v$ is quite skewed: the left-hand side of condition a)
above may be large, while the left-hand side of condition b) is initially $0$.

To construct a valid solution for ($\mathcal{B}_{D}$), we therefore lift the
initial value $z_{S}$ of each terminal subset $S$ to supersets of $S$, by
adding Steiner vertices. The lifting procedure processes each Steiner vertex
$v$ one at a time; when processing $v$, we change $z$ by moving dual from some
sets $U$ to $U\cup\\{v\\}$. Such a dual transfer decreases the left-hand side
of condition a) for edge $uv$, and increases the (initially $0$) left-hand
sides of condition b) for edges connecting $v$ to neighbours other than $v$.

We will soon see that there is a way of carefully lifting duals around $v$
that ensures that all edges incident to $v$ become satisfied. The definition
of our procedure will ensure that these edges remain satisfied for the rest of
the lifting procedure. Since there are no Steiner-Steiner edges, all edges
will be satisfied once all Steiner vertices are processed.

Lifting variable $z_{U}$. (5.5cm,4.5cm)[fr]

Throughout the lifting procedure, we will maintain that $z$ remains unchanged,
when projected to the terminals. Formally, we maintain the following crucial
projection invariant:

The quantity $\sum_{U:S\subseteq U\subseteq S\cup(V\setminus R)}z_{U}$ remains
constant, for all terminal sets $S$. (PI)

This invariant leads to two observations: first, the constraint (4) is
satisfied by $z$ at all times, even when it is defined on subsets of all
vertices; second, $\sum_{U\subseteq V}z_{U}$ is constant throughout, and the
objective value of $z$ in ($\mathcal{B}_{D}$) is not affected by the lifting.
The existence of a lifting of duals around Steiner vertex $v$ such that (PI)
is maintained, and such that all edges incident to $v$ are satisfied can be
phrased as a feasibility problem for a linear system of inequalities. We will
use Farkas’ lemma and the feasibility of $z$ for (4) to complete the proof.

We now fill in the proof details. Let $\Gamma(v)$ denote the set of neighbours
of vertex $v$ in the given graph $G$. In each iteration, where we process
Steiner node $v$, let

$\mathcal{U}_{v}:=\\{U:z_{U}>0~{}~{}\textrm{and}~{}~{}U\cap\Gamma(v)\neq\varnothing\\}$

be the sets in $z$’s support that contain neighbours of $v$. Note that
$U\in\mathcal{U}_{v}$ could contain Steiner vertices on which the lifting
procedure has already taken place. However, by (PI) and by Lemma 3.4 the
multi-family $\\{U\cap R:U\in\mathcal{U}_{v}\\}$ is laminar. In the lifting
process, we will transfer $x_{U}$ units of the $z_{U}$ units of dual of each
set $U\in\mathcal{U}_{v}$ to the set $U^{\prime}=U\cup\\{v\\}$; this decreases
the dual load (LHS of (2)) on arcs from $U\cap\Gamma(v)$ to $v$ (e.g. $uv$ in
Figure 3.3 on page 3.3) and increases the dual load on arcs from $v$ to
$\Gamma(v)\backslash U$ (e.g. $vu^{\prime}$ in the figure). The following
system of inequalities describes the set of feasible liftings.

$\displaystyle\forall U\in\mathcal{U}_{v}:$ $\displaystyle\qquad x_{U}\leq
z_{U}$ (L1) $\displaystyle\forall u\in\Gamma(v):$
$\displaystyle\qquad\sum_{U:u\in U}(z_{U}-x_{U})\leq c_{uv}$ (L2)
$\displaystyle\forall u\in\Gamma(v):$ $\displaystyle\qquad\sum_{U:u\notin
U}x_{U}\leq c_{uv}$ (L3)

######  Claim 3.6.

If (L1), (L2), (L3) have a feasible solution $x\geq 0$, then the lifting
procedure can be performed at Steiner vertex $v$, while maintaining the
projection invariant property.

###### Proof.

Define the new solution to be $z_{U}:=z_{U}-x_{U}$, and, $z_{(U\cup
v)}:=x_{U}$, for all $U\in\mathcal{U}_{v}$, and $z_{U}$ remains unchanged for
all other $U$. It is easy to check that all edges which were satisfied remain
satisfied, and (L2) and (L3) imply that all edges incident to $v$ are
satisfied. Also note that the projection invariant property is maintained. ∎

By Farkas’ lemma, if (L1), (L2), (L3) do not have a feasible solution $x\geq
0$, then there exist non-negative multipliers — $\lambda_{U}$ for all
$U\in\mathcal{U}_{v}$, and $\alpha_{u},\beta_{u}$ for all $u\in\Gamma(v)$ —
satisfying the following dual set of linear inequalities:

$\displaystyle\sum_{U\in\mathcal{U}_{v}}\lambda_{U}z_{U}+\sum_{u\in\Gamma(v)}\alpha_{u}\bigl{(}c_{uv}-\sum_{U:u\in
U}z_{U}\bigr{)}+\sum_{u\in\Gamma(v)}\beta_{u}c_{uv}$ $\displaystyle\quad<\quad
0$ (D1) $\displaystyle\forall U\in\mathcal{U}_{v}:\lambda_{U}-\sum_{u\in
U}\alpha_{u}+\sum_{u\notin U}\beta_{u}$ $\displaystyle\quad\geq\quad 0$ (D2)

As a technicality, note that the sub-system
$\\{\eqref{eq:L1},\eqref{eq:L2},x\geq 0\\}$ is feasible — take $x=z$. Thus any
$\alpha,\beta,\lambda$ satisfying (D1) and (D2) has $\sum_{u}\beta_{u}>0$, so
by dividing all $\alpha,\beta,\lambda$ by $\sum_{i}\beta_{i}$, we may assume
without loss of generality that

$\displaystyle\sum_{u\in\Gamma(v)}\beta_{u}=1.$ (D3)

Subtracting (D3) from (D2) allows us to rewrite the latter set of constraints
conveniently as

$\displaystyle\forall U\in\mathcal{U}_{v}:$
$\displaystyle\qquad\lambda_{U}-\sum_{u\in U}(\alpha_{u}+\beta_{u})+1\geq 0.$
(D2’)

The following claim shows that (L1), (L2), (L3) does have a feasible solution,
and thus by Claim 3.6, lifting can be done, which completes the proof of Lemma
3.5.

######  Claim 3.7.

There exists no feasible solution to $\\{\alpha,\beta,\lambda\geq
0:\eqref{eq:D1},\eqref{eq:D2'},\textrm{and }\eqref{eq:D3}\\}$.

###### Proof.

Consider the linear program which minimizes the LHS of (D1) subject to the
constraints (D2’) and (D3). We show that the LP has value at least $0$, which
will complete the proof.

Let $(\lambda^{*},\alpha^{*},\beta^{*})$ be an optimal solution to the LP. In
Lemma 3.8 we will show that the constraint matrix of the LP is totally
unimodular; hence, since the right-hand side of the given system is integral,
we may assume that $\lambda^{*},\alpha^{*}$, and $\beta^{*}$ are non-negative
and integral. From (D3) we infer

There is a unique $\bar{u}\in\Gamma(v)$ for which $\beta^{*}_{\bar{u}}=1$; for
all $u\neq\bar{u}$, $\beta^{*}_{u}=0$. (19)

Moreover, since each $\lambda_{U}$ appears only in the two constraints (D2’)
and $\lambda_{U}\geq 0$, and since $\lambda_{U}$ has nonnegative coefficient
in the objective, we may assume

$\lambda^{*}_{U}=\lambda^{*}_{U}(\alpha^{*},\beta^{*}):=\max\\{\sum_{u\in
U}(\alpha^{*}_{u}+\beta^{*}_{u})-1,0\\}$ (20)

for all $U$.

Next, we establish the following:

$\alpha^{*}_{u}+\beta^{*}_{u}\in\\{0,1\\}$ for all $u\in\Gamma(v)$. (21)

Suppose for the sake of contradiction that property (21) does not hold for our
solution. Let $u$ be such that $\alpha^{*}_{u}+\beta^{*}_{u}\geq 2$. By (19),
$\alpha^{*}_{u}\geq 1$. We propose the following update to our solution:
decrease $\alpha^{*}_{u}$ by $1$ (which by (20) will decrease
$\lambda^{*}_{U}$ by $1$ for all $U\in\mathcal{U}_{v}$). This maintains the
feasibility of (D2’), and the objective value decreases by

$\sum_{U\in\mathcal{U}_{v}:u\in U}z_{U}+(c_{uv}-\sum_{u\in U}z_{U})$

which is non-negative as $c\geq 0$. By repeating this operation, we may
clearly ensure property (21).

Let $K\subseteq\Gamma(v)$ be the set
$\\{u\mid\alpha^{*}_{u}+\beta^{*}_{u}=1\\}$ and recall $\bar{u}$ is the unique
terminal with $\beta^{*}_{\bar{u}}=1$; $\bar{u}$ is clearly a member of $K$.
At $(\alpha^{*},\beta^{*},\lambda^{*})$, we evaluate the objective and collect
like terms to get value

$\displaystyle\sum_{U\in\mathcal{U}_{v}}z_{U}\rho(U\cap K)+\sum_{u\in
K\setminus\bar{u}}(c_{uv}-\sum_{U:u\in U}z_{U})+c_{\bar{u}v}$
$\displaystyle=\sum_{u\in K}c_{uv}+\sum_{U\in\mathcal{U}_{v}}z_{U}(\rho(U\cap
K)-|(K\backslash\bar{u})\cap U|)$ $\displaystyle=\sum_{u\in
K}c_{uv}-\sum_{U\in\mathcal{U}_{v}:U\cap K\neq\varnothing,\bar{u}\not\in
U}z_{U}$

where the last equality follows by considering cases. Finally, combining the
fact that $\sum_{u\in K}c_{uv}\geq C_{K}$ (since these edges form one possible
full component on terminal set $K$) together with (4) for the pair
$(K,\bar{u})$, it follows that the LP’s optimal value is non-negative as
needed. ∎

######  Lemma 3.8.

The incidence matrix defined by (D2’) and (D3) is totally unimodular.

###### Proof.

The incidence matrix has $|\mathcal{U}_{v}|+1$ rows ($|\mathcal{U}_{v}|$
corresponding to (D2’) and one last row corresponding to (D3)) and
$|\mathcal{U}_{v}|+2|\Gamma(v)|$ columns. Furthermore, the columns
corresponding to $\alpha_{u}$’s are same as those corresponding to
$\beta_{u}$’s, except for the last row, where there are $0$’s in the
$\alpha$-columns and $1$’s in the $\beta$-columns.

To show that this matrix is totally unimodular we use Ghouila-Houri’s
characterization of total unimodularity (e.g. see [30, Thm. 19.3]):

######  Theorem 6 (Ghouila-Houri 1962).

A matrix is totally unimodular iff the following holds for _every_ subset
$\mathcal{R}$ of rows: we can assign weights $w_{r}\in\\{-1,+1\\}$ to each row
$r\in\mathcal{R}$ such that $\sum_{r\in\mathcal{R}}w_{r}r$ is a $\\{0,\pm
1\\}$-vector.

Note that we can safely ignore the columns corresponding to variables
$\lambda_{U}$ for sets $U\in\mathcal{U}_{v}$, since each of them contains a
single $1$ occurring in constraint (D2’) for set $U$.

The row subset $\mathcal{R}$ corresponds to a subset of $\mathcal{U}_{v}$ —
which we will denote $\mathcal{R}\cap\mathcal{U}_{v}$ — plus possibly the
single row corresponding to (D3). Each row in $\mathcal{R}\cap\mathcal{U}_{v}$
has its values determined by the characteristic vector of $U\cap\Gamma(v)$. So
long as any set appears more than once in $\\{U\cap\Gamma(v)\mid
U\in\mathcal{R}\cap\mathcal{U}_{v}\\}$ we can assign one copy weight $+1$ and
the other copy weight $-1$; these rows cancel out. Thus, henceforth we assume
$\\{U\cap\Gamma(v)\mid U\in\mathcal{R}\cap\mathcal{U}_{v}\\}$ has no duplicate
sets.

There is a standard representation of a laminar family as a forest of rooted
trees, where there is a node corresponding to each set, with containment in
the family corresponding to ancestry in the forest. Given the forest for the
laminar family $\\{U\cap\Gamma(v)\mid U\in\mathcal{R}\cap\mathcal{U}_{v}\\}$,
the assignment of weights to the rows of the matrix is as follows. Let the
root nodes of all trees be at height $0$ with height increasing as one goes to
children nodes. Give weight $-1$ to rows corresponding to nodes at even
height, and weight $+1$ to rows corresponding to nodes at odd height. If
$\mathcal{R}$ contains the row corresponding to (D3), give it weight $+1$.

Finally, let us argue that these weights have the needed property. Consider
first a column corresponding to $\alpha_{u}$ for any $u$. The rows of
$\mathcal{R}$ with $1$ in this column form a path, from the largest set
containing $u$ (which is a root node) to the smallest set containing $u$. The
weighted sum in this column is an alternating sum $-1+1-1+1\dotsb$, which is
either $-1$ or $0$, which is in $\\{0,\pm 1\\}$ as needed. Second, in a column
for some $\beta_{u}$, if $\mathcal{R}$ doesn’t contain (resp. contains) the
row corresponding to (D3), the weighted sum is the same as for $\alpha_{u}$
(resp. plus 1); in either case its weighted sum is in $\\{0,\pm 1\\}$ as
needed. ∎

This finishes the proof of Lemma 3.5, and hence also that of Theorem 5. ∎

##  4 Improved Integrality Gap Upper Bounds

We first show the improved bound of $73/60$ for uniformly quasibipartite
graphs. We then show the $(2\sqrt{2}-1)\doteq 1.828$ upper bound on general
graphs, which contains the main ideas, and then end by giving a
$\sqrt{3}\doteq 1.729$ upper bound.

###  4.1 Uniformly Quasibipartite Instances

Uniformly quasibipartite instances of the Steiner tree problem are
quasibipartite graphs where the cost of edges incident on a Steiner vertex are
the same. They were first studied by Gröpl et al. [20], who gave a $73/60$
factor approximation algorithm. In the following, we show that the cost of the
returned tree is no more than than
$\frac{73}{60}\mathop{\mathrm{OPT}}\eqref{eq:LP-PU}$, which upper-bounds the
integrality gap by $\frac{73}{60}$.

We start by describing the algorithm of Gröpl et al. [20] in terms of full
components. A collection $\mathcal{K}^{\prime}$ of full components is acyclic
if there is no list of $t>1$ distinct terminals and hyperedges in
$\mathcal{K}^{\prime}$ of the form $r_{1}\in K_{1}\ni r_{2}\in K_{2}\dotsb\ni
r_{t}\in K_{t}\ni r_{1}$ — i.e. there are no _hypercycles_.

Procedure RatioGreedy 1: Initialize the set of acyclic components
$\mathcal{L}$ to $\varnothing$.  2: Let $L^{*}$ be a minimizer of
$\frac{C_{L}}{|L|-1}$ over all full components $L$ such that $|L|\geq 2$ and
$L\cup\mathcal{L}$ is acyclic.  3: Add $L^{*}$ to $\mathcal{L}$.  4: Continue
until $(R,\mathcal{L})$ is a hyper-spanning tree and return $\mathcal{L}$.

######  Theorem 7.

On a uniformly quasibipartite instance RatioGreedy returns a Steiner tree of
cost at most $\frac{73}{60}\mathop{\mathrm{OPT}}\eqref{eq:LP-PU}$.

###### Proof.

Let $t$ denote the number of iterations and
$\mathcal{L}:=\\{L_{1},\ldots,L_{t}\\}$ be the ordered sequence of full
components obtained. We now define a dual solution to ($\mathcal{P}_{D}$). Let
$\pi(i)$ denote the partition induced by the connected components of
$\\{L_{1},\dotsc,L_{i}\\}$. Let $\theta(i)$ denote $C_{L_{i}}/(|L_{i}|-1)$ and
note that $\theta$ is nondecreasing. Define $\theta(0)=0$ for convenience. We
define a dual solution $y$ with

$y_{\pi(i)}=\theta(i+1)-\theta(i)$

for $0\leq i<t$, and all other coordinates of $y$ set to zero; $y$ is not
generally feasible, but we will scale it down to make it so. By evaluating a
telescoping sum, it is not hard to find that
$\sum_{i}y_{\pi(i)}(r(\pi(i))-1)=C(\mathcal{L})$. In the rest of the proof we
will show for any $K\in\mathcal{K}$,
$\sum_{i}y_{\pi(i)}\mathtt{rc}^{\pi(i)}_{K}\leq 73/60\cdot C_{K}$ — by
scaling, this also proves that $\frac{60}{73}y$ is a feasible dual solution,
and hence completes the proof.

Fix any $K\in\mathcal{K}$ and let $|K|=k$. Since the instance in question is
uniformly quasi-bipartite, the full component $K$ is a star with a Steiner
centre and edges of a fixed cost $c$ to each terminal in $K$. For $1\leq i<k$,
let $\tau(i)$ denote the last iteration $j$ in which
$\mathtt{rc}_{K}^{\pi(j)}\geq k-i$. Let $K_{i}$ denote any subset of $K$ of
size $k-i+1$ such that $K_{i}$ contains at most one element from each part of
$\pi(\tau(i))$; i.e., $|K_{i}|=k-i+1$ and
$\mathtt{rc}_{K_{i}}^{\pi(\tau(i))}=k-i$.

Our analysis hinges on the fact that $K_{i}$ was a valid choice for
$L_{\tau(i)+1}$. More specifically, note that
$\\{L_{1},\dotsc,L_{\tau(i)},K_{i}\\}$ is acyclic, hence by the greedy nature
of the algorithm, for any $1\leq i<k,$

$\theta(\tau(i)+1)=C_{L_{\tau(i)+1}}/(|L_{\tau(i)+1}|-1)\leq
C_{K_{i}}/(|K_{i}|-1)\leq\frac{c\cdot(k-i+1)}{k-i}.$

Moreover, using the definition of $\tau$ and telescoping we compute

$\sum_{\pi}y_{\pi}\mathtt{rc}_{K}^{\pi}=\sum_{i=0}^{t-1}(\theta(i+1)-\theta(i))\mathtt{rc}_{K}^{\pi(i)}=\sum_{i=1}^{k-1}\theta(\tau(i)+1)\leq\sum_{i=1}^{k-1}\frac{c\cdot(k-i+1)}{k-i}=c\cdot(k-1+H(k-1)),$

where $H(\cdot)$ denotes the harmonic series. Finally, note that
$(k-1+H(k-1))\leq\frac{73}{60}k$ for all $k\geq 2$ (achieved at $k=5$).
Therefore, $\frac{60}{73}y$ is a valid solution to ($\mathcal{P}_{D}$). ∎

###  4.2 General graphs

We start with a few definitions and notations in order to prove the
$2\sqrt{2}-1$ and $\sqrt{3}$ integrality gap bounds on ($\mathcal{P}$). Both
results use similar algorithms, and the latter is a more complex version of
the former. For conciseness we let a “graph” be a triple $G=(V,E,R)$ where
$R\subset V$ are $G$’s terminals. In the following, we let
${\mathtt{mtst}}(G;c)$ denote the minimum _terminal spanning tree_ , i.e. the
minimum spanning tree of the terminal-induced subgraph $G[R]$ under edge-costs
$c:E\to\mathbf{R}$. We will abuse notation and let ${\mathtt{mtst}}(G;c)$ mean
both the tree and its cost under $c$.

When contracting an edge $uv$ in a graph, the new merged node resulting from
contraction is defined to be a terminal iff at least one of $u$ or $v$ was a
terminal; this is natural since a Steiner tree in the new graph is a minimal
set of edges which, together with $uv$, connects all terminals in the old
graph. Our algorithm performs contraction, which may introduce parallel edges,
but one may delete all but the cheapest edge from each parallel class without
affecting the analysis.

Our first algorithm proceeds in stages. In each stage we apply the operation
$G\mapsto G/K$ which denotes contracting all edges in some full component $K$.
To describe and analyze the algorithm we introduce some notation. For a
minimum terminal spanning tree $T={\mathtt{mtst}}(G;c)$ define ${\tt
drop}_{T}(K;c):=c(T)-{\mathtt{mtst}}(G/K;c)$. We also define ${\tt
gain}_{T}(K;c):={\tt drop}_{T}(K)-c(K)$, where $c(K)$ is the cost of full
component $K$. A tree $T$ is called _gainless_ if for every full component $K$
we have ${\tt gain}_{T}(K;c)\leq 0$. The following useful fact is implicit in
[23] (see also Appendix B).

######  Theorem 8 (Implicit in [23]).

If ${\mathtt{mtst}}(G;c)$ is gainless, then
$\mathop{\mathrm{OPT}}\eqref{eq:LP-PU}$ equals the cost of
${\mathtt{mtst}}(G;c)$.

We now give the first algorithm and its analysis, which uses a reduced cost
trick introduced by Chakrabarty et al.[4].

Procedure Reduced One-Pass Heuristic 1: Define costs $c^{\prime}_{e}$ by
$c^{\prime}_{e}:=c_{e}/\sqrt{2}$ for all terminal-terminal edges $e$, and
$c^{\prime}_{e}=c_{e}$ for all other edges. Let $G_{1}:=G,$
$T_{i}:={\mathtt{mtst}}(G_{i};c^{\prime})$, and $i:=1$.  2: The algorithm
considers the full components in any order. When we examine a full component
$K$, if ${\tt gain}_{T_{i}}(K;c^{\prime})>0$, let $K_{i}:=K$,
$G_{i+1}:=G_{i}/K_{i}$, $T_{i+1}:={\mathtt{mtst}}(G_{i+1};c^{\prime})$, and
$i:=i+1$.  3: Let $f$ be the final value of $i$. Return the tree
$T_{alg}:=T_{f}\cup\bigcup_{i=1}^{f-1}K_{i}$.

Note that the full components are scanned in any order and they are not
examined a priori. Hence the algorithm works just as well if the full
components arrive “online,” which might be useful for some applications.

######  Theorem 9.

$c(T_{alg})\leq(2\sqrt{2}-1)\mathop{\mathrm{OPT}}\eqref{eq:LP-PU}$.

###### Proof.

First we claim that ${\tt gain}_{T_{f}}(K;c^{\prime})\leq 0$ for all $K$. To
see this there are two cases. If $K=K_{i}$ for some $i$, then we immediately
see that ${\tt drop}_{T_{j}}(K)=0$ for all $j>i$ so ${\tt
gain}_{T_{f}}(K)=-c(K)\leq 0$. Otherwise (if for all $i,$ $K\neq K_{i}$) $K$
had nonpositive gain when examined by the algorithm; and the well-known
_contraction lemma_ (e.g., see [19, §1.5]) immediately implies that ${\tt
gain}_{T_{i}}(K)$ is nonincreasing in $i$, so ${\tt gain}_{T_{f}}(K)\leq 0$.

By Theorem 8, $c^{\prime}(T_{f})$ equals the value of ($\mathcal{P}$) on the
graph $G_{f}$ with costs $c^{\prime}$. Since $c^{\prime}\leq c$, and since at
each step we only contract terminals, the value of this optimum must be at
most $\mathop{\mathrm{OPT}}\eqref{eq:LP-PU}$. Using the fact that
$c(T_{f})=\sqrt{2}c^{\prime}(T_{f})$, we get

$\displaystyle
c(T_{f})=\sqrt{2}c^{\prime}(T_{f})\leq\sqrt{2}\mathop{\mathrm{OPT}}\eqref{eq:LP-
PU}$ (22)

Furthermore, for every $i$ we have ${\tt gain}_{T_{i}}(K_{i};c^{\prime})>0$,
that is, ${\tt drop}_{T_{i}}(K_{i};c^{\prime})>c^{\prime}(K)=c(K)$. The
equality follows since $K$ contains no terminal-terminal edges. However, ${\tt
drop}_{T_{i}}(K_{i};c^{\prime})=\frac{1}{\sqrt{2}}{\tt drop}_{T_{i}}(K_{i};c)$
because all edges of $T_{i}$ are terminal-terminal. Thus, we get for every
$i=1$ to $f$, ${\tt drop}_{T_{i}}(K_{i};c)>\sqrt{2}\cdot c(K_{i})$.

Since ${\tt
drop}_{T_{i}}(K_{i};c):={\mathtt{mtst}}(G_{i};c)-{\mathtt{mtst}}(G_{i+1};c)$,
we have

$\sum_{i=1}^{f-1}{\tt drop}_{T_{i}}(K_{i};c)={\mathtt{mtst}}(G;c)-c(T_{f}).$

Thus, we have

$\sum_{i=1}^{f-1}c(K_{i})\leq\frac{1}{\sqrt{2}}\sum_{i=1}^{f}{\tt
drop}_{T_{i}}(K_{i};c)=\frac{1}{\sqrt{2}}({\mathtt{mtst}}(G;c)-c(T_{f}))\leq\frac{1}{\sqrt{2}}(2\mathop{\mathrm{OPT}}\eqref{eq:LP-
PU}-c(T_{f}))$

where we use the fact that ${\mathtt{mtst}}(G,c)$ is at most twice
$\mathop{\mathrm{OPT}}\eqref{eq:LP-PU}$777This follows using standard
arguments, and can be seen, for instance, by applying Theorem 8 to the cost-
function with all terminal-terminal costs divided by 2, and using short-
cutting.. Therefore

$c(T_{alg})=c(T_{f})+\sum_{i=1}^{f-1}c(K_{i})\leq\Bigl{(}1-\frac{1}{\sqrt{2}}\Bigr{)}c(T_{f})+\sqrt{2}\mathop{\mathrm{OPT}}\eqref{eq:LP-
PU}.$

Finally, using $c(T_{f})\leq\sqrt{2}\mathop{\mathrm{OPT}}\eqref{eq:LP-PU}$
from (22), the proof of Theorem 9 is complete. ∎

####  4.2.1 Improving to $\sqrt{3}$

To get the improved factor of $\sqrt{3}$, we use a more refined iterated
contraction approach. The crucial new concept is that of the loss of a full
component, introduced by Karpinski and Zelikovsky [22]. The intuition is as
follows. In each iteration, the $(2\sqrt{2}-1)$-factor algorithm contracts a
full component $K$, and thus commits to include $K$ in the final solution; the
new algorithm makes a smaller commitment, by contracting a _subset_ of $K$’s
edges, which allows for a possibility of better recovery later.

Given a full component $K$ (viewed as a tree with leaf set $K$ and internal
Steiner nodes), ${\tt loss}(K)$ is defined to be the minimum-cost subset of
$E(K)$ such that $(V(K),{\tt loss}(K))$ has at least one terminal per
connected component — i.e. the cheapest way in $K$ to connect each Steiner
node to the terminal set. We also use ${\tt loss}(K)$ to denote the total
_cost_ of these edges. Note that no two terminals are connected by ${\tt
loss}(K)$. A very useful theorem of Karpinski and Zelikovsky [22] is that for
any full component $K$, ${\tt loss}(K)\leq c(K)/2$.

Now we have the ingredients to give our new algorithm. In the description
below, $\alpha>1$ is a parameter (which will be set to $\sqrt{3}$). In each
iteration, the algorithm contracts the loss of a single full component $K$ (we
note it follows that the terminal set has constant size over all iterations).

Procedure Reduced One-Pass Loss-Contracting Heuristic 1: Initially $G_{1}:=G$,
$T_{1}:={\mathtt{mtst}}(G;c)$, and $i:=1$.  2: The algorithm considers the
full components in any order. When we examine a full component $K$, if  ${\tt
gain}_{T_{i}}(K;c)>(\alpha-1){\tt loss}(K),$ let $K_{i}:=K$,
$G_{i+1}:=G_{i}/{\tt loss}(K_{i})$, $T_{i+1}:={\mathtt{mtst}}(G_{i+1};c)$, and
$i:=i+1$.  3: Let $f$ be the final value of $i$. Return the tree
$T_{alg}:=T_{f}\cup\bigcup_{i=1}^{f-1}{\tt loss}(K_{i}).$

We now analyze the algorithm.

######  Claim 4.1.

$c(T_{f})\leq(\frac{1+\alpha}{2})\mathop{\mathrm{OPT}}\eqref{eq:LP-PU}$.

###### Proof.

Using the contraction lemma again, ${\tt gain}_{T_{f}}(K;c)\leq(\alpha-1){\tt
loss}(K)$ for all $K$, so

$\displaystyle{\tt drop}_{T_{f}}(K;c)\leq c(K)+(\alpha-1){\tt
loss}(K)=c(K)+(\alpha-1){\tt loss}(K)\leq\Big{(}\frac{1+\alpha}{2}\Big{)}c(K)$
(23)

since ${\tt loss}(K)\leq c(K)/2$.

To finish the proof of Claim 4.1, we proceed as in the proof of Equation (22).
Define $c^{\prime}_{e}:=c_{e}/(\frac{1+\alpha}{2})$ for all edges $e$ which
join two vertices of the original terminal set $R$, and $c^{\prime}_{e}=c_{e}$
for all other edges. Note that (23) implies that $T_{f}$ is gainless with
respect to $c^{\prime}$. Thus, by Theorem 8, the value of LP ($\mathcal{P}$)
on $(G_{f},c^{\prime})$ equals $c^{\prime}(T_{f})$. Since we only reduce costs
(as $\alpha\geq 1$), this optimum is no more than the original
$\mathop{\mathrm{OPT}}\eqref{eq:LP-PU}$ giving us
$c^{\prime}(T_{f})\leq\mathop{\mathrm{OPT}}\eqref{eq:LP-PU}$. Now using the
definition of $c^{\prime}$, the proof of the claim is complete. ∎

######  Claim 4.2.

For any $i\geq 1$, we have $c(T_{i})-c(T_{i+1})\geq{\tt
gain}_{T_{i}}(K_{i};c)+{\tt loss}(K_{i})$.

###### Proof.

Recall that $T_{i+1}$ is a minimum terminal spanning tree of $G_{i+1}$ under
$c$. Consider the following other terminal spanning tree $T$ of $G_{i+1}$:
take $T$ to be the union of $K_{i}/{\tt loss}(K_{i})$ with
${\mathtt{mtst}}(G_{i}/K_{i};c)$. Hence $c(T_{i+1})\leq
c(T)={\mathtt{mtst}}(G_{i}/K_{i};c)+c(K_{i})-{\tt loss}(K_{i})$. Rearranging,
and using the definition of gain, we obtain:

$c(T_{i})-c(T_{i+1})\geq c(T_{i})-{\mathtt{mtst}}(G_{i}/K_{i};c)-c(K_{i})+{\tt
loss}(K_{i})={\tt gain}_{T_{i}}(K_{i};c)+{\tt loss}(K_{i}),$

and this completes the proof. ∎

Now we are ready to prove the integrality gap upper bound of $\sqrt{3}$.

######  Theorem 10.

$c(T_{alg})\leq\sqrt{3}\mathop{\mathrm{OPT}}\eqref{eq:LP-PU}$.

###### Proof.

By the algorithm, we have for all $i$ that ${\tt
gain}_{T_{i}}(K_{i})\geq(\alpha-1){\tt loss}(K_{i})$, and thus ${\tt
gain}_{T_{i}}(K_{i};c)+{\tt loss}(K_{i})\geq\alpha{\tt loss}(K_{i})$. Thus,
from Claim 4.2, we get

$\sum_{i=1}^{f-1}{\tt
loss}(K_{i})\leq\frac{1}{\alpha}\sum_{i=1}^{f-1}\Big{(}c(T_{i})-c(T_{i+1})\Big{)}$

The right-hand sum telescopes to give us
$c(T_{1})-c(T_{f})={\mathtt{mtst}}(G;c)-c(T_{f})$. Thus,

$\displaystyle c(T_{alg})$ $\displaystyle=c(T_{f})+\sum_{i=1}^{f-1}{\tt
loss}(K_{i})\leq
c(T_{f})+\frac{1}{\alpha}({\mathtt{mtst}}(G;c)-c(T_{f}))=\frac{1}{\alpha}{\mathtt{mtst}}(G;c)+\frac{\alpha-1}{\alpha}c(T_{f})$
$\displaystyle\leq\Big{(}\frac{2}{\alpha}+\frac{(\alpha-1)(1+\alpha)}{2\alpha}\Big{)}\mathop{\mathrm{OPT}}\eqref{eq:LP-
PU}=\Big{(}\frac{\alpha^{2}+3}{2\alpha}\Big{)}\mathop{\mathrm{OPT}}\eqref{eq:LP-
PU}$

which follows from ${\mathtt{mtst}}(G;c)\leq
2\mathop{\mathrm{OPT}}\eqref{eq:LP-PU}$ and Claim 4.1. Setting
$\alpha=\sqrt{3}$, the proof of the theorem is complete. ∎

##  5 Conclusion

In this paper we looked at several hypergraphic LP relaxations for the Steiner
tree problem, and showed they all have the same objective value. Furthermore,
we noted some connections to the bidirected cut relaxation for Steiner trees:
although hypergraphic relaxations are stronger than the bidirected cut
relaxation in general, in quasibipartite graphs all these relaxations are
equivalent. We obtained structural results about the hypergraphic relaxations
showing that basic feasible solutions have sparse support. We also showed
improved upper bounds on the integrality gaps on the hypergraphic relaxations
via simple algorithms.

Reiterating the comments in Section 1.2.3, the hypergraphic LPs are powerful
(e.g. as evidenced by Byrka et al. [3]) but may not be manageable for
computational implementation. Some interesting areas for future work include:
non-ellipsoid-based algorithms to solve the hypergraphic LPs in the
$r$-restricted setting; resolving the complexity of optimizing them in the
unrestricted setting; and directly using the bidirected cut relaxation to
achieve good results (e.g. in quasi-bipartite instances).

## References

  * [1] Y. P. Aneja.  An integer linear programming approach to the Steiner problem in graphs.  Networks, 10:167–178, 1980.
  * [2] A. Borchers and D. Du.  The $k$-Steiner ratio in graphs.  SIAM J. Comput., 26(3):857–869, 1997.
  * [3] J. Byrka, F. Grandoni, T. Rothvoß, and L. Sanità.  An improved LP-based approximation for Steiner tree.  To appear in Proc. 42nd STOC, 2010.
  * [4] D. Chakrabarty, N. R. Devanur, and V. V. Vazirani.  New geometry-inspired relaxations and algorithms for the metric Steiner tree problem.  In IPCO, pages 344–358, 2008.
  * [5] M. Chlebík and J. Chlebíková.  Approximation hardness of the Steiner tree problem on graphs.  In Proceedings, Scandinavian Workshop on Algorithm Theory, pages 170–179, 2002.
  * [6] S. Chopra.  On the spanning tree polyhedron.  Operations Research Letters, 8:25–29, 1989.
  * [7] S. Chopra and M. R. Rao.  The Steiner tree problem 1: Formulations, compositions, and extension of facets.  Mathematical Programming, 64:209–229, 1994.
  * [8] S. Chopra and M. R. Rao.  The Steiner tree problem 2: Properties and classes of facets.  Mathematical Programming, 64:231–246, 1994.
  * [9] G. Cornuéjols, D. Naddef, and J. Fonlupt.  The traveling salesman problem on a graph and some related integer polyhedra.  Math. Programming, 33:1–27, 1985.
  * [10] M. Didi Biha, H. Kerivin, and A. R. Mahjoub.  Steiner trees and polyhedra.  Discrete Applied Mathematics, 112(1-3):101–120, 2001.
  * [11] J. Edmonds.  Optimum branchings.  Journal of Research of the National Bureau of Standards B, 71B:233–240, 1967.
  * [12] J. Edmonds.  Matroids and the greedy algorithm.  Math. Programming, 1:127–136, 1971.
  * [13] J. Edmonds and R. Giles.  A min-max relation for submodular functions on graphs.  Annals of Discrete Mathematics, 1:185–204, 1977.
  * [14] A. Frank, T. Király, and Z. Király.  On the orientation of graphs and hypergraphs.  Discrete Appl. Math., 131(2):385–400, 2003.
  * [15] D. R. Fulkerson.  Blocking and anti-blocking pairs of polyhedra.  Math. Programming, 1:168–194, 1971.
  * [16] D. Gijswijt and G. Pap.  An algorithm for weighted fractional matroid matching.  arXiv:0806.1818, 2008.
  * [17] M. X. Goemans.  The Steiner tree polytope and related polyhedra.  Math. Program., 63(2):157–182, 1994.
  * [18] M. X. Goemans and Y. Myung.  A catalog of Steiner tree formulations.  Networks, 23:19–28, 1993.
  * [19] C. Gröpl, S. Hougardy, T. Nierhoff, and H. J. Prömel.  Approximation algorithms for the Steiner tree problem in graphs.  In X. Cheng and D. Du, editors, Steiner trees in industries, pages 235–279. Kluwer Academic Publishers, Norvell, Massachusetts, 2001.
  * [20] C. Gröpl, S. Hougardy, T. Nierhoff, and H. J. Prömel.  Steiner trees in uniformly quasi-bipartite graphs.  Inform. Process. Lett., 83(4):195–200, 2002.  Preliminary version appeared as a Technical Report at TU Berlin, 2001\.
  * [21] K. Jain.  A factor 2 approximation algorithm for the generalized Steiner network problem.  Combinatorica, 21(1):39–60, 2001.  Preliminary version appeared in _Proc. 39th FOCS_ , pages 448–457, 1998.
  * [22] M. Karpinski and A. Zelikovsky.  New approximation algorithms for the Steiner tree problems.  J. Combinatorial Optimization, 1(1):47–65, 1997.
  * [23] J. Könemann, D. Pritchard, and K. Tan.  A partition-based relaxation for Steiner trees.  Math. Programming, 2009.  [In press].
  * [24] T. Polzin.  Algorithms for the Steiner Problem in Networks.  PhD thesis, Universität des Saarlandes, February 2003.
  * [25] T. Polzin and S. Vahdati Daneshmand.  A comparison of Steiner tree relaxations.  Discrete Applied Mathematics, 112(1-3):241–261, 2001.  Preliminary version appeared at COS 1998.
  * [26] T. Polzin and S. Vahdati Daneshmand.  On Steiner trees and minimum spanning trees in hypergraphs.  Oper. Res. Lett., 31(1):12–20, 2003.
  * [27] D. Pritchard.  Linear Programming Tools & Approximation Algorithms for Combinatorial Optimization.  PhD thesis, University of Waterloo, 2009.
  * [28] S. Rajagopalan and V. V. Vazirani.  On the bidirected cut relaxation for the metric Steiner tree problem.  In Proceedings, ACM-SIAM Symposium on Discrete Algorithms, pages 742–751, 1999.
  * [29] G. Robins and A. Zelikovsky.  Tighter bounds for graph Steiner tree approximation.  SIAM J. Discrete Math., 19(1):122–134, 2005.  Preliminary version appeared as “Improved Steiner tree approximation in graphs” at SODA 2000.
  * [30] A. Schrijver.  Theory of Linear and Integer Programming.  Wiley, Chichester, 1986.
  * [31] M. Singh and L. C. Lau.  Approximating minimum bounded degree spanning trees to within one of optimal.  In Proc. 39th STOC, pages 661–670, 2007.
  * [32] R. P. Stanley.  Enumerative Combinatorics, volume 1.  Wadsworth & Brooks/Cole, 1986.
  * [33] J. H. V. Vate.  Fractional matroid matchings.  J. Comb. Theory, Ser. B, 55(1):133–145, 1992.
  * [34] V. Vazirani.  Recent results on approximating the Steiner tree problem and its generalizations.  Theoret. Comput. Sci., 235(1):205–216, 2000.
  * [35] D. Warme.  Spanning Trees in Hypergraphs with Applications to Steiner Trees.  PhD thesis, University of Virginia, 1998.
  * [36] R. T. Wong.  A dual ascent approach for Steiner tree problems on a directed graph.  Math. Programming, 28:271–287, 1984.

##  Appendix A Directed Hypergraph LP Relaxation

######  Theorem 11.

For any Steiner tree instance, $\mathop{\mathrm{OPT}}\eqref{eq:LP-
PU}=\mathop{\mathrm{OPT}}\eqref{eq:LP-PUDir}$.

###### Proof.

First, we show $\mathop{\mathrm{OPT}}\eqref{eq:LP-
PU}\leq\mathop{\mathrm{OPT}}\eqref{eq:LP-PUDir}$. Consider a feasible solution
$x$ to $\eqref{eq:LP-PUDir}$, and define a solution $x^{\prime}$ to
$\eqref{eq:LP-PU}$ by $x^{\prime}_{K}=\sum_{i\in K}x_{K^{i}}$; informally,
$x^{\prime}$ is obtained from $x$ by ignoring the orientation of the
hyperedges. Clearly $x^{\prime}$ and $x$ have the same objective value.
Further, $x^{\prime}$ is feasible for $\eqref{eq:LP-PU}$; to see this, for any
partition $\pi$, note that (5) is implied by the sum of constraints (3) over
$U$ set to those parts of $\pi$ not containing the root — any orientation of a
full component with rank contribution $t$ must leave at least $t$ parts.

To obtain the reverse direction $\mathop{\mathrm{OPT}}\eqref{eq:LP-
PUDir}\leq\mathop{\mathrm{OPT}}\eqref{eq:LP-PU}$, we use a similar strategy.
We require some notation and a hypergraph orientation theorem of Frank et al.
[14]. For any $U\subset R$ we say that a directed hyperedge _$K^{i}$ lies in
$\Delta^{\mbox{\scriptsize{$\mathrm{in}$}}}(U)$_ if $i\in U$ and $K\backslash
U\neq\varnothing$, i.e. if
$K^{i}\in\Delta^{\mbox{\scriptsize{$\mathrm{out}$}}}(R\backslash U)$. Two
subsets $U$ and $W$ of $R$ are called _crossing_ if all four sets $U\setminus
W$, $W\setminus U$, $U\cap W$, and $R\setminus(U\cup W)$ are non-empty. A set-
function $p:2^{R}\to{\mathbb{Z}}$ is a _crossing supermodular_ function if

$p(U)+p(W)\leq p(U\cap W)+p(U\cup W)$

for all crossing sets $U$ and $W$. A directed hypergraph is said to _cover_
$p$ if $|\Delta^{\mbox{\scriptsize{$\mathrm{in}$}}}(U)|\geq p(U)$ for all
$U\subset R$. Here is the needed result.

######  Theorem 12 (Frank, Király & Király [14]).

Given a hypergraph $H=(R,\mathcal{X})$, and a crossing supermodular function
$p$, the hypergraph has an orientation covering $p$ if and only if for every
partition $\pi$ of $R$,
_(a)_
$\sum_{K\in\mathcal{X}}\min\\{1,\mathtt{rc}^{\pi}_{K}\\}\geq\sum_{\pi_{i}\in\pi}p(\pi_{i})$,
and, _(b)_
$\sum_{K\in\mathcal{X}}\mathtt{rc}^{\pi}_{K}\geq\sum_{\pi_{i}\in\pi}p(R\setminus\pi_{i})$.

We will show every rational solution $x$ to $\eqref{eq:LP-PU}$ can be
fractionally oriented to get a feasible solution for $\eqref{eq:LP-PUDir}$,
which will complete the proof of Theorem 11. Let $M$ be the smallest integer
such that the vector $Mx$ is integral. Let $\mathcal{X}$ be a multi-set of
hyperedges which contains $Mx_{K}$ copies of each $K$. Define the function $p$
by $p(U)=M$ if $r\in U\neq R$, and $p(U)=0$ otherwise; i.e. $p(U)=M$ iff
$R\backslash U$ is valid.

######  Claim A.1.

$H=(R,\mathcal{X})$ satisfies conditions (a) and (b).

###### Proof.

Note $\sum_{\pi_{i}\in\pi}p(R\setminus\pi_{i})=M(r(\pi)-1)$ since all parts of
$\pi$ are valid except the part containing the root $r$. Thus condition (b),
upon scaling by $\frac{1}{M}$, is a restatement of constraint (5), which holds
since $x$ is feasible for ($\mathcal{P}$).

For this $p$, condition (a) follows from (b) in the following sense. Fix a
partition $\pi$, and let $\pi_{1}$ be the part of $\pi$ containing $r$. If
$\pi_{1}=R$ then (a) is vacuously true, so assume $\pi_{1}\neq R$. Let
$\sigma$ be the rank-2 partition $\\{\pi_{1},R\setminus\pi_{1}\\}$. Then it is
easy to check that
$\min\\{1,\mathtt{rc}^{\pi}_{K}\\}\geq\mathtt{rc}^{\sigma}_{K}$ for all $K$,
and consequently
$\sum_{K\in\mathcal{X}}\min\\{1,\mathtt{rc}^{\pi}_{K}\\}\geq\sum_{K\in\mathcal{X}}\mathtt{rc}^{\sigma}_{K}$
and
$\sum_{\pi_{i}\in\sigma}p(R\setminus\pi_{i})=M=\sum_{\pi_{i}\in\pi}p(\pi_{i})$.
Thus, (a) for $\pi$ follows from (b) for $\sigma$. ∎

It is not hard to check that $p$ is crossing supermodular. Now using Theorem
12, take an orientation of $\mathcal{X}$ that covers $p$.

For each $K\in\mathcal{K}$ and each $i\in K$, let $n_{K^{i}}$ denote the
number of the $Mx_{K}$ copies of $K$ that are oriented as $K^{i}$, i.e.
directed towards $i$. So, $\sum_{i\in K}n_{K^{i}}=Mx_{K}$. Let
$x^{\prime}_{K^{i}}:=\frac{n_{K^{i}}}{M}$ for all $K^{i}$. Hence
$\sum_{i}x^{\prime}_{K^{i}}=x_{K}$ and $x^{\prime}$ has the same objective
value as $x$.

To complete the proof, we show $x^{\prime}$ is feasible for ($\mathcal{D}$).
Fix a valid subset $U$ and consider condition (3) for a valid set $U$. Note
that $p(R\backslash U)=M$. Therefore, since the orientation covers $p$, we get

$\sum_{K^{i}\in\Delta^{\mbox{\scriptsize{$\mathrm{out}$}}}(U)}x^{\prime}_{K^{i}}=\frac{1}{M}\sum_{K^{i}\in\Delta^{\mbox{\scriptsize{$\mathrm{out}$}}}(U)}n_{K^{i}}=\frac{1}{M}\sum_{K^{i}\in\Delta^{\mbox{\scriptsize{$\mathrm{in}$}}}(R\backslash
U)}n_{K^{i}}\geq\frac{1}{M}p(R\backslash U)=\frac{1}{M}M=1$

as needed. ∎

##  Appendix B Gainless MSTs and Hypergraphic Relaxations

######  Theorem 8 (Implicit in [23]).

If the MST induced by the terminals is gainless, then
$\mathop{\mathrm{OPT}}\eqref{eq:LP-PU}$ equals the cost of that MST.

###### Proof.

Let $\Pi$ be the set of all partitions of the terminal set. As before, we let
$r(\pi)$ be the rank of a partition $\pi\in\Pi$, and we use $E_{\pi}$ for the
set of edges in our graph that cross the partition; i.e., $E_{\pi}$ contains
all edges whose endpoints lie in different parts of $\pi$. Fulkerson’s [15]
formulation of the spanning tree polyhedron and its dual are as follows.

$\displaystyle\min\Big{\\{}\sum_{e\in E}c_{e}x_{e}:\quad$ $\displaystyle
x\in\mathbf{R}^{E}_{\geq 0}$ ($\mathcal{M}$) $\displaystyle\sum_{e\in
E_{\pi}}x_{e}\geq r(\pi)-1\quad$ $\displaystyle\forall\pi\in\Pi\Big{\\}}$ (24)

$\displaystyle\max\Big{\\{}\sum_{\pi}(r(\pi)-1)\cdot y_{\pi}:\quad$
$\displaystyle y\in\mathbf{R}^{\Pi}_{\geq 0}$ ($\mathcal{M}_{D}$)
$\displaystyle\sum_{\pi:e\in E_{\pi}}y_{\pi}\leq c_{e},\quad$
$\displaystyle\forall e\in E\Big{\\}}$ (25)

The high-level overview of the proof is as follows. We first give a brief
sketch of a folklore primal-dual interpretation of Kruskal’s minimum-spanning
tree algorithm with respect to Fulkerson’s LP (for more information see, e.g.,
[23]). Running Kruskal’s algorithm on the terminal set then returns a minimum
spanning tree $T$ and a feasible dual $y$ to Equation ($\mathcal{M}_{D}$) such
that

$c(T)=\sum_{\pi}(r(\pi)-1)y_{\pi}.$

The final step will be to show that, if the returned MST is gainless, then the
spanning tree dual $y$ is feasible for ($\mathcal{P}_{D}$), and its value is
$c(T)$ as well. Weak duality and the fact that the optimal value of
($\mathcal{P}$) is at most $c(T)$ imply the theorem.

Kruskal’s algorithm can be viewed as a process over time. For each time
$\tau\geq 0$, the algorithm keeps a forest $T^{\tau}$, and a feasible dual
solution $y^{\tau}$; initially $T^{0}=(V,\varnothing)$ and $y^{0}=0$. Let
$\pi^{\tau}$ be the partition induced by the connected components of
$T^{\tau}$. If $T^{\tau}$ is not a spanning tree, Kruskal’s algorithm grows
the dual variable $y_{\pi^{\tau}}$ corresponding to the current partition
until constraint Equation ($\mathcal{M}_{D}$)e: for some edge $e$ prevents any
further increase. The algorithm then adds $e$ to the partial tree and
continues. The algorithm stops at the first time $\tau^{*}$ where
$T^{\tau^{*}}$ is a spanning tree.

Let $T$ be the gainless spanning tree returned by Kruskal, and let $y$ be the
corresponding dual. We claim that $y$ is feasible for ($\mathcal{P}_{D}$). To
see this, consider a full component $K$. Clearly, the rank contribution
$\mathtt{rc}^{\pi^{0}}_{K}$ of $K$ to the initial partition $\pi^{0}$ is
$|K|-1$; similarly, the final rank contribution
$\mathtt{rc}^{\pi^{\tau^{*}}}_{K}$ is $0$. Every edge that is added during the
algorithm’s run either leaves the rank contribution of $K$ unchanged, or it
decreases it by $1$. Let $e_{1},\ldots,e_{|K|-1}$ be the edges of the final
tree $T$ whose addition to $T$ decreases $K$’s rank contribution. Also let

$0\leq\tau_{1}\leq\tau_{2}\leq\ldots\leq\tau_{|K|-1}\leq\tau^{*}$

be the times where these edges are added. Note that, by definition, we must
have $c_{e_{i}}=\tau_{i}$ for all $i$. We therefore have

$\sum_{i=1}^{|K|-1}c_{e_{i}}=\sum_{i=1}^{|K|-1}\tau_{i}.$ (26)

The right-hand side of this equality is easily checked to be equal to

$\int_{0}^{\tau^{*}}\mathtt{rc}^{\pi^{\tau}}_{K}d\tau,$

which in turn is equal to $\sum_{\pi}\mathtt{rc}^{\pi}_{K}y_{\pi}$, by the
definition of Kruskal’s algorithm. It is not hard to see that the left-hand
side of (26) is the drop ${\tt drop}_{T}(K)$ induced by $K$. Together with the
fact that $T$ is gainless, we obtain

$c_{K}\geq{\tt drop}_{T}(K)=\sum_{\pi}\mathtt{rc}^{\pi}_{K}y_{\pi}.$

Now observe that the right-hand side of this equation is the left-hand side of
(6). It follows that $y$ is feasible for ($\mathcal{P}_{D}$). ∎