Document [original]

On Generalizations of Network Design Problems with

Degree Bounds

Nikhil Bansal1, Rohit Khandekar1, Jochen K¨onemann2, Viswanath Nagarajan3, and

Britta Peis4

1IBM T.J. Watson Research Center. {nikhil,rohitk}@us.ibm.com

2University of Waterloo. [email protected]

3Tepper School of Business, CMU. [email protected]

4Technische Universit¨at Berlin. [email protected]

Abstract. The problem of designing efficient networks with degree-bound con-

straints has received a lot of attention recently. In this paper, we study several

generalizations of this fundamental problem. Our generalizations are of the fol-

lowing two types:

–Generalize constraints on vertex-degree to arbitrary subsets of edges.

–Generalize the underlying network design problem to other combinatorial

optimization problems like polymatroid intersection and lattice polyhedra.

We present several algorithmic results and lower bounds for these problems. At

a high level, our algorithms are based on the iterative rounding/relaxation tech-

nique introduced in the context of degree bounded network design by Lau et

al. [LNSS07] and Singh-Lau [SL07]. However many new ideas are required to

apply this technique to the problems we consider. Our main results are:

–We consider the minimum crossing spanning tree problem [B+04] in the

case that the ‘degree constraints’ have a laminar structure (this general-

izes the well-known bounded degree MST [SL07]). We provide a (1, b +

O(log n)) bicriteria approximation for this problem, that improves over ear-

lier results [B+04,BKN08].

–We introduce the minimum crossing polymatroid intersection problem, and

give a (2,2b+∆−1) bicriteria approximation (where ∆is the maximum

number of degree-constraints that an element is part of). In the special case

of bounded-degree arborescence (here ∆= 1), this improves the previously

best known (2,2b+ 2) bound [LNSS07] to (2,2b).

–We also introduce the minimum crossing lattice polyhedra problem, and ob-

tain a (1, b + 2∆−1) bicriteria approximation under certain condition. This

result provides a unified framework and common generalization of various

problems studied previously, such as degree bounded matroids [KLS08].

1 Introduction

Recently there has been a substantial progress in algorithms for network design prob-

lems with additional degree-bound constraints. These problems arise naturally in var-

ious contexts, the degree bound may correspond to limitations in outgoing bandwidth

from a node, limitations in processing power, or even limitations of budget for the out-

going edges. The most widely studied problem in this line of research is the mini-

mum cost degree bounded spanning tree problem. Here given a weighted undirected

graph, and degree bounds for vertices, the goal is to find the minimum cost spanning

tree subject to these degree bounds. Even in the absence of weights, this problem is

NP-Hard, since finding a spanning tree with maximum degree two is equivalent to

finding a Hamiltonian Path. A variety of techniques has been used for this problem

[R+93,KR02,KR05,C+05,C+06,RS06,G06] which culminated in a recent breakthrough

by Singh and Lau [SL07] who gave the best possible algorithm, that achieves the opti-

mum cost, and an additive +1 violation in the degrees.

Subsequently, these results and techniques have been applied to different and more

general settings such as matroids, arborescences, directed network design problems

with intersecting and crossing super-modular connectivity requirements,and survivable

network design [LNSS07,LS08,BKN08,KLS08]. Another direction has been to look at

more general bounds than simply degree bounds, e.g., [B+04,BKN08,KLS08]. In this

paper, we study further extensions and generalizations of these problems. In addition to

several results, we also introduce and investigate the degree bounded lattice polyhedron

problem. This problem forms a common generalization of several degree bounded op-

timization problems studied recently. We now formally describe various problems we

consider, our results and techniques and how they connect to the previous work.

2 Our results, techniques and previous work

2.1 Minimum Crossing Spanning Tree

The algorithm of Singh and Lau [SL07] for the degree-bounded minimum spanning

tree problem is based on an iterative rounding approach of Jain [J01] based on a natural

linear programming relaxation. They show that in each iteration either some variable

is set to 0 or 1, or else the degree constraint on some vertex can be dropped. A natu-

ral question is whether one can generalize this approach to bounds on arbitrary subsets

of edges, instead of just degree bounds. This has been studied in the literature as the

Minimum Crossing Spanning Tree Problem (MCST). In this problem, we are given sub-

sets of edges E1,...,Em⊆Eand degree bounds b1,...,bm, and the goal is to find a

minimum cost spanning tree that contains at most biedges from Ei.

There are two previous results on the MCST problem. The first result, due to Bilo

et al. [B+04], gives a multiplicative guarantee on both cost and degree violation: the

algorithm finds a spanning tree where the degree is O(log n)bi+O(log m)and the cost

violation is a multiplicative O(log n). This algorithm is based on randomized rounding.

The second result [BKN08] gives an optimal cost guarantee and an additive guarantee

on degree: if each edge lies in at most ∆sets {Ei}m

i=1, then there is an algorithm that

finds a spanning tree of optimum cost and degree at most bi+∆−1. This algorithm

uses the iterative rounding/relaxation approach of Singh and Lau [SL07]. Note that

these degree guarantees are incomparable: the first result is better for large ∆, whereas

the second does better when ∆is small. For example, when ∆=Θ(n)there is either

an additive O(n)or a multiplicative O(log n)bound for the degree.

We consider a special case of MCST when the degree-boundshave a ‘laminar struc-

ture’, and improve over the above bounds. Our motivation is to understand how far one

can take the iterative rounding approach and provide small additive degree constraint

violations with respect to the MCST problem. In the laminar MCST problem, we are

given graph G= (V, E)with edge-costs c:E→R+, and degree bounds represented

by a laminar family Con Valong with a bound b(S)for each S∈ C. The goal is to

compute a minimum cost spanning tree in Gthat contains at most b(S)edges from

δ(S)for each S∈ C; here δ(S) := {(u, v)∈E|u∈S, v 6∈ S}is the set of edges

crossing S. We refer to edge-subsets of the form δ(S)for some S⊆Vas vertex-cuts.

We obtain the following result for laminar MCST in Section 3, that improves over both

the previously known bounds.

Theorem 1 There is a polynomial time algorithm for laminar MCST that computes a

spanning tree of cost at most the optimum, and that contains at most b(S) + O(log n)

edges from δ(S)for all S∈ C.

This algorithm is again based on iterative rounding, and it has two new main ideas.

First, we modify the iterative rounding procedure of Singh and Lau, to drop a constant

fraction of constraints in each iteration. This is crucial as it can be shown that dropping

one constraint at a time as in Singh and Lau can indeed lead to a degree violation of

Ω(∆). Second, the algorithm does not just drop degree constraints, but in some itera-

tions it also generates new degree constraints, by merging existing degree constraints.

Degree-boundedMatroids. A natural generalizationof the MCST problem is the mini-

mum crossing matroid basis problem [KLS08]. Here we are given a matroid on ground-

set Ewith rank function r: 2E→N, cost function c:E→Rand degree bounds

specified by subsets {Ei⊆E}m

i=1 and respective bounds {bi}m

i=1. The goal is to find a

min-cost basis Bof the matroid satisfying |B∩Ei| ≤ bifor all i∈[m]. Once again

we denote by ∆, the maximum number of sets {Ei}m

i=1 that any element of Elies in.

A result of [BKN08,KLS08] shows that iterated rounding can be used to finds a basis

of optimal cost that violates degree bounds by an at most and additive ∆−1term. Our

second result extends the guarantee of [B+04] to the crossing matroid problem.

Theorem 2 There is a polynomial time algorithm for the minimum crossing matroid

basis problem, that computes a basis of cost at most O(log k)times the optimum and

with at most O(log k)bi+O(log m)elements from Eifor each i∈[m]. Here mis the

number of degree constraints and kis the rank of the underlying matroid.

This algorithm is based on randomly rounding an optimal LP solution. Although the

algorithm in Theorem 2 is a natural extension of [B+04], the analysis is not completely

straightforward. The algorithm of Bilo et al. [B+04] performs O(log n)rounds of the

following: sample each edge independently according to the value produced by the LP

solution. Thekeyargument hereis a result of Alon [A95] showingthat w.h.p. the chosen

edge-set (from the above procedure) contains a spanning tree: this proof relies on the

graph structure and the notion of connected components. However it is not clear how

to apply this argument to matroids, since there is no equivalent of a connected compo-

nent in general matroids. Instead, we obtain the desired result by using a theorem of

Polesskii [Pol90] (also proved in [Kar98]) that states: if a matroid of rank kcontains

2L·ln kdisjoint bases, then picking each element independently with probability 1

results in a set containing a basis w.h.p. Details of Theorem 2 are given in Appendix B.

Hardness of approximation. Our next result shows that the crossing spanning tree

problem is strictly harder than the bounded degree minimum spanning tree problem.

Theorem 3 Unless NP has quasi-polynomial time algorithms, the minimum crossing

matroid basis problem admits no O(logαm)additive approximation for some constant

α > 0. This holds even when there are no costs. Moreover, the minimum crossing

spanning tree problem does not admit a (1, b +O(logαm))-bicriteria approximation.

To show the hardness result in Theorem 3, we give a reduction from the Label Cover

Problem. The reductionproceeds in two steps. First, we show the hardness for a uniform

