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

arXiv: https://arxiv.org/abs/2510.03899 · HTML: https://mlsanity.com/paper/2510.03899/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 26 of its 55 references that are in the map.
- First posted on arXiv 4 Oct 2025.

## Builds on (most cited first, 26 of 26)

- [Advances and Open Problems in Federated Learning](https://mlsanity.com/paper/1912.04977/) (2019)
- [Green AI](https://mlsanity.com/paper/1907.10597/) (2019)
- [Fairness in Machine Learning: A Survey](https://mlsanity.com/paper/2010.04053/) (2020)
- [A Survey on Distributed Machine Learning](https://mlsanity.com/paper/1912.09789/) (2019)
- [Fair Clustering Through Fairlets](https://mlsanity.com/paper/1802.05733/) (2018)
- [Compositional Fairness Constraints for Graph Embeddings](https://mlsanity.com/paper/1905.10674/) (2019)
- [A Comprehensive Survey on Trustworthy Graph Neural Networks: Privacy, Robustness, Fairness, and Explainability](https://mlsanity.com/paper/2204.08570/) (2022)
- [Fairness in Graph Mining: A Survey](https://mlsanity.com/paper/2204.09888/) (2022)
- [Guarantees for Spectral Clustering with Fairness Constraints](https://mlsanity.com/paper/1901.08668/) (2019)
- [Clustering without Over-Representation](https://mlsanity.com/paper/1905.12753/) (2019)
- [Green Edge AI: A Contemporary Survey](https://mlsanity.com/paper/2312.00333/) (2023)
- [Fairness-Aware Graph Neural Networks: A Survey](https://mlsanity.com/paper/2307.03929/) (2023)
- [Group-Fairness in Influence Maximization](https://mlsanity.com/paper/1903.00967/) (2019)
- [The Evolution of Distributed Systems for Graph Neural Networks and their Origin in Graph Processing and Deep Learning: A Survey](https://mlsanity.com/paper/2305.13854/) (2023)
- [An Introduction to Temporal Graphs: An Algorithmic Perspective](https://mlsanity.com/paper/1503.00278/) (2015)
- [Fair GLASSO: Estimating Fair Graphical Models with Unbiased Statistical Behavior](https://mlsanity.com/paper/2406.09513/) (2024)
- [Fairness-Aware Estimation of Graphical Models](https://mlsanity.com/paper/2408.17396/) (2024)
- [The complexity of computing optimum labelings for temporal connectivity](https://mlsanity.com/paper/2202.05880/) (2022)
- [On the Size and the Approximability of Minimum Temporally Connected Subgraphs](https://mlsanity.com/paper/1602.06411/) (2016)
- [Temporal Walk Centrality: Ranking Nodes in Evolving Networks](https://mlsanity.com/paper/2202.03706/) (2022)
- [Finding Densest Subgraphs with Edge-Color Constraints](https://mlsanity.com/paper/2402.09124/) (2024)
- [On the Enumeration and Counting of Bicriteria Temporal Paths](https://mlsanity.com/paper/1812.02507/) (2018)
- [Span-core Decomposition for Temporal Networks: Algorithms and Applications](https://mlsanity.com/paper/1910.03645/) (2019)
- [A Higher-Order Temporal H-Index for Evolving Networks](https://mlsanity.com/paper/2305.16001/) (2023)
- [An Edge-Based Decomposition Framework for Temporal Networks](https://mlsanity.com/paper/2309.11843/) (2023)
- [Fast algorithms to improve fair information access in networks](https://mlsanity.com/paper/2409.03127/) (2024)

## Abstract (arXiv)

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-ε)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.