Approximation Algorithms for Constrained Steiner Tree Problems

One of the most fundamental problems in network design problems and complexity theory is the Steiner tree problem in which one is given an edge-cost graph, and is asked to find a minimum-cost subtree in the graph that spans a given subset of vertices, called terminals. This problem was given as one of the 21 NP complete problems in Karp’s list. In this thesis, we aim to investigate some variants of the Steiner tree problem. In the budgeted rooted Steiner tree problem, we are given a graph G with n nodes, a predefined node r, a cost function is associated to each edge/node and a prize function is associated to each node, and a real-valued budget B. The aim is to find a tree in G rooted at r such that the total cost is at most B and the total prize is maximized. In the quota rooted Steiner tree problem, we are given a real-valued quota Q, instead of the budget, and we aim at minimizing the cost of a tree rooted at r whose overall prize is at least Q. In this thesis, we study some relevant generalizations of the above problems, namely we consider: (i) directed graphs with monotone submodular prize functions over subsets of nodes, (ii) directed graphs with additive prize functions, and (iii) undirected graphs with monotone submodular prize functions. For scenario (i), we propose a polynomial time O(1ε3√B)-approximation algorithm for the budgeted problem that violates the budget constraint by a factor of at most 1 + ε, for any ε ∈ (0, 1], where the costs are positive integers values associated to the edges. For scenario (ii), we develop a technique resorting on a standard flow based linear programming relaxation to compute a tree with good trade-off between prize and cost, which allows us to provide very simple polynomial time approximation algorithms for both the budgeted and the quota problems. For the budgeted node-weighted problem, our algorithm achieves an O(1ε2 n2/3 ln n)-approximation at the cost of a budget violation of a factor of at most 1 + ε, for any ε ∈ (0, 1]. For the quota node-weighted problem, our algorithm guarantees an approximation factor of O(n 2/3 ln n) at the cost of a violation of the quota constraint by a factor of at most 2. Our algorithms work for nonnegative real-valued costs and are the first non-trivial polynomial time algorithms with approximation factors depending on n. The same technique can be used to find an approximation algorithm for the node-weighted directed Steiner tree problem (DSteinerT). Recently, Li and Laekhanukit [SODA 2022] ruled out poly-logarithmic approximation algorithms for DSteinerT based on a standard flow-based linear programming relaxation. By using the same linear relaxation, we provide a surprisingly simple polynomial time O((1 + ε) √n ln n)-approximation algorithm for DSteinerT, for any ε > 0. For scenario (iii), we provide a polynomial time O(1ε3√n log n) approximation algorithm for the node-weighted budgeted problem that violates the budget constraint by a factor of at most 1 + ε, for any ε ∈ (0, 1]. Also in this case we introduce a general technique that exploits a flow-based linear program to find trees with a good trade-off between prize and cost, which allows us to provide a good approximation also for the quota node-weighted problem. Finally, we provide some new/improved approximation bounds for several related problems, including the undirected version of scenario (ii), the maximum budgeted connected set cover problem, and the budgeted sensor cover problem.