matroid instance, without costs. Then, we show how to use this to reduce to an MCST

problem with costs, such that any minimum spanning tree with optimum cost violates

the degree bounds. The details are given in Section A.

We note that there is still a large gap between the positive and the negative results

for MCST. There is also an additive Ω(√∆)gap for the standard LP-based approaches,

using discrepancy arguments5. While this integrality gap is substantially better than our

hardness result, given the lack of any reasonable hardness results on discrepancy type

problems, it is not clear how this could improve the hardness result for MCST.

2.2 Minimum Crossing Arborescence and Polymatroid Intersection

The degree bounded spanning tree problem has also been studied on directed graphs

[KKRR04,LNSS07,BKN08]. Here we are given a weighted directed graph G= (V, E)

with root r∈Vand outdegree bounds bvon the vertices v∈V. The degree bounded

min-cost arborescence problem is to find a minimum cost arborescence rooted at r

subject to the degree bounds. The results for arborescences are rather different from

those for spanning trees. Bansal et al. [BKN08] designed an algorithm that for any

0≤ǫ≤1/2, produces a (bv/(1 −ǫ)+4,1/ǫ)bi-criteria guarantee. In fact this guaran-

tee holds more generally for directed network design with ‘intersecting supermodular

requirements’. It turns out that this guarantee is best one can hope for via the natural

LP relaxation, even for arborescences, since there is a similar integrality gap for every

0≤ǫ≤1/2. In particular, any approximation better than multiplicative factor 2 in the

degree bounds causes a factor of at least 2 in the costs. If we do not care about costs, we

can set ǫ= 0 and obtain only an additive degree violation; in fact, [BKN08] improved

this guarantee to plus 2.

Now, suppose we consider bounds on general edge sets. Given that additive guar-

antees exist for both crossing spanning trees and unweighted arborescences (with out-

degree bounds), a natural question is whether results analogous to spanning trees or

matroids also hold for unweighted arborescences. In particular, suppose we consider

the unweighted arborescence problem with bounds {bi}m

i=1 on sets {Ei}m

i=1, where the

set system has ∆:= maxe∈E|{i∈[m] : e∈Ei}| =O(1), or even if ∆= 1 (i.e.,

sets Eiare disjoint). Is there an additive degree violation guarantee in this case? Some-

what surprisingly, we show that for the natural LP relaxation, the answer is negative in

a rather strong sense:

5This was pointed out to us by Mohit Singh.

Theorem 4 For any ǫ > 0, there exists an instance of the unweighted minimum cross-

ing arborescence problem such that even though the LP is feasible, the bound on some

set {Ei}m

i=1 must be violated by a multiplicative factor at least 2−ǫ. Moreover, this

instance has ∆= 1, and just one non-degree constraint.

On the positive side we show a tight upper bound matching the lower bound above,

for the much more general polymatroid intersection problem.

Definition 1 (Minimum crossing polymatroid intersection problem). Let r1, r2:

2E→Zbe two supermodular functions, c:E→Rand {Ei}i∈Ibe a collection of

subsets of Ewith corresponding bounds {bi}i∈I. Then the minimum crossing polyma-

troid intersection problem is:

min cTx

x(S)≥max{r1(S), r2(S)} ∀S⊆E

x(Ei)≤bi∀i∈[m]

xe∈ {0,1} ∀e∈E.

Recall that the arborescence problem is an intersection of a partition matroid and a

graphic matroid, and hence it is a special case of the matroid intersection problem. The

following theorem captures our main result for this problem.

Theorem 5 Any optimal basic solution x∗of the linear relaxation of the minimum

crossing polymatroid intersection problem can be rounded into an integral solution

ˆxsuch that ˆx(S)≥max{r1(S), r2(S)}for all S⊆Eand

cTˆx≤2cTx∗and ˆx(Ei)≤2bi+∆−1∀i∈I.

We note that this result is the best one can hope given the lower bounds above.

First, the integrality gap instance mentioned previously implies that the multiplicative

factor in the degree cannot be improved beyond 2. Second, the [BKN08] lower bound

for arborescences implies that one cannot hope to obtain a ratio better than 2 in costs

(withoutviolating factorstrictly greaterthan 2 in degrees).For thespecial case of degree

bounded arborescence, Theorem 5 improvesthe previously best known bicriteria bound

of (2,2b+ 2) [LNSS07] to (2,2b).

The algorithm for this theorem uses iterative rounding, and its proof is based on

a ‘fractional token’ counting argument similar to the one used in proving the ∆−1

additive guarantee for the MCST problem [BKN08]. Proofs of Theorems 4 and 5 are

in Appendix C.

2.3 Minimum Crossing Lattice Polyhedron Problem

We generalize the minimum crossing polymatroid intersection problem even further

to minimum crossing lattice polyhedra. Lattice polyhedra form a common framework

for several discrete optimization problems such as polymatroids, intersection of two

polymatroids, shortest paths, max flow/min cut in s, t-planar graphs, supermodular sys-

tems, etc. (see Appendix D). Lattice polyhedra were first investigated by Hoffman and

Schwartz [HS78] and the natural LP relaxation was shown to be totally dual integral.

Even though greedy-type algorithms are known for all the examples mentioned above,

so far no combinatorial algorithm has been found for lattice polyhedra in general. Two-

phase greedy algorithms have been established only in cases where an underlying rank

function satisfies a monotonicity property (see [Fra99],[FP08]).

Before formally defining the crossing lattice polyhedra problem, we need to intro-

duce some terminology. Let (F,≤)be a partially ordered set with F 6=∅. We consider

alattice (F,≤), where there are two commutative binary operations, meet ∧and join

∨, that are defined on all pairs A, B ∈ F, such that:

A∧B≤A, B ≤A∨B

Note that our definition is more general than the usual definition of a lattice, since the

join A∨Bis not required to be the least common upper bound of Aand B. A function

r:F → Z+is said to be supermodular on (F,≤,∧,∨)iff:

r(A) + r(B)≤r(A∧B) + r(A∨B),for all A, B ∈ F

Given a supermodular function r:F → Z+, a ground set E, a cost function c:E→

R+, and a set-valued function ρ:F → 2Esatisfying:

1. Consecutive property: If A≤B≤Cthen ρ(A)∩ρ(C)⊆ρ(B),

2. Submodularity: For all A, B ∈ F,ρ(A∨B)∪ρ(A∧B)⊆ρ(A)∪ρ(B),

the lattice polyhedron problem is defined as the following integer program:

min{cT·x|X

e∈ρ(S)

xe≥r(S),∀S∈ F;x∈ {0,1}E}

Definition 2 (Minimum crossinglatticepolyhedron).Given a lattice polyhedronspec-

ified by (F,≤,∧,∨, E, ρ, r, c), and a family {Ei}m

i=1 of subsets of Ewith bounds

{bi}m

i=1, the minimum crossing lattice polyhedron problem is:

min cT·x

x(ρ(S)) ≥r(S),∀S∈ F Rank constraints

x(Ei)≤bi,∀i∈IDegree constraints

x∈ {0,1}E

We prove the following result for this problem.

Theorem 6 Consideranyinstanceof minimumcrossinglattice polyhedra(Definition2)

that satisfies the following assumption:

(∗)S < T =⇒ |ρ(S)|<|ρ(T)|,for all S, T ∈ F

Then there is an algorithm that computes a solution of cost at most the optimal, where

all rank constraints are satisfied, and each degree bound is violated by at most an

additive 2∆−1. Here ∆:= maxe∈E|{i∈[m] : e∈Ei}|.

This theorem also holds in the presence of both lower and upper degree-bounds.

We note that assumption (∗)is satisfied for matroids, so Theorem 6 matches the previ-

ously best-known bound [KLS08] for degree bounded matroids (with both upper/lower

bounds). We also note that this theorem is only applicable when the rank constraints are

separable in polynomialtime; this correspondsto the problem of minimizing a submod-

ular function on ground-set Eover the subsets {ρ(S)|S∈ F} ⊆ 2E. This is indeed

possible in all aforementioned examples of lattice polyhedra.

Observe that property (∗)is valid in case of inclusion-wise ordering, i.e., if

S≤T⇐⇒ ρ(S)⊆ρ(T)∀S, T ∈ F.

In this special case, we can improve the result of Theorem 6.

Theorem 7 If the underlying lattice of the minimum crossing lattice polyhedron prob-

lem is ordered by inclusion, then there is an algorithm that computes a solution of cost

at most the optimal, where all rank constraints are satisfied, and each degree bound is

violated by at most an additive ∆−1.

Theorems 6 and 7 are similar to the corresponding proofs for MCST [BKN08] and

degree-boundedmatroid [KLS08], however the arguments need to be carefully adapted

in the more general setting of lattice polyhedra. Proofs appear in Appendix D.

3 Crossing Spanning Tree with Laminar degree bounds

We consider the crossing spanning tree problem with bounds on vertex-cuts that form

a laminar family. In this problem, we are given an undirected graph G= (V, Eo)on n

vertices, non-negative edge-costs cefor e∈Eo, and a family Dof subsets of Vwith

“degree-bounds”b(S)for each S∈ D. We assume that Dis a laminar family of vertex-

sets: i.e. S⊆Tor T⊆Sor S∩T=∅holds for any S, T ∈ D. The problem involves

