| Full text | |
| Author(s): |
Benedito, Marcelo P. L.
;
Pedrosa, Lehilton L. C.
;
Rosado, Hugo K. K.
Total Authors: 3
|
| Document type: | Journal article |
| Source: | DISCRETE APPLIED MATHEMATICS; v. 340, p. 14-pg., 2023-12-15. |
| Abstract | |
The Cable-Trench Problem (CTP) is a common generalization of the Single-Source Shortest Paths Problem (SSSP) and the Minimum Spanning Tree Problem (MST): given an edge-weighted graph with a special root vertex and parameters iota, gamma >= 0, the goal is to find a spanning tree that minimizes the total edge costs plus the total cost of the paths from each vertex to the root, scaled by iota and gamma, respectively. While it is well known that both SSSP and MST can be solved in polynomial time, CTP is NP-hard. We show that computing an approximate solution with factor less than 1.000475 is NP-hard, thus ruling out a polynomial-time approximation scheme, unless P = NP. We also consider the more general Steiner Cable-Trench Problem (SCTP), for which only a given subset of terminal vertices must be spanned by a solution. The tree might include non-terminal vertices, known as Steiner vertices, although only paths from terminals to the root are considered in the total cost. For this problem, we present a (2.88 +is an element of)-approximation based on a counting argument, for any is an element of > 0; also, we give a simple parameterized algorithm with the number of terminals as parameter. (c) 2023 Elsevier B.V. All rights reserved. (AU) | |
| FAPESP's process: | 15/11937-9 - Investigation of hard problems from the algorithmic and structural stand points |
| Grantee: | Flávio Keidi Miyazawa |
| Support Opportunities: | Research Projects - Thematic Grants |
| FAPESP's process: | 19/10400-2 - Approximation and parameterized algorithms for pair connectivity problems |
| Grantee: | Marcelo Pinheiro Leite Benedito |
| Support Opportunities: | Scholarships in Brazil - Doctorate |