2017/06/30 by Matthias Bentert, René van Bevern, André Nichterlein +3
Computer Science · Mathematics · #Advanced Graph Theory Research #Algorithm #Approximation algorithm #Complexity and Algorithms in Graphs #Computer network #Computer science #Integer programming #Linear programming #Mathematics #Optimization and Search Problems #Parameterized complexity #Polynomial #Time complexity #Wireless #Wireless network #Wireless sensor network #acm:90C27 #cs.DM #cs.DS #msc:90C27
paper · pdf · doi:10.1287/ijoc.2020.1045
published as INFORMS Journal on Computing 34(1):55-75, 2022 · Additional experiments, lower bounds strengthened to metric case, added kernelization lower bounds
arxiv created 2020/09/03 · openalex publication_date 2021/06/03 · arxiv updated 2022/03/23 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
We study an NP-hard problem motivated by energy-efficiently maintaining the connectivity of a symmetric wireless communication network: Given an edge-weighted n-vertex graph, find a connected spanning subgraph of minimum cost, where the cost is determined by letting each vertex pay the most expensive edge incident to it in the subgraph. On the negative side, we show that o(log n)-approximating the difference d between the optimal solution cost and a natural lower bound is NP-hard and that, under the Exponential Time Hypothesis, there are no exact algorithms running in 2o(n) time or in f(d)⋅ nO(1) time for any computable function f. Moreover, we show that the special case of connecting c network components with minimum additional cost generally cannot be polynomial-time reduced to instances of size cO(1) unless the polynomial-time hierarchy collapses. On the positive side, we provide an algorithm that reconnects O(log n) connected components with minimum additional cost in polynomial time. These algorithms are motivated by application scenarios of monitoring areas or where an existing sensor network may fall apart into several connected components due to sensor faults. In experiments, the algorithm outperforms CPLEX with known ILP formulations when n is sufficiently large compared to c.