On the complexity of the Cable-Trench Problem

Autor(es)

Benedito, Marcelo P. L. ; Pedrosa, Lehilton L. C. ; Rosado, Hugo K. K.

• Tipo de documento: Artigo Científico
• Fonte: DISCRETE APPLIED MATHEMATICS; v. 340, p. 14-pg., 2023-12-15.

Resumo

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)

• Processo FAPESP: 15/11937-9 - Investigação de problemas difíceis do ponto de vista algorítmico e estrutural
• Beneficiário: Flávio Keidi Miyazawa
• Modalidade de apoio: Auxílio à Pesquisa - Temático
• Processo FAPESP: 19/10400-2 - Algoritmos de aproximação e parametrizados para problemas de conectividade de pares
• Beneficiário: Marcelo Pinheiro Leite Benedito
• Modalidade de apoio: Bolsas no Brasil - Doutorado