Sub-Tree Scheduling for Wireless Sensor Networks with Partial Coverage: Complexity and Polynomial-Size Formulations

Given an undirected graph (Formula presented.) whose edge weights change over (Formula presented.) time slots, the sub-tree scheduling for wireless sensor networks with partial coverage asks to partition the vertices of (Formula presented.) in (Formula presented.) non-empty trees such that the total weight of the trees is minimized. In this article, we show that the problem is NP-hard in both the cases where (Formula presented.) (Formula presented.) is part of the input and (Formula presented.) is a fixed instance parameter. In both our proofs we reduce the cardinality of the Steiner tree problem. Then, in order to provide easy-to-implement and effective computational tools to benchmark heuristics, we introduce new polynomial-size integer linear programming formulations for the problem. Being defined by a polynomial number of variables and constraints, the formulations can be used to address instances of the problem by means of off-the-shelf mixed-integer linear programming solvers with minimum implementation efforts. All proposed formulations share the property that the integrality requirement can be relaxed on subsets of variables. This enables several algorithmic choices to solve the models, including Benders' decomposition approaches and branch-and-bound with specific branching priorities. We experimentally identify the best resolution method for each formulation. Moreover, the experimental results obtained on benchmark instances of the problem, compared against those reported in the literature, support the effectiveness arising from using the new proposed formulations.