TY - JOUR

T1 - Parameterized Algorithms for Power-Efficiently Connecting Wireless Sensor Networks: Theory and Experiments

AU - Bentert, Matthias

AU - van Bevern, Rene

AU - Nichterlein, Andre

AU - Niedermeier, Rolf

AU - Smirnov, Pavel V.

N1 - Accepted by Optimization: Algorithms Applications. Funding: This work was supported by the Council for Grants of the President of the Russian Federation [SP-2178.2019.5] , the Russian Foundation for Basic Research [18-501-12031 NNIO_a] , and the Ministry of Science and Higher Education of the Russian Federation [075-15-2019-1675] . The results in Sections 4.6, 5.1, and 5.4.3 were obtained while R. van Bevern and P. V. Smirnov were supported by the Russian Foundation for Basic Research [Grant 18-501-12031 NNIO_a] . The results in Sections 4.6 and 5.1-5.4.3 were obtained while R. van Bevern was supported by a stipend of the President of the Russian Federation [SP-2178.2019.5] , and P. V. Smirnov was supported by the Mathematical Center in Akademgorodok [Agreement 075-15-2019-1675] with the Ministry of Science and Higher Education of the Russian Federation. The results in Sections 3, 5.2.2, and 5.4.2 were obtained while both were supported by the Mathematical Center in Akademgorodok.

PY - 2022/1

Y1 - 2022/1

N2 - We study a problem of energy-efficiently connecting a symmetric wireless communication network: given an n-vertex graph with edge weights, find a connected spanning subgraph of minimum cost, where the cost is determined by each vertex paying the heaviest edge incident to it in the subgraph. The problem is known to be NP-hard. Strengthening this hardness result, we show that even o(log n)-approximating the difference d between the optimal solution cost and a natural lower bound is NP-hard. Moreover, we show 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. We also 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 because of sensor faults. In experiments, the algorithm outperforms CPLEX with known integer linear programming (ILP) formulations when n is sufficiently large compared with c.

AB - We study a problem of energy-efficiently connecting a symmetric wireless communication network: given an n-vertex graph with edge weights, find a connected spanning subgraph of minimum cost, where the cost is determined by each vertex paying the heaviest edge incident to it in the subgraph. The problem is known to be NP-hard. Strengthening this hardness result, we show that even o(log n)-approximating the difference d between the optimal solution cost and a natural lower bound is NP-hard. Moreover, we show 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. We also 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 because of sensor faults. In experiments, the algorithm outperforms CPLEX with known integer linear programming (ILP) formulations when n is sufficiently large compared with c.

KW - connected spanning subgraphs

KW - monitoring areas

KW - reconnecting sensor networks

KW - parameterized complexity analysis

KW - approximation hardness

KW - parameterization above lower bounds

KW - color-coding

KW - experimental comparison

KW - SYMMETRIC CONNECTIVITY

KW - ASSIGNMENT

KW - CONSUMPTION

KW - NUMBER

KW - Connected spanning subgraphs

UR - http://www.scopus.com/inward/record.url?scp=85131027694&partnerID=8YFLogxK

UR - https://www.mendeley.com/catalogue/9f52282b-9e1f-3418-bb4b-901c35a72064/

U2 - 10.1287/ijoc.2020.1045

DO - 10.1287/ijoc.2020.1045

M3 - Article

VL - 34

SP - 55

EP - 75

JO - Informs journal on computing

JF - Informs journal on computing

SN - 1091-9856

IS - 1

ER -