Network design is a central problem in combinatorial optimization and computer science. To capture more practical situations, the more general model of network design with degreeconstraints was suggested in the early 90's [22,8] and has attracted researchers in both theory and practice for decades. One of the most famous examples is the Degree-Bounded Minimum Spanning Tree (DB-MST) problem, which models the problem of designing a multi-casting network in which each node only has enough power to broadcast to a bounded number of its neighbors. This problem has been studied in a sequence of works (see, e.g., [16,18,11,24]), leading to the breakthrough result of Goemans [11] followed by the work of Singh and Lau [24], which settled the problem by giving an algorithm that outputs a solution with optimum cost, while violating the degree bound by an additive factor of +1. Since the works on DB-MST, many efforts have been dedicated to the study the generalizations of the problem: the Degree-Bounded Steiner Tree problem, in which the goal is to find a minimum-cost subgraph that connects all the terminals, while meeting the given degree bounds, was studied in [17,21]. The Survivable Network Design problem, where each pair of nodes v, w are required to have at least λ vw edge-disjoint v-w paths, has also been studied in literature; see, e.g., [20,21].
Recently, degree-bounded network design problems have been studied in the online setting [4,3,5]. Besides the standard (also called point-to-point) network design problems, Dehghani et al. [4] also studied the Degree-Bounded Group Steiner Tree problem (DB-GST). They gave a negative result, which shows that it is not possible to approximate both cost and weight of the Online DB-GST problem simultaneously, even when the input graph is a star. More specifically, there exists an input demand sequence that forces any algorithm to pay a factor of Ω(n) either in the cost or in the degree violation. To date, there was no non-trivial approximation algorithm for DB-GST, either in the online or offline setting, and even when all the edges have zero-cost. This was listed as an open problem by Hajiaghayi [14] at the 8th Flexible Network Design Workshop (FND 2016).
In this paper, we study a degree-bounded variant of the classic network design problem, the Degree-Bounded Directed Steiner Tree problem (DB-DST). Formally, in DB-DST, we are given an n-vertex directed graph G = (V, E) with costs on edges, a root vertex r, a set of k terminals K, and degree bounds d v for each vertex v. The goal is to find a minimumcost rooted tree T ⊆ G that contains a path from the root r to every terminal t ∈ K, while respecting the degree bound, i.e., the out-degree of each vertex v in T is at most d v . Despite being a classic problem, there was no previous positive result on DB-DST as it is a generalization of DB-GST.
The barriers in obtaining any non-trivial approximation algorithm for DB-GST and DB-DST are similar. Most of the previous algorithms for these two problems either run on the metric closure of the input graph [9,7,23], require metric-tree embedding [9,1,6] or use height-reduction techniques [25,2,13,10], all of which lose track of the degree of the solution subgraph.
We present a bi-criteria (O(log k log n), O(log 2 n))-approximation algorithm for DB-DST that runs in quasi-polynomial-time (see Section 1.1 for the definition), thus solving the open problem of Hajiaghayi [14]. Our technique expands upon the recent result of Grandoni, Laekhanukit and Li [13] for the Directed Steiner Tree problem. We observe that the algorithm in [13] can be easily extended to the problem with degree bounds. Nevertheless, to amend the degree-constrained problem into their framework, we are required to prove a concentration bound for degrees, which is rather non-trivial. Notice that the O(log n log k)-approximation factor on the cost of the tree is almost tight due to the hardness of Ω(log 2-n) in [15] for Directed Steiner Tree and the slightly improved hardness of Ω(log 2 n/ log log n) in [13].
While our result for DB-DST is (almost) tight on the cost guarantee, the degree violation factor O(log 2 n) is an O(log n) factor away from the approximation lower bound of Ω(log n) from the Set Cover hardness. To understand if the gap can be reduced, we study the special case of DB-DST obtained from the hardness construction in [15], namely the Degree-Bounded Group Steiner Tree problem on trees (DB-GST-T). In this problem, we are given an (undirected) tree T • = (V • , E • ) with edge-costs, a root r, k subsets of vertices (called groups) O 1 , . . . , O k ⊆ V and a degree bound d v for each vertex v ∈ V • . The goal is to find a minimum-cost subtree T ⊆ T • that joins r to at least one vertex from each group O t , for every t ∈ [k], while respecting the degree bound, i.e., the number of children of each vertex v in T is at most d v . We present an (O(log k log n), O(log n))-bicriteria approximation algorithm for DB-GST-T. So, the degree violation of our algorithm is tight and the cost-guarantee is almost tight. This improves upon the O(log n log k, log n log k)-bicriteria approximation algorithm due to Kortsarz and Nutov [19] who observe that the randomized rounding algorithm in [9] also gives a guarantee on degree-violation.
Our first result is an (O(log k log n), O(log 2 n))-bicriteria approximation for DB-DST that runs in quasi-polynomial time: We say that a randomized algorithm is an (α, β)-bicriteriaapproximation algorithm if it outputs a tree T containing an r→t path for every terminal t ∈ K such that the number of children of every vertex v in T is at most β • d v , and the expected cost of the tree is at most α times the cost of the optimum tree that does not violate the degree constraints.
Theorem 1. There is a randomized (O(log n log k), O(log 2 n))-bicriteria approximation algorithm for the degree-bounded directed Steiner tree problem in n O(log n) -time.
To the best of our knowledge, our result for DB-DST is the first non-trivial bicriteria approximation for the problem. As we mentioned, the O(log n log k)-factor for the cost is almost tight due to the hardness results of [15] and [13] for DST. There is a hardness of Ω(log n) for the degree violation factor from the Set Cover problem, even if we ignore the cost of the output tree.
Remark. As in [13,10], we could save a factor of log log n in the approximation factor for the problem, with a slight increase in the running time. However, this complicates the algorithmic framework. To deliver the algorithmic idea in a cleaner way, we choose to present the results with O(log n log k) approximation ratios.
On Approximating Degree-Bounded Network Design Problems Our second result is for the degree-bounded group Steiner tree problem on trees (DB-GST-T). We obtain an O(log n log k), O(log n) -bicriteria approximation, which is (almost) tight on both factors: Theorem 2. There is a randomized O(log n log k), O(log n) -bicriteria approximation for the degree-bounded group Steiner tree problem on trees.
Our algorithm for DB-DST takes ingredients from both [13] and [10]. As in these papers, we consider an optimum solution, and recursively partition it into balanced sub-trees; we then assign a "state" to each of these sub-trees. The tree structure of this recursive partition, as well as all of the states, form what we call a state tree. We solve the problem indirectly, by finding a good state tree, which we can transform back into a corresponding good solution. The state of a sub-tree contains a set of special vertices in the sub-tree that we call portals; these were used in [10] to obtain their improved approximation algorithm for DST. We construct a super-tree T • that contains all possible state trees as sub-trees and reduce the problem considered into that of finding a good sub-tree of small cost in T • . This can be done by formulating a linear program (LP) relaxation and rounding the LP solution using a recursive procedure. The construction of the super-tree and the LP rounding techniques are similar to those in [13]. To extend the algorithm to DB-DST, we need to store the degrees of all of the portals in the state.
This algorithmic framework outputs a so-called "multi-tree": This is a tree where a vertex or an edge can appear multiple times. Repeating the procedure for Q = O(log n log k) times, we obtain a set of Q multi-trees. This process violates the degree requirements and thus we obtain bicriteria approximation results. The analysis of this process is non-trivial as we need to prove a concentration bound on the number of times a vertex appears in a multi-tree.
Our technique for DB-GST-T is in observing that the rounding algorithm for GST-T (no degree bounds) in [9] is indeed a generalization of random walk. As we slightly boost the branching probability by a constant factor, this (almost) does not affect the degree bound, but the probability of connecting the root vertex to each group is amplified dramatically. A drawback is that it also incurs a huge blow-up in the cost. To handle the blow-up, we stop amplifying the branching probability when the connecting probability is sufficiently large. The best (but inaccurate) way to illustrate our algorithm is by considering a random walk from the root vertex to a group O t . We change the random process by branching into two directions simultaneously in each step, and then stop the extra branching when it generates Θ(log n) simultaneous random walks. Since we have O(log n) simultaneous random walks, the cost incurred by the process is blown-up by a factor O(log n), but the degree-violation is blown-up by only a factor 2. At the same time, the probability of reaching the group O t goes up by a factor Ω(log n). Thus, if we need O(log k log n) rounds to reach every group, then we now need only O(log k) rounds. There is no difference in the cost for running the algorithm for O(log k log n) rounds or O(log k) rounds (with an extra O(log n) factor in the cost), but it saves a factor in the degree-violation of O(log n).
Preliminaries for Degree-Bounded Directed Steiner Tree
In our algorithm and analysis for the DB-DST problem, a tree is always an out-arborescence. Given a tree T , we use root(T ) to denote its root. Given T and a vertex v in T , we use Λ T (v) to denote the set of children of v, and Λ * T (v) to denote the set of descendants of v (including v itself) in the tree T . A sub-tree T of T is a weakly-connected sub-graph of T ; such a T must be an out-arborescence. Sometimes, we shall use left and right children to refer to the two children of a vertex in a tree; in this case, the order of the two children is important and will be clearly specified. For an edge e = (u, v), we use head(e) = v to denote its head.foot_0 For a triple ξ = (u, v, v ) of three vertices, we use second(ξ) = v and third(ξ) = v to denote the second and third parameter of ξ.
We shall assume each terminal t ∈ K has only one incoming edge and no outgoing edges in G. This can be assumed w.l.o.g using the following simple operation: For every terminal t ∈ K that does not satisfy the condition, we add a new vertex t , an edge (t, t ) with cost c (t,t ) = 0 and replace t with t in K. We increase d t by 1 and set d t = 0.
One more assumption we can make is that each non-terminal u ∈ V \ K has at most 2 outgoing edges in G. To make sure that this holds, we focus on some non-terminal u with b ≥ 3 outgoing edges. We replace the star centered at u with its b outgoing edges by a gadget which is a full binary-tree rooted at u with b leaves being the out-neighbors of u. For every newly added vertex u, we set d u = d max . This way every vertex in G will have at most 2 outgoing edges. The cost of the edges in the gadget can be naturally defined: every leaf edge (of this gadget) ending at w has cost c (u,w) , and all internal edges have zero cost. However, this operation changes the degree of vertices. To address this issue, we define a simple transformation function φ v : Z → Z for every v ∈ V as follows: If v is a vertex in the original graph, then φ v is identically 1. Otherwise, v is a non-root internal vertex of some gadget and we define φ v to be the identity function. Then we can compute the original degree ρ u of a vertex u in a tree T of G recursively as follows: ρ u = 0 if u is a leaf, and ρ u = v∈Λ T (u) φ v (ρ v ) otherwise. So, we require that for every v in the output tree T , the original degree ρ v of v is at most d v .
We shall use the following basic tool as the starting point of our algorithm design. Its proof is elementary and deferred to Appendix B. Lemma 3. Let T = (V T , E T ) be an n-vertex binary tree. Then there exists a vertex
Given a tree T = (V T , E T ) as in the lemma, we can partition it into two trees T 1 = (V T1 , E T1 ) and T 2 = (V T2 , E T2 ), where T 2 contains vertices in Λ * T (v) and T 1 contains vertices in V T \(Λ * T (v)\{v}). First assume n ≥ 4. Since 2n/3+1 < n, we know that v = root(T ), thus implying root(T 1 ) = root(T ) = root(T 2 ) = v, which is a leaf in T 1 . Consequently, we have
which is strictly less than n. Thus, T 1 and T 2 are sub-trees that form a balanced partition of (the edges of) T . We call this procedure the balanced tree partitioning on T .
When n = 3, there are 2 types of trees. If the root has two children, then we could not make both |V T1 | and |V T2 | to be smaller than 3. If the tree is a path of 2 edges, then we can choose v to be the middle vertex and the procedure partitions the tree into two edges. Later, we shall apply the balanced tree partitioning procedure recursively. We stop the recursion when the tree is either an edge, or only contains the root and its 2 children. In other words, the tree has only 1 level of edges.
On Approximating Degree-Bounded Network Design Problems
We define a multi-tree in G as an intermediate structure. It is simply a tree over multi-sets of vertices and edges in G:
We say that each vertex a ∈ V T is a copy of the vertex label(a) ∈ V and each edge (a, b) ∈ E T is a copy of the edge (label(a), label(b)) ∈ E. So, we say that T is rooted at a copy of v ∈ V , if label(root(T )) = v, and T contains a copy of some v ∈ V if there exists some a ∈ V T with label(a) = v. We extend the costs c e , the functions φ v and the degree bounds d v to their copies in a multi-tree as follows: for a vertex a and an edge (a, b) in a multitree,
Given a multi-tree T , the "original degree" ρ a of a vertex a can be computed in the same way as before.
Definition 5 (Good Multi-Trees). Let T = (V T , E T ) be a multi-tree in G. We say that T is good if it is rooted at a copy of r, has leaves being copies of terminals, and the original degree of any vertex a in T is at most d a .
We can then state the main theorem for DB-DST, which we prove in Sections 3 to 5.
We show that this implies Theorem 1.
Proof of Theorem 1. We run the algorithm in Theorem 6 Q times to obtain Q good multitrees T 1 , T 2 , . . . , T Q , for some large enough Q = O(log n log k). Our output will contain all edges that appear in the Q multi-trees. Notice that the output may not be a tree, but we can remove edges so that it becomes a tree. Applying union bound, all terminals appear in the union of the Q trees with probability at least 0.9, when Q is big enough. By Property (6c) in the theorem statement, we have for every v,
The above inequality holds since the Q trees are produced independently.
Thus, if M = O(log n) is big enough, by Markov's inequality we have
.
The event on the left side is exactly that the number of copies of v in T 1 , . . . , T Q is at least M/s. Thus, with probability at least 0.8, every terminal t appears in one of the Q trees and every vertex v appears at most M/s = O(log 2 n) times in the trees. Taking the union of all trees and reflecting the edges in the original graph G, we have a sub-graph G of G containing a path from r to every terminal t ∈ K. The total cost of edges in
We can take an arbitrary Steiner tree T in G as the output of the algorithm. This gives us an (O(log n log k), O(log 2 n))-bicriteria approximation algorithm for the degree-bounded directed Steiner tree problem. The running time of the algorithm is n O(log n) .
Organization. The remaining part of the paper is organized as follows. In Section 3, we define states and good state trees. In Section 4, we argue that the problem of finding a small cost valid tree can be reduced to that of finding a small cost state-tree. In Section 5, we present our linear programming rounding algorithm that finishes the proof of Theorem 6. Section 6 is dedicated to the proof of Theorem 2 for the degree-bounded group Steiner tree problem on trees (DB-GST-T).
Given the optimum tree T * (which is binary by our assumptions) for the DB-DST problem, we can apply the balanced tree partitioning recursively to obtain a decomposition tree: We start from T * and partition it into two trees T 1 and T 2 using the balanced-tree-partitioning procedure, and then recursively partition T 1 and T 2 until we obtain sub-trees with 1 level of edges: Such a tree contains either a single edge, or two edges from the root. Then the decomposition tree is a full binary tree where each node corresponds to a sub-tree of T * . Due to the balance condition, the height of the tree will be O(log n). Throughout the paper, we shall use h = Θ(log n) to denote an upper bound on the height of this decomposition tree. Thanks to its small depth, the decomposition tree becomes the object of interest. However, as each node in the tree corresponds to a sub-tree of the optimum solution T * , it contains too much information for the algorithm to handle. Instead, we shall only extract a small piece of information from each node that we call the state of the node. On one hand, a state contains much less information than a sub-tree does, so we can afford to enumerate all possible states for a node. On the other hand, the states of nodes in the decomposition tree still contain enough information for us to check whether the correspondent multi-tree is good. We call the binary tree of states a state tree; we require in a good state tree, the states of nodes satisfy some consistency constraints. Then we can establish a two-direction connection between good multi-trees and good state trees.
Given a valid tree T in G and a sub-tree T of T , we now start to make definitions related to the state of T w.r.t T . It is convenient to think that T is the optimum tree T * and T is a sub-tree of T = T * obtained from the recursive balanced-partitioning procedure since this is how we use the definitions. However, the definitions are w.r.t. general T and T ; from now on till the end of Section 3, we fix any valid tree T and its sub-tree T .
Other than root(T ), the state for T w.r.t. T contains the set of portals of T :
In general, the set of portals of T can be large, but if T is obtained from the recursive balanced-tree-partitioning procedure for T , then the number of portals can be shown to be at most h + 1. As we shall often use the root and set of portals together, we make the following definition:
On Approximating Degree-Bounded Network Design Problems Definition 8 (Root-Portals-Pair). A pair (r , S) is called a root-portals-pair for vertex r and portals S if r ∈ S ⊆ V \ K.
It is easy to see that the root-portal-pairs for an internal node of the decomposition tree and its two children satisfy some properties stated in the following definition: Definition 9 (Allowable Child-Pair). Given three root-portals-pairs (r , S), (r , S 1 ) and (r , S 2 ), we say ((r , S 1 ), (r , S 2 )) is an allowable child-pair of (r , S) if r / ∈ S, S 1 ∪ S 2 = S ∪ {r } and S 1 ∩ S 2 = {r }.
The following claim motivates the definition of allowable child pairs:
2 ) be the two sub-trees obtained by applying the balanced tree partitioning on T . Let r = root(T ) = root(T 1 ), r = root(T 2 ) = r and S, S 1 , S 2 be the sets of portals in T , T 1 , T 2 respectively. Then, ((r , S 1 ), (r , S 2 )) is an allowable child-pair of (r , S).
Proof. First, r is not a portal of T since it is a non-root internal vertex in of T . Second, it is easy to see that
The next piece of the information in a state is a degree vector:
As explained in section 2.1, ρ v will be the original degree of v in the tree T .
Definition 12 (Consistency of degree vectors). Given a root-portals-pair (r , S), an allowable child-pair ((r , S 1 ), (r , S 2 )) of (r , S), three degree vectors ρ, ρ 1 and ρ 2 for S, S 1 and S 2 respectively, we say ρ 1 and ρ 2 are consistent with ρ, if for every v ∈ S 1 \ {r }, we have
So, the degree vectors are consistent if there is no contradictory information among them.
Definition 13 (Edge/Triple Agreeing with Degree Vector). Given a root-portals-pair (r , S) with |S| ≤ 2, a degree vector ρ for S, and an edge (r , v) ∈ E with {r , v} \ K = S, we say (r , v) agrees with
Similarly, given a root-portals-pair (r , S) with |S| ≤ 3, a degree vector ρ for S, and two edges
Notice that, in the above definition, either v ∈ S or v ∈ K. In the former case, ρ v is defined; in the latter case ρ v is not defined but we know φ v is identically 1. The same argument holds for v . The definition corresponds to the case when T is a base case of the recursive balanced tree partitioning, i.e., T contains only 1 level of edges. If T contains an edge e = (r , v), then the portal set of T is {r , v} \ K. We shall have ρ r = (φ v (ρ v ) or 1). Similarly, if T contains 3 vertices (r , v, v ) with r being the root, then we must have ρ r = (φ v (ρ v ) or 1) + (φ v (ρ v ) or 1).
X. Guo, G. Kortsarz, B. Laekhanukit, S. Li, D. Vaz, and J. Xian 39:9
With degree vectors, we can define states and good state-trees: Definition 14. A state is a tuple (r , S, ρ) where (r , S) is a root-portals-pair and ρ is a degree vector for S.
The state of the tree T w.r.t T is the tuple (r , S, ρ) with r = root(T ), S being the set of portals in T , and ρ being the vector of original degrees of vertices in S w.r.t. the tree T .
Definition 15 (Good State Trees). A good state tree is a full binary tree τ of depth at most h, where every node p is associated with a state (r p , S p , ρ p ), and every leaf o is associated with either an edge e o ∈ E or a triple ξ o such that the following conditions hold.
(15a) r root(τ ) , S root(τ ) = (r, {r}).
(15b) For any leaf o of τ , either e o or ξ o agrees with ρ o . (15c) For an internal node p in τ , letting q and o be the left and right children of p, then the pair ((r q , S q ), (r o , S o )) is an allowable child-pair of (r p , S p ) (so, r q = r p = r o ), and ρ q and ρ o are consistent with ρ p .
We say that a terminal t ∈ K is involved in a good state tree τ if there exists a leaf o of τ with t = head(e o ), or t ∈ {second(ξ o ), third(ξ o )}.
Reduction to Finding Good State-Trees
In this section, we show that the decomposition tree of the optimum tree T * can be turned into a good state tree τ * with desired properties. The procedure in the proof of the following lemma is only for the analysis purpose and is not a part of our algorithm.
Lemma 16. There is a good state-tree τ * involving all terminals with cost(τ * ) = cost(T * ).
Proof. As we alluded, the state tree τ * is constructed by taking the state for each node in the decomposition tree for T * . Formally, it is obtained by calling gen-state-tree(T * ) (defined in Algorithm 1). In the algorithm ρ T * is the vector of original degrees of all vertices in T * .
Algorithm 1 gen-state-tree(T ).
1: create a node p with r p = root(T ), S p = portals of T and ρ p being ρ T * restricted to S p 2: if T has only 1 level of edges then 3:
if T contains a single edge e then let e p = e and return the single node p 4:
otherwise, T contains two edges (r , v) and (r , v ), let ξ p = (r , v, v ) and return p 5: apply balanced tree partitioning to decompose T into T 1 and T 2 6: τ 1 ← gen-state-tree(T 1 ), τ 2 ← gen-state-tree(T 2 ) 7: return the tree τ obtained by combining p, τ 1 and τ 2 with edges (p, root(τ 1 )) and (p, root(τ 2 )), with root(τ 1 ) and root(τ 2 ) being the left and right children of p respectively
We first show that τ * is a good state tree, by showing that it satisfies all the properties in Definition 15. Property (15a) trivially holds by the way we define the parameters for the root recursion of gen-state-tree. Property (15b) holds by that each ρ p is ρ T * restricted to S p . Property (15c) follows from the same facts and Claim 10. cost(τ * ) = e∈E T * c e = cost(T * ) since every edge in T * is counted exactly once in τ * .
Now we focus on the other direction of the reduction and prove the following lemma:
Lemma 17. Given a good state tree τ , we can efficiently construct a good multi-tree T with cost(T ) = cost(τ ). Moreover, if a terminal t ∈ K is involved in τ , then T contains a copy of t.
Proof. The multi-tree T is constructed by joining the edges associated with all leaf nodes o in τ using a recursive procedure. For each node p in τ , we shall construct a multi-tree T p for p, as well as a mapping π p from S p to vertices in T p . The multi-tree T p and the mapping π p satisfy the following properties:
In particular, the two properties imply that root(T p ) is a copy of r p .
The trees and mappings are constructed from the bottom to the top of the tree τ . Focus on a leaf node p with e p = (r , v). If e p is defined, then T p only contains a copy of the edge (r , v). π p maps r to the copy of r , and if v / ∈ K (thus, v ∈ S p ), v to the copy of v in T p . Otherwise ξ p is defined. Then T p contains a tree with two edges: a copy of (r p , second(ξ p )) and a copy of (r p , third(ξ p )). π p can also be defined naturally. Now consider the case that p is an internal node and let q and o be its left and right children. Then, we have r p = r q , r o / ∈ S p , S q ∪ S o = S p ∪ {r o } and S q ∩ S o = {r o } by Property (15c). Then we identify π q (r o ) with π o (r o ) = root(T o ), and then the multi-tree T p is the new tree containing vertices in T q and T o . Notice that both π q (r o ) and π o (r o ) are copies of r o ; thus, the obtained T p can be well-defined. The mapping π p is just the combination of π q and π o : For a vertex v ∈ S q , let π p (v) = π q (v); for a vertex v ∈ S o , let π p (v) = π o (v); since S q ∩ S o = {r o } and we identified π q (r o ) with π o (r o ), the mapping is well-defined. Also, it is easy to see that (P1) and (P2) holds for T p and π p .
Our final multi-tree for τ will be T = T root(τ ) . It is straightforward to see that if t ∈ K is involved in τ , then T contains a copy of t. Notice that all the ρ p -vectors are consistent with each other, and for every leaf o, e o or o agrees with ρ o . Thus, aggregating all the ρ p vectors will recover the vector ρ T of original degrees of vertices in ρ T . So, the multi-tree T is good since every
Finally, the running time of the algorithm is polynomial in the size of the state-tree τ .
Finding a Good State Tree using LP Rounding
With the relationship between good multi-trees and good state trees established, we can now focus on the problem of finding a good state-tree of small cost involving many terminals. We shall construct a quasi-polynomial sized tree T • so that every good state-tree τ corresponds to a sub-tree T of T • satisfying some property. Roughly speaking, T • is the "super-set" of all potential good state-trees τ . However, since the consistency conditions are defined over three states for a parent and its two children, it is more convenient to insert a "virtual" node between every internal node and its two children. Also, it is convenient to break a leaf state node o into two nodes, one containing the state information and the other containing e o or ξ o . Formally, for a good state-tree τ , we construct a correspondent tree T as follows.
1. Let T be a copy of τ . All nodes in T are called state nodes. 2. For every internal state node p in T with left and right children p 1 and p 2 , we create a virtual node q and replace the two edges (p, p 1 ) and (p, p 2 ) with 3 edges (p, q), (q, p 1 ) and (q, p 2 ); p 1 is still the left child and p 2 is the right child. 3. For every leaf state node p, we create a base node o and let o be the child of p. Then we move the e p or ξ p information from the node p to node o: If e p is defined, then we let e o = e p and undefine e p ; otherwise, let ξ o = ξ p and undefine ξ p . 4. We add a super node r and an edge from r to the root of T. r will be the new root for T.
We call this T the extended state-tree for τ ; we say T is good if its correspondent τ is good. Clearly, there is a 1-to-1 correspondence between good state trees and good extended trees. Our T • will be the "super-set" of all potential good extended state trees T. Formally, we create a super node r to be the root of T • . Then, for every ρ r ∈ [1, d r ], we call cnstr-T • (0, r, {r}, ρ = (ρ r )) to obtain a tree and let its root be a child of r.
1: create a state node p with (r p , S p , ρ p ) = (r , S, ρ) 2: for every (r , v) ∈ E such that {r , v} \ K = S and (r , v) agrees with ρ do for every allowable child-pair ((r , S 1 ), (r , S 2 )) of (r , S) do 10:
for every pair of degree vectors ρ 1 for S 1 and ρ 2 for S 2 such that ρ 1 and ρ 2 are consistent with ρ do 11: create a "virtual node" q and let q be a child of p 12:
let the left and right sub-trees of q be T 1 and T 2 respectively 15: return the tree T rooted at p
The following claim is immediate from the construction of T • . Claim 18. A subtree T of T • with root(T) = root(T • ) is a good extended state tree if and only if the following happens:
The super node in T has exactly one child (which is a state node). Each state node in T has exactly one child (which is a base node or a virtual node).
For each virtual node q in T, both q's children in T • are in T. On the other hand, every good extended tree T of depth at most h + 1 is a sub-tree of T • with root being root(T • ). Also, we say that a vertex v is involved in T if there is a base node o in T with v = head(e o ) or v ∈ {second(ξ o ), third(ξ o )}. The cost of T, denoted as cost(T), is defined as the sum of c(o) over all base nodes in T. So, the problem now becomes finding a small-cost good extended state tree in T • that involves each terminal with large probability.
We formulate an LP relaxation for our task. Let V • be the set of nodes in T • , r = root(T • ) and let V • state , V • virt and V • base be the sets of state, virtual and base nodes in T • respectively. Notice that there is only one super node, which is the root r. For every v ∈ V , let
, third(ξ o )}} be the set of base nodes involving v. Let T * be our target good extended state tree; this is the tree correspondent to the good state tree τ * . Then, in our LP, we have a variable x p for every p ∈ V • , that indicates whether p is in the T * or not. min
(1)
(2)
The objective function of LP ( 1) is to minimize the total cost of all leaves in T * . Constraint (2) requires that for every state or super node p in T * , exactly one child of p is in T * . Constraint (3) requires that a virtual node q in T * has both its children in T * . Constraint (5) says for every node p in T * and every terminal t ∈ K, there is a most one descendant base node o of p that is in O t . In the whole tree T * , exactly one leaf node o has t = head(e o ) or t ∈ {second(ξ o ), third(ξ o )}, for every t ∈ K (Constraint (6)); in the LP, all the variables are between 0 and 1 (Constraint (4)).
Notice that (5) for p = r and any t ∈ K and (6) for the same t imply that x r = 1. Constraint ( 2) and (3) imply that the x values over the nodes of a root-to-leaf path in T • are non-increasing.
Given a valid solution x to LP (1), our rounding algorithm will round it to obtain the set V ⊆ V • , which induces a good state tree. The algorithm is very similar to that of [9] with the only one difference: For every state node or super-node p that is added to V, we add exactly one child q of p to V, while the algorithm of [9] makes independent decisions for each child. The algorithm is formally described in Algorithm 3. In the main algorithm, we simply call round(r). It is straightforward to see that the tree induced by round(r) is a good extended state tree. The following claim also holds:
Let V be the random set returned by round(p). Then we have Pr[q ∈ V] = xq xp . Applying the above claim for p = r and every q ∈ V • base , we have that the expected cost of the tree induced by V is exactly cost(x).
The main theorem we need about the rounding algorithm is as follows:
randomly choose a child q of p according to probability vector
return {p} ∪ round(left child of p) ∪ round(right child of p) 6: else return {p} Theorem 20. Let V be the random set returned by round(r). Then, for any terminal
h+1 . Theorem 20 was proved [9] for the original rounding algorithm and was reproved in [23]. However, adapting the analysis to our slightly different rounding algorithm is straightforward and thus we omit the proof of the theorem here.
We now wrap up and finish the proof of the main theorem (Theorem 6) except for Property (6c), of which the proof is deferred to Appendix A due to the space constraint. We solve LP(1) to obtain a solution x. Notice that cost(x) ≤ cost(T * ) = cost(τ * ) = cost(T * ). Let V ← round(r). Then by Claim 18 and the rounding algorithm, the tree T induced by V is a good extended state tree. Let τ be the good state tree correspondent to T, and let T be the good multi-tree in G constructed using the procedure in Section 4.2. The cost of the multi-tree T is at most cost(x). By Theorem 20, for every t ∈ K, the probability that t is involved T is at least 1/(h + 1) = Ω(1/ log n).
Let us consider the running time of the algorithmic framework, which is polynomial on the size of the tree T • . First notice that if ((r , S 1 ), (r , S 2 )) is an allowable child pair of (r , S), then we have |S 1 |, |S 2 | ≤ |S| + 1 since S 1 ∪ S 2 = S ∪ {r }. Thus, a state-node p at the h -th level in T • (the children of r have level 0 and for simplicity we do not consider super and virtual nodes when counting levels) has |S p | ≤ h + 1. Thus, every state node p in
Then we consider the degree of the tree T • , which is the maximum number of possible children of a state node p with (r p , S p , ρ p ) = (r , S, ρ). First, there are at most n × 2 |Sp| ≤ n • 2 h+1 different allowable child pairs ((r , S 1 ), (r , S 2 )) of the pair (r , S): there are at most n choices for r and 2 h ways to split S into S 1 and S 2 . Then, for a fixed allowable child pair ((r , S 1 ), (r , S 2 )), we consider the number of pairs of degree vectors ρ 1 , ρ 2 such that ρ 1 and ρ 2 are consistent with ρ. This is determined by the value of ρ 1 r = ρ 2 r , which has at most d max possibilities. So, the number of virtual children of a state node is at most n O(log n) . So the running time of the LP rounding algorithm is n O(log n) . This finishes the proof of Theorems 6 except for Property (6c), whose is deferred to Appendix A.
In this section, we prove Theorem 2, which is repeated here.
Theorem 2. There is a randomized O(log n log k), O(log n) -bicriteria approximation for the degree-bounded group Steiner tree problem on trees.
We first set up some notations for the theorem. Recall that T • is the input tree, V • denotes the set of vertices of T • , and r denotes the root of T • . For simplicity, we assume the costs are on the vertices instead of edges: Every vertex u ∈ V • has a cost c u ≥ 0. Notice that this does not change the problem. We have k groups indexed by [k]. For each group t ∈ [k], we are given a set O t ⊆ V • of leaves in T • . W.l.o.g, we assume all O t 's are disjoint. Every vertex v ∈ V is given a degree bound D v . The goal of the problem is then to output the smallest cost subtree T of T • that satisfies the degree constraints and contains the root r and one vertex from each O t , t ∈ [k]. Since now we only have one tree T • , we use the following notations for children and descendants: For every vertex u ∈ V • , let Λ u denote the set of children of u in T • , and Λ * u to denote the set of descendants of u in T • (including u itself). Now we describe the LP relaxation we use for our problem. For every vertex u ∈ T • , we use x u to indicate whether u is chosen or not (in the correspondent integer program). LP ( 7) is a valid LP relaxation for the DB-GST-T problem:
In the correspondent integer program, the objective we try to minimize is u∈V • c u x u , i.e, the total cost of all verticies we choose. Constraint (8) says that if we choose a vertex v, then we must choose its parent u. Constraint (9) requires for every group t, exactly one vertex in O t is added to the tree. Constraint (10) holds since if u is chosen, at most one vertex in Λ * u ∩ O t is chosen for every group t. Constraint (11) is the degree constraint. In the LP relaxation, we require each x u to take value in [0, 1] (Constraint ( 12)). Notice that (9) and (10) for the root r imply that x r = 1.
Modifying the LP solutions. Solving LP (7), we can obtain an optimum LP solution (x u ) u∈V • . In our rounding algorithm, it would be convenient if every x u is a (non-positive) integer power of 2 that is not too small. So, we shall modify the LP solution using the following operations, which may violate many of the LP constraints slightly. For every v ∈ V • with x v < 1 2n , we change x v to 0. This can only decrease the cost of the solution. It is easy to see that Constraints (8), ( 10) and (11) will not be violated. Constraint (9) may not hold any more, but we still have
We can remove all vertices v with x v = 0 from the instance and thus assume x v ≥ 1 2n for every v ∈ V • . Next, we increase each x v to the smallest (non-positive) integer power of 2 that is greater than or equal to x v . This will violate many constraints in the LP by a factor of 2. We list the properties that our new vector (x u ) u∈V • has: (P1) For every u ∈ V • , x u is an integer power of 2 between 1 2n and 1. (P2) The x values along any root-to-leaf path in
(P4)
where opt is the cost of the optimum integer solution.
We now describe our rounding algorithm. We define two important global parameters: L := log(2n) and γ := log L -2. We say an edge (u, v) with v ∈ Λ u has "hop value" 1 if x u < x v and 0 if x u = x v . For every vertex u ∈ V • , we define u to be the sum of hop values over all edges in the path from the root to u in T • . Thus, for every u ∈ V • and v ∈ Λ u , we have vu ∈ {0, 1}, and v = u if and only if x v = x u . By Properties (P1) and (P2), we have that v ∈ [0, L] for every v ∈ V • .
Our rounding algorithm is applied on some scaled solution x , which is defined as follows:
x u = 2 min{ u ,γ} x u , for every u ∈ V • .
As we mentioned in the introduction, this change will increase the probability of choosing v conditioned on choosing u by a factor of 2, for some
We prove one important property for x , which is necessary for us to run the recursive rounding algorithm.
Claim 21. For every u ∈ V • and v ∈ Λ u , we have x v ≤ x u .
Proof. If x v = x u , then the edge (u, v) has hop value 0 and thus v = u . In this case we have x v = x u as well. Otherwise, we have x v ≤ x u /2 and h v = h u + 1. So, min {h v , γ} ≤ min {h u , γ} + 1 and therefore x v ≤ x u .
Notice that x r = 1 and every x v is an integer power of 2 between 2 -L and 1. Our recursive rounding algorithm is run over x . In the procedure recursive-rounding(u), we add u to our output tree and do the following: for every v ∈ Λ u , with probability x v /x u independent of all other choices, we call recursive-rounding(v). In the root recursion, we shall call recursive-rounding(r).
Our final algorithm will repeat the recursive procedure M times independently, for a large enough M = O(log k). Let T 1 , T 2 , • • • , T M be the M trees we obtained from the M repetitions. Our final tree T will be the union of the M trees.
We first analyze the expected cost of T . First focus on the tree T 1 . It is easy to see that the probability u is chosen by T 1 is exactly x u ≤ 2 γ x u = O(L)x u . Therefore, the expected cost of T 1 is at most O(L) • opt by Property (P6). Therefore, the expected cost of the tree T is at most
We then analyze the degree constraints on T . Given that u is selected by T 1 , the probability that we select a child of v of u is
xu . By Property (P5), we have
Even if we condition on the event that u appears in all the M trees, the degree of u is the summation of many independent random {0, 1}-variables. The expectation of the summation is at most
Using Chernoff bound, one can show that the probability that the degree of u is more than O(log n) • d u is at most 1 10n , for some large enough O(log n) factor. Therefore, with probability at least 0.9, every node u in T has degree at most O(log n) • d u . Therefore, we proved that the degree violation factor of our algorithm is O(log n), as claimed in Theorem 2.
It remains to show that with high probability, the tree T contains a vertex from every group. This is the goal of this section. Till the end of the section, we focus on the tree T 1 and a fixed group t. For every vertex u ∈ V • , we define E u to be the event that u is chosen by T 1 . Our goal is to give a lower bound on Pr[ o∈Ot E o ], i.e., the probability that some vertex in O t is chosen by the tree T 1 .
Notice that when two adjacent nodes in T • have the same x value, then the child is chosen whenever the parent is. Thus, we can w.l.o.g contract any sub-tree of nodes in T • with the same x value into one single super-vertex, without changing the rounding algorithm. Notice that if two adjacent vertices u ∈ V • , v ∈ Λ u have u = v , then we have x u = x v and thus x u = x v . So, we contract every maximal sub-tree of vertices in T • with the same value. After this operation, for every u ∈ V • , u is exactly the level of u in the tree T
we can remove all its descendants without changing the analysis in this section. So, again we have that O t only contains leaves.
For every vertex u, we define z u := o∈Ot∩Λ * u x o . Notice that z u ≤ 2x u by Property (P4). In the following, we shall bound Pr o∈Ot∩Λ * u E o E u for every u ∈ V • from bottom to top. This is done in two stages due to the threshold γ we used when we define x variables. First we consider the case when u ≥ γ and then we focus on the case when u < γ. The two stages are captured by Lemmas 22 and 23 respectively.
Lemma 22. For a vertex u with u ≥ γ, we have Pr
Similar lemmas have been proved multiple times in many previous results. Since our parameters are slightly different, we provide the complete proof in Appendix B. The lemma implies that for every u with u ≥ γ, we have Pr 2L and for every ∈ [0, γ -1], define α = 2α +1 -4α 2 +1 . It is easy to see that for every ∈ [0, γ], we have α ≤ 2 γ- 2L . Then, we have for every
Therefore, we have
The second inequality used that 1 -θ ≥ e -2θ for every θ ∈ (0, 1/2). The last equality used that γ = log L -2 and thus 2 γ = Θ(L).
With the α values defined, we also have the following lemma for the case when u ≤ γ:
Lemma 23. For every vertex u = ≤ γ, we have Pr
The proof of this lemma is deferred to Appendix B. Applying the lemma for the root r of T • , we have that Pr As is typical, we shall introduce a parameter s > 0 and consider the expectation the random exponential variables e smp (we use e for the natural constant). We shall bound E[e smp |p ∈ V] from bottom to top by induction. So, in this proof, it is more convenient to for us to use a different definition of levels: the level of a node p in T • is the maximum number of edges in a path in T • starting from p. So, the leaves have level 0 and for an internal node p in T • , the level of p is 1 plus the maximum of the level of q over all children q of p. We define an α i for every integer i ≥ 0 as α 0 = e s and α i = e αi-1-1 , ∀i ≥ 1. Notice that α 0 , α 1 , . . . is an increasing sequence. Thus, we can induce the following lemma.
Lemma 24. For any node p in T • of level at most i, E e smp p ∈ V ≤ α zp/xp i . Proof. We prove the lemma by induction on i. If i = 0, then p is a leaf, and thus, we have either z p = 0 or z p = x p , depending on whether p ∈ O v or not. If z p = 0, then m p is always 0, and thus, E e smp p ∈ V = 1 = α zp/xp 0 . If z p = x p , then m p is always 1 (conditioned on p ∈ V), and thus, E e smp p ∈ V = e s = α zp/xp 0 . So, the lemma holds if i = 0. Now, let i ≥ 1 be any integer and we assume the lemma holds for i -1. We shall prove that it also holds for i. Focus on a node p of level at most i. Then all children q of p have level at most i -1. If p is a virtual node, then p ∈ V implies that both children of p in V. Since the two children are handled independently in the rounding algorithm, we have
If p is the super node or a state node, then we have q∈Λ T • (p) x q = x p . Conditioned on p ∈ V, the rounding procedure adds exactly one child q of p to V. Then, we have
x q
x p E e smq q ∈ V = 1 + q∈Λ T • (p)
x q
x p E[e smq q ∈ V] -1
Thus, we always have To see the second inequality in the last line, we notice the following three facts: (i) α θ i-1 -1 is a convex function of θ and when θ = 0 its value is 0, (ii) z q /x q ∈ [0, 1] for every q in the summation, and (iii) i-1 -1). The equality in the last line is by the definition of α i .
Let h = Θ(h) = Θ(log n) be the level of the root. Now, we set s = ln(1 + 1 2h ). We prove inductively the following lemma: Lemma 25. For every i ∈ [0, h ], we have α i ≤ 1 + 1 2h -i .
The inequality in the first line used the induction hypothesis:
is the probability that we choose v in T 1 conditioned on that we choose u, and 1 2(L-) zv xv is the lower bound on the probability that we choose some vertex in O t ∩ Λ * v conditioned on that v is chosen. The equality in the line used that x u = 2 γ x u and x v = 2 γ x v . The inequality in the second line used that 1 -θ ≤ e -θ for every real number θ. The first inequality in the third line used that e -θ ≤ 1 -θ + θ 2 2 for every θ ≥ 0. The second inequality in the line used Property 4, which says zu xu ≤ 2. The last inequality used that (2(L -) -1) • 2(L -+ 1) ≥ 4(L -) 2 since L -≥ 1.
Lemma 23. For every vertex u = ≤ γ, we have Pr
Proof. We prove this lemma via mathematical induction. The lemma holds if = γ as we mentioned. So, we assume < γ and the lemma holds with replaced by + 1. If u is a leaf, then we have Pr
xu and the lemma holds. So, again we assume u is not a leaf. Then,
To see the equality in the first line, we notice that x u = 2 x u and x v = 2 +1 x v for every v ∈ Λ u . Many other inequalities used the same arguments as in Lemma 22.
[12] mistakenly called u the head and v the tail. We follow the common convention to call v the head.