computing a minimum-cost spanning tree Tof Gthat contains at most b(S)edges from

δ(S)for each S∈ D. This problem reduces to the usual degree-bounded MST when

D={{v} | v∈V}. In this section we prove Theorem 1.

The algorithm uses iterative rounding based on an LP relaxation. The algorithm

modifies the laminar family of degree bounds during its execution. A generic iteration

starts with a subset Fof edges already picked in the solution, a subset Eof undecided

edges, i.e., the edges not yet picked in or dropped from the solution, a laminar family

Lon V, and residual degree bounds b(S)for each S∈ L. The laminar family Lhas

a natural forest-like structure with nodes corresponding to each element of L. A node

S∈ L is called the parent of node C∈ L if Sis the inclusion-wise minimal set

in L \ {C}that contains C; and Cis called a child of S. Node D∈ L is called a

grandchild of node S∈ Lif Sis the parent of D’s parent. Nodes S, T ∈ Lare siblings

if they have the same parent node. A node that has no parent is called root. The level of

any node S∈ L is the length of the path in this forest from Sto the root of its tree. We

also maintain a linear ordering of the children of each L-node. A subset B ⊆ Lis called

consecutive if all nodes in Bare siblings (with parent S) and they appear consecutively

in the ordering of S’s children. In any iteration (F, E, L, b), the algorithm solves the

following LP relaxation of the residual problem.

min X

e∈E

cexe(1)

s.t. x(E(V)) = |V|−|F|−1

x(E(U)) ≤ |U|−|F(U)|−1∀U⊂V

x(δE(S)) ≤b(S)∀S∈ L

xe≥0∀e∈E

For any vertex-subset U⊆Vand edge-set H, we let H(U) := {(u, v)∈H|

u, v ∈U}denote the edges induced on U; and δH(S) := {(u, v)∈H|u∈S, v 6∈

S}the set of edges crossing S. The first two sets of constraints are spanning tree

constraints while the third set corresponds to the degree

bounds. Let xdenote an optimal extreme point solution to

this LP. By reducing degree bounds b(S), if needed, we as-

sume that xsatisfies all degree bounds at equality (the de-

gree bounds may be fractional-valued). Let α:= 24.

Definition 3. An edge e∈Eis said to be local for S∈ L

if ehas at least one end-point in Sbut is neither in E(C)

nor in δ(C)∩δ(S)for any grandchild Cof S. Let local(S)

denote the set of local edges for S. A node S∈ L is said to

be good if |local(S)| ≤ α.

The figure on the right shows a set S, its children B1and

B2, and grand-children C1,...,C4; edges in local(S)are

drawn solid, non-local ones are shown dashed.

The algorithm is initialized with F← ∅,E←Eo,

L ← D, the original degree bounds on D, and an arbi-

trary linear ordering on the children of each node in D. In

a generic iteration (F, E, L, b), the algorithm performs one

of the following steps:

1. If xe= 1 for some edge e∈Ethen F←F∪ {e},E←E\ {e}, and set

b(S)←b(S)−1for all S∈ Lwith e∈δ(S).

2. If xe= 0 for some edge e∈Ethen E←E\{e}.

3. DropN: Suppose there at least |L|/4good non-leaf nodes in L. Then either odd-

levels or even-levels contain a set M ⊆ L of |L|/8good non-leaf nodes. Drop

the degree bounds of all children of Mand modify Laccordingly. The ordering of

siblings also extends naturally.

4. DropL: Suppose there are more than |L|/4good leaf nodes in L, denoted by N.

Then partition Ninto parts corresponding to siblings in L. For any part {N1,···,

Nk} ⊆ N consisting of ordered(not necessarily contiguous)children of some node

(a) Define Mi=N2i−1∪N2ifor all 1≤i≤ ⌊k/2⌋(if kis odd Nkis not used).

(b) Modify Lby removing leaves {N1,···, Nk}and adding new leaf-nodes {M1,

···, M⌊k/2⌋}as children of S. The children of Sin the new laminar family are

ordered as follows: each node Mitakes the position of either N2i−1or N2i,

and other children of Sare unaffected.

12 3 4

N1N4

DropN step

Good non-leaf S

DropL step

Good leaves {Ni}5

i=1

Fig.1. Examples of the degree constraint modifications DropN and DropL.

Assuming that one of the above steps applies at each iteration, the algorithm termi-

nates when E=∅and outputs the final set Fas a solution. It is clear that the algorithm

outputs a spanning tree of G. An inductive argument (see e.g. [LNSS07]) can be used

to show that the LP (1) is feasible at each each iteration and c(F) + LPcur ≤LPo

where LPois the original LP value, LPcur is the current LP value, and Fis the chosen

edge-set at the current iteration. Thus the cost of the final solution is at most the initial

LP optimum LPo. Next we show that one of the four iterative steps always applies.

Lemma 1 In each iteration, one of the four steps above applies.

Proof: We crucially use the fact that xis an extreme point solution of (1). This implies

that xis uniquely defined by satisfying a linearly independent and laminar subset Sof

the spanning tree constraints at equality together with a sub-family L′⊆ L of degree-

constraints, such that |E|=|S|+|L′|. If the first two steps do not apply, then 0< xe<

1for all e∈E. A counting argument (see, e.g., [SL07]) shows that there are at least 2

edges induced on each S∈ L′that are not induced on any of its children; so 2|S| ≤ |E|.

From the definition of local edges, we get that any edge e= (u, v)is local to at most

the following six sets: the smallest set S1∈ L containing u, the smallest set S2∈ L

containing v, the parents P1and P2of S1and S2resp., the least-common-ancestor L

of P1and P2, and the parent of L. Thus PS∈L |local(S)| ≤ 6|E|. Combining these

facts, we conclude that PS∈L |local(S)| ≤ 12|L|. Thus at least |L|/2sets S∈ Lmust

have |local(S)| ≤ α= 24, i.e., must be good. Now either at least |L|/4of them must

be non-leaves or at least |L|/4of them must be leaves. In the first case, step 3 holds and

in the second case, step 4 holds.

It remains to bound the violation in the degree constraints, which turns out to

rather challenging. We note that this is unlike usual applications of iterative round-

ing/relaxation, where the harder part is in showing that one of the iterative steps applies.

It is clear that the algorithm reduces the size of Lby at least |L|/8in each DropN

or DropL iteration. Since the initial number of degree constraints is at most 2n−1,

Lemma 2 The number of drop iterations (DropN and DropL) is T:= O(log n).

3.1 Performance guarantee for degree constraints

We begin with some notation. The iterations of the algorithm are broken into periods

between successive drop iterations: there are exactly Tdrop-iterations (Lemma 2). In

what follows, the t-th drop iteration is called round t. The time trefers to the instant

just after round t; time 0refers to the start of the algorithm. At any time t, define:

–Ltdenotes the laminar family of degree constraints.

–Etdenotes the undecided edge set, i.e., support of the current LP optimal solution.

–For any set Bof consecutive siblings in Lt,Bnd(B, t) = PN∈B b(N)equals the

sum of the residual degree bounds on nodes of B.

–For any set Bof consecutive siblings in Lt,Inc(B, t)equals the number of edges

from δEt(∪N∈BN)included in the final solution.

Recall that bdenotes the residual degree bounds at any point in the algorithm. The

following lemma is the main ingredient in bounding the degree violation.

Lemma 3 Forany setBof consecutivesiblingsin Lt(at any time t),we have Inc(B, t)≤

Bnd(B, t) + 4α·(T−t).

Observe that this implies the desired bound on each original degree constraint S:

using t= 0 and B={S}, the violation is bounded by an additive 4α·Tterm.

Proof: The proof of this lemma is by induction on T−t. The base case t=Tis trivial

since the only iterations after this correspond to including 1-edges: hence there is no

violation in any degree bound, i.e. Inc({N}, T )≤b(N)for all N∈ LT. Hence for any

B ⊆ L,Inc(B, T )≤PN∈B Inc({N}, T )≤PN∈B b(N) = Bnd(B, T ).

Now suppose t < T , and assume the lemma for t+ 1. Fix a consecutive B ⊆ Lt.

We consider different cases depending on what kind of drop occurs in round t+ 1.

DropN round. Here either all nodes in Bget dropped or none gets dropped.

Case 1: None of Bis dropped. The inductive hypothesis implies Inc(B, t + 1) ≤

Bnd(B, t+1)+4α·(T−t−1).Since the only iterations between round tand round t+1

involve edge-fixing, we have Inc(B, t)≤Bnd(B, t)−Bnd(B, t + 1) + Inc(B, t + 1) ≤

Bnd(B, t) + 4α·(T−t−1).

Case 2: All of Bis dropped. Let Cdenote the set of all children (in Lt) of nodes in

B. Note that Cconsists of consecutive siblings in Lt+1, and inductively Inc(C, t + 1) ≤

Bnd(C, t + 1) + 4α·(T−t−1). Let S∈ Ltdenote the parent of the B-nodes;

so Care grand-children of Sin Lt. Let xdenote the optimal LP solution just before

round t+ 1 (when the degree bounds are still given by Lt), and H=Et+1 the support

