Bundit Laekhanukit
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Research Subjects
Bundit Laekhanukit has a total of 59 co-authors. Here are the top co-authors by number of shared publications:
Danupon Nanongkai
7 shared publicationsParinya Chalermsook
7 shared publications- Danupon Nanongkai
MPI-INF Germany
5 shared publications - Guy Kortsarz
Computer Science, Rutgers University, Camden, USA
4 shared publications - Jittat Fakcharoenphol
Kasetsart University, Bangkok, Thailand
4 shared publications - Shi Li
Nanjing University, Nanjing, China
4 shared publications
Latest Publications
- Open Access
- 23 April 2026
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 73 (2) , 1-23
Survivable Network Design with Group-to-Group Requirement
In the classical survivable network design problem (SNDP), we are given an undirected graph G=(V,E) with costs on edges and a connectivity requirement k(s,t) for each pair of vertices. The goal is to find a minimum-cost subgraph H⊆ G such that every pair (s,t) is connected by k(s,t) edge or (openly) vertex disjoint paths, abbreviated as EC-SNDP and VC-SNDP, respectively. The seminal result of Jain [FOCS’98, Combinatorica’01] gives a 2-approximation algorithm for EC-SNDP, and a decade later, an O(k 3 log n )-approximation algorithm for VC-SNDP, where k is the largest connectivity requirement, was discovered by Chuzhoy and Khanna [FOCS’09, Theory Comput.’12]. While there is a rich literature on point-to-point settings of SNDP, the viable case of connectivity between subsets is still relatively poorly understood. This article concerns the generalization of EC-SNDP into the subset-to-subset setting, namely Group EC-SNDP. We develop a framework, which yields the first non-trivial (true) approximation algorithm for Group EC-SNDP. Previously, only a bicriteria approximation algorithm is known for Group EC-SNDP [Chalermsook, Grandoni, and Laekhanukit, SODA’15], and a true approximation algorithm is known only for the single-source variant with connectivity requirement k(S,T) ∈ { 0,1,2} [Gupta, Krishnaswamy, and Ravi, SODA’10; Khandekar, Kortsarz, and Nutov, FSTTCS’09 and Theor. Comput. Sci.’12]. On the negative side, in terms of the number of connectivity demands q , we give an Ω (q /log q )-hardness result for large k , complementing the previous inapproximability results, e.g., hardness in terms of k : k 1/5-ɛ -hardness [Cheriyan et al., SODA’12; Laekhanukit, SODA’14; Chalermsook et al., SODA’15; Manurangsi, IPL’19]; hardness in terms of n : 2 log 1-ɛ n -hardness [Chalermsook et al., SODA’15].
- 23 April 2026
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 73 (2) , 1-23
Open AccessSurvivable Network Design with Group-to-Group Requirement
In the classical survivable network design problem (SNDP), we are given an undirected graph G=(V,E) with costs on edges and a connectivity requirement k(s,t) for each pair of vertices. The goal is to find a minimum-cost subgraph H⊆ G such that every pair (s,t) is connected by k(s,t) edge or (openly) vertex disjoint paths, abbreviated as EC-SNDP and VC-SNDP, respectively. The seminal result of Jain [FOCS’98, Combinatorica’01] gives a 2-approximation algorithm for EC-SNDP, and a decade later, an O(k 3 log n )-approximation algorithm for VC-SNDP, where k is the largest connectivity requirement, was discovered by Chuzhoy and Khanna [FOCS’09, Theory Comput.’12]. While there is a rich literature on point-to-point settings of SNDP, the viable case of connectivity between subsets is still relatively poorly understood. This article concerns the generalization of EC-SNDP into the subset-to-subset setting, namely Group EC-SNDP. We develop a framework, which yields the first non-trivial (true) approximation algorithm for Group EC-SNDP. Previously, only a bicriteria approximation algorithm is known for Group EC-SNDP [Chalermsook, Grandoni, and Laekhanukit, SODA’15], and a true approximation algorithm is known only for the single-source variant with connectivity requirement k(S,T) ∈ { 0,1,2} [Gupta, Krishnaswamy, and Ravi, SODA’10; Khandekar, Kortsarz, and Nutov, FSTTCS’09 and Theor. Comput. Sci.’12]. On the negative side, in terms of the number of connectivity demands q , we give an Ω (q /log q )-hardness result for large k , complementing the previous inapproximability results, e.g., hardness in terms of k : k 1/5-ɛ -hardness [Cheriyan et al., SODA’12; Laekhanukit, SODA’14; Chalermsook et al., SODA’15; Manurangsi, IPL’19]; hardness in terms of n : 2 log 1-ɛ n -hardness [Chalermsook et al., SODA’15].
- Open Access
- 4 November 2024
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Algorithms
- Vol. 21 (1) , 1-9
Polynomial Integrality Gap of Flow LP for Directed Steiner Tree
In the Directed Steiner Tree (DST) problem, we are given a directed graph \(G=(V,E)\) on \(n\) vertices with edge-costs \(c\in{\mathbb{R}}_{\geq 0}^{E}\) , a root vertex \(r\in V\) , and a set \(K\subseteq V\setminus\{r\}\) of \(k\) terminals. The goal is to find a minimum-cost subgraph of \(G\) that contains a path from \(r\) to every terminal \(t\in K\) . DST has been a notorious problem for decades as there is a large gap between the best-known polynomial-time approximation ratio of \(O(k^{\epsilon})\) for any constant \(\epsilon \gt 0\) , and the best quasi-polynomial-time approximation ratio of \(O\left(\frac{\log^{2}k}{\log\log k}\right)\) . Toward understanding this gap, we study the integrality gap of the standard flow linear programming relaxation for the problem. We show that the linear program (LP) has an integrality gap of \(\Omega(n^{0.0418})\) . Previously, the integrality gap of the LP is only known to be \(\Omega\left(\frac{\log^{2}n}{\log\log n}\right)\) [Halperin et al., SODA’03 & SIAM J. Comput.] and \(\Omega(\sqrt{k})\) [Zosin-Khuller, SODA’02] in some instance with \(\sqrt{k}=O\left(\frac{\log n}{\log\log n}\right)\) . Our result gives the first known lower bound on the integrality gap of this standard LP that is polynomial in \(n\) , the number of vertices. Consequently, we rule out the possibility of developing a poly-logarithmic approximation algorithm for the problem based on the flow LP relaxation.- 4 November 2024
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Algorithms
- Vol. 21 (1) , 1-9
Open AccessPolynomial Integrality Gap of Flow LP for Directed Steiner Tree
In the Directed Steiner Tree (DST) problem, we are given a directed graph \(G=(V,E)\) on \(n\) vertices with edge-costs \(c\in{\mathbb{R}}_{\geq 0}^{E}\) , a root vertex \(r\in V\) , and a set \(K\subseteq V\setminus\{r\}\) of \(k\) terminals. The goal is to find a minimum-cost subgraph of \(G\) that contains a path from \(r\) to every terminal \(t\in K\) . DST has been a notorious problem for decades as there is a large gap between the best-known polynomial-time approximation ratio of \(O(k^{\epsilon})\) for any constant \(\epsilon \gt 0\) , and the best quasi-polynomial-time approximation ratio of \(O\left(\frac{\log^{2}k}{\log\log k}\right)\) . Toward understanding this gap, we study the integrality gap of the standard flow linear programming relaxation for the problem. We show that the linear program (LP) has an integrality gap of \(\Omega(n^{0.0418})\) . Previously, the integrality gap of the LP is only known to be \(\Omega\left(\frac{\log^{2}n}{\log\log n}\right)\) [Halperin et al., SODA’03 & SIAM J. Comput.] and \(\Omega(\sqrt{k})\) [Zosin-Khuller, SODA’02] in some instance with \(\sqrt{k}=O\left(\frac{\log n}{\log\log n}\right)\) . Our result gives the first known lower bound on the integrality gap of this standard LP that is polynomial in \(n\) , the number of vertices. Consequently, we rule out the possibility of developing a poly-logarithmic approximation algorithm for the problem based on the flow LP relaxation. - 28 July 2022
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 52 (2) , STOC19-298
$O(\log^2{k}/\log\log{k})$-Approximation Algorithm for Directed Steiner Tree: A Tight Quasi-Polynomial Time Algorithm
In the directed Steiner tree (DST) problem, we are given an $n$-vertex directed edge-weighted graph, a root $r$, and a collection of $k$ terminal nodes. Our goal is to find a minimum-cost subgraph ...- 28 July 2022
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 52 (2) , STOC19-298
$O(\log^2{k}/\log\log{k})$-Approximation Algorithm for Directed Steiner Tree: A Tight Quasi-Polynomial Time Algorithm
In the directed Steiner tree (DST) problem, we are given an $n$-vertex directed edge-weighted graph, a root $r$, and a collection of $k$ terminal nodes. Our goal is to find a minimum-cost subgraph ...- Open Access
Survivable Network Design Revisited: Group-Connectivity
In the classical survivable network design problem (SNDP), we are given an undirected graph $G=(V,E)$ with costs on edges and a connectivity requirement $k(s,t)$ for each pair of vertices. The goal is to find a minimum-cost subgraph $H\subseteq V$ such that every pair $(s,t)$ are connected by $k(s,t)$ edge or (openly) vertex disjoint paths, abbreviated as EC-SNDP and VC-SNDP, respectively. The seminal result of Jain [FOCS'98, Combinatorica'01] gives a $2$-approximation algorithm for EC-SNDP, and a decade later, an $O(k^3\log n)$-approximation algorithm for VC-SNDP, where $k$ is the largest connectivity requirement, was discovered by Chuzhoy and Khanna [FOCS'09, Theory Comput.'12]. While there is rich literature on point-to-point settings of SNDP, the viable case of connectivity between subsets is still relatively poorly understood. This paper concerns the generalization of SNDP into the subset-to-subset setting, namely Group EC-SNDP. We develop the framework, which yields the first non-trivial (true) approximation algorithm for Group EC-SNDP. Previously, only a bicriteria approximation algorithm is known for Group EC-SNDP [Chalermsook, Grandoni, and Laekhanukit, SODA'15], and a true approximation algorithm is known only for the single-source variant with connectivity requirement $k(S,T)\in\{0,1,2\}$ [Gupta, Krishnaswamy, and Ravi, SODA'10; Khandekar, Kortsarz, and Nutov, FSTTCS'09 and Theor. Comput. Sci.'12].Open AccessSurvivable Network Design Revisited: Group-Connectivity
In the classical survivable network design problem (SNDP), we are given an undirected graph $G=(V,E)$ with costs on edges and a connectivity requirement $k(s,t)$ for each pair of vertices. The goal is to find a minimum-cost subgraph $H\subseteq V$ such that every pair $(s,t)$ are connected by $k(s,t)$ edge or (openly) vertex disjoint paths, abbreviated as EC-SNDP and VC-SNDP, respectively. The seminal result of Jain [FOCS'98, Combinatorica'01] gives a $2$-approximation algorithm for EC-SNDP, and a decade later, an $O(k^3\log n)$-approximation algorithm for VC-SNDP, where $k$ is the largest connectivity requirement, was discovered by Chuzhoy and Khanna [FOCS'09, Theory Comput.'12]. While there is rich literature on point-to-point settings of SNDP, the viable case of connectivity between subsets is still relatively poorly understood. This paper concerns the generalization of SNDP into the subset-to-subset setting, namely Group EC-SNDP. We develop the framework, which yields the first non-trivial (true) approximation algorithm for Group EC-SNDP. Previously, only a bicriteria approximation algorithm is known for Group EC-SNDP [Chalermsook, Grandoni, and Laekhanukit, SODA'15], and a true approximation algorithm is known only for the single-source variant with connectivity requirement $k(S,T)\in\{0,1,2\}$ [Gupta, Krishnaswamy, and Ravi, SODA'10; Khandekar, Kortsarz, and Nutov, FSTTCS'09 and Theor. Comput. Sci.'12]. - Open Access
Almost Tight Approximation Hardness for Single-Source Directed k-Edge-Connectivity
In the $k$-connected directed Steiner tree problem ($k$-DST), we are given an $n$-vertex directed graph $G=(V,E)$ with edge costs, a connectivity requirement $k$, a root $r\in V$ and a set of terminals $T\subseteq V$. The goal is to find a minimum-cost subgraph $H\subseteq G$ that has $k$ internally disjoint paths from the root vertex $r$ to every terminal $t\in T$. In this paper, we show the approximation hardness of $k$-DST for various parameters, which thus close some long-standing open problems. - $\Omega\left(|T|/\log |T|\right)$-approximation hardness, which holds under the standard assumption $\mathrm{NP}\neq \mathrm{ZPP}$. The inapproximability ratio is tightened to $\Omega\left(|T|\right)$ under the Strongish Planted Clique Hypothesis [Manurangsi, Rubinstein and Schramm, ITCS 2021]. The latter hardness result matches the approximation ratio of $|T|$ obtained by a trivial approximation algorithm, thus closing the long-standing open problem. - $\Omega\left(\sqrt{2}^k / k\right)$-approximation hardness for the general case of $k$-DST under the assumption $\mathrm{NP}\neq\mathrm{ZPP}$. This is the first hardness result known for survivable network design problems with an inapproximability ratio exponential in $k$. - $\Omega\left((k/L)^{L/4}\right)$-approximation hardness for $k$-DST on $L$-layered graphs for $L\le O\left(\log n\right)$. This almost matches the approximation ratio of $O(k^{L-1}\cdot L \cdot \log |T|)$ achieving in $O\left(n^L\right)$-time due to Laekhanukit [ICALP`16].Open AccessAlmost Tight Approximation Hardness for Single-Source Directed k-Edge-Connectivity
In the $k$-connected directed Steiner tree problem ($k$-DST), we are given an $n$-vertex directed graph $G=(V,E)$ with edge costs, a connectivity requirement $k$, a root $r\in V$ and a set of terminals $T\subseteq V$. The goal is to find a minimum-cost subgraph $H\subseteq G$ that has $k$ internally disjoint paths from the root vertex $r$ to every terminal $t\in T$. In this paper, we show the approximation hardness of $k$-DST for various parameters, which thus close some long-standing open problems. - $\Omega\left(|T|/\log |T|\right)$-approximation hardness, which holds under the standard assumption $\mathrm{NP}\neq \mathrm{ZPP}$. The inapproximability ratio is tightened to $\Omega\left(|T|\right)$ under the Strongish Planted Clique Hypothesis [Manurangsi, Rubinstein and Schramm, ITCS 2021]. The latter hardness result matches the approximation ratio of $|T|$ obtained by a trivial approximation algorithm, thus closing the long-standing open problem. - $\Omega\left(\sqrt{2}^k / k\right)$-approximation hardness for the general case of $k$-DST under the assumption $\mathrm{NP}\neq\mathrm{ZPP}$. This is the first hardness result known for survivable network design problems with an inapproximability ratio exponential in $k$. - $\Omega\left((k/L)^{L/4}\right)$-approximation hardness for $k$-DST on $L$-layered graphs for $L\le O\left(\log n\right)$. This almost matches the approximation ratio of $O(k^{L-1}\cdot L \cdot \log |T|)$ achieving in $O\left(n^L\right)$-time due to Laekhanukit [ICALP`16]. - 24 January 2022
- Published by Springer Nature in Algorithmica
- Vol. 84 (5) , 1252-1278
On Approximating Degree-Bounded Network Design Problems
- 24 January 2022
- Published by Springer Nature in Algorithmica
- Vol. 84 (5) , 1252-1278
On Approximating Degree-Bounded Network Design Problems
- Open Access
On the Approximability of the Traveling Salesman Problem with Line Neighborhoods
We study the variant of the Euclidean Traveling Salesman problem where instead of a set of points, we are given a set of lines as input, and the goal is to find the shortest tour that visits each line. The best known upper and lower bounds for the problem in $\mathbb{R}^d$, with $d\ge 3$, are $\mathrm{NP}$-hardness and an $O(\log^3 n)$-approximation algorithm which is based on a reduction to the group Steiner tree problem. We show that TSP with lines in $\mathbb{R}^d$ is APX-hard for any $d\ge 3$. More generally, this implies that TSP with $k$-dimensional flats does not admit a PTAS for any $1\le k \leq d-2$ unless $\mathrm{P}=\mathrm{NP}$, which gives a complete classification of the approximability of these problems, as there are known PTASes for $k=0$ (i.e., points) and $k=d-1$ (hyperplanes). We are able to give a stronger inapproximability factor for $d=O(\log n)$ by showing that TSP with lines does not admit a $(2-\epsilon)$-approximation in $d$ dimensions under the unique games conjecture. On the positive side, we leverage recent results on restricted variants of the group Steiner tree problem in order to give an $O(\log^2 n)$-approximation algorithm for the problem, albeit with a running time of $n^{O(\log\log n)}$.Open AccessOn the Approximability of the Traveling Salesman Problem with Line Neighborhoods
We study the variant of the Euclidean Traveling Salesman problem where instead of a set of points, we are given a set of lines as input, and the goal is to find the shortest tour that visits each line. The best known upper and lower bounds for the problem in $\mathbb{R}^d$, with $d\ge 3$, are $\mathrm{NP}$-hardness and an $O(\log^3 n)$-approximation algorithm which is based on a reduction to the group Steiner tree problem. We show that TSP with lines in $\mathbb{R}^d$ is APX-hard for any $d\ge 3$. More generally, this implies that TSP with $k$-dimensional flats does not admit a PTAS for any $1\le k \leq d-2$ unless $\mathrm{P}=\mathrm{NP}$, which gives a complete classification of the approximability of these problems, as there are known PTASes for $k=0$ (i.e., points) and $k=d-1$ (hyperplanes). We are able to give a stronger inapproximability factor for $d=O(\log n)$ by showing that TSP with lines does not admit a $(2-\epsilon)$-approximation in $d$ dimensions under the unique games conjecture. On the positive side, we leverage recent results on restricted variants of the group Steiner tree problem in order to give an $O(\log^2 n)$-approximation algorithm for the problem, albeit with a running time of $n^{O(\log\log n)}$. - Open Access
- 8 July 2020
- Published by Association for Computing Machinery (ACM)
- p. 185-186
Worst-case conditional hardness and fast algorithms with random inputs for non-dominated sorting
We study the computational complexity of the non-dominated sorting problem (NDS): Given a set P of n points in Rm, for each point p ∈ P, compute ℓ, the length of longest domination chain p1 > p2 > ··· > pℓ = p, where x dominates y (denoted as x > y) if x is not larger than y in every coordinate. A special case of NDS, which we label as NDS1, is to find all the non-dominated points in P. NDS has emerged as a critical component for multi-objective optimization problems (MOPs). For m ≤ 3, Θ(n log n)-time is known. For a fixed small m > 3, the best bound is O(n logm-2n log log n). For larger m, the best result is an O(mn2)-time algorithm. We show that the O(mn2) running time is nearly optimal by proving an almost matching conditional lower bound: for any ∈ > 0, and ω(log n) ≤ m ≤ (log n)o(1), there is no O(mn2-ε)-time algorithm for NDS or NDS1 unless a popular conjecture in fine-grained complexity theory is false. To complete our results, we present an algorithm for NDS with an expected running time O(mn + n2/m + n log2n) on uniform random inputs.
- 8 July 2020
- Published by Association for Computing Machinery (ACM)
- p. 185-186
Open AccessWorst-case conditional hardness and fast algorithms with random inputs for non-dominated sorting
We study the computational complexity of the non-dominated sorting problem (NDS): Given a set P of n points in Rm, for each point p ∈ P, compute ℓ, the length of longest domination chain p1 > p2 > ··· > pℓ = p, where x dominates y (denoted as x > y) if x is not larger than y in every coordinate. A special case of NDS, which we label as NDS1, is to find all the non-dominated points in P. NDS has emerged as a critical component for multi-objective optimization problems (MOPs). For m ≤ 3, Θ(n log n)-time is known. For a fixed small m > 3, the best bound is O(n logm-2n log log n). For larger m, the best result is an O(mn2)-time algorithm. We show that the O(mn2) running time is nearly optimal by proving an almost matching conditional lower bound: for any ∈ > 0, and ω(log n) ≤ m ≤ (log n)o(1), there is no O(mn2-ε)-time algorithm for NDS or NDS1 unless a popular conjecture in fine-grained complexity theory is false. To complete our results, we present an algorithm for NDS with an expected running time O(mn + n2/m + n log2n) on uniform random inputs.
- Open Access
- 12 June 2020
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Algorithms
- Vol. 16 (3) , 1-31
Approximating Spanners and Directed Steiner Forest
It was recently found that there are very close connections between the existence of additive spanners (subgraphs where all distances are preserved up to an additive stretch), distance preservers (subgraphs in which demand pairs have their distance preserved exactly), and pairwise spanners (subgraphs in which demand pairs have their distance preserved up to a multiplicative or additive stretch) [Abboud-Bodwin SODA’16 8 J.ACM’17, Bodwin-Williams SODA’16]. We study these problems from an optimization point of view, where rather than studying the existence of extremal instances, we are given an instance and are asked to find the sparsest possible spanner/preserver. We give an O ( n 3/5 + ε )-approximation for distance preservers and pairwise spanners (for arbitrary constant ε > 0). This is the first nontrivial upper bound for either problem, both of which are known to be as hard to approximate as Label Cover. We also prove Label Cover hardness for approximating additive spanners, even for the cases of additive 1 stretch (where one might expect a polylogarithmic approximation, since the related multiplicative 2-spanner problem admits an O (log n )-approximation) and additive polylogarithmic stretch (where the related multiplicative spanner problem has an O (1)-approximation). Interestingly, the techniques we use in our approximation algorithm extend beyond distance-based problem to pure connectivity network design problems. In particular, our techniques allow us to give an O ( n 3/5 + ε )-approximation for the Directed Steiner Forest problem (for arbitrary constant ε > 0) when all edges have uniform costs, improving the previous best O ( n 2/3 + ε )-approximation due to Berman et al. [ICALP’11] (which holds for general edge costs).
- 12 June 2020
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Algorithms
- Vol. 16 (3) , 1-31
Open AccessApproximating Spanners and Directed Steiner Forest
It was recently found that there are very close connections between the existence of additive spanners (subgraphs where all distances are preserved up to an additive stretch), distance preservers (subgraphs in which demand pairs have their distance preserved exactly), and pairwise spanners (subgraphs in which demand pairs have their distance preserved up to a multiplicative or additive stretch) [Abboud-Bodwin SODA’16 8 J.ACM’17, Bodwin-Williams SODA’16]. We study these problems from an optimization point of view, where rather than studying the existence of extremal instances, we are given an instance and are asked to find the sparsest possible spanner/preserver. We give an O ( n 3/5 + ε )-approximation for distance preservers and pairwise spanners (for arbitrary constant ε > 0). This is the first nontrivial upper bound for either problem, both of which are known to be as hard to approximate as Label Cover. We also prove Label Cover hardness for approximating additive spanners, even for the cases of additive 1 stretch (where one might expect a polylogarithmic approximation, since the related multiplicative 2-spanner problem admits an O (log n )-approximation) and additive polylogarithmic stretch (where the related multiplicative spanner problem has an O (1)-approximation). Interestingly, the techniques we use in our approximation algorithm extend beyond distance-based problem to pure connectivity network design problems. In particular, our techniques allow us to give an O ( n 3/5 + ε )-approximation for the Directed Steiner Forest problem (for arbitrary constant ε > 0) when all edges have uniform costs, improving the previous best O ( n 2/3 + ε )-approximation due to Berman et al. [ICALP’11] (which holds for general edge costs).
- Open Access
On Approximating Degree-Bounded Network Design Problems
Directed Steiner Tree (DST) is a central problem in combinatorial optimization and theoretical computer science: Given a directed graph $G=(V, E)$ with edge costs $c \in \mathbb{R}_{\geq 0}^E$, a root $r \in V$ and $k$ terminals $K\subseteq V$, we need to output the minimum-cost arborescence in $G$ that contains an $r$\textrightarrow $t$ path for every $t \in K$. Recently, Grandoni, Laekhanukit and Li, and independently Ghuge and Nagarajan, gave quasi-polynomial time $O(\log^2k/\log \log k)$-approximation algorithms for the problem, which are tight under popular complexity assumptions. In this paper, we consider the more general Degree-Bounded Directed Steiner Tree (DB-DST) problem, where we are additionally given a degree bound $d_v$ on each vertex $v \in V$, and we require that every vertex $v$ in the output tree has at most $d_v$ children. We give a quasi-polynomial time $(O(\log n \log k), O(\log^2 n))$-bicriteria approximation: The algorithm produces a solution with cost at most $O(\log n\log k)$ times the cost of the optimum solution that violates the degree constraints by at most a factor of $O(\log^2n)$. This is the first non-trivial result for the problem. While our cost-guarantee is nearly optimal, the degree violation factor of $O(\log^2n)$ is an $O(\log n)$-factor away from the approximation lower bound of $\Omega(\log n)$ from the set-cover hardness. The hardness result holds even on the special case of the {\em Degree-Bounded Group Steiner Tree} problem on trees (DB-GST-T). With the hope of closing the gap, we study the question of whether the degree violation factor can be made tight for this special case. We answer the question in the affirmative by giving an $(O(\log n\log k), O(\log n))$-bicriteria approximation algorithm for DB-GST-T.Open AccessOn Approximating Degree-Bounded Network Design Problems
Directed Steiner Tree (DST) is a central problem in combinatorial optimization and theoretical computer science: Given a directed graph $G=(V, E)$ with edge costs $c \in \mathbb{R}_{\geq 0}^E$, a root $r \in V$ and $k$ terminals $K\subseteq V$, we need to output the minimum-cost arborescence in $G$ that contains an $r$\textrightarrow $t$ path for every $t \in K$. Recently, Grandoni, Laekhanukit and Li, and independently Ghuge and Nagarajan, gave quasi-polynomial time $O(\log^2k/\log \log k)$-approximation algorithms for the problem, which are tight under popular complexity assumptions. In this paper, we consider the more general Degree-Bounded Directed Steiner Tree (DB-DST) problem, where we are additionally given a degree bound $d_v$ on each vertex $v \in V$, and we require that every vertex $v$ in the output tree has at most $d_v$ children. We give a quasi-polynomial time $(O(\log n \log k), O(\log^2 n))$-bicriteria approximation: The algorithm produces a solution with cost at most $O(\log n\log k)$ times the cost of the optimum solution that violates the degree constraints by at most a factor of $O(\log^2n)$. This is the first non-trivial result for the problem. While our cost-guarantee is nearly optimal, the degree violation factor of $O(\log^2n)$ is an $O(\log n)$-factor away from the approximation lower bound of $\Omega(\log n)$ from the set-cover hardness. The hardness result holds even on the special case of the {\em Degree-Bounded Group Steiner Tree} problem on trees (DB-GST-T). With the hope of closing the gap, we study the question of whether the degree violation factor can be made tight for this special case. We answer the question in the affirmative by giving an $(O(\log n\log k), O(\log n))$-bicriteria approximation algorithm for DB-GST-T.