Approximating Min-Cost Chain-Constrained Spanning Trees: A
Reduction from Weighted to Unweighted Problems∗

arXiv:1605.03203v1 [] 10 May 2016

André Linhares†

Chaitanya Swamy†

Abstract
We study the min-cost chain-constrained spanning-tree (abbreviated MCCST) problem: find a mincost spanning tree in a graph subject to degree constraints on a nested family of node sets. We devise
the first polytime algorithm that finds a spanning tree that (i) violates the degree constraints by at most
a constant factor and (ii) whose cost is within a constant factor of the optimum. Previously, only an
algorithm for unweighted CCST was known [14], which satisfied (i) but did not yield any cost bounds.
This also yields the first result that obtains an O(1)-factor for both the cost approximation and violation
of degree constraints for any spanning-tree problem with general degree bounds on node sets, where an
edge participates in a super-constant number of degree constraints.
A notable feature of our algorithm is that we reduce MCCST to unweighted CCST (and then utilize [14]) via a novel application of Lagrangian duality to simplify the cost structure of the underlying
problem and obtain a decomposition into certain uniform-cost subproblems.
We show that this Lagrangian-relaxation based idea is in fact applicable more generally and, for any
cost-minimization problem with packing side-constraints, yields a reduction from the weighted to the
unweighted problem. We believe that this reduction is of independent interest. As another application
of our technique, we consider the k-budgeted matroid basis problem, where we build upon a recent
1.5
rounding algorithm of [4] to obtain an improved nO(k /ǫ) -time algorithm that returns a solution that
satisfies (any) one of the budget constraints exactly and incurs a (1 + ǫ)-violation of the other budget
constraints.

1 Introduction
Constrained spanning-tree problems, where one seeks a minimum-cost spanning tree satisfying additional
({0, 1}-coefficient) packing constraints, constitute an important and widely-studied class of problems. In
particular, when the packing constraints correspond to node-degree bounds, we obtain the classical mincost bounded-degree spanning tree (MBDST) problem, which has a rich history of study [7, 11, 12, 5, 8, 16]
culminating in the work of [16] that yielded an optimal result for MBDST. Such degree-constrained networkdesign problems arise in diverse areas including VLSI design, vehicle routing and communication networks
(see, e.g., the references in [15]), and their study has led to the development of powerful techniques in
approximation algorithms.
Whereas the iterative rounding and relaxation technique introduced in [16] (which extends the iterativerounding framework of [10]) yields a versatile technique for handling node-degree constraints (even for
more-general network-design problems), we have a rather limited understanding of spanning-tree problems
with more-general degree constraints, such as constraints |T ∩ δ(S)| ≤ bS for sets S in some (structured)
∗

A preliminary version [13] will appear in the Proceedings of the 18th IPCO, 2016.
{alinhare,cswamy}@uwaterloo.ca. Dept. of Combinatorics and Optimization, University of Waterloo, Waterloo,
ON N2L 3G1. Research supported partially by the second author’s NSERC grant 327620-09, NSERC Discovery Accelerator
Supplement Award, and Ontario Early Researcher Award.
†

1

family S of node sets.1 A fundamental impediment here is our inability to leverage the techniques in [8, 16].
The few known results yield: (a) (sub-) optimal cost, but a super-constant additive- or multiplicative- factor
violation of the degree bounds [3, 1, 6, 2]; or (b) a multiplicative O(1)-factor violation of the degree bounds
(when S is a nested family), but no cost guarantee [14]. In particular, in stark contrast to the results known
for node-degree-bounded network-design problems, there is no known algorithm that yields an O(1)-factor
cost approximation and an (additive or multiplicative) O(1)-factor violation of the degree bounds. (Such
guarantees are only known when each edge participates in O(1) degree constraints [2]; see however [17] for
an exception.)
We consider the min-cost chain-constrained spanning-tree (MCCST) problem introduced by [14], which
is perhaps the most-basic setting involving general degree bounds where there is a significant gap in our
understanding vis-a-vis node-degree bounded problems. In MCCST, we are given an undirected connected
graph G = (V, E), nonnegative edge costs {ce }, a nested family S (or chain) of node sets S1 ( S2 ( · · · (
Sℓ ( V , and integer degree bounds {bS }S∈S . The goal is to find a minimum-cost spanning tree T such
that |δT (S)| ≤ bS for all S ∈ S, where δT (S) := T ∩ δ(S). Olver and Zenklusen [14] give an algorithm
for unweighted CCST that returns a tree T such that |δT (S)| = O(bS ) (i.e., there is no bound on c(T )),
and show that, for some ρ > 0, it is NP-complete to obtain an additive ρ · logloglog|V|V| | violation of the degree
bounds. We therefore focus on bicriteria (α, β)-guarantees for MCCST, where the tree T returned satisfies
c(T ) ≤ α · OPT and |δT (S)| ≤ β · bS for all S ∈ S.

Our contributions. Our main result is the first O(1), O(1) -approximation algorithm for MCCST. Given
λ
·OPT and |δT (S)| ≤ 9λ·bS for all S ∈ S, using
any λ > 1, our algorithm returns a tree T with c(T ) ≤ λ−1
the algorithm of [14] for unweighted CCST, denoted AOZ , as a black box (Theorem 3.3). As noted above,
this is also the first algorithm that achieves an O(1), O(1) -approximation for any spanning-tree problem
with general degree constraints where an edge belongs to a super-constant number of degree constraints.
We show in Section 4 that our techniques are applicable more generally. We give a reduction showing that for any cost-minimization problem with packing side-constraints, if we have an algorithm for the
unweighted problem that returns a solution with an O(1)-factor violation of the packing constraints and
satisfies a certain property, then one can utilize it to obtain an O(1), O(1) -approximation for the costminimization problem. Furthermore, we show that if the algorithm
for the unweighted counterpart satisfies

a stronger property, then we can utilize it to obtain a 1, O(1) -approximation (Theorem 5.1).
We believe that our reductions are of independent interest and will be useful in other settings as well.
Demonstrating this, we show an application to the k-budgeted matroid basis problem, wherein we seek to
2
find a basis satisfying k budget constraints. Grandoni et al. [9] devised an nO(k /ǫ) -time algorithm that
returned a (1, 1 + ǫ, . . . , 1 + ǫ)-solution: i.e., the solution satisfies (any) one budget constraint exactly and
violates the other budget constraints by a (1+ǫ)-factor (if the problem is feasible). Very recently, Bansal and
1.5
Nagarajan [4] improved the running time to nO(k /ǫ) but return only a (1+ǫ, . . . , 1+ǫ)-solution. Applying
our reduction (to the algorithm in [4]), we obtain the best of both worlds: we return a (1, 1 + ǫ, . . . , 1 + ǫ)1.5
solution in nO(k /ǫ) -time (Theorem 5.7).
The chief novelty in our algorithm and analysis, and the key underlying idea, is an unorthodox use of
Lagrangian duality. Whereas typically Lagrangian relaxation is used to drop complicating constraints and
thereby simplify the constraint structure of the underlying problem, in contrast, we use Lagrangian duality
to simplify the cost structure of the underlying problem by equalizing edge costs in certain subproblems. To
elaborate (see Section 3.1), the algorithm in [14] for unweighted CCST can be viewed as taking a solution x
to the natural linear-programming (LP) relaxation for MCCST, converting it to another feasible solution x′
satisfying a certain structural property, and exploiting this property to round x′ to a spanning tree. The main
1

Such general degree constraints arise in the context of finding thin trees [1], where S consists of all node sets, which turn out
to be a very useful tool in devising approximation algorithms for asymmetric TSP.

2

bottleneck here in handling costs (as also noted in [14]) is that c⊺ x′ could be much larger than c⊺ x since the
conversion ignores the ce s and works with an alternate “potential” function.
∗
Our crucial insight is that we can exploit Lagrangian duality to obtain perturbed edge costs {cye }
such that the change in perturbed cost due to the conversion process is ∗bounded.
Loosely speaking, if
y
y∗
the conversion process shifts weight from xf to xe , then we ensure that ce = cf (see Lemma 3.5); thus,
∗
∗
(cy )⊺ x = (cy )⊺ x′ ! The perturbation also ensures that applying AOZ to x′ yields a tree whose perturbed cost
∗
∗
∗
is equal to (cy )⊺ x′ = (cy )⊺ x. Finally, we show that for an optimal LP solution x∗ , the “error” (cy − c)⊺ x∗
∗
incurred in working with the cy -cost is O(OPT ); this yields the O(1), O(1) -approximation.
We extend the above idea to an arbitrary cost-minimization problem with packing side-constraints as
follows. Let x∗ be an optimal solution to the LP-relaxation, and P be the polytope obtained by dropping the
packing constraints. We observe that the same Lagrangian-duality based perturbation ensures that all points
on the minimal face of P containing x∗ have the same perturbed cost. Therefore, if we have an algorithm
for the unweighted problem that rounds x∗ to a point x̂ on this minimal face, then we again obtain that
∗
∗
(cy )⊺ x̂ = (cy )⊺ x∗ , which then leads to an O(1), O(1) -approximation (as in the case of MCCST).
Related work. Whereas node-degree-bounded spanning-tree problems have been widely studied, relatively few results are known for spanning-tree problems with general degree constraints for a family S of
node-sets. With the exception of the result of [14] for unweighted CCST, these other results [3, 1, 6, 2]
all yield a tree of cost at most the optimum with an ω(1) additive- or multiplicative- factor violation of the
degree bounds. Both [3] and [2] obtain additive factors via iterative rounding and relaxation. The factor
in [3] is (r − 1) for an arbitrary S, where r is the maximum number of degree constraints involving an edge
(which could be |V | even when S is a chain), while [2] yields an O(log |V |) factor when S is a laminar
family (the factor does not improve when S is a chain). The dependent-rounding techniques in [1, 6] yield a



tree T satisfying |δT (S)| ≤ min O logloglog|S||S| bS , (1 + ǫ)bS + O logǫ|S| for all S ∈ S, for any family S.

For MBDST, Goemans [8] obtained the first O(1), O(1) -approximation; his result yields a tree of cost
at most the optimum and at most +2 violation of the degree bounds. This was subsequently improved to an
(optimal) additive +1 violation by [16]. Zenklusen [17] considers an orthogonal generalization of MBDST,
where there is a matroid-independence constraint on the edges incident to each node, and obtains a tree of
cost at most the optimum and “additive” O(1) violation (defined appropriately) of the matroid constraints.
To our knowledge, this is the only prior work that obtains an O(1)-approximation to both the cost and
packing constraints for a constrained spanning-tree problem where an edge participates in ω(1) packing
constraints (albeit this problem is quite different from spanning tree with general degree constraints).
Finally, we note that our Lagrangian-relaxation based technique is somewhat similar to its use in [11].
However, whereas [11] uses this to reduce uniform-degree MBDST to the problem of finding an MST of
minimum maximum degree, which is another weighted problem, we utilize Lagrangian relaxation in a more
refined fashion to reduce the weighted problem to its unweighted counterpart.

2 An LP-relaxation for MCCST and preliminaries
We consider the following natural LP-relaxation for MCCST. Throughout, we use e to index the edges of
the underlying graph G = (V, E). For a set S ⊆ V , let E(S) denote {uv ∈ E : u, v ∈ S}, and δ(S) denote

3

the edges on the boundary of S. For a vector z ∈ RE and an edge-set F , we use z(F ) to denote
min

X

ce xe

P

e∈F

ze .
(P)

e

s.t.


x E(S) ≤ |S| − 1

x(E) = |V | − 1

x δ(S) ≤ bS
x ≥ 0.

∀∅ =
6 S(V
∀S ∈ S

(1)
(2)
(3)
(4)

For any x ∈ RE
+ , let supp(x) := {e : xe > 0} denote the support of x. It is well known that the polytope,
PST (G), defined by (1), (2), and (4) is the convex hull of spanning trees of G. We call points in PST (G)
fractional spanning trees. We refer to (1), (2) as the spanning-tree
constraints. We will also utilize (Pλ ),

the modified version of (P) where we replace (3) with x δ(S) ≤ λbS for all S ∈ S, where λ ≥ 1. Let
OPT (λ) denote the optimal value of (Pλ ), and let OPT := OPT (1).
Preliminaries. A family L ⊆ 2V of sets is a laminar family if for all A, B ∈ L, we have A ⊆ B or B ⊆ A
or A ∩ B = ∅. As is standard, we say that A ∈ L is a child of L ∈ L if L is the minimal
set of L such

L , E L ) be the graph obtained from L, E(L) by contracting the
that A ( L. For each L ∈ L, let GL
=
(V
L
L
L
children of L in L; we drop the superscript L when L is clear from the context.
Given x ∈ PST (G), define a laminar decomposition L of x to be a (inclusion-wise)
maximal laminar

family of sets whose spanning-tree constraints are tight at x, so x E(A) = |A| − 1 for all A ∈ L. Note
that V ∈ L and {v} ∈ L for all v ∈ V . A laminar decomposition can be constructed in polytime (using
network-flow techniques). For any L ∈ L, let xL
L , or simply xL if L is clear from context, denote x restricted
to EL . Observe that xL is a fractional spanning tree of GL .

3 An LP-rounding approximation algorithm
3.1 An overview
We first give a high-level overview. Clearly, if (P) is infeasible, there is no spanning tree satisfying the
degree constraints, so in the sequel, we assume that (P) is feasible. We seek to obtain a spanning tree T
of cost c(T ) = O(OPT ) such that |δT (S)| = O(bS ) for all S ∈ S, where δT (S) is the set of edges of T
crossing S.
In order to explain the key ideas leading to our algorithm, we first briefly discuss the approach of Olver
and Zenklusen [14] for unweighted CCST. Their approach ignores the edge costs {ce } and instead starts
with a feasible solution x to (P) that minimizes a suitable (linear) potential function. They use this potential
function to argue that if L is a laminar decomposition of x, then (x, L) satisfies a key structural property
called rainbow freeness. Exploiting this, they give a rounding algorithm, hereby referred to as AOZ , that for
every L ∈ L, rounds xL to a spanning tree TL of GL such that |δTL (S)| ≈ O xL (δ(S)) for all S ∈ S, so
that concatenating the TL s yields a spanning tree T of G satisfying |δT (S)| = O x(δ(S)) = O(bS ) for all
S ∈ S (Theorem 3.2). However, as already noted in [14], a fundamental obstacle towards generalizing their
approach to handle the weighted version (i.e., MCCST) is that in order to achieve rainbow freeness, which
is crucial for their rounding algorithm, one needs to abandon the cost function c and work with an alternate
potential function.
We circumvent this difficulty as follows. First, we note that the algorithm in [14] can be equivalently
viewed as rounding an arbitrary solution x to (P) as follows. Let L be a laminar decomposition of x.
Using the same potential-function idea, we can convert x to another solution x′ to (P) that admits a laminar
4

decomposition L′ refining L such that (x′ , L′ ) satisfies rainbow freeness (see Lemma 3.1), and then round
x′ using AOZ . Of course, the difficulty noted above remains, since the move to rainbow freeness (which
again ignores c and uses a potential function) does not yield any bounds on the cost c⊺ x′ relative to c⊺ x.
We observe however that there is one simple property (*) under which one can guarantee that c⊺ x′ = c⊺ x,
namely, if for every L ∈ L, all edges in supp(x) ∩ EL have the same cost. However, it is unclear how to
utilize this observation since there is no reason to expect our instance to have this rather special property:
for instance, all edges of G could have very different costs!
Now let x∗ be an optimal solution to (P) (we will later modify this somewhat) and L be a laminar
decomposition of x∗ . The crucial insight that allows us to leverage property (*), and a key notable aspect
of our algorithm and analysis, is that one can leverage Lagrangian duality to suitably perturb the edge
costs so that the perturbed costs satisfy property (*). More precisely, letting y ∗ ∈ RS+ denote the optimal
values∗ of the dualPvariables corresponding to constraints (3), if we define the perturbed cost of edge e to
∗
be cye := ce + S∈S:e∈δ(S) yS∗ , then the cy -cost of all edges in supp(x∗ ) ∩ EL are indeed equal, for
every L ∈ L (Lemma 3.5). In essence, this holds because for any
e′ ∈ supp(x∗ ), by complementary
P
slackness, we have ce′ = (dual contribution to e′ from (1),(2)) − S∈S:e′ ∈δ(S) yS∗ . Since any two edges
e, f ∈ supp(x∗ ) ∩ EL appear in the same sets of L, one can argue that the dual contributions to e and f
∗
∗
from (1), (2) are equal, and thus, cye = cyf .
∗
Now since (x∗ , L∗ ) satisfies (*) with the perturbed costs cy , we can convert (x∗ , L∗ ) to (x′ , L′ ) satisfying rainbow freeness without altering the perturbed cost, and then round x′ to a spanning tree T using AOZ . This immediately yields |δT (S)| = O(bS ) for all S ∈ S. To bound the cost, we argue that
P
P ∗
∗
c(T ) ≤ cy (T ) = e cye x∗e = c⊺ x∗ + S∈S bS yS∗ (Lemma 3.6), where the last equality followsPfrom complementary slackness. (Note that the perturbed costs are used only in the analysis.) However, S∈S bS yS∗
need not be bounded in terms of c⊺ x∗ . To fix this, we modify our starting solution x∗ : we solve (Pλ ) (which
recall is (P) with inflated degree bounds {λbS }), where λ > 1, to obtain x∗ , and use this x∗ in our algorithm.
Now, letting y ∗ be the optimal dual values corresponding to the inflated degree constraints, a simple duality
P
(λ)
argument shows that S∈S bS yS∗ ≤ OPT (1)−OPT
(Lemma 3.7), which yields c(T ) = O(OPT ) (see
λ−1
Theorem 3.3).
A noteworthy feature of our algorithm is the rather unconventional use of Lagrangian relaxation, where
we use duality to simplify the cost structure (as opposed to the constraint-structure) of the underlying problem by equalizing edge costs in certain subproblems. This turns out to be the crucial ingredient that allows us
to utilize the algorithm of [14] for unweighted CCST as a black box without worrying about the difficulties
posed by (the move to) rainbow freeness. In fact, as we show in Sections 4 and 5, this Lagrangian-relaxation
idea is applicable more generally, and yields a novel reduction from weighted problems to their unweighted
counterparts. We believe that this reduction is of independent interest and will find use in other settings as
well; indeed, we demonstrate another application of our ideas in Section 5.2.

3.2 Algorithm details and analysis
To specify our algorithm formally, we first define the rainbow-freeness property and state the main result
of [14] (which we utilize as a black box) precisely.
For an edge e, define Se := {S ∈ S : e ∈ δ(S)}. Note that Se could be empty. We say that two edges
e, f ∈ E form a rainbow if Se ⊆ Sf or Sf ⊆ Se . (This definition is slightly different from the one in [14], in
that we allow Se = Sf .) We say that (x, L) is a rainbow-free decomposition if L is a laminar decomposition
of x and for every set L ∈ L, no two edges of supp(x) ∩ EL form a rainbow. (Recall that GL = (VL , EL )
denotes the graph obtained from L, E(L) by contracting the children of L.) The following lemma shows
that one can convert an arbitrary decomposition (x, L) to a rainbow-free one; we defer the proof to the
Appendix. (As noted earlier, this lemma is used to equivalently view the algorithm in [14] as a rounding
algorithm that rounds an arbitrary solution x to (P).)
5

Lemma 3.1. Let x ∈ PST (G) and L be a laminar decomposition of x. We can compute in polytime a
fractional spanning tree x′ ∈ PST (G) and a rainbow-free decomposition (x′ , L′ ) such that: (i) supp(x′ ) ⊆
supp(x); (ii) L ⊆ L′ ; and (iii) x′ (δ(S)) ≤ x(δ(S)) for all S ∈ S.
Theorem 3.2 ([14]). There is a polytime algorithm, AOZ , that given a fractional spanning tree x′ ∈ PST (G)
and a rainbow-free decomposition (x′ , L′ ), returns a spanning tree TL ⊆ supp(x′ ) of GL for everyL ∈ L′
such that the concatenation T of the TL s is a spanning tree of G satisfying |δT (S)| ≤ 9x′ δ(S) for all
S ∈ S.
We can now describe our algorithm quite compactly. Let λ > 1 be a parameter.
1. Compute an optimal solution x∗ to (Pλ ), a laminar decomposition L of x∗ .
2. Apply Lemma 3.1 to (x∗ , L) to obtain a rainbow-free decomposition (x′ , L′ ).
′
′
′
3. Apply AOZ to the input (x′ , L′ ) to obtain spanning trees TLL of GL
L for every L ∈ L . Return the
′
concatenation T of all the TLL s.
Analysis.

We show that the above algorithm satisfies the following guarantee.

Theorem 3.3. The above algorithm run with parameter λ > 1 returns a spanning tree T satisfying c(T ) ≤
λ
λ−1 · OPT and |δT (S)| ≤ 9λbS for all S ∈ S.
The bound on |δT (S)| follows immediately from Lemma 3.1 and Theorem 3.2 since x∗ , and hence x′
obtained in step 2, is a feasible solution to (Pλ ). So we focus on bounding c(T ). This will follow from
∗
three things. First, we define the perturbed cy -cost precisely. Next, Lemma 3.5 proves the key result
that for every L ∈ L, all edges in supp(x∗ ) ∩ EL have the same perturbed cost. Using this it is easy to
P
P ∗
∗
show that c(T ) ≤ cy (T ) = e cye x∗e = OPT (λ) + λ S∈S bS yS∗ (Lemma 3.6). Finally, we show that
P
OPT −OPT (λ)
∗
(Lemma 3.7), which yields the bound stated in Theorem 3.3.
S∈S bS yS ≤
λ−1
To define the perturbed costs, we consider the Lagrangian dual of (Pλ ) obtained by dualizing the (inflated) degree constraints x δ(S) ≤ λbS for all S ∈ S:


X
X
max
x(δ(S)) − λbS )yS .
(LDλ )
ce xe +
gλ (y) :=
min
y∈RS
+

x∈PST (G)

e

S∈S


P
P
For y ∈ RS , let Gλ,y (x) := e ce xe + S∈S x(δ(S)) − λbS ySP= e cye xe − λ S∈S bS yS denote the
objective function of the LP that defines gλ (y), where cye := ce + S∈S:e∈δ(S) yS .
P

P

∗

Let y ∗ be an optimal solution to (LDλ ). Our perturbed costs are {cye }. We prove the following preliminary lemma, then proceed to show that the perturbed costs satisfy property (*).
Lemma 3.4. We have gλ (y ∗ ) = Gλ,y∗ (x∗ ) = OPT (λ).
P
Proof. For any y ∈ RS+ , we have gλ (y) + λ S∈S bS yS =

X

min
cye xe s.t. x E(S) ≤ |S| − 1 ∀∅ =
6 S ( V,
|

e


X
max −
(|S| − 1)µS
∅6=S⊆V

|

{z

x(E) = |V | − 1,

(Pλ,y )

s.t.

−

X

∅6=S⊆V :
e∈E(S)

µS ≤ cye ∀e ∈ E,

{z

(Dλ,y )

6


x≥0 =
}

µS ≥ 0 ∀∅ =
6 S(V


}

where the second equality follows since (Dλ,y ) is the dual of (Pλ,y ). It follows that
gλ (y ∗ ) = max gλ (y) = max −
y∈RS
+

X

∅6=S⊆V

(|S| − 1)µS − λ

−

s.t.

X

∅6=S⊆V :
e∈E(S)

µS −

X

bS y S

(Dλ )

S∈S

X

S∈S:
e∈δ(S)

yS ≤ ce

y ≥ 0, µS ≥ 0

∀e ∈ E
∀∅ =
6 S ( V.

Notice that (Dλ ) is the dual of (Pλ ), hence, gλ (y ∗ ) = OPT (λ). Moreover, it also follows that ŷ is an optimal
solution to (LDλ ) iff there exists µ̂ = (µ̂S )∅6=S⊆V such that (µ̂, ŷ) is an optimal solution to (Dλ ).
So let µ∗ be such that (µ∗ , y ∗ ) is an optimal solution to (Dλ ). It follows
that x∗ and (µ∗ , y ∗ ) satisfy

complementary slackness. So we have that if µ∗S > 0 then x∗ E(S) = |S| − 1, and if x∗e > 0 then
P
P
P
∗
− ∅6=S⊆V :e∈E(S) µ∗S − S∈S:e∈δ(S) yS∗ = ce , or equivalently cye = − ∅6=S⊆V :e∈E(S) µ∗S . Therefore,
Gλ,y∗ (x∗ ) =

X
e

=−
=−

∗

cye x∗e − λ
X

∅6=S⊆V

X

∅6=S⊆V

X

bS yS∗ =

X
−
e

S∈S

X

∅6=S⊆V :e∈E(S)

X

µ∗S x∗ E(S) − λ
bS yS∗


X
bS yS∗
µ∗S x∗e − λ
S∈S

S∈S

(|S| −

1)µ∗S

−λ

X

bS yS∗ = gλ (y ∗ ).

S∈S

∗

Lemma 3.5. For any L ∈ L, all edges of supp(x∗ ) ∩ EL have the same cy -cost.
y∗
Proof. Consider any two edges e, f ∈ supp(x∗ ) ∩ EL . Suppose for a contradiction that cy∗
e < cf . Obtain
/ {e, f }). Using the same
x̂ from x∗ by increasing x∗e by ǫ and decreasing x∗f by ǫ (so x̂e′ = x∗e′ for all e′ ∈
argument as in the proof of Lemma 3.1, one can show that x̂ ∈ PST (G) for a sufficiently small ǫ > 0. Since
∗
∗
cye < cyf , we have gλ (y ∗ ) ≤ Gλ,y∗ (x̂) < Gλ,y∗ (x∗ ) = gλ (y ∗ ), where the last equality follows from Lemma
3.4, and we obtain a contradiction.
P ∗
P
P
Lemma 3.6. We have c(T ) ≤ e cye x∗e = e ce x∗e + λ S∈S bS yS∗ .
∗

Proof. Observe that c(T ) ≤ cy (T ) since ce ≤ cye for all e ∈ E as y ∗ ≥ 0. We now bound cy (T ). To
∗ L
∗
keep notation simple, we use GL = (VL , EL ) and x∗L to denote GL
L and (x′ )L (which recall is x restricted
′
′
∗ L
to ELL ) respectively, and P
G′L = (VL′ , EL′ ) and x∗L to denote GL
L and (x )L respectively.
∗
∗
y
y
We have c (T ) =
L∈L c (T ∩ EL ) since the sets {EL }L∈L partition E. Fix L ∈ L. Note that
x∗L is a fractional spanning tree of GL = (VL , EL ) since for any ∅ =
6 Q ⊆ VL , if R is the subset of V
corresponding to Q, and A1 , . . . , Ak areP
the children of L whose corresponding contracted nodes lie in Q,
we have x∗L EL (Q) = x∗ E(R) − ki=1 x∗ E(Ai ) ≤ |R \ (A1 ∪ . . . ∪ Ak )| + k − 1 = |Q| − 1
with equality holding when Q = VL . Note that T ∩ EL is a spanning tree of GL since T is obtained by
concatenating spanning trees for the graphs {G′L′ }L′ ∈L′ , and L′ refines L. Also, all edges of supp(x∗ ) ∩ EL
P
∗
∗
∗
have the same cy -cost by Lemma 3.5. So we have cy (T ∩ EL ) = e∈EL cye x∗e . It follows that
∗

∗

cy (T ) =

X

∗

cye x∗e =

e

=

X
e

X
ce x∗e +
e

ce x∗e

+

∗

X

S∈S

yS∗ x∗

X

yS∗ x∗e

S∈S:e∈δ(S)



X
 X
δ(S) =
ce x∗e + λ
bS yS∗ .
e

7

S∈S

Lemma 3.7. We have

P

∗
S∈S bS yS

≤

OPT (1)−OPT (λ)
.
λ−1

Proof. By Lemma 3.4, we have that
OPT (λ) = gλ (y ∗ ) = Gλ,y∗ (x∗ ).
Using Lemma 3.4 again, now with λ = 1, and since y ∗ is a feasible solution to (LD1 ), we obtain that
OPT (1) = maxy∈RS g1 (y) ≥ g1 (y ∗ ). Note that the objective functions of the LPs defining g1 (y ∗ ) and
+
P
gλ (y ∗ ) differ by a constant: G1,y∗ (x) − Gλ,y∗ (x) = (λ − 1) S∈S bS yS∗ for all x ∈ PST (G). Since x∗ is an
optimal solution to minx∈PST (G) Gλ,y∗ (x), it is also an optimal solution to minx∈PST (G) G1,y∗ (x). It follows
that
OPT (1) ≥ g1 (y ∗ ) = G1,y∗ (x∗ ) .
P
Therefore, OPT (1) − OPT (λ) ≥ G1,y∗ (x∗ ) − Gλ,y∗ (x∗ ) = (λ − 1) S∈S bS yS∗ .

Proof of Theorem 3.3. As noted earlier, the bounds on δT (S)
from Lemma 3.1 and
 follow immediately

′ δ(S) ≤ 9x∗ δ(S) ≤ 9λb . The bound on c(T )
Theorem 3.2: for any S ∈ S, we have |δ
(S)|
≤
9x
S
PT
follows from Lemmas 3.6 and 3.7 since e ce x∗e = OPT (λ).

4 A reduction from weighted to unweighted problems
We now show that our ideas are applicable more generally, and yield bicriteria approximation algorithms
for any cost-minimization problem with packing side-constraints, provided we have a suitable approximation algorithm for the unweighted counterpart. Thus, our technique yields a reduction from weighted to
unweighted problems, which we believe is of independent interest.
To demonstrate this, we first isolate the key properties of the rounding algorithm B used above for
unweighted CCST that enable us to use it as a black box to obtain our result for MCCST; this will yield
an alternate, illuminating explanation of Theorem 3.3. Note that B is obtained by combining the procedure
in Lemma 3.1 and AOZ (Theorem 3.2). First, we of course utilize that B is an approximation
algorithm

∗
for unweighted CCST, so it returns a spanning tree T such that |δT (S)| = O x (δ(S)) for all S ∈ S.
Second, we exploit the fact that B returns a tree T that preserves tightness of all spanning-tree constraints
that are tight at x∗ . This is the crucial property that allows us to bound c(T ), since this implies (as we
P y∗ ∗
∗
explain below) that cy (T ) =
e ce xe , which then yields the bound on c(T ) as before. The equality
follows because the set of optimal solutions to the LP minx∈PST (G) Gλ,y∗ (x) is a face of PST (G); thus all
points on the minimal face of PST (G) containing x∗ are optimal solutions to this LP, and the stated property
implies that the characteristic vector of T lies on this minimal face. In other words, while AOZ proceeds
by exploiting the notions of rainbow freeness and laminar decomposition, these notions are not essential to
obtaining our result; any rounding algorithm for unweighted CCST satisfying the above two properties can
be utilized to obtain our guarantee for MCCST.
We now formalize the above two properties for an arbitrary cost-minimization problem with packing
side-constraints, and prove that they suffice to yield a bicriteria guarantee. Consider the following abstract
, and b ∈ Rm
problem, where P ⊆ Rn+ is a fixed polytope: given c ∈ Rn+ , A ∈ Rm×n
+ , find
+
min c⊺ x

s.t.

x is an extreme point of P,

Ax ≤ b.

(QP )

Observe that we can cast MCCST as a special case of (QP ), by taking P = PST (G) (whose extreme points
are spanning trees of G), c to be the edge costs, and Ax ≤ b to be the degree constraints. Moreover,
by taking P to be the convex hull of a bounded set {x ∈ Zn+ : Cx ≤ d} we can use (QP ) to encode a
discrete-optimization problem.
8

We say that B is a face-preserving rounding algorithm (FPRA) for unweighted (QP ) if given any point
x ∈ P, B finds in polytime an extreme point x̂ of P such that:
(P1) x̂ belongs to the minimal face of P that contains x.
We say that B is a β-approximation FPRA (where β ≥ 1) if we also have:
(P2) Ax̂ ≤ βAx.
 ⊺
P
P
Let (RP
λ ) denote the LP min c x : x ∈ P, Ax ≤ λb ; note that (R1 ) is the LP-relaxation of (Q ).
Let opt(λ) denote the optimal value of (RP
λ ), and let opt := opt(1). We say that an algorithm is a (ρ1 , ρ2 )approximation algorithm for (QP ) if it finds in polytime an extreme point x̂ of P such that c⊺ x̂ ≤ ρ1 opt and
Ax̂ ≤ ρ2 b.
Theorem 4.1. LetB be a β-approximation FPRA for unweighted (QP ). Then, given any λ > 1, one can
λ
obtain a λ−1
, βλ -approximation algorithm for (QP ) using a single call to B.

Proof sketch. We dovetail the algorithm for MCCST and its analysis. We simply compute an optimal solution x∗ to (RP
λ ) and round it to an extreme point x̂ of P using B. By property (P2), it is clear that
Ax̂ ≤ β(Ax∗ ) ≤ βλb.
y
⊺
For y ∈ Rm
+ , define c := c + A y. To bound the cost, as before, we consider the Lagrangian dual of
(RP
λ ) obtained by dualizing the side-constraints Ax ≤ λb.


h
(y)
:=
min
H
(x)
, where Hλ,y (x) := (cy )⊺ x − λy ⊺ b.
max
λ
λ,y
m
y∈R+

x∈P

Let y ∗ = argmaxy∈Rm
hλ (y). We can mimic the proof of Lemma 3.4 to show that x∗ is an optimal solution
+
to minx∈P Hλ,y∗ (x). The set of optimal solutions to this LP is a face of P. So all points on the minimal face
of P containing x∗ are optimal solutions to this LP. By property (P1), x̂ belongs to this minimal face and so
∗
∗
is an optimal solution to this LP. So (cy )⊺ x̂ = (cy )⊺ x∗ = c⊺ x∗ + (y ∗ )⊺ Ax∗ = opt(λ) + λ(y ∗ )⊺ b, where
the last equality follows by complementary slackness. Also, by the same arguments as in Lemma 3.7, we
∗
∗
λ
. Since c ≤ cy , we have c⊺ x̂ ≤ (cy )⊺ x̂ ≤ λ−1
· opt.
have (y ∗ )⊺ b ≤ opt(1)−opt(λ)
λ−1


5 Towards a 1, O(1) -approximation algorithm for (QP )


A natural question that emerges from Theorems 3.3 and 4.1 is whether one can obtain a 1, O(1) -approximation,
i.e., obtain a solution of cost at most opt that violates the packing side-constraints by an (multiplicative)
O(1)-factor. Such results are known for degree-bounded spanning tree problems with various kinds of
degree constraints [8, 16, 3, 17], so, in particular, it is natural to ask whether such a result also holds
for MCCST. (Note that for MCCST, the dependent-rounding techniques in [1, 6] yield a tree T with



for all S ∈ S.) We show
c(T ) ≤ OPT and |δT (S)| ≤ min O logloglog|S||S| bS , (1 + ǫ)bS + O logǫ|S|
that our approach is versatile enough to yield such a guarantee provided we assume a stronger property from
the rounding algorithm B for unweighted (QP ).
Let Ai denote the i-th row of A, for i = 1, . . . , m. We say that B is an (α, β)-approximation FPRA for
unweighted (QP ) if in addition to properties (P1) and (P2), it satisfies:
(P3)

⊺
it rounds a feasible solution x to (RP
α ) to an extreme point x̂ of P satisfying Ai x̂ ≥
such that A⊺i x = αbi .

A⊺i x
α

for every i

(For MCCST, property (P3) requires that |δT (S)| ≥ bS for every set S ∈ S whose degree constraint (in
(Pα )) is tight at the fractional spanning tree x.)
Theorem 5.1. Let B be an (α, β)-approximation FPRA for unweighted (QP ). Then, one can obtain a
(1, αβ)-approximation algorithm for (QP ) using a single call to B.
9

Proof. We show that applying the algorithm from Theorem 4.1 with λ = α yields the claimed result. It
is clear that the extreme point x̂ returned satisfies Ax̂ ≤ αβb. As in the proof of Theorem 4.1, let y ∗
be an optimal solution to maxy∈Rm
hλ (y) (where λ = α). In Lemma 3.6 and the proof of Theorem 4.1,
+
∗ ⊺
⊺
y
we use the weak bound c x̂ ≤ (c ) x̂. We tighten this to obtain the improved bound on c⊺ x̂. We have
∗
c⊺ x̂ = (cy )⊺ x̂ − (y ∗ )⊺ Ax̂, and
(y ∗ )⊺ Ax̂ =

X

i:A⊺i x∗ =λbi

yi∗ (A⊺i x̂) ≥

X

i:A⊺i x∗ =λbi

yi∗ A⊺i x∗
=
α

X

yi∗ bi = (y ∗ )⊺ b.

i:A⊺i x∗ =λbi

The first and last equalities above follow because yi∗ > 0 implies that A⊺i x∗ = λbi . The inequality follows
from property (P3). Thus, following the rest of the arguments in the proof of Theorem 4.1, we obtain that
∗

c⊺ x̂ ≤ (cy )⊺ x̂ − (y ∗ )⊺ b = c⊺ x∗ + (λ − 1)(y ∗ )⊺ b ≤ opt(1).

5.1 Obtaining an additive approximation for (QP ) and cost at most opt via an FPRA with
two-sided additive guarantees
We now present a variant of Theorem 5.1 that shows that we can achieve cost at most opt and additive
approximation for the packing side constraints using an FPRA with two-sided additive guarantees. We
give an application of this result in Section 5.2, where we utilize it to obtain improved guarantees for the
k-budgeted matroid basis problem.
Theorem 5.2. Let B be an FPRA for unweighted (QP ) that given x ∈ P returns an extreme point x̂ of P
such that Ax − ∆ ≤ Ax̂ ≤ Ax + ∆, where ∆ ∈ Rm
+ may depend on A and c (but not on b). Using a single
call to B, we can obtain an extreme point x̃ of P such that c⊺ x̃ ≤ opt and Ax̃ ≤ b + 2∆.
The above result is obtained via essentially the
 ⊺same arguments as those in Theorems 4.1 and 5.1. For
P
a vector ∆ ∈ Rm
,
let
(W
)
denote
the
LP
min
c x : x ∈ P, Ax ≤ b + ∆ . Let ~0 denote the all-zeros
+
∆
vector, and note that (W~P
)
is
the
LP-relaxation
of
(QP ). Let opt(∆) denote the optimum value of (WP
∆ ),
0
P
and let opt := opt(~0). The Lagrangian dual of (W∆ ) obtained by dualizing the side-constraints Ax ≤ b+ ∆
is


ϕ
(y)
:=
min
Φ
(x)
,
(LD∆ )
max
∆
∆,y
m
x∈P

y∈R+

where Φ∆,y (x) := (cy )⊺ x − y ⊺ (b + ∆). (Recall that cy := c + A⊺ y.) Let x∗ be an optimal solution to (WP
∆)
∗
ϕ∆ (y). We have the following variants of Lemmas 3.4 and 3.7.
and y = argmaxy∈Rm
+
Lemma 5.3. We have ϕ∆ (y ∗ ) = Φ∆,y∗ (x∗ ) = opt(∆).
Proof. This follows by mimicking the arguments used in the proof of Lemma 3.4.
Lemma 5.4. We have (y ∗ )⊺ ∆ ≤ opt(~0) − opt(∆).
Proof. We mimic the proof of Lemma 3.7. By Lemma 5.3, we have that
opt(∆) = ϕ∆ (y ∗ ) = Φ∆,y∗ (x∗ )
and opt(~0) = maxy∈RS ϕ~0 (y) ≥ ϕ~0 (y ∗ ). Note that Φ~0,y∗ (x) − Φ∆,y∗ (x) = (y ∗ )⊺ ∆, which is inde+
pendent of x. So since x∗ is an optimal solution to minx∈P Φ∆,y∗ (x), it is also an optimal solution to
minx∈P Φ~0,y∗ (x). It follows that
opt(~0) ≥ ϕ~0 (y ∗ ) = Φ~0,y∗ (x∗ ).
Hence, opt(~0) − opt(∆) ≥ Φ~0,y∗ (x∗ ) − Φ∆,y∗ (x∗ ) = (y ∗ )⊺ ∆.
10

Proof of Theorem 5.2. The algorithm simply computes an optimal solution x∗ to (WP
∆ ), and rounds it to an
extreme point x̃ of P using algorithm B.
It is clear that Ax̃ ≤ Ax∗ + ∆ ≤ (b + ∆) + ∆ = b + 2∆. Next we argue that c⊺ x̃ ≤ opt. We have
∗
c⊺ x̃ = (cy )⊺ x̃ − (y ∗ )⊺ Ax̃, and
X
X
(y ∗ )⊺ Ax̃ =
yi∗ (A⊺i x̃) ≥
yi∗ (A⊺i x∗ − ∆i )
i:A⊺i x∗ =bi +∆i

=

X

i:A⊺i x∗ =bi +∆i

yi∗ bi = (y ∗ )⊺ b.

i:A⊺i x∗ =bi +∆i

By Lemma 5.3, x∗ is an optimal solution to minx∈P Ψ∆,y∗ (x). So all points on the minimal face of P
containing x∗ are optimal solutions to this LP. In particular, since x̃ belongs to this minimal face (by property
(P1)), x̃ is an optimal solution to this LP. This observation, along with the inequality above, yields c⊺ x̃ ≤
∗
(cy )⊺ x∗ − (y ∗ )⊺ b = opt(∆) + (y ∗ )⊺ ∆. Finally, using Lemma 5.4 yields c⊺ x̃ ≤ opt(~0) as required.

5.2 Application to k-budgeted matroid basis
Here, we seek toP
find a basis S of a matroid M = (U, I) satisfying k budget constraints {di (S) ≤ Bi }1≤i≤k ,
where di (S) := e∈S di (e). Note that this can be cast a special case of (QP ), where P = P(M ) is the basis
polytope of M , the objective function encodes a chosen budget constraint (say the k-th budget constraint),
and Ax ≤ b encodes the remaining budget constraints. We show that our techniques, combined with a recent
1.5
randomized algorithm of [4], yields a (randomized) algorithm that, for any ǫ > 0, returns in nO(k /ǫ) time
a basis that (exactly) satisfies the chosen budget constraint, and violates the other budget constraints by
(at most) a (1 + ǫ)-factor, where n := |U | is the size of the ground-set of M . This matches the currentbest approximation guarantee of [9] (who give a deterministic algorithm) and the current-best running time
of [4].
Theorem 5.5 ([4]). For some constant ν > 0, there exists a randomized FPRA, BBN , √
for unweighted
(QP(M )√
) that rounds any x ∈ P(M ) to an extreme point x̂ of P(M ) such that Ax − ν k∆ ≤ Ax̂ ≤
Ax + ν k∆, where ∆ = (max1≤j≤n aij )1≤i≤k−1 = (maxe∈U di (e))1≤i≤k−1 .
Lemma 5.6. There exists
√ a polytime randomized algorithm that finds a basis S of M such that dk (S) ≤ Bk ,
and di (S) ≤ Bi + 2ν k maxe∈U di (e) for all 1 ≤ i ≤ k − 1, or determines that the instance is infeasible.
Proof. As explained above, we cast the problem as a special case of (QP ) by using the k-th budget constraint
as the objective function, and the remaining budget constraints as packing side-constraints. If the LPrelaxation of (QP ) is infeasible, then the budgeted-matroid-basis instance is infeasible. Otherwise, the
above guarantee follows by applying Theorem 5.2 with the algorithm B=BBN .
Using ideas from [4], we combine the algorithm from Lemma 5.6 with a partial enumeration step as
follows. We say an element e ∈ U is heavy if the inequality di (e) > 2νǫ√k Bi holds for at least one index
i ∈ {1, . . . , k}. Let H denote the set of all heavy elements. We state our algorithm below. Let ǫ > 0 be a
parameter.
e ⊆ H of size |H|
e ≤ 2νk1.5 , we do the following.
1. For every set H
ǫ
e and deleting the
(a) Let M ′ be the matroid obtained from M by contracting the elements of H
e
elements of H \ H.
e for i ∈ {1, . . . , k}.
(b) Compute residual budgets Bi′ := Bi − di (H),
(c) Run the algorithm from Lemma 5.6 on matroid M ′ with budgets {Bi′ }1≤i≤k .
11

(d) If the algorithm succeeds (that is, if the LP that it attempts to solve is feasible), then let T be
e ∪ T . If S is a basis of M , dk (S) ≤ Bk , and
the set of elements returned, and let S := H
di (S) ≤ (1 + ǫ)Bi for all 1 ≤ i ≤ k − 1, then return S.
2. If step 1 does not return any set S, then return that the instance is infeasible.
1.5

Theorem 5.7. The algorithm above, run with parameter ǫ > 0, finds in nO(k /ǫ) time a basis S of M such
that dk (S) ≤ Bk and di (S) ≤ (1 + ǫ)Bi for all 1 ≤ i ≤ k − 1, or determines that the instance is infeasible.
2νk1.5

1.5

= nO(k /ǫ) . Since steps 1(a)–1(d) run in
Proof. Note that the number of iterations is at most n ǫ
1.5 /ǫ)
O(k
poly(n) time, the overall running time is n
as claimed.
If the instance is infeasible, then any outcome of the algorithm (infeasible, or a basis S) is correct.
(Note that due to the verification done at the end of step 1(d), any set S returned must have the required
properties.) So assume that the instance is feasible, and let S ∗ be a basis of M that exactly satisfies all
the budget constraints. We argue that in this case the algorithm does indeed return a basis with the desired
properties. Let H ∗ := S ∗ ∩H be the set of heavy elements that S ∗ contains. Note that since a heavy element
uses up at least one budget to an extent greater than 2νǫ√k , and since S ∗ satisfies all the k budget constraints,
1.5
e = H ∗ (if the algorithm
we must have |H ∗ | ≤ kǫ = 2νk . Note that at the iteration corresponding to H
2ν

√

k

ǫ

reaches it), the set S ∗ \ H ∗ is feasible for the residual problem (with a matroid M ′ and residual budgets
{Bi′ } defined in steps 1(a) and 1(b)). Further, note that this set also certifies that the resulting set S satisfies
dk (S) = dk (H ∗ ) + dk (T ) ≤ dk (H ∗ ) + dk (S ∗ \ H ∗ ) = dk (S ∗ ) ≤ Bk . Finally, for every i ∈ {1, . . . , k − 1},
we have
√
di (S) = di (H ∗ ) + di (T ) ≤ di (H ∗ ) + Bi′ + 2ν k max di (e)
√

ǫ
≤ Bi + 2ν k √ Bi = (1 + ǫ)Bi ,
2ν k

e∈U \H

and so the set S will pass the verification done at step 1(d) and will be returned by the algorithm.

References
[1] A. Asadpour, M. Goemans, A. Madry, S. Oveis Gharan, and A. Saberi. An O(log n/ log log n)approximation algorithm for the asymmetric traveling salesman problem. In Proceedings of the 20th
SODA, pages 379–389, 2010.
[2] N. Bansal, R. Khandekar, J. Könemann, V. Nagarajan, and B. Peis. On generalizations of network
design problems with degree bounds. Mathematical Programming, 141(1-2):479–506, 2013.
[3] N. Bansal, R. Khandekar, and V. Nagarajan. Additive guarantees for degree-bounded directed network
design. SICOMP, 39(4):1413–1431, 2009.
[4] N. Bansal and V. Nagarajan. Approximation-friendly discrepancy rounding. To appear in Proc., IPCO
2016. Also appears as arXiv:1512.02254, 2015.
[5] K. Chaudhuri, S. Rao, S. Riesenfeld, and K. Talwar. What would Edmonds do? Augmenting paths and
witnesses for degree-bounded MSTs. Algorithmica 55:157–189, 2009.
[6] C. Chekuri, J. Vondrak, and R. Zenklusen. Dependent randomized rounding via exchange properties
of combinatorial structures. In 51st FOCS, 2010.

12

[7] M. Fürer and B. Raghavachari. Approximating the minimum-degree Steiner Tree to within one of
optimal. Journal of Algorithms 17(3):409–423, 1994.
[8] M. Goemans. Minimum bounded degree spanning trees. In 47th FOCS, 2006.
[9] F. Grandoni, R. Ravi, M. Singh, and R. Zenklusen. New approaches to multi-objective optimization.
Mathematical Programming, 146(1-2):525–554, 2014.
[10] K. Jain. A factor 2 approximation algorithm for the generalized Steiner network problem. Combinatorica, 21:39–60, 2001.
[11] J. Könemann and R. Ravi. A matter of degree: improved approximation algorithms for degree-bounded
minimum spanning trees. SICOMP, 31:1783–1793, 2002. SIAM Journal on Computing, 31:1783–
1793, 2002.
[12] J. Könemann and R. Ravi. Primal-dual meets local search: approximating MST’s with nonuniform
degree bounds. In Proceedings of the 35th STOC, 389–395 2003.
[13] A. Linhares and C. Swamy. Approximating min-cost chain-constrained spanning trees: a reduction
from weighted to unweighted problems. To appear in Proceedings of the 18th IPCO, 2016.
[14] N. Olver and R. Zenklusen. Chain-constrained spanning trees. In Proceedings of the 16th IPCO, pages
324–335, 2013.
[15] R. Ravi, M. Marathe, S. Ravi, D. Rosenkrantz, and H. Hunt III. Approximation algorithms for degreeconstrained minimum-cost network-design problems. Algorithmica 31(1):58–78, 2001.
[16] M. Singh and L. Lau. Approximating minimum bounded degree spanning trees to within one of
optimal. In Proceedings of the 39th STOC, pages 661–670. 2007.
[17] R. Zenklusen. Matroidal degree-bounded minimum spanning trees. In Proceedings of the 23rd SODA,
pages 1512–1521, 2012.

A

Proof of Lemma 3.1

This follows from essentially the same potential-function argument as used in [14] to obtain a rainbow-free
solution. Sort the edges of supp(x) in increasing order of |Se | breaking ties arbitrarily. Let e1 , e2 , . . . , ek
denote this ordering. Let w ∈ RE be any weight function such that we1 < we2 < · · · < wek (e.g., wei = i
for all i). Let x′ be an optimal solution to the following LP. (Note that the LP has variables {ze }e∈E , and
that the {xe }e∈E values are fixed.)
X
min
we ze
(P’)
e

s.t.

z ∈ PST (G), ze = 0


z δ(S) ≤ x δ(S)

z E(L) = |L| − 1

∀e ∈
/ supp(x)
∀S ∈ S

∀L ∈ L.

Properties (i) and (iii) hold by construction. Since we force the spanning-tree constraints corresponding to
sets in L to be tight, we can start with L and extend it to obtain a laminar decomposition L′ of x′ that refines
L, so (ii) holds.
13

It remains to show that (x′ , L′ ) is a rainbow-free decomposition. Consider any set L ∈ L′ and any two
′
edges e, f ∈ supp(x′ )∩ELL , and suppose that e, f form a rainbow. Let we < wf , so we must have Se ⊆ Sf .
Now perturb x′ by adding ǫ to x′e (the argument below will show that x′e < 1) and subtracting ǫ from x′f ,
where ǫ > 0 is chosen to be suitably small; let x′′ be this perturbed vector. Clearly, wT x′′ < wT x′ , so if
we show that x′′ is feasible to (P’),
then we obtain a contradiction. Clearly,
supp(x′′ ) ⊆


 supp(x). Since
Se ⊆ Sf it follows that x′′ δ(S) ≤ x δ(S) for all S ∈ S. Also, x′′ E(L) = x′ E(L) = |L| − 1 for all
L ∈ L.
Finally, we show
that x′′ ∈ PST (G) for a sufficiently
small ǫ > 0. (Hence, x′e < x′′e ≤ 1.) For A ⊆ V


such thatx′ E(A) < |A| − 1, we obtain x′′ E(A) ≤ |A| − 1 by taking ǫ > 0 suitably small; for A with
x′ E(A) = |A| − 1, we obtain x′′ E(A) = |A| − 1 since the spanning-tree constraints for all L ∈ L′ are
tight at (x′ and) x′′ and these span all other tight spanning-tree constraints.

14

