Fair Minimum Labeling: Efficient Temporal Network Activations for Reachability and Equity

arXiv:2510.03899v3 Announce Type: replace-cross Abstract: Balancing resource efficiency and fairness is critical in networked systems that support modern learning applications. We introduce the Fair Minimum Labeling (FML) problem: the task of designing a minimum-cost temporal edge activation plan that ensures each group of nodes in a network has sufficient access to a designated target set, according to specified coverage requirements. FML captures key trade-offs in systems where edge activations incur resource costs and equitable access is essential, such as distributed data collection, update dissemination in edge-cloud systems, and fair service restoration in critical infrastructure. We first give a structural characterisation of the single-terminal case, showing that it is equivalent to the rooted Covering Steiner problem. We prove that FML is NP-hard and admits no ((1-epsilon)ln |C|)-approximation for |C| groups, already on a star, while for any fixed number of groups it inherits a constant-factor approximation and remains APX-hard. We then present probabilistic approximation algorithms for the two-group, single-terminal case: an algorithm whose tree subroutine is exact, hence optimal on tree-structured networks and O(log |V|) in expectation on general graphs, together with a faster bicriteria variant whose coverage violation degrades gracefully with the merge depth of the tree computation. For practical scalability, we additionally introduce a graph-native variant based on a shortest-path-tree reduction. Empirical results show that FML enforces group-level fairness, while the graph-native variant substantially improves scalability and achieves competitive activation cost.

Source: arXiv cs.LG | 2026-09-02