  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 $2^{o(n)}$ time or in
$f(d)\cdot n^{O(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 $c^{O(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$.
