## Abstract

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 ∈ R^{E}_{≥}0, a root r ∈ V and k terminals K ⊆ V, we need to output a minimum-cost arborescence in G that contains an r→t path for every t ∈ K. Recently, Grandoni, Laekhanukit and Li, and independently Ghuge and Nagarajan, gave quasi-polynomial time O(log^{2} k/ 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 dv on each vertex v ∈ V, and we require that every vertex v in the output tree has at most dv 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^{2} n). This is the first non-trivial result for the problem. While our cost-guarantee is nearly optimal, the degree violation factor of O(log^{2} n) is an O(log n)factor away from the approximation lower bound of Ω(log n) from the Set Cover hardness. The hardness result holds even on the special case of the 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.

Original language | English (US) |
---|---|

Title of host publication | Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2020 |

Editors | Jaroslaw Byrka, Raghu Meka |

Publisher | Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing |

ISBN (Electronic) | 9783959771641 |

DOIs | |

State | Published - Aug 1 2020 |

Event | 23rd International Conference on Approximation Algorithms for Combinatorial Optimization Problems and 24th International Conference on Randomization and Computation, APPROX/RANDOM 2020 - Virtual, Online, United States Duration: Aug 17 2020 → Aug 19 2020 |

### Publication series

Name | Leibniz International Proceedings in Informatics, LIPIcs |
---|---|

Volume | 176 |

ISSN (Print) | 1868-8969 |

### Conference

Conference | 23rd International Conference on Approximation Algorithms for Combinatorial Optimization Problems and 24th International Conference on Randomization and Computation, APPROX/RANDOM 2020 |
---|---|

Country/Territory | United States |

City | Virtual, Online |

Period | 8/17/20 → 8/19/20 |

## All Science Journal Classification (ASJC) codes

- Software

## Keywords

- Degree-bounded
- Directed Steiner Tree
- Group Steiner Tree