edges of x. At that point, we have b(N) = x(δ(N)) for all N∈ B ∪ C. Also let

Bnd′(B, t + 1) := PN∈B b(N)be the sum of bounds on B-nodes just before round

t+ 1. Since Sis a good node in round t+ 1,|Bnd′(B, t + 1) −Bnd(C, t + 1)|=

|PN∈B b(N)−PM∈C b(M)|=|PN∈B x(δ(N)) −PM∈C x(δ(M))| ≤ 2α. The

last inequality follows since Sis good; the factor of 2appears since some edges, e.g.,

the edges between two children or two grandchildrenof S, may get counted twice. Note

also that the symmetric difference of δH(∪N∈BN)and δH(∪M∈CM)is contained in

local(S). Thus δH(∪N∈BN)and δH(∪M∈CM)differ in at most αedges.

Again since all iterations between time tand t+ 1 are edge-fixing:

Inc(B, t)≤Bnd(B, t)−Bnd′(B, t + 1) + |δH(∪N∈BN)\δH(∪M∈CM)|

+Inc(C, t + 1)

≤Bnd(B, t)−Bnd′(B, t + 1) + α+Inc(C, t + 1)

≤Bnd(B, t)−Bnd′(B, t + 1) + α+Bnd(C, t + 1) + 4α·(T−t−1)

≤Bnd(B, t)−Bnd′(B, t + 1) + α+Bnd′(B, t + 1) + 2α+ 4α·(T−t−1)

≤Bnd(B, t) + 4α·(T−t)

Thefirstinequalityfollowsfromsimplecounting;thesecondfollowssinceδH(∪N∈BN)

and δH(∪M∈CM)differ in at most αedges; the third is the induction hypothesis, and

the fourth is Bnd(C, t + 1) ≤Bnd′(B, t + 1) + 2α(as shown above).

DropLround.Inthis case,let Sbe the parentof B-nodesin Lt,and N={N1,···, Np}

be all the ordered children of S, of which Bis a subsequence (since it is consecutive).

Suppose indices 1≤π(1) < π(2) <···< π(k)≤pcorrespond to good leaf-nodes

in N. Then for each 1≤i≤ ⌊k/2⌋, nodes Nπ(2i−1) and Nπ(2i)are merged in this

round. Let {π(i)|e≤i≤f}(possibly empty) denote the indices of good leaf-nodes

in B. Then it is clear that the only nodes of Bthat may be merged with nodes outside

Bare Nπ(e)and Nπ(f); all other B-nodes are either not merged or merged with another

B-node. Let Cbe the inclusion-wise minimal set of children of Sin Lt+1 s.t.

–Cis consecutive in Lt+1,

–Ccontains all nodes of B \{Nπ(i)}k

i=1, and

–Ccontains all new leaf nodes resulting from merging two good leaf nodes of B.

Note that ∪M∈C Mconsists of some subset of Band at most two good leaf-nodes in

N \B. These two extra nodes (if any) are those merged with the good leaf-nodes Nπ(e)

and Nπ(f)of B. Again let Bnd′(B, t + 1) := PN∈B b(N)denote the sum of bounds

on Bjust before drop round t+ 1, when degree constraints are Lt. Let H=Et+1 be

the undecided edges in round t+ 1. By the definition of bounds on merged leaves, we

have Bnd(C, t + 1) ≤Bnd′(B, t + 1) + 2α. The term 2αis present due to the two extra

good leaf-nodes described above.

Claim 1 We have |δH(∪N∈BN)\δH(∪M∈CM)| ≤ 2α.

Proof: We say that N∈ N is represented in Cif either N∈ C or Nis contained

in some node of C. Let Dbe set of nodes of Bthat are not represented in Cand the

nodes of N \B that are represented in C. Observe that by definition of C, the set D ⊆

{Nπ(e−1), Nπ(e), Nπ(f), Nπ(f+1)}; in fact it can be easily seen that |D| ≤ 2. Moreover

Dconsists of only good leaf nodes. Thus, we have |∪L∈D δH(L)| ≤ 2α. Now note that

the edges in δH(∪N∈BN)\δH(∪M∈CM)must be in ∪L∈DδH(L). This completes the

proof.

As in the previous case, we have

Inc(B, t)≤Bnd(B, t)−Bnd′(B, t + 1) + |δH(∪N∈BN)\δH(∪M∈CM)|

+Inc(C, t + 1)

≤Bnd(B, t)−Bnd′(B, t + 1) + 2α+Inc(C, t + 1)

≤Bnd(B, t)−Bnd′(B, t + 1) + 2α+Bnd(C, t + 1) + 4α·(T−t−1)

≤Bnd(B, t)−Bnd′(B, t + 1) + 2α+Bnd′(B, t + 1) + 2α+ 4α·(T−t−1)

=Bnd(B, t) + 4α·(T−t)

The first inequality follows from simple counting; the second uses Claim 1, the third

is the induction hypothesis (since Cis consecutive), and the fourth is Bnd(C, t + 1) ≤

Bnd′(B, t + 1) + 2α(from above).

This completes the proof of the inductive step and hence Lemma 3.

References

[A95] N. Alon, A note on network reliability, Discrete Probability and Algorithms, D. Aldous et

al. Eds., IMA volumes in mathematics and its applications, 72, 1995, 11-14.

[A+93] S. Arora, L. Babai, J. Stern, and Z. Sweedyk, The hardness of approximate optima in

lattices, codes, and systems of linear equations, IEEE Symposium on Foundations of Computer

Science, 1993.

[BKN08] N.Bansal, R. Khandekar and V. Nagarajan, Additive guarantees for degree bounded

network design, Proceedings of the 40th annual ACM symposium on Theory of computing,

Victoria, Canada, 2008, 769-778.

[B+04] V. Bilo, V. Goyal, R. Ravi and, M. Singh, On the crossing spanning tree problem, in

APPROX 2004.

[C+05] K. Chaudhuri, S. Rao, S. Riesenfeld, and K. Talwar, What would Edmonds do? Aug-

menting paths and witnesses for degree-bounded MSTs, In Proceedings of 8th International

Workshop on Approximation Algorithms for Combinatorial Optimization Problems, pp. 26-

39, 2005.

[C+06] K. Chaudhuri, S. Rao, S. Riesenfeld, and K. Talwar. Push relabel and an improved ap-

proximation algorithm for the bounded-degree mst problem, In Proceedings of 33th Interna-

tional Colloquium on Automata, Languages and Programming, 2006.

[Edm70] J. Edmonds, Submodular functions, matroids and certain polyhedra, Proc. Int. Conf.

on Combinatorics (Calgary), 1970, pp. 69–87.

[EJ85] P.H. Edelman and R.E. Jamison, The theory of convex geometries, Geometriae Dedicata

19 (1985), 247–270.

[FP08] U.Faigle and B. Peis, Two-phase greedy algorithms for some classes of combinatorial

linear programs, Proc. of the 19th annual ACM-SIAM symposium on discrete algorithms, San

Francisco, 2008, 161-166.

[FKP08] U. Faigle, W. Kern and B. Peis, A ranking model for cooperative games, convexity and

the greedy algorithm, working paper.

[Fra99] A. Frank, Increasing the rooted connectivity of a digraph by one, Math. Programming

84 (1999), 565–576.

[Fuj05] S. Fujishige, Submodular Functions and Optimization, Annals of Discrete Mathematics,

vol. 58, Elsevier Science Publishers, North-Holland, 2nd ed., 2005.

[G06] M.X. Goemans, Minimum Bounded-Degree Spanning Trees, Proceedings of the 47th An-

nual IEEE Symposium on Foundations of Computer Science, 273282, 2006.

[HS78] A. Hoffman and D.E. Schwartz, On lattice polyhedra, Proceedings of Fifth Hungarian

Combinatorial Coll. (A. Hajnal and V.T. Sos, eds.), North-Holland, Amsterdam, 1978, pp. 593–

598.

[J01] K. Jain, A factor 2 approximation algorithm for the generalized Steiner network problem,

Combinatorica, 2001, 39-61.

[Kar98] D. R. Karger, Random sampling and greedy sparsification for matroid optimization

problems, Mathematical Programming, 82, 1998, pp. 99–116.

[KLS08] T. Kir´aly, L.C. Lau and M. Singh, Degree bounded matroids and submodular flows, in

IPCO 2008.

[KKRR04] P. N. Klein, R. Krishnan, B. Raghavachari and R. Ravi, Approximation algorithms

for finding low degree subgraphs, Networks, 44(3), 2004, 203-215.

[KR02] J. K¨onemann and R. Ravi, A matter of degree: Improved approximation algorithms for

degree bounded minimum spanning trees, SIAM J. on Computing, 31:1783-1793, 2002.

[KR05] J. K¨onemann and R. Ravi, Primal-Dual meets local search: approximating MSTs with

nonuniform degree bounds, SIAM J. on Computing, 34(3):763-773, 2005.

[LNSS07] L.C. Lau, J. Naor, M. R. Salavatipour and M. Singh, Survivable network design with

degree or order constraints (full version), in STOC 2007.

[LS08] L.C. Lau and M. Singh, Additive Approximation forBounded Degree Survivable Network

Design, in STOC 2008.

[Pol90] V. P. Polesskii, Bounds on the connectedness probability of a random graph, Problems

of Information Transmission, 27, 1990, pp. 86–97.

[R+93] R. Ravi, M.V. Marathe, S.S. Ravi, D.J. Rosenkrants, and H.B. Hunt, Many birds with one

stone: Multi-objective approximation algorithms, in Proceedings of the 25th ACM-Symposium

on Theory of Computing, pp 438-447, 1993.

[RS06] R. Ravi and M. Singh, Delegate and Conquer: An LP-based approximation algorithm

for Minimum Degree MSTs. In Proceedings of 33rd International Colloquium on Automata,

Languages and Programming, 2006.

[Sch03] A. Schrijver, Combinatorial Optimization, Springer, 2003.

[SL07] M. Singh and L.C. Lau, Approximating minimum bounded degree spanning trees to

within one of optimal, in STOC 2007.

A Hardness Result for Minimum Crossing Spanning Tree

In this section we will show that unless NP has quasi-polynomial time algorithms,

any solution with optimum cost for minimum crossing spanning tree, must violate the

degree by at least an additive term of O(logcm)for some universal constant c. Before

we prove this result, we show hardness for the more general minimum crossing matroid

basis problem: given a matroid Mon a ground set Vof elements, a cost function

c:V→R+, and degree bounds specified by pairs {(Ei, bi)}m

i=1 (where each Ei⊆V

and bi∈N), find a minimum cost basis Iin Msuch that |I∩Ei| ≤ bifor all i∈[m].

Later we show how to adapt this hardness result to special case of the spanning tree

matroid.

Theorem 8 Unless NP has quasi-polynomial time algorithms, the minimum crossing

matroid basis problem admits no O(logcm)additive approximation for some fixed con-

stant c > 0. This holds even if we do not care about the costs.

Proof: We reduce from the label cover problem [A+93]. The input is a graph G=

(U, E)where the vertex set Uis partitioned into pieces U1,···, Uneach having size q,

and all edges in Eare between distinct pieces. We say that there is a superedge between

Uiand Ujif there is an edge connecting some vertex in Uito some vertex in Uj. Let t

denote the total number of superedges.

t=|{(i, j)∈[n]

2|there is an edge in Ebetween Uiand Uj}|

The goal is to pick one vertex from each part {Ui}n

i=1 so as to maximize the number of

induced edges. This is called the value of the label cover instance. Note that the value

can be at most t.

It is well known that there exists a universal constant γ > 1such that for every

k∈N, there is a reduction from any instance of SAT (having size N) to a label cover

instance hG= (U, E), q, tisuch that:

–If the SAT instance is satisfiable, the label cover instance has optimal value t.

–If the SAT instance is not satisfiable, the label cover instance has optimal value

< t/γk.

–|G|=NO(k),q= 2k, and the reduction runs in time NO(k).

We construct a uniform matroid Mwith rank ton ground set E(recall that any

subset of tedges is a basis in a uniform matroid). There is a set of degree bounds

corresponding to each i∈[n]: for every collection Cof edges incident to vertices in

Uisuch that no two edges in Care incident to the same vertex in Ui, there is a degree

bound requiring at most one element to be chosen from C. Note that the number of

degree bounds m≤n·(nq)q≤n2q.

Observe that if the originalSAT instance is satisfiable, then the matroid Mcontains

a basis obeying all the degree bounds: namely the tedges covered in the optimal solu-

tion to the label coverinstance. This is because if we consider any Ui, then all the edges

having a vertex in Uias their endpoint, have the same endpoint. Thus, by the way the

collection Cis defined, at most one such edge can lie in it.

On the other hand, we will show that if the SAT instance is unsatisfiable, then every

basis in Mpicks at least ρ=γk/2edges from some degree-constrained set of edges.

Suppose (for a contradiction) that there is a basis (i.e. set of tedges B⊆E) such that

|B∩C|< ρ for each degree constraint C. This means that each part {Ui}n

i=1 contains

fewer than ρvertices that are incident to edges B. For each part i∈[n], let Wi⊆Ui

denote the vertices incident to edges of B; note that |Wi|< ρ. Consider the label cover

solution obtained as follows. For each i∈[n], choose one vertex from Wiuniformly

at random. Clearly, the expected number of edges in the resulting induced subgraph is

at least t/ρ2=t/γk, which contradicts that the value of label cover instance is strictly

less than t/γk.

The steps described in the above reduction can be done in time polynomial in m

and |G|. Also, instead of randomly choosing vertices from the sets Wi, we can use

conditional expectations to derive a deterministic algorithm that recovers at least t/ρ2

edges. Setting k=Θ(log log N)(recall that Nis the size of the original SAT instance),

we obtain an instance of bounded-degreematroidbasis of size max{m, |G|} =NlogaN

and ρ=γk/2= logbN, where a, b > 0are constants. Note that log m= loga+1 N,

which implies ρ= logcmfor c=b

a+1 >0a constant. Thus it follows that for this

constant c > 0the bounded-degree matroid basis problem has no O(logcm)additive

approximation, unless NP has quasi-polynomial time algorithms.

We now consider the special case of minimum-cost crossing spanning tree: given an

edge-weighted graph with degree-bounds on medge-sets, find a minimum cost span-

ning tree satisfying all degree bounds. Using Theorem 3, we prove the following.

Corollary 1 UnlessNP hasquasi-polynomialtimealgorithms,thereisno(b+logcm, 1)

approximation for the minimum-cost crossing spanning tree problem, for some fixed

constant c > 0.

Proof: Recall that Theorem3 actually showsthe hardnessof approximatingthe bounded-

degree uniform matroid problem. We show how the bases of a uniform matroid can be

represented in a suitable instance of the min-cost crossing spanning tree problem. Let

the uniform matroid from Theorem 3 consist of eelements and have rank t≤e. We

construct a graph as in Figure 2, with vertices v1,···, vecorresponding to elements in

the uniform matroid. Each vertex viis connected to the root rby two vertex-disjoint

paths: hvi, ui, riand hvi, wi, ri. The edges {(r, ui)|i∈[e]}∪{(vi, ui)|i∈[e]}have

cost zero, and edges {(r, wi)|i∈[e]}∪{(vi, wi)|i∈[e]}have cost 1. Corresponding

to each degree bound (in the uniform matroid) of b(C)on a subset C⊆[e], there is a

constraint to pick at most |C|+b(C)edges from δ({ui|i∈C}).

The dashed edges have cost 0, solid edges have cost 1.

Fig.2. The crossing spanning tree instance used in the reduction.

Observe that for each i∈[e], any spanning tree must choose at least three edges

among {(r, ui),(ui, vi),(r, wi),(wi, vi)}, in fact any three edges suffice. Thus for any

spanning tree of cost 2n−t, there must be exactly tindices ifor which both edges

(r, ui)and (ui, vi)lie in the spanning tree. Thus we can associate a basis in the uniform

matroid with every spanning tree of cost 2n−t.

In Theorem 3, for the bounded-degree uniform matroid problem, it is hard to dis-

tinguish the following two cases: (yes-case) there is a basis b∗satisfying all degree

bounds, and (NO-case) every basis violates some degree bound by an additive ρ=

Ω(logcm)term. In the yes-case, whenever ilies in the basis b∗, we choose the edges

{(r, ui),(ui, vi), r(wi)}. This solution has cost 2n−t, and satisfies all the degree

bounds. On the other hand, in the no-case any spanning tree with cost 2n−t, must vio-

late some degree bound by at least an additive ρ. This implies that there is no (b+ρ, 1)

approximation for minimum-costcrossing spanning tree: given some instance I(which

is either a YES-instance or NO-instance) of the bounded degree matroid problem, we

reduce Ito a crossing spanning tree instance as above and apply the (b+ρ, 1) algo-

rithm. If we obtain a tree of cost at most 2n−tthen Iis a (YES-instance), otherwise it

is a (NO-instance).

B An algorithm for minimum crossing matroid basis

In this section, we consider the minimum crossing matroid problem defined as fol-

lows. Given a matroid Mhaving nelements, rank function r: 2[n]→Nand cost

c: [n]→R, and marbitrary “degree” constraints {Ei, bi}m

i=1, find a minimum cost

basis subject to the degree constraints. For the case of crossing spanning tree, Bilo et al.

gave an (O(log n)b+O(log m), O(log n)) approximation algorithm based on random-

ized rounding of the natural LP relaxation. We note that this result can be extended to

the bounded-degree matroid problem. In particular, we show that

Theorem 9 There is an (O(log k)b+O(log m), O(log k)) bicriteria approximation

algorithm for the bounded-degree matroid basis problem with mdegree constraints on

a matroid of rank k.

The algorithm is very simple: We consider the following LP relaxation.

min X

e∈[n]

ce·xe

x(S)≤r(S)∀S⊆[n]

x([n]) = r([n])

x(Ei)≤bi∀i∈[m]

If xdenotes an optimal solution to the aboveLP-relaxation, then the integer solution

Rconsists of each element e∈[n]chosen independently with probability min{ρ·

xe,1}, where ρ= 2⌈ln k⌉. We will show that w.h.p. Rcontains a basis and that all the

degree violations are small. Using the Chernoff bound for each i∈[m],Pr[|R∩Ei|>

2ρbi+ 2 log m]≤1

m2(since the expected value of |R∩Ei|is at most ρ·bi). Thus with

probability at least 1−1

m, for every degree bound i∈[m], we have |R∩Ei| ≤ 2ρbi+

2 log m. Before showing that Rcontains a basis w.h.p., we state a relevant theorem of

Polesskii [Pol90], which was also proved in Karger [Kar98].

Theorem 10 (Theorem 4.2, Karger [Kar98]) Suppose a matroid Nof rank kcon-

tains 2L·ln kdisjoint bases. Then if each element of Nis chosen independently with

probability 1

L, the resulting set contains a basis with probability at least 1−O(1

k).

Claim 2 The set Rcontains a basis of Mwith probability at least 1−O(1

k).

Proof: This is a direct application of Theorem 10. Let Lbe some large integer so that

L·xeis integral for all e∈[n](recall that xis the optimal LP solution). Construct

matroid Nfrom Mby keeping 2L⌈ln k⌉·xecopies of each element e∈[n]; clearly

the rank of Nequals k(rank of M). Since xis a fractional basis in M, matroid N

contains P= 2L· ⌈ln k⌉disjoint bases. This follows from the matroid base packing

theorem, Corollary 42.1d, [Sch03], which states that a matroid on element set Vwith

rank function rhas ℓdisjoint bases if and only if ℓ(r(V)−r(S)) ≤ |V\S|.

Consider picking each element in Nindependently with probability 1

L, and let T′

be the resulting set of elements. Let T⊆[n]be the set of distinct element of Min T′;

clearly T′contains a basis of Niff Tcontains a basis of M. Theorem 10 implies that T

contains a basis with probability at least 1−O(1

k). We now relate the random set Tto

the randomset R. Itis clear that eachelemente∈[n]is chosenindependentlyin T(asis

the case in R). The probabilityqeof notpicking element e∈[n]in Tequals (1−1

L)P xe

which is at most 1−P

Lxe. Note that qe≥max(0,1−P

Lxe). Now, pe= min(1,P

Lxe)

is the probability that eis picked in set R, and hence pe= max(0,1−P

Lxe)which is

at most qe. Thus the random set Rstochastically dominates T. Since basis containment

is a monotone property, the probability that Rcontains a basis is larger than that for T,

implying the claim.

Combining the high probability statements for degree-bound violation and Claim 2,

we obtain Theorem 2.

C Minimum Crossing Arborescence and Polymatroid Intersection

Recall that there is an additive +2 approximation for the degree bounded arborescence

problem without costs. In this section, we consider this problem when bounds on arbi-

trary edge sets are allowed. Surprisingly, we show that even if we add one extra ”non-

degree” bound, the degree bounded arborescence problem without cost has a (multi-

plicative) integrality gap of 2. In particular, we prove Theorem 4:

Proof: [Theorem 4] We first define the graph. This graph is shown in Figure 3, and

is similar to the one in [BKN08] (but has different parameters). Let kbe an arbitrarily

large integer, consider a k-ary arborescence rooted at root r, of depth d > 2 ln(2/ǫ)/ǫ.

We call the edges of this arborescence solid edges. Consider the natural drawing of this

tree, and label these leaves 1,...,kd, from right to left. Next we define dashed edges as

follows. There is one edge going from root rto leaf 1, and one edge from each leaf ito

i+ 1 for i= 1,...,kd−1. Finally, the dotted edges are defined as follows. For each

internal node v(other than the root), there is an incoming dotted edge from the leftmost

leaf root in the subtree rooted at v. This completes the description of the graph. The

degree bounds are as follows. For each non-leaf vertex, there is an out-degree bound of

kt1

Fig.3. The integrality gap instance. The set E1consists of all dashed edges.

k/2. In addition, we define the E1to be the set of all dashed edges and assign it a bound

of b1=kd/2. Note that |E1|=kd. It is easily verified that ∆= 1.

Consider the LP solution which assigns xe= 0.5to every edge. It is easily verified

that this is a valid arborescence solution (each vertex can be sent a unit of flow from

the root by sending 0.5 unit of flow along the solid edges, and 0.5 unit along the dashed

and dotted edges), and satisfies all the Eibounds.

We now show that in any integral solution, the degree is violated by at factor of at

least2−ǫ. Let us assume that eachinternalvertexhasan outdegreeof atmost k(1−ǫ/2),

otherwise this is a violated vertex and we are done. It suffices to show that in this case,

there must be at least kd(1 −ǫ/2) edges chosen from E1in a valid arborescence. This

followsfrom the simple property(see [BKN08], Prop. 1, for a formal proof) that if a leaf

idoes not have path from root to itself using only solid edges, then the edge (i−1, i)

must be present in the arboresence. Now, if internal degree is at most k(1 −ǫ/2), then

the number of leaves with a path from root using only solid edges is at most (1−ǫ/2)dkd

which, by our choice of d, is at most ǫkd/2. Thus at least, kd(1 −ǫ/2) edges must be

chosen from E1which proves the result.

Recall that several problems such as the minimum cost arboresence problem can

be cast as a matroid intersection problem. While the degree bounded version of the

minimum cost arborescence problem is well understood [BKN08], not much is known

about its behavior with degree bounds on arbitrary subsets. We now consider the mini-

mum crossing polymatroidintersection problem (see Defintion 1) and proveTheorem 5.

The algorithm 1 for minimum crossing polymatroid intersection is based on itera-

tively rounding the following natural LP relaxation.

min cTx

x(S)≥max{r1(S), r2(S)}−|F∩S| ∀S⊆E

x(Ei)≤b′

i∀i∈W

0≤xe≤1∀e∈E.

Above, Edenotes the set of unfixed elements, Fthe set of chosen elements, W⊆[m]

the set of remaining degree bounds, and b′

i(for each i∈W) the residual degree-bound

in the ith constraint.

Algorithm 1 Algorithm for minimum crossing polymatroid intersection.

1: Intially, set F=∅,W= [m],b′

i=bi, for all i∈I

2: while E6=∅do

3: Compute an optimal basic solution x∗of the LP;

4: for all e∈Ewith x∗(e) = 0 do

5: E←E\ {e}

6: end for

7: for all e∈Ewith x∗(e)≥1

2do

8: F←F∪ {e};E←E\ {e}

9: b′

i←b′

i−x∗(e), for all i∈Wwith e∈Ei

10: end for

11: for all i∈Wwith |Ei| ≤ ⌈2b′

i⌉+∆−1do

12: W←W\ {i}

13: end for

14: end while

15: Return the incidence vector xFof F;

Note that this algorithm rounds variables of value x∗(e)≥1

2to 1, and hence we

loose a factor of two in the cost and in the degree bounds. Theorem 5 follows as a

consequence if we can show that in each iteration, either some variable can be rounded,

or some constraint can be dropped. For this, we prove:

Lemma 1. If x∗∈REis a basic optimal solution of (LP2) with 0< x∗(e)<1

2for

all e∈E, then there exists at least one i∈Wsuch that

|Ei| ≤ ⌈2b′

i⌉+∆−1

Proof: Since x∗is a basic feasible solution, there exist linearly independent tight

sets T1⊆ {S⊆E|x∗(S) = r1(S)},T2⊆ {S⊆E|x∗(S) = r2(S)}and

B ⊆ {Ei⊆E|x∗(Ei) = b′

i}such that

|E|=|T1|+|T2|+|B|.

Since x∗is modular and r1, r2are supermodular on the Boolean lattice (2E,⊆), it can

be assumed (again, using uncrossing arguments) that each of (T1,⊆)and (T2,⊆)form

a chain. We use the following claim from [BKN08] (which was originally stated for

spanning trees, but immediately extends to any polymatroid).

Claim ([BKN08]). We have |T1|,|T2| ≤ Pe∈Ex∗

e. Additionally, Tj=x∗(E)(for

j∈ {1,2}) only if E∈ Tj.

Suppose (for a contradiction) that for all i∈W,|Ei| ≥ ⌈2b′

i⌉+∆. For each i∈W,

define Spi:= Pe∈Ei(1 −2x∗

e) = |Ei|−2x∗(Ei). Then we have Spi≥ |Ei|−2b′

i≥

|Ei|−⌈2b′

i⌉ ≥ ∆. Hence Pi∈WSpi≥∆·|W|.

For each e∈E, let re:= |{i∈W:e∈Ei}| ≤ ∆. Note also that 0<1−2x∗

e<1

for each e∈E. Now,

i∈W

Spi=X

e∈E

re·(1 −2x∗

e)≤∆·X

e∈E

(1 −2x∗

=∆·(|E|−2·x∗(E)) ≤∆·(|E|−|T1|−|T2|)

Thus we have Pi∈WSpi≤∆·|B| ≤ ∆·|W|with equality only if E∈ T1∩T2(from

Claim C), re=∆for all e∈E, and B=W.

We now claim that equality Pi∈WSpi=∆·|W|is not possible. If this were the

case, χ(E)is a constraint in each of T1and T2; and Pi∈B χ(Ei) = Pi∈Wχ(Ei) =

∆·χ(E). However this contradicts the linear independence of constraints in T1and

B. Thus it must be that Pi∈WSpi< ∆ · |W|, which contradicts the assumption that

|Ei| ≥ ⌈2b′

i⌉+∆for all i∈W.

Proof: [Theorem 5] Lemma 1 implies that an improvementis possible in each iteration

of Algorithm 1. Since we only round elements that the LP sets to value at least half, the

cost guarantee is immediate. Consider any degree bound i∈[m]; let b′

idenote its

residual bound when it is dropped, and F′the set of chosen elements at that iteration.

Again, rounding elements of fractional value at least half implies |Ei∩F′| ≤ ⌊2bi−

2b′

i⌋= 2bi−⌈2b′

i⌉. Furthermore, the number of Ei-elements in the support of the basic

solution at the iteration when constraint iis dropped is at most ⌈2b′

i⌉+∆−1. Thus

the number of Ei-elements chosen in the final solution is at most 2bi−⌈2b′

i⌉+⌈2b′

i⌉+

∆−1 = 2 ·bi+∆−1

D Minimum Crossing Lattice Polyhedra

Before we study minimum crossing lattice polyhedra (Definition 2), we give a few ex-

amples of well-known discrete optimization problems which can be formalized as the

problem to find an optimal integral vector of a lattice polyhedron.

D.1 Examples of lattice polyhedra

The reductions given here can also be found in [Sch03] and [FKP08], for example.

Polymatroid intersection. Let r1, r2:E→Z+be two supermodular rank functions

on the same ground set E,c:E→Rand consider the polymatroid intersection

problem

min{cTx|x(T)≥max{r1(T), r2(T)}∀T⊆E, x ∈ {0,1}E}.

We show that this problem might as well be formulated as a lattice polyhedronproblem:

Let E′and E′′ be two disjoint copies of Eand set ˜

E=E′∪E′′. We consider the lattice

(F,⊆,∪,∩)defined on

F={S⊆˜

E|S⊆E′or E′⊆S}.

The set-valued function ρ:F → 2Eand the rank function r:F → Z+are now given

r(T′) := r1(T)and r(˜

E\T′′) := r2(T)∀T⊆E,

ρ(T′) := Tand ρ(˜

E\T′′) := T∀T⊆E,

where T′and T′′ are the E′and E′′-copies, respectively, of the set T. Since ρsatisfies

the consecutivity and submodularity properties on (F,⊆,∩,∪), problem

min{cTx|X

e∈ρ(S)

xe≥r(S),∀S∈ F;x∈ {0,1}E}

is a lattice polyhedron problem and equivalent to the polymatroid intersection problem

above.

Shortest paths. Let D= (V, E)be a digraph with edge-costs c:E→R+and

designated vertices s, t ∈V. In the shortest-path problem one aims to find a directed

s, t-path Pin Gof minimum cost c(P) = Pe∈Pce. We formulate the shortest-path

problem as a lattice polyhedron problem as follows: Consider the collection of all s, t-

cuts

F={U⊆V|s∈U, t 6∈ U},

and map each cut U∈ F to the set of its outgoing edges; i.e., ρ(U) := δ+(U)⊆

2E. It is well-known that the function ρ:F → 2Esatisfies the consecutivity and

submodularity propertieson (F,⊆,∩,∪). Since the constant function r≡1is certainly

supermodular on F, the shortest-path problem

min{cTx|X

e∈δ+(S)

xe≥1,∀S∈ F;x∈ {0,1}E}

turns out to be a special instance of the lattice polyhedron problem.

Max flow/min cut in s,t-planar graphs. Let G= (V, E)be a directed or undirected

graph with s, t ∈Vand denote by P ⊆ 2Ethe collection of all cycle-free s, t-paths in

G. Given edge-capacities c:E→Rthe min cut problem can be formulated as

min{cTx|X

e∈P

xe≥1,∀P∈ P;x∈ {0,1}E}.

Note that this problem is a lattice polyhedron (with constant rank function r≡1and

identity function ρ(P) = Pfor all P∈ P) as soon as we can find a lattice (P,≤,∨,∧)

on the collection of paths satisfying the consecutivity and submodularity properties.

Given a planar representation of Gwith s, t on the outer boundary of the representation

(graphs for which such a representation exists are called s,t-planar graphs), we can

define such a lattice in a natural manner: we simply set

P≤Q⇐⇒ Qis the uppermost path in G[P∪Q]∀P, Q ∈ P,

where G[P∪Q]is the subgraph of Ginduced by the edges in Pand Q, and the up-

permost path is constructed greedily as follows: start with the uppermost edge leaving

sand always traverse the next outgoing edge in clockwise order (w.r.t. the planar rep-

resentation). Consequently, the join P∨Qis the uppermost path, and the meet P∧Q

is the lowestmost path in G(P∪Q)(the latter is constructed analoguesly by starting

with the lowest s-leaving edge and always traversing the next outgoing edge in coun-

terclockwise order). It is not hard to see that the resulting lattice satisfies the desired

consecutivity and submodularity properties.

We note that the two-phase greedy algorithms described in [Fra99], [FP08] find a

min cut together with a max flow (i.e., the dual solution) in an s, t-planar graph even in

the more general setting with supermodular monotone rank function r:P → Z+.

Supermodular systems. Following Fujishige [Fuj05], a supermodular system (D, r)

consists of a family of subsets D ⊆ 2Eof a finite set Ewith ∅, E ∈ D such that (D,⊆

,∪,∩)forms a distributive lattice, together with a supermodular function r:D → R

which is normalized in the sense r(∅) = 0. Fujishige described a greedy algorithm

which optimizes a linear function over the base polyhedron of a supermodular system

{x∈RE|x(E) = r(E); x(S)≥r(S),∀S∈ D}.

Note that our iterative rounding algorithm for the minimum crossing lattice polyhe-

dron problem also applies when we are interested in a basis solution, i.e., one sat-

isfying x(E) = r(E). Since any supermodular system defines a lattice polyhedron

with inclusion-wise ordering, Theorem 7 applies in the special case where we are inter-

ested in an integral vector of a supermodular base polyhedron satisfying certain degree

bounds.

D.2 Algorithm for minimum crossing lattice polyhedra

We consider the minimum crossing lattice polyhedron problem in a slightly more gen-

eral form than Definition 2: we allow both upper and lower bounds on the family

{Ei}m

i=1. Let {ai}m

i=1 denote the respectivelower-bounds,as in Definition 2, let {bi}m

i=1

denote the upper-bounds. We first give an algorithm for Theorem 6 and prove it.

The algorithm for minimum crossing lattice polyhedra is based on iterative round-

ing. At each iteration, we maintain the following:

–F⊆Eof elements that have been chosen into the solution.

–E′⊆E\Fof undecided elements.

–W⊆[m]of degree bounds.

Initially E′=E,F=∅and W= [m]. In a generic iteration with E′, F, W , we solve

the following LP relaxation on variables {xe|e∈E′}, called LPlat(E′, F, W ) :

min cT·x

x(ρ(S)) ≥r(S)−|F∩ρ(S)|,∀S∈ F

ai−|F∩Ei| ≤ x(Ei)≤bi−|F∩Ei|,∀i∈W

0≤xe≤1,∀e∈E′

Consider an optimal basic feasible solution xto the aboveLP relaxation. The algorithm

does one of the following in iteration (E′, F, W), until E′=W=∅.

1. If there is e∈E′with xe= 0, then E′←E′\{e}.

2. If there is e∈E′with xe= 1, then F←F∪{e}and E′←E′\{e}.

3. If there is i∈Wwith |Ei∩E′| ≤ 2∆, then W←W\{i}.

D.3 Proof of Theorem 6

Assuming that one of the steps (1)-(3) applies at each iteration, it is clear that we obtain

a final solution F∗that has cost at most the optimal value, satisfies the rank constraints,

and violates each degree constraint by at most an additive 2∆−1. We next show that

one of (1)-(3) applies at each iteration (E′, F, W).

Lemma 4 Suppose(F,≤)is a lattice satisfying the consecutive and submodular prop-

erties, and condition (∗), function ris supermodular, and xis a basic feasible solution

to LPlat with 0< xe<1for all e∈E′. Then there exists some i∈Wwith

|Ei∩E′| ≤ 2∆.

We first establish some standard uncrossing claims, before proving the lemma. We

also need some more definitions. Two elements A, B ∈ F are said to be comparable if

either A≤Bor B≤A; they are non-comparableotherwise. A subset L ⊆ F is called

achain if Lcontains no pair of non-comparable elements.

Let r′(S) := r(S)−|F∩ρ(S)|for all S∈ F denote the right hand side of the rank

constraints in the LP solved in a generic iteration (E′, F, W).

Claim. r′is supermodular.

Proof: This follows from the consecutive and submodular properties of lattice (F,≤).

Consider any A, B ∈ F, and

|F∩ρA|+|F∩ρB|=|F∩(ρA∪ρB)|+|F∩(ρA∩ρB)|

≥ |F∩(ρA∧B∪ρA∨B)|+|F∩(ρA∩ρB)|

≥ |F∩(ρA∧B∪ρA∨B)|+|F∩(ρA∧B∩ρA∨B)|

=|F∩ρA∧B|+|F∩ρA∨B|

The second inequality follows from submodularity (i.e. ρA∪ρB⊇ρA∧B∪ρA∨B),

and the third inequality uses the consecutive property ρA∧B∩ρA∨B⊆ρA, ρB(since

A∧B≤A, B ≤A∨B). This combined with supermodularity of rimplies r′(A) +

r′(B)≤r′(A∧B) + r′(A∨B)for all A, B ∈ F.

For any element A∈ F, let χ(A)∈ {0,1}E′be the incidence vector of ρ(A)⊆E′. Let

T:= {A∈ F | x(ρA) = r′(A)}denote the elements in Fthat correspond to tight rank

constraints in the LP solution xof this iteration. Using the fact that r′is supermodular

(from above), and by standard uncrossing arguments, we obtain the following.

Lemma 5 If S, T ∈ F satisfy x(ρS) = r′(S)and x(ρT) = r′(T), then:

x(ρ(S∧T)) = r′(S∧T)and x(ρ(S∨T)) = r′(S∨T)

Moreover, χ(S) + χ(T) = χ(S∧T) + χ(S∨T).

Proof: We have the following sequence of inequalities:

r′(S∧T) + r′(S∨T)≤x(ρS∧T) + x(ρS∨T)

=x(ρS∧T∩ρS∨T) + x(ρS∧T∪ρS∨T)

≤x(ρS∧T∩ρS∨T) + x(ρS∪ρT)

≤x(ρS∩ρT) + x(ρS∪ρT)

=x(ρS) + x(ρT)

=r′(S) + r′(T)

≤r′(S∧T) + r′(S∨T)

The first inequality is by feasibility of x, the third inequality is the submodular lattice

property, the fourth inequality is by consecutive property, and the last inequality is su-

permodularity of r′. Thus we have equality throughout, in particular x(ρ(S∨T)) =

r′(S∨T)and x(ρ(S∧T)) = r′(S∧T). Finally since xe>0for all e∈E′, we also

have χ(S) + χ(T) = χ(S∧T) + χ(S∨T).

Lemma 6 ([Sch03]) There exists a chain L ⊆ T such that the vectors {χ(A)|A∈ L}

are linearly independent and span {χ(B)|B∈ T}.

We are now ready for the proof of Lemma 4.

Proof: [Lemma 4] |E′|is the number of non-zero variables in basic feasible x. Hence

there existtight linearlyindependentconstraints:L ⊆ F correspondingto rank-constraints

and B ⊆ Wdegree-constraints, such that |E′|=|L|+|B|. Furthermore, by Lemma 6

Lis a chain in F, say consisting of the elements S1< S2<···< Sk. We claim that,

|ρ(Sj)\∪j−1

t=1 ρ(St)| ≥ 2,for each 1≤j≤k(2)

The above condition is clearly true for j= 1: since x(ρ(S1)) = r′(S1)≥1(it is

positive and integer-valued), and xe<1for all e∈E′. Consider any j≥2. By

the consecutive property on St≤Sj−1< Sj(for any 1≤t≤j−1), we have

ρ(Sj)∩ρ(St)⊆ρ(Sj−1). So, ρ(Sj)\∪j−1

t=1 ρ(St)=ρ(Sj)\ρ(Sj−1). We now claim

that |ρ(Sj)\ρ(Sj−1)| ≥ 2, which would prove (2). Since Sj−1< Sj, assumption (∗)

implies that there is at least one element e∈ρ(Sj)\ρ(Sj−1). Moreover, if this is the

only element, i.e., if ρ(Sj)\ρ(Sj−1) = {e}, then ρ(Sj−1) = ρ(Sj)\{e}must be true

(again by property (∗)). But this causes a contradiction to the non-integrality of xe:

xe=x(ρ(Sj)) −x(ρ(Sj−1)) = r′(ρ(Sj)) −r′(ρ(Sj−1)) ∈Z.

Now, equation (2) implies that k=|L| ≤ |E′|

2. Hence |E′| ≤ 2|B|.

Suppose(for contradiction)that |Ei∩E′| ≥ 2∆+1 foralli∈W. Then Pi∈W|Ei∩

E′| ≥ (2∆+ 1) ·|W|. Since each element in E′appears in at most ∆sets {Ei}i∈W,

we have ∆·|E′| ≥ Pi∈W|Ei∩E′| ≥ (2∆+ 1) · |W|. Thus |E′|>2|W| ≥ 2|B|,

which contradicts |E′| ≤ 2|B|from above.

We are now able to prove the main result of this section:

Proof: [Theorem 6] Since the algorithm only picks 1-elements into the solution F,

the guarantee on cost can be easily seen. As argued in Lemma 4, at each iteration

(E′, F, W )one of the Steps (1)-(3) apply. This implies that the quantity |E′|+|W|

decreases by 1 in each iteration; hence the algorithmterminates after at most |E|+|I|it-

erations.To see the guaranteeon degree violation, consider any i∈Iandlet (E′, F, W)

denotethe iteration in which it is dropped,i.e. Step (3) applies here with |Ei∩E′| ≤ 2∆

(note that there must be such an iteration, since finally W=∅). Since a degree bound

is dropped at this iteration, we have 0< xe<1for all e∈E′(otherwise one of the

earlier steps (1) or (2) applies).

1. Lower Bound: ai−|F∩Ei| ≤ x(Ei∩E′)<|E′∩Ei| ≤ 2∆, i.e. ai≤ |F∩Ei|+

2∆−1. The final solution contains at least all elements in F, so the degree lower

bound on Eiis violated by at most 2∆−1.

2. UpperBound:The final solution contains at most |F∩Ei|+|E′∩Ei|elements from

Ei. If Ei∩E′=∅, the upper bound on Eiis not violated. Else, 0< x(Ei∩E′)≤

bi−|F∩Ei|, i.e. bi≥1 + |F∩Ei|, and |F∩Ei|+|E′∩Ei| ≤ bi+ 2∆−1. So

in either case, the final solution violates the upper bound on Eiby at most 2∆−1.

Observing that all the steps (1)-(3) preserve the feasibility of the LPlat, it follows that

the final solution satisfies all rank constraints (since E′=∅finally).

D.4 Inlcusion-wise ordered lattice polyhedra

We nowconsider a special case of minimum crossing lattice polyhedrawhere the lattice

Fis ordered by inclusion. This class of lattice polyhedraclearly satisfy assumption (∗),

so Theorem 6 applies. However in this case, we prove the stronger guarantee in Theo-

rem 7 for the setting with only upper bounds as in Definition 2. The algorithm remains

the same as the one above for Theorem 6. In order to prove Theorem 7 it suffices to

show the following strengthening of Lemma 4.

Lemma 7 Suppose(F,≤)is a lattice satisfying the consecutive and submodular prop-

erties, and condition

S≤T⇐⇒ ρS⊆ρT∀S, T ∈ F,

function ris supermodular, andxis a basic feasible solution to LPlat with 0< xe<1

for all e∈E′. Then there exists some i∈Wwith |Ei∩E′| ≤ b′

i+∆−1.

Proof: Since xis a basic feasible solution, there exist linearly independent tight rank

function- and degree bound constraints Tand B ⊆ Wsuch that

|E′|=|T|+|B|.

Using uncrossing arguments, we can assume that (T,≤)forms a chain

T={T1< T2< . . . < Tk}.

Consider an arbitrary pair Ti< Ti+1 in T. Since xe>0for all e∈Eand ρ(Ti)⊂

ρ(Ti+1), it follows that 0< x(ρ(Ti+1)\ρ(Ti)) and therefore, by the integrality of r,

x(ρ(Ti+1)\ρ(Ti)) = x(ρ(Ti+1)) −x(ρ(Ti)) = r(Ti+1)−r(Ti)≥1.

Thus,

x(E)≥x(ρ(Tk)) =

k−1

i=1

x(ρ(Ti+1)\ρ(Ti)) ≥k=|T |

with equality only if E=ρ(Tk). This implies that

|E′|−x(E) = |T|+|B|−x(E)≤ |B|.(3)

Let E′

i=E′∩Ei. To prove the statement of the Lemma, it suffices to show:

i∈W

(|E′

i|−b′

i) = X

i∈W

(|E′

i|−x(Ei)) < ∆|W|.

In order to prove this, define ∆e=|{i∈W|e∈Ei}|and consider the derivations

i∈W

(|E′

i|−x(Ei)) = X

i∈WX

e∈E′

(1 −xe) = X

e∈E

∆e(1 −xe)

=∆X

e∈E

(1 −xe)−X

e∈E

(∆−∆e)(1 −xe)

≤

|{z}

eq.(3)

∆|B|− X

e∈E

(∆−∆e)(1 −xe)

=∆|W|−∆|W\B|− X

e∈E

(∆−∆e)(1 −xe)≤∆|W|.

Note that equality can only hold if E=ρ(Tk)and ∆|W\B|+Pe∈E(∆−∆e)(1 −

xe) = 0. The latter can only be true if |B| =|W|and ∆e=∆for each e∈E. But this

would imply that X

i∈B

χEi=∆χE=∆χTk,

where χS∈ {0,1}F×Eis the incidence vector of S∈ F with χS

e= 1 iff e∈ρ(S).

However, this contradicts the fact that the constraints Tand Bare linearly independent.