Fair Minimum Labeling: Efficient Temporal Network Activations for Reachability and Equity
Authors: Lutz Oettershagen
Othon Michail
Venue: NeurIPS 2025 poster ()
Keywords: fairness
temporal graphs
reachability
resource efficiency
approximation algorithms
optimization
group-level coverage
multi-source learning
communication-constrained learning
Green AI
Primary area: theory
TL;DR: We introduce the Fair Minimum Labeling problem for designing temporally efficient and fair activation plans, prove tight hardness bounds, and present approximation algorithms with strong empirical results on fair multi-source learning.

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 show that FML is NP-hard and $\Omega(\log |V|)$-hard to approximate, where $V$ is the set of nodes, and we present probabilistic approximation algorithms that match this bound, achieving the best possible guarantee for the activation cost. We demonstrate the practical utility of FML in a fair multi-source data aggregation task for training a shared model. Empirical results show that FML enforces group-level fairness with substantially lower activation cost than baseline heuristics, underscoring its potential for building resource-efficient, equitable temporal reachability in learning-integrated networks.

Fair Minimum Labeling: Efficient Temporal Network Activations for Reachability and Equity
Lutz Oettershagen University of Liverpool vuzzcetttershngg@@vvvrroo....... ac.
Othon Michail University of Liverpool
othon. otlon.niichall0liivrroo.... ac
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-offss 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 show that FML NP-hard and (log |-la-hadd to approximate, where V the set of nodes, and we present probabilistic approximation algorithms that match this bound, achieving the best possible guarantee for the activation cost. We demonstrate the practical utility of FML. in fair multi-source data aggregation task for training a shared model. Empirical results show that FML enforces group-level fairness with substantially lower activation cost than baseline heuristics, underscoring its potential for building resource-efficient, equitable temporal reachability in learning- integrated networks.
Introduction
Resource efficiency and fairness represent dual challenges in designing modern machine learning and networked systems. From large-scale federated learning managing communication budgets across heterogeneous devices [19], to recommender systems scheduling updates and notifications diverse user groups [18], and distributed sensor networks operating under stringent energy constraints [17], the underlying theme is constant: interactions are dynamic, resources limited, and equity across participants or data sources is paramount [8, 12, 26). In such systems, the graph structure captures potential interactions, but the temporal dimension, i.e., when connections active, governs the actual flow of information, updates, and influence.
Optimizing these temporal interactions solely for aggregate performance minimal static infrastruc- ture cost often yields suboptimal or unfair outcomes. Simple heuristics might overload communication bottlenecks, drain energy reserves rapidly, systematically neglect harder-to-reach nodes groups representing minority populations, specific event types, or distinct data distributions. This can lead to biased data collection pipelines, skewed model training, feedback loops that amplify inequity, and inefficient use of limited resources like energy or bandwidth.
Therefore, principled mechanisms are needed that explicitly co-optimize efficiency and fairness in these dynamic network settings. We consider systems where central controller has the ability to decide when communication links are active. Our focus is on designing temporal activation patterns over an underlying static graph G = (V, E) that satisfy strong temporal reachability guarantees for distinct node groups, while minimizing the total number of activations. Nodes may represent users, sensors, or agents belonging to specific populations (Vi...., Vi), and fairness dictates that
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

each group must maintain adequate connectivity over time to designated target nodes. Minimizing the number of edge activations directly translates to reduced energy consumption, communication overhead, and computational load, which is central for sustainable system design [26, 38).
To address this, we introduce the Fair Minimum Labeling (FML) problem framework. Conceptually, FML seeks to determine which edges in the graph need to be activated and when, such that the required number of nodes from each specified group can reach the target nodes via paths formed by these time-ordered activations. The primary objective is to achieve this guaranteed fair reachability using the minimum total number of edge activations over time. FML thus provides formal basis for optimizing resource sparsity while enforeing equitable temporal access.
The introduction of FML novel optimization problem is motivated by both practical relevance and theoretical gaps. First, it applies to a wide range of systems where temporal resource allocation directly affects group equity. In distributed data gathering for learning applications, such as those involving environmental sensors, mobile agents, or geographically diverse data streams [31, 43, 42), FML enables minimal-cost activation plans that ensure all groups are fairly represented in the collected data. In edge-cloud systems, it helps decide when communication links should be active so that all device groups can receive timely model updates under bandwidth constraints. Similarly, in infrastructure restoration, FML can guide activation sequences that ensure fair reactivation of services. Second, FML fills a critical gap in the literature. Existing fairness- aware graph methods, such as fair clustering [24], node embeddings [37], and influence maximization [40, 44], are primarily designed for static settings and do not model temporal interactions or activation cost. Fairness has been studied in wireless systems [17], and temporal connectivity has been explored in dynamic networks [22, 27], but fairness constraints remain absent in algorithmic temporal graph design. FMI. addresses this gap by explicitly minimizing temporal edge activations, treated as a proxy for resource cost, while enforcing group-level temporal reachability. In contrast to decentralized approaches such as classical federated learning [19], where participation is uncoordinated, FML assumes centralized control over link activations, allowing the enforcement of fairness guarantees over time. This design objective distinguishes FML from prior work focused on static structures or continuous flows.
Our main contributions can be summarized as follows:
We introduce the Fair Minimum Labeling (FML) problem, a new framework for designing temporally sparse interaction patterns that guarantee group-wise temporal reachability under global resource constraints. We show that FML generalizes classical temporal connectivity problems and prove that it is NP-hard and 22 Ihaad approximate.
We develop a probabilistic approximation framework based on tree embeddings, yielding two algorithms: (i) an O (log |V)-approximmttion for activation cost, and (ii) a highly efficient bicriteria approximation that guarantees Oloog [V)) expected cost and fairness violation factor of (1+ =)", where H E Oloo (V)) denotes the height of the embedding tree. Our algorithms address the case of two distinct groups temporally reaching single terminal.
We empirically evaluate our algorithms on multi-source learning tasks. The results show that FML-based methods reliably enforce fairness with significantly lower activation cost than agnostic baselines, while remaining computationally efficient.
The omitted proofs are provided in Appendix A.
2 Preliminaries
We denote the set of positive integers (natural numbers without zero) by N =
For é E N. we use [6] denote the set {1, ..,,,.... ,,.. The powerset of set X is denoted by P(X).
A static graph is an ordered pair G = E), where V is a finite set of nodes (or vertices) and u,v E V, * t} is finite set of undirected edges. We assume static graphs are simple (no self-loops, no multiple edges between the same pair of nodes). A colored static graph G = (V, E, with colors C has an additional function c V + P(C) assigning a (possibly empty) set of colors c(u) to each node u E V where C = [Cmax] is a set of Cmax colors. We use V. = (u V c(v) = c). Let n [V] and = EE}.
E C =(tue)
temporal graph is an ordered pair g = (V,E), where V is a finite set of nodes and a finite set of temporal edges. Each temporal edge is pair e = ((u, 2), 7), where {u, f} is undirected pair
2

---

of distinct nodes from V, and T E N is the rimestamp indicating when the interaction between u and 2 occurs.
Given a static graph G = E),, a temporal labeling is a function A F. - P(N) that assigns a set of timestamps (possibly empty) to each static edge E. A labeling À induces a temporal graph Gy = (V, Ex). where the node set is the same as the static graph's s. and the set of temporal edges {u,,) E E' and T E X(e) The size (or cost) of labeling X, denoted by [^], is the total number of assigned timestamps, which corresponds to the number of temporal edges in the induced temporal graph, that is, | |Ex| EeEE [A(e)]-
defined as: Σ'x = {((u, v),,)
A temporal path (or time-respecting path) in a temporal graph 9 = E) from node to node a sequence of temporal edges ((v,, #1 J: ()):((() 02), T2)....).... ( ((up-1, : Tp) from & such that vo u, Up and the timestamps are strictly increasing, i.c., Ti < 72
< Tp. A node is
temporally reachable from a node u in G if such a temporal path exists from u to v.
We define the reachability indicator function r(u, with respect to a given temporal graph G = EV.E). For any two nodes u, V:
1 if v is temporally reachable from u in G, r r(u, v)
otherwise.
By convention, we consider every node to be temporally reachable from itself (via a path of length zero), so r(v, v) = 1 for all V. The specific temporal graph 9 (often an induced graph Gx) for which reachability considered will always be clear from the context. Finally, for U, W S V. let r(U, W) = Euet,wew r(u, v) be the sum of pairwise reachability of nodes in U to nodes in W.
3 Related Work
The Fair Minimum Labeling (FML) problem intersects several research areas, primarily temporal graph algorithms, network optimization with fairness considerations, and resource-efficient Al.
Temporal Graph Connectivity and Labeling. A core component of FML is finding minimum-cost set of temporal edge activations. Mertzios et al. [27] (and its journal version [28]) introduced the study of temporal network design in multi-labeled temporal graphs, where the goal is to optimize some global cost measure of the graph labeling, such as the total number of timestamps, while satisfying specific temporal reachability properties. The Minimum Labeling (ML) problem is such a temporal network design problem, seeking the minimum number of labels to make an entire static graph temporally connected. For its directed version on strongly connected digraphs, [27] had provided bounds on the number of labels needed, proving that 2 labels per are and at most 4([V]- 1) total labels are always sufficient. Using similar constructions on undirected graphs, Akrida et al. [2] proved that 2 V - 3 total labels are sufficient, later refined by Klobas et al. [25] to 2| under certain conditions. who also showed ML polynomially solvable. While ML aims for global temporal connectivity, FML focuses on targeted reachability for specific node groups to designated terminal set, under explicit fairness (coverage) constraints for each group, and cost minimization objective. Klobas et al. [25] also introduced extensions like Minimum Steiner Labeling (MSL), where the goal is to pairwise temporally connect a predefined set of terminal nodes. Our FML generalizes ML and MSL. Other research has explored concepts like temporally-connen connected spanning subgraphs [3]. temporal core decompositions [15, 33), and various notions of temporal paths and reachability [22, 7, 29, 16, 34, 35, 30J. However, these works generally do not incorporate group fairness constraints or the specific cost model of minimizing temporal edge activations as FML does.
Fairness in Graph Mining and Network Optimization. There is a significant body of work on incorporating fairness into static graph algorithms and network optimization, driven by the need for equitable outcomes in various applications. This includes, e.g., fair clustering [1. 10, 24], fair node embeddings [37, 6]. fair influence maximization [40, 44], and graph learning tasks [9, 11, 32, 45, 36). While these contributions are crucial for advancing fairness in graph-based AI, they predominantly operate on static graphs and often define fairness differently (e.g., proportionality in output, balanced representation in a static structure). For example, related problem in static graphs the Balanced Connected Subgruph (BCS) problem [5] which seeks a connected subgraph with balanced representation from different node colors. FML,, in contrast, addresses fairness through temporal path- nath-based accesxibility for predefined groups, directly optimizing the dynamic activation of interactions over time to meet these fairness goals while minimizing resource usage. Moreover,
3

---

(V)
À
(a) Example of colored static graph G with one terminal node t V shown square.
(b) Temporal labeling λ1 connects 50% of the colored nodes to t, but only red nodes.
(c) Temporal labeling A2 connects 50% of the colored nodes in equal proportion
Figure I: A simple toy example showing non-equitable and an equitable labeling of small colored graph. The labelings Å₁ and X assign time stamps 71 < 72 T3 edges. Both connect 50% of the colored nodes, but only X2 connects both colors resulting in higher costs of three. Therefore, under color requirement of 50% for each color, only A2 a valid solution for the FML problem.
in networked systems, fairness is a long-standing concern in resource allocation. This includes fair bandwidth sharing in communication networks [21], fair scheduling in wireless systems [17, 41], and equitable service provisioning.
edge-cloud environments, fair scheduling of updates (e.g.. for recommender systems [18]) or computation offloading is critical. FML contributes to this line of work by providing a formal model for achieving group-level temporal reachability fairness specifically through the lens of minimizing discrete edge activations, key proxy for communication cost, energy, or computational overhead, aligning with sustainability principles [26, 38). Unlike other problems that focus on flow rates or latency targets, FML provides hard guarantees on temporal path existence for specified quotas from diverse groups.
Connection to Combinatorial Optimization. FML resembles Set Cover and Steiner Tree [20], with its goal of covering group nodes via minimal-cost temporal activations. Its 2(oog [V] approximation hardness matches Set Cover [14], but FML is more complex due to temporal constraints, labeling- based edge induction, and fairness across groups Standard algorithms fall short; our approximation algorithms use probabilistic tree embeddings address FML's structural challenges.
4 The fair minimum labeling problem
We now formalize the central optimization problem studied in this work: designing temporally sparse activation patterns over static graph to guarantee group-level access designated target nodes under strict resource constraints. In many monitoring, or update dissemination, ensuring both efficiency and equitable access over time is essential. Existing frameworks, however, lack mechanisms to enforce fairness through temporal reachability while minimizing total activation effort.
systems, such as data aggregation, distributed
The Fair Minimum Labeling (FML) problem addresses this gap by integrating three key aspects: (i) cost-aware edge activation planning, (ii) per-group temporal reachability guarantees, and flexible, group-specific coverage requirements. The goal is to compute a temporal edge labeling that minimizes total activation cost while satisfying fairness constraints across all groups (see Appendix B for an application example).
(iii)
EV,E.c) with node colors C. a set of terminals T C V, p N, and a requirement function fc V + R for each color e the goal of assigned time labels |>| Al=E EeeE (X()) such that for each color e E C, the number of nodes in V. that can temporally reach at least terminals t E T under X is at least fo(V.). Reachability is defined with respect to the temporal subgraph induced by X.
Definition 1 (Fair Minimum Labeling (FML)). Given a colored static graph
find a temporal labeling X E P(N) that minimizes the total number
Figure shows a simple example. In the corresponding decision version, we are additionally given a budget & N and asked whether there exists temporal labeling À such that |X| k while satisfying the fairness constraints for all groups. We also note that a symmetric variant of the problem can be defined by requiring temporal reachability from (rather than lowards) the terminal set T.
The FMI problem generalizes both the Minimum Labeling (ML.) and the Minimum Steiner Labeling (MSL) problems (see Observation I in the appendix). Since MSL is NP-complete [25], it immediately

---

follows that FML is No-complete. Moreover, we show that FML remains NP-hard and hard to approximate within a factor better than (llogg) even in the special case where the terminal set is singleton, i.e., T = {t}.
Theorem The FML problem with a single terminal is No-complete, and no ((1 c) n)) approximation algorithm exists unless NP C DTIME (log log x)).
5
Approximation
Given the hardness results in Theorem 1, we now present approximation algorithms that are tight in expectation with respect to cost and solve the FML problem in instances with single terminal. We focus on the case where each node has colors B (blue), R (red), or no color, i.e., C = {B. R, 0}. For convenience, we the set notation B V and R S V to directly refer to the nodes of each group of colored nodes. Furthermore, we define the group-specific requirement functions as f' (B) = al B] and fR( (t) ax [R] for fixed parameter a R with 0 S a S 1, indicating that an equal fraction a of both B and R nodes must reach the terminal. This two-group setting captures a common fairness use case and provides a natural foundation for future extensions multiple groups or terminals.
Our approach leverages the framework of probabilistic tree embeddings, a powerful technique for approximating arbitrary metric spaces with simpler tree metrics. The concept of probabilistic tree embeddings was first introduced by Bartal [4], who showed that any finite metric space can be probabilistically approximated by distribution
tree metrics, incurring only logarithmic distortion in expectation. This result was later significantly improved by Fakcharoenphol, Rao, and Talwar (FRT) [13], who established that any n-point metric space can be embedded into distribution over dominating tree metrics with an expected stretch of Oloog n), and that this bound is tight.
Definition 2 (Probabilistic Tree Embedding). Let (X, d) be a finite metric space. A probabilistic tree embedding is a randomized mapping from (X, d) into a distribution 'D over free metrics (X, dr) such that for all x. y X:
For every (X, dr) E D, d(x, v) S dr(r,y)
2. The expected stretch is Edd=D (a, w)] S (log d(æ, v) for all x, y X.
Algorithm 1: Approximation Framework for FML with Single Terminal
Input:
Graph G = E), V, V. V, terminal / a. E [0, Output:
Temporal graph labeling Àg
Compute shortest path metric de on G.
2 Generate probabilistic tree emhedding for dc) using FRT [13), sample a single
weighted tree T' (V, Er, w) from the distribution D. Let w(u, v) dr (u, v).
3 Root the tree T at the terminal t. Compute an FML solution \T for the weighted tree T (rooted at t) with groups Rt, B and parameter a, minimizing the weighted cost C7- = [((u,,)r))> w(u, v), using either the exact (Section 5.1) or approximate (Section 5.2) algorithm.
5 Project the tree solution Ar back to a solution Ag in the original graph G (Section 5.3).
return AG
Algorithm outlines our general framework for approximating the Fair Minimum Labeling (FML) problem using probabilistic tree embeddings. We begin with the input graph G = (V, E) and the FML parameters (R, B, t, a). We define the standard shortest path metric de on G, where do(u, (u, v) is the minimum number of edges embedding algorithm of Fakcharoenphol, Rao, and Talwar [13]. practice, we first sample a single weighted tree T = (V. Er, w) from the distribution D and then solve an adapted version of the FML problem on the sampled weighted tree T. We use the original node set with colors and R. terminal t, and the parameter a. The objective, however, is modified to align with the structure provided by the embedding and the goal minimizing the final cost in G. We aim to find a temporal labeling by for the tree T that minimizes the total weighted cost
path between u and v. We then employ the probabilistic tree
CT =
Σ
w(u, u) = Σ
dr(u,
(LUU),T)ET
5

---

subject to the coverage constraints being satisfied with respect to temporal reachability within the tree T, requiring that an a-fraction of the nodes in each of and R can temporally reach the terminal t.
To achieve this, we use dynamic programming algorithms presented in the following sections:
An exact algorithm (Section 5.1) finds the minimum weighted cost Cr. satisfying the constraints exactly on T.
An approximation algorithm (Section 5.2) finds labeling Ar with weighted cost CT < opt that satisfies the constraints approximately, introducing an error factor 5 S (1+)) the counts of blue and red nodes, where H is the height of T and > 0.
Finally, in Section 5.3, we discuss how the solution obtained in the tree can be projected back the graph G and Ag can be obtained.
5.1 An exact algorithm for FML in weighted trees
We compute labels at the nodes of the tree T in a bottom-up fashion starting from the leafs. The edges of the tree have weights wu, v) 2 corresponding the shortest paths distance between u, e V in G. Without loss of generality the maximum distance (in terms of edge weights) from any leaf to the root is at most k. Furthermore, all leafs are colored blue or red. We use labels of the form (b, r, c) where b and are the numbers of blue and red nodes in the subtree, and is the sum of edge weights used to connect the b + r nodes to the node having the label. For example, a blue node gets label (1, O, 0) and red node (0, 1, 0). Let v be an inner node with É children W1...., Ug. We construct the following labels based on the labels of the children. Let {Li...., Le} be the sets of labels at M1..... ug. We only choose at most one label per child that determines the (possibly empty) subtree include. Therefore, we construct most I[ (1 + L2)) labels node v. At each node we keep at most one label (b, r, c) for each possible pair (b, r) with the minimum value of c. Because r and b are most there are (n²)) possibilities of (b, r) which is also an upper bound of the number of mom-dominated) labels at each node. Algorithm 2 in the appendix shows the pseudocode.
Theorem 2. The FML problem on a tree with a single terminal can be solved in (
5.2 A bicriterial approximation
The running time of (nn²) of the exact algorithm for solving the FMI problem in trees limits its scalability. The bottleneck is the linear number of labels per node, and the pairwise merging costing O(n²) per node. So the idea to reduce the number of labels per node in a principled way. A classic method to reduce dynamic programming overhead is label sparsification by grid rounding. The key is to group labels with similar (b, r) values into a common bucket and keep only the best, i.e., lowest cost label in that bucket.
Specifically our approach partitions the integer range [0, into geometric intervals, or buckets, Beoogeeoeeei
defined as follows: Bucket i corresponds to the interval ((1 + =)²=1 (1+ =)' for i 2 1 until the upper bound n is reached. This results in O(log1+ (IB) log1+ (I)) = 0 ( log" n) buckets for possible (b, r) bbukett pairs. Once the label set L, is constructed at node v, each label (b, r, c) is mapped pair of bucket indices (Bucket BucketIndex(r)). and only the label with the minimum cost e is retained per bucket. All other labels in the same bucket are discarded, thereby reducing the label set to at most O
n) entries.
Theorem 3. Let Lete: >> O. Let T be the input tree with root and height H. (1+))H++ Let copt (hope: (Dopt:Topt: Copt. be an optimal exact label at the root t with minimum weighted cost Copt. that satisfies bopt 2 B) and Topt 2 R)R. Then the geometric bucketing algorithu finds a label E' 16/,r', ,d) in the final set Li at the root with
(i) d S Copt.
(ii) 8' 2 (a|BI//E and TTpp/E (a)R))/E
5.3 Projecting the solution to the graph G
Let Ar be the temporal labeling obtained by one of these algorithms on the tree T. The tree labeling dr must be translated into a valid temporal labeling AG for the original graph G. This projection

---

ensures that the reachability achieved in the tree is preserved in the graph. For each temporal tree edge activation (fu, u). E \T we first identify shortest path Pur between u and v in the original (fu,0),78 graph G. Let this path consist of the sequence of p = da u) edges e1, e Cp. To mimic the activation of the tree edge {u, o) time T, we activate the path Pao in G using a sequence of timestamps. The final graph labeling Àş is the union of all temporal edges generated by projecting all (fu, u).7) E År.
The projection mechanism ensures that if node w is temporally reachable from node u in the tree T using the labeling 'r, then w is also temporally reachable from u in the graph G using the labeling AG. This holds because each temporal tree edge in a path is replaced by a corresponding temporal path segment in G, and the timestamping ensures correct sequencing and avoids conflicts. Therefore, if \y satisfies the coverage constraints of Definition 1 (either exactly or approximately with factor f the projected solution λg will also satisfy these constraints either exactly or approximately with the same factor Ç in the original graph G. Note that we potentially include additional colored nodes that will be able to reach the terminal t, however, this can only improve the approximation.
Theorem 4. Algorithm I, combined with the appropriate weighted tree algorithm, yields a random- ized algorithm for FML with one terminal on general graphs with two colors.
If the exact weighted tree algorithm (Section 5.1) used, the framework produces a solution d that satisfies the fairness coverage constraints exactly, and its expected cost B[|AG]] is within an (log n) factor of the optimal cost kig. The expected running time O(n)).
If the bicriteria weighted tree algorithm (Section 5.2) is used, the framework yields solution X with expected cost E[[AG]] S Oloog kig that approximately satisfies the coverage and fairness constraints, with violation bounded by the factor & = (1 + z) where H E Ollogn). This results in randomized bicriteria (O(log appproxiiiinnnnnnnn
The expected running time is in On + ne meeAAlog* m.)
Both variants use (n)) space for the tree embedding and (n) (exact) or Ane-= log² n) (bicriteria) additional space for the DP tables.
5.4 Generalizations
The algorithms and the specific complexity analysis presented in the previous sections are for the two-group (plus no-color) case. However, the framework is generalizable. For & distinct groups, the dynamic programming label becomes (91, 92,-...- Ik, c), where 9i is the count of covered nodes from group i. The state space for the counts becomes O(re)) ). The pairwise merge operation takes ((Z*)) = O(22k) time. With n nodes, the total runtime for the exact DP is (1+2++1)
Our framework can also be extended support non-uniform activation costs w(e), while preserving the Olog n) approximation guarantee, by defining the metric for the FRT embedding using these costs. First, we compute shortest-path metric d(u. v) where the distance between nodes is defined as the minimum cost of a path between them, using the activation costs wi(e as the edge weights. We then use FRT to embed this weighted metric into a tree T. Our DP algorithm then runs on the tree T. and because the tree distances being optimized are already low-distortion approximations of the minimum activation costs, the (log n) guarantee on the final, total weighted cost holds directly.
Finally, in dynamic environments (e.g., node arrivals, failures or departures), partial recomputation of our labeling is feasible. The DP can be rerun locally on affected subtrees, and minor changes in the graph structure often preserve the validity of the tree embedding. While full dynamic adaptation is beyond the scope of our current work, the methods lend themselves such extensions.
6 Experiments
In this section, we evaluate the performance of our algorithms. We compare the following methods:
FMLAPPROX, our approximation algorithm based on Algorithm that uses the exact tree dynamic programming subroutine described in Section 5.1.
PPRO,, our bicriteria approximation algorithm based on Algorithm 1 that uses the approximate tree dynamic programming subroutine described in Section 5.2.
7

---

We designed the following greedy baselines for comparison as there are direct competitors to our approach, where we start with two natural starting points, (i) what happens if you ignore fairness entirely and focus only cost? (ii) what are the simplest, most direct ways to enforce fairness? Leading to the following baselines:
GREEDY is faimess-agnostic baseline that activates shortest paths to the closest colored nodes until a (IB) + RR) total colored nodes are covered, irrespective of group balance.
CL.SEST greedily activates unweighted shortest paths from the terminal to the closest uncovered colored node (regardless of group) until a-coverage achieved for both groups.
ALTERNATING proceeds similar to Closest, but alternates between activating the closest uncovered node from group B and group R.
We implemented all algorithms Python 3.9 and PyTorch 2.5.1. All experiments ran on a computer cluster. Each experiment ran exclusively on node with an Intel(R) Xeon(R) Gold 6130 CPU 200 96 GB of RAM. We used a time limit of 12 hours. Our source code is available at https://gitti: com/tgdemigeeeeee con//tgdesig//mml
6.1 Case study: Fair and efficient multi-source data collection
We evaluate our FML framework in a multi-source learning context, where data must be collected from distributed sources under strict resource constraints. Such sources, e.g., sensors, mobile agents, or geographically distributed streams, often differ by group and face limitations like bandwidth or energy. Ensuring fair representation of each group during training is essential to prevent biased models. However, naive approaches, such as connecting all sources, minimizing total cost, or favoring proximity, either waste resources or neglect important groups. Our method computes a single temporal edge labeling that guarantees sufficient group-wiss wiiup temporal reachabilityy to central node while minimizing the number of activations. This enables efficient and fair data collection without the need for repeated adaptation or full connectivity, outperforming the baselines.
6.1.1 Network topology and data sources
We simulate a networked learning scenario over a random geometric graph G = EV with [V| = 1024 nodes and connection radius r 0.2. The designated terminal node E V collects data from subset of data sources B U R S V \ {t}. Each of the data sources belongs to one of two demographic groups B R. assigned based on spatial proximity the terminal (near vs. far).
Each data source generates synthetic data (x. y) with x E TR?,, y E 0, 1 by sampling x from a mixture of two Gaussians and setting y deterministically:
Group B: o(H,o21) with a = 0.55, E ((-2,1), (2, (2, and y = 1 1 > 0}. Group R: N(H,021) with a = 0.55, {(1, -2), (1,2)), and y 1 1 < 0).
Thus, the two groups encode orthogonal classification rules, making it impossible to achieve high accuracy both without training both.
The algorithms activate edges A C E to connect data sources to the terminal. For the baselines, the activation cost is defined as the sum of hop-distances from all covered data sources to the terminal. The collected data is used to train a shared MIP classifier. We use a fully connected MLP using an input layer of size d = 2, followed by two hidden layers with 32 neurons each and ReI.U activations, and final output layer with single neuron and sigmoid activation for binary classification. We train the model using the Adam optimizer [23] with learning rate 0.01, batch size 64, and weight decay 10-2 for l2 regularization. The loss is binary cross- cots-entropp. Training runs for 100 epochs with early stopping based validation loss. The model is trained using the combined dataset collected from data sources temporally connected to the terminal. Accuracy is reported separately on held-out test sets for each group. We also report the coverage of nodes in B and R that can temporally reach t. We report the mean values and standard deviations over ten independent runs.
The results in Table 1 demonstrate the trade-off's between fairnsss, cost, and accuracy across different methods. The straightforward GREEDY, while achieving the low activation cost (88.3), completely neglects group R (CoverageR 0), leading to severe disparity in model accuracy between groups with

---

Table 1; Multi-source learning results (mean and standard deviations over ten independent runs).
Algorithm
Time (s)
Cost
Coverage
Coverage
Acc;
Acc
GREEDY
0.49 1: 0.08
88.3 - 6.25
64.0 E 0.00
0.0 +: 0.00
1.00 : 0.00
0.27 1: 0.17
CLOSEST
0.73 1: 0.13
0.00
44.3 2.31
32.0 i 0.00
0.97 1 0.04
0.94 -: 0.08
ALTERNATING
0.71 + 0.09
212.8 + 1.81
312 1.87
32.0 + 0.00
0.96 + 0.04
0.94 = 0.07
FMLAPPROX
69.20 18.11
74.3
33.5 + 0.53
32.3 + 0.448
0.98 + 0.03
0.93 + 0.08
FMLBIAPPROX
8.54 1 6.36
7
33.1 1 0.99
31.3 1 0.48
0.97 = 0.03
0.94 = 0.08
Асeв 1.00 and AccR = 0.27. This highlights the risk of fairness-agnostic optimization, CLOSEST and ALTERNATING heuristics ensure coverage for both groups, but incur significantly higher costs with 224.0 and 212.8, respectively. In contrast, both our FML-based algorithms, FMLAPPROX and FMLBIAPPROX, achieve near-perfect group-level fairness (Coverage
33, Coverage 32) with substantially lower cost of around 74, and maintain high accuracy for both groups with Aceg 0.97 and AceR 2 0.93. FMLBIAPPROX performs comparably to the exact method terms of fairness and accuracy, while being significantly faster (8.54s vs. 69.20s average). These results confirm the effectiveness of FML in achieving resource-efficient and equitable temporal reachability.
We also ran additional experiments where we explicitly placed the terminal at either a central (high- degree) or peripheral (low-degree) node. Our bicriteria algorithm (FMLBIA proved highly effective in both scenarios, consistently achieving over 98% of the required coverage.
6.2 Running time and approximation quality
We additionally compare the performance of our approximations FMLBIÁPPROX and FMLAPPROX. To this end, we generated Barabási-Alber graphs with n E {256, 512, 1024, 2048, 4096} and fixed attachment parameter
3 (i.e., each node connects m existing nodes). Moreover, chose e E (0.1. 0.01, 0.001}. }. For each parameter combination, we used ten independent runs. Figure 2a reports the average running time and standard deviation across all in the time limit completed runs. For the largest graphs, FMLAPPROX failed to complete five instances for n 2048 and seven for n 4096, while FMLBIAPPROX timed out three and five runs, respectively. Among the runs that finished, FMLBIAPPROX consistently outperformed FMLAPPROX, achieving up to an order-of-magnitude speedup. Importantly, decreasing led to only modest increases running time, yet produced significant gains in solution quality. Figure 2b shows the mean ratio of B (R. resp.) colored nodes selected by FMLBIÁPPROX compared to FMLAPPROX. Smaller values of particularly 0.001, yield ratios close to 1, indicating near perfect agreement with the exact baseline. These results demonstrate the effectiveness FMPRIX in achieving high-quality solutions with substantially reduced running time. Finally, the majority of the running time, more than 99.9% across all settings, is spent on solving the dynamic program on the FRT tree. The time spent tree embedding is negligible in comparison.
10a
AMgeRiAguex 0.00)
Moan Strdo (Appoux (kond))
FM
Bontinee scidd)
10P
FMg.eep (x-0.)
FMLAPF3OX
10P
0.6
101
0.4
(ewB801)) fembua)
(r-nidon)
(embus)
512
2048
Numnbe of modes [V]
Numbee of aodas [V]
(a) Mean running times.
(b) Mean approximation ratio.
Figure Comparison of TMLBIAPPROX and FMLAPPROX. The results show the mean and standard deviation error bars over ten independent runs.

---

Table Results on the real-world network.
Epsilon
Runtime (8)
Accuracy (%)
0.01
3625.0 420.7
93.1
0.001
4661.5 991.3
99.3
6.3 Practical scalability
We sampled a connected 30,000-node induced subgraph (201,900 edges) from the Pokec dataset' [39]. We randomly selected one node as the terminal and colored 10% of the remaining nodes (balanced 50/50) using the binary gender attribute (Blue male, Red female). We then ran FMLBIAPPROX with full coverage requirement (a = 1.0) and two precision settings (E = 0.01 and & 0.001) in 10 independent runs. Table 2 shows the results. Accuracy represents the ratio of achieved coverage to the required coverage. This real-world experiment confirms the practical scalability and effectiveness of our FMLBIAPPROX algorithm, which achieves high accuracy under both precision settings.
We investigated the bicriteria guarantee's dependency Over 10 runs, the average tree height was exceptionally small, H z 6.68. Our theoretical analysis provides a worst-case coverage guarantee of (1 + E) -) For & = 0.01, this guarantees at least (1.01)-7.08 92.6% coverage. Our empirically measured accuracy was 93.1 9..1%. This demonstrates that our algorithm robustly meets its formal theoretical guarantee in a real-world setting.
height H on our new Pokec dataset.
Limitations
Conceptual limitations. While the FML framework captures fundamental trade-off between temporal resource efficiency and faimess, it assumes centralized control over the activation of communication links. This limits its applicability in decentralized or asynchronous settings such as classical federated learning [19]. Moreover, the current formulation requires predefined group membership and fixed coverage thresholds, which may be restrictive in adaptive or data-driven fairness scenarios. Finally, FML treats fairness group-level temporal reachability, but does not model finer-grained objectives such as individual fairness or fairness over time.
Technical limitations. Our approximation algorithms currently focus on the case of a single terminal and two groups. While this setting already models common use cases, generalizing to arbitrary numbers of terminals and group types remains open. The exact dynamic programming algorithm has a running time complexity in O(n)), limiting scalability. The bicriteria approximation improves efficiency, reducing runtime Onn + ne 1ne-41m "loo" n)), but trades off exact fairness for scalability: its guarantees degrade with the tree height, leading to (1 + eloog factor in group coverage.
8 Conclusion and future work
We introduced the Fair Minimum Labeling (FML) problem, which formalizes the design of temporal activation schedules that ensure fair group-wise reachability under resource constraints. FML bridges gap between fairness-aware graph optimization and temporal connectivity models. We proved that FML is NP-hard and (loog nı) -had to approximate, even under restricted settings. To address this challenge, we developed randomized approximation framework based probabilistic tree embeddings, achieving tight (logn) expected-cos bounds. A bicriteria variant further scales to large networks while guaranteeing bounded faimess violations. Experiments on multi-source learning tasks confirmed that FML-based methods achieve ncar-optimal fairness and accuracy at substantially lower cost than competing baselines. Future work includes exploiting structural properties such as low treewidth or planarity, extending the model to weighted and online settings, and designing distributed variants for decentralized privacy-sensitive deployments. Moreover, extending FML to multiple terminals is a promising yet non-trivial direction. This would require the dynamic program or richer state representations, thereby substantially increasing both the state space and the complexity of the merge step.
maintain ermmina-reachability
html
10

---

Acknowledgments
This work was undertaken on Barkla, part of the High Performance Computing facilities at the University of Liverpool, UK.
References
[1] Sara Ahmadian, Alessandro Epasto, Ravi Kumar, and Mohammad Mahdian. Clustering without over-representation. In Proceedings of the 25th ACM SIGKDD International Conference Knowledge Discovery & Data Mining, pages 267-275, 2019.
[2] Eleni C. Akrida, Leszek Gasieniee, George B. Mertzios, and Paul G. Spirakis. The complexity of optimal design of temporally connected graphs. Theory of Computing Systems, 61:907-944, 2017.
[3] Kyriakos Axiotis and Dimitris Fotakis. On the size and the approximability of minimum temporally connected subgraphs. In Proceedings of the 43rd International Colloquium Automata, Languages, and Progrumming, pages 149:1-149:14, 2016.
[4] Yair Bartal. Probabilistic approximation of metric spaces and its algorithmic applications. In Proceedings of the 37th Conference on Foundations of Computer Science, pages 184-193, 1996.
[5] Sujoy Bhore. Sourav Chakraborty, Satyabrata Jana, Joseph S. B. Mitchell, Supantha Pandit, and Sasanka Roy. The balanced connected subgraph problem. Discrete Applied Mathematics,
3 319:111-120 2022.
[6] Avishek Bose and William Hamilton. Compositional fairnsss constraints for graph embeddings. In Proceedings of the 36th International Conference on Machine Learning, pages 715-724, 2019.
[7] Arnaud Casteigts, Paola Flocchini, Walter Quattrociocchi, and Nicola Santoro. Time-varying graphs and dynamic networks. International Journal of Parallel, Emergent and Distributed Systems, 27(5):387-408; 2012.
[8] Simon Caton and Christian Haas. Fairness in machine learning: A survey. ACM Computing Surveys, 56(7), 2024.
[9] April Chen, Ryan A. Rossi, Namyong Park, Puja Trivedi, Yu Wang, Tong Yu, Sungehul Kim, Franck Demoncourt, and Nesreen K Ahmed, Faimess--wwae graph neural networks: A survey, ACM Transactions on Knowledge Discovery from Data, 18(6):1-23, 2024.
[10] Flavio Chierichetti, Ravi Kumar, Silvio Lattanzi, and Sergei Vassilvitskii. Fair clustering through fairlets. In Advances in Neural Information Processing Systems, volume 30, 2017.
[11] Enyan Dai, Tianxiang Zhao, Huaisheng Zhu, Junjie Xu, Zhimeng Guo, Hui Liu, Jiliang Tang, and Suhang Wang. A comprehensive survey trustworthy graph neural networks: Privacy, robustness, fairness, and explainability. Machine Intelligence Research, 21(6):1011-100 2024.
[12] Yushun Dong, Jing Ma. Song Wang, Chen Chen, and Jundong Li. Fairness in graph mining: A survey. IEEE Transactions Knowledge and Data Engineering, 30500110033,-0002, 2023.
[13] Jittat Fakcharoenphol, Satish Rao, and Kunal Talwar. A tight bound on approximating arbitrary metrics by tree metrics. In Proceedings of the 35th Annual ACM Symposium on Theory of Computing, pages 448-455, 2003.
[14] Uriel Feige. A threshold of In for approximating set cover. Journal of the ACM (JACM), 45(4):634-652 1998.
[15] Edoardo Galimberti, Martino Ciaperoni, Alain Barrat, Francesco Bonchi, Ciro Cattuto, and Francesco Gullo. Span-core decomposition for temporal networks: Algorithms and applications. ACM Transactions on Knowledge Discovery from Data (TKDD), 15(1): 1-44, 2020.
[16] Aristides Gionis, Lutz Oettershagen, and Ilie Sarpe. Mining temporal networks. Companion Proceedings of the ACM on Web Conference 2024, pages 1260-1263, 2024.
11

---

[17] SHI Huaizhou, R. Venkatesha Prasad, Ertan Onur, and I.G.M.M. Niemegeers. Fairness in wireless networks: Issues, measures and challenges. IEEE Communications Surveys & Tutorials, 16(1))5-24, 2013.
[18] Zeinab Jalali, Qilan Chen, Shwetha M. Srikanta, Weixiang Wang, Myunghwan Kim, Hema Raghavan, and Sucheta Soundarajan. Fairness of information flow in social networks. ACM Transactions on Knowledge Discovery from Data, 17(6):1-26, 2023.
[19] Peter Kairouz, H. Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Ar- jun Nitin Bhagoji, Kallista Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, al. Advances and open problems in federated learning. Foundations and trends@) in machine learning, 14(1-2):1 1-200, 2021.
[20] Richard M. Karp. Reducibility among combinatorial problems. In Proceedings of Complexity of Computer Computations, pages 85-103, 1972.
[21] Frank Kelly. Charging and rate control for clastic traffic. European transactions Telecommuu- nications, 8(1):33-37, 1997.
[22] David Kempe, Jon Kleinberg, and Amit Kumar. Connectivity and inference problems for tem- poral networks. In Proceedings of the 32nd Annual ACM Symposium on Theory of Computing. pages
2000.
[23] Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint 11Xiv:1412.6980, 2014.
[24] Matthäus Kleindessner, Samira Samadi, Pranjal Awasthi, and Jamie Morgenstern. Guarantees for spectral clustering with faimess constraints. In Proceedings of the 36th International Conference on Machine Learning, pages 3458-3467, 2019.
[25] Nina Klobas, George B. Mertzios, Hendrik Molter, and Paul G. Spirakis. The complexity of computing optimum labelings for temporal connectivity. Journal of Computer and System Sciences, 146:103564, 2024.
[26] Yuyi Mao, Xianghao Yu, Kaibin Huang, Ying-Jun Angela Zhang, and Jun Zhang, Green edge AI: contemporary survey. Proceedings of the IEEE, 1 11(07)880-911, 2024.
[27] George B. Mertzios, Othon Michail, Ioannis Chatzigiannakis, and Paul G. Spirakis. Tem- poral network optimization subject connectivity constraints. In Proceedings of the 40th International Colloquium on Automata, Languages, and Programming, pages 657-668, 2013.
[28] George B. Mertzios, Othon Michail, and Paul G. Spirakis. Temporal network optimization subject to connectivity constraints. Algorithmica, 81(4):14161149, 2019,
[29] Othon Michail. An introduction to temporal graphs: An algorithmic perspective. Internet Mathematics, 12(4):239-28) 2016.
[30] Petra Mutzel and Lutz Oettershagen. On the enumeration of bicriteria temporal paths. In International Conference on Theory and Applications of Models of Computation, pages 518- 535. Springer, 2019.
[31] Omar Nassef, Wenting Sun, Hakimeh Purmehdi, Mallik Tatipamula, and Toktam Mahmoodi. A survey: Distributed machine learning for 5G and beyond. Computer Networks, 207:108820, 2022.
[32] Madeline Navarro, Samuel Rey, Andrei Buciulea, Antonio G. Marques, and Santiago Segarra. Fair glasso: Estimating fair graphical models with unbiased statistical behavior. In Advances in Neural Information Processing Systems, volume 37, pages 139589-139620, 2024.
[33] Lutz Oettershagen, Athanasios L.. Konstantinidis, and Giuseppe F. Italiano. An bage- decomposition framework for temporal networks. Proceedings of the Eighteenth ACM International Conference Web Search and Data Mining, pages 735-743, 2025.
12

---

[34] Lutz Oettershagen, Nils M. Kriege, and Petra Mutzel. A higher-order temporal h-index for evolving networks. In Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 1770-1782, 2023.
[35] Lutz Oettershagen, Petra Mutzel, and Nils M. Kriege. Temporal walk centrality: ranking nodes in evolving networks. In Proceedings of the ACM Web conference 2022, pages 1640-1650,
2022.
[36] Lutz Oettershagen, Honglian Wang, and Aristides Gionis. Finding densest subgraphs with edge-color constraints. In Proceedings of the ACM Web Conference 2024, pages 936-947, 2024.
[37] Tahleen Rahman, Bartlomiej Surma, Michael Backes, and Yang Zhang. Fairwalk: Towards fair graph embedding. Proceedings of the 28th International Joint Conference on Artificial Intelligence, page 3289-3295, 2019.
(38) Roy Schwartz, Jesse Dodge, Noah A. Smith, and Oren Etzioni. Green AI. Communications of the ACM, 63(12):54 63, 2020.
[39] Lubos Takac and Michal Zabovsky. Data analysis in public social networks. In International scientific conference and international workshop present day trends of innovations, volume 1, 2012.
[40] Alan Tsang, Bryan Wilder, Eric Rice, Milind Tambe, and Yair Zick. Group-faireess in influence maximization. arXiv preprint arXiv: 190.:0093300 2019.
[41] Nitin Vaidya, Paramvir Bahl, and Seema Gupta. Distributed fair scheduling in a wireless LAN. In Proceedings of the 6th Annual International Conference on Mobile Computing and Networking, pages 167-178, 2000.
[42] Jana Vatter, Ruben Mayer, and Arno Jacobsen. The evolution of distributed systems for graph neural networks and their origin in graph processing and deep learning: A survey, ACM Computing Surveys, 56(1):1-37, 2023.
[43] Joost Verbraeken, Matthijs Wolting, Jonathan Katzy, Jeroen Kloppenburg, Tim Verbelen, and Jan S. Rellermeyer. A survey distributed machine learning. ACM Computing Surveys, 53(2):1-33, 2020.
[44] Dennis Robert Windham, Caroline J. Wendt, Alex Crane, Madelyn J. Warr, Freda Shi, Sorelle A. Friedler, Blair D. Sullivan, and Aaron Clauset. Fast algorithms improve fair information access in networks. arXiv preprint arXiv:2409.03127, 2024.
[45] Zhuoping Zhou, Davoud Ataee Tarzanagh, Bojian Hou, Qi Long, and Li Shen. Fairness- aware estimation of graphical models. Advances in Neural Information Processing Systems, volume 37, pages 17870-17909, 2024.
13

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
The abstract clearly states the contributions made in the paper.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: We added a section discussing conceptual and technical limitations of the work (see Section 7).
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
14

---

Justification:
All theoretical results have proofs in Appendix A.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification:
We clearly describe the algorithms used in the experiments (see Section 6).
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architccture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reprodueibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
15

---

Answer: [Yes]
Justification: Data, source code, and scripts are available in an anonymous public repository. The link is available in Section 6.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to to reproduce the results. See the NeurIPS code and data submission guidelines (https: //iips.cocc httppscccppuull///geeee wet.guudde/eeeeaeeeeee
ssi ssionPolccy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer:
[Yes]
Justification: All details are provided in the experiments section (Section 6).
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: We use mean and standard deviation in experiments and clearly describe this fact.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
16

---

It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative еπхо rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: We clearly describe the experimental setup and the used computer resources at the beginning of Section
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't make into the paper).
9. Code ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics https: / http://rrpp..ccppl/////eeeeeeee
Answer: [Yes]
Justification:
We have read the NeurlPS Code of Ethics and have followed it.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there is special consid- cration due to laws or regulations their jurisdiction..
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: We discuss the broader impacts on society the introduction (Section and in the limitations section (Section 7).
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
17

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: Our work does not poses such risk and safeguards are not necessary.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification: Our work does not existing assets.
Guidelines:
The answer NA means that the paper does existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
18

---

If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: Our paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmoel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: Our work does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question:
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
Our paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration of LLM usage
19

---

Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that if the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, or originality the research, declaration is not required.
Answer: [NA]
Justification: The core method development in this research does not involve LLMs any important, original, or non-standard components.
Guidelines:
The answer NA
that the method development in this research does involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy buttps://neurppe:: http///rpps.ccoooeeeeeeeeeeeeeee cc//oonfeeeeccce/222//III for what should or should be described.
20

---

Appendix
Algorithm 2:
Bottom-up Label Computation on Tree T
Input:
Rooted tree T = (Vr, Er) with edge weights w(u, v), coloring c Vr - {B, R, 0). Vr, a set of non-dominated labels rb,
Output: At each node
1
foreach node v E Vr in post-order do
Initialize Labels(U) <- 0)
3
if c(v) = B then add (1, 0,0) if (() R then add (0, 0) C+ C ((0,0,0)}
5
foreach child of do 1/ Merge labels C + C Labels(u) and keep track of edge weights C'+
8
foreach (b1, 6)) E do
Add (b1, 11 C1) C
10
foreach (b2, r2, 02) E Labcls(u) do
11
Add (b) b2, P1 72, Ci + C2 + wov, u)) C'
12
Keep only the label with minimum for each (b, r) in Labels(v)
A
Omitted Proofs
Observation 1. The FML problem generalizes both the Minimum Labeling (ML) and the Minimum Steiner Labeling (MSL) problems.
Proof of Observation 1. In MI., the goal is to make the entire graph temporally connected. We model this by setting the terminal set T V. and using single color с₁ for all nodes, i.e., C. {(i} with <(v) = Ci for all v E V. Additionally, we set p = [T], and we define the requirement function (V) |V12, which requires full pairwise temporal reachability among all nodes. Then, any labeling that satisfies the FML condition r(V.V) 2 |V|2 must realize all-pairs temporal connectivity, which is exactly the ML objective. In MSL, the goal is to ensure temporal connectivity among given subset terminals T Ç V. We use one color e1 and assign it only to the nodes in T while all other nodes then define the requirement function Sa (T) ITi² to require full temporal connectivity within the terminal set. The resulting FMI. instance enforces exactly the MSL condition, and minimizing the cost corresponds to MSL.
assigned any color, i.e., C = {ci, 0} and Va, T. Again, set p -77.. We
L
Proof of Theorem I. Regarding the membership NP, given an instance of FML with graph G = (V. F., c), color set C, requirement functions {fe)cec, terminal set T C V. budget candidate temporal labeling
N, and
- P(N). we first check whether [}] < k. This is a simple summation over the labeled edge sets and takes polynomial time. Next, for each color class E C, we compute the total number of temporally reachable terminal nodes from nodes V., For each V, and each induced by A. This can be done using a modified BFS per source node, each with time complexity polynomial in |V| [X), As have at most [V| [T] such checks across all color classes, the total verification time is polynomial. For each E C. we verify that r(V., T) 2 fo(V.. If this holds for all colors, the labeling is valid.
T. check if there exists temporal path from u to in the temporal graph
For hardness, we reduce from the SET COVER problem, which is NP-hard and admits no ((1 lo) approoxxiiaaoonn unless NP C DTIME[1 Oloo Oloo r)..
Let (U, S, ksc) be Set Cover instance, where U [ui...., um is the universe and S collection of subsets S; C U. We construct an FML instance with one ter- minal and one color class as follows, The graph G = (V, E, includes terminal node one node 8; for each set S, E S, one node lj for each element u; E and chain of intermediate nodes wi.....,, W for each s, which simulate labeling cost. Edges added between each t, and
(Si,.... S.
21

---

every s; such that u, E St, and each is connected to through its respective chain. Thus, the vertex set is V = utf im [S)...... ....................... sn U {w,, 1 S S n, S & < L}. and the edge set includes (1), if uj E S; and the path edges {s,, Wx,1 J. [Wi,1, mx.)). ... (
We define single color class et and assign it all i, nodes, i.e., Va, = (1,,..., fm), and set the 1. The requirement function for color is defined as fcr (Vo,) = m, requiring that all tj nodes reach r via temporal paths. The budget set to k = m + L Ksc.
terminal set as T = {r} and
Suppose there exists a cover S" = {S S } with & S ksc such that USES S U. Then we can construct temporal labeling as follows. For each chosen set Si, E S', we assign labels with timestamps 2, 3..... : L++ along its path from St, ro For each element uj, we select some S. S' containing U and assign timestamp 1 to the edge (t..St, St, }. Every t3 now has valid temporal path to r via Sip, and the total number of labels used is m + L. & m + L ksc, so the faimess requirement satisfied.
Conversely, suppose there is a valid labeling of cost at most = m + L. ksc such that every L is temporally reachable from some 8 via a path to Each of the element nodes must at least one label on an edge to a set node st, accounting for m labels. For any s; to enable reachability to r, the entire chain of L edges must be labeled with consecutive timestamps. Therefore, the number of such activated chains is at most ksc. The corresponding sets S' form a set cover of U of size at most ksc.
To show the inapproximability, we use pre-preserving reduction from Set Cover. We choose = mm/0,, where 8 > is the gap parameter. In the YES case, the optimal FML labeling cost is at most m L ksc, and in the NO case, the cost must exceed m + L- (1 8) In kisc. Since L significantly larger than m, the additive term m becomes negligible, and the approximation gap approaches (1 - d) log m. Because the total number of nodes in the FMI instance is n = ( L) and I, = (mm), we have n = ((isc - m.) and hence log n = O(lg m). Therefore, the logarithmic hardness gap in for SET COVER translates directly to a O n) gap for the FML instance.
Proof of Theorem 2. We can represent not including subtrees using an additional label (0, 0,0) at each node. Suppose a node e has children U1, U2,.... Ue with label sets L1, I......, .., Lzg holds [Lal S C' with C = (n²)). We can combine L, and L2 into new set L1,2 of size at most C keeping only minimal-cost labels for each pair (b, r). Then combine L1,2 with L3 to get 2,,2,3, and so forth. Each pairwise merge of two sets of size at most C can be done in (CC²) time by considering all pairs of labels. We sum up (b, r), add the costs plus weights of the edges connecting children, and then discard dominated labels. Because we immediately discard duplicates and dominated labels, the intermediate result remains of size at most C. Since, each merge corresponds to one child, or equivalently to one edge, and there are n edges, the total costs of merging is ((n)) for all nodes. Therefore, the total running time is in O(n)).
Before we prove Theorem 3, we show the following result.
Lemma 1. Let > O. Let T be tree with root t, height H, and edge weights v) 2 1. For any node v in T with height he in its subtree, hy S H and any exact label = (b, r, e) at u, there exists a label l' = (',T''c) kept in the approximate set L2 at node with
(i) c ccc
(ii) 8 b/(1 + e)thut and r' 2 r1((1 + te)not1
Proof. The proof proceeds by induction the height he of node For the base case consider
a leaf u with ht = 0. Let (oolor and Teolor(1) (t) be indicator functions returning one if v is blue or red, resp., and zero otherwise. The only possible exact labels are l = (brolor (1), Tcolor (v). 0). with weighted cost e = O. The algorithm generates and keeps this exact label l' = l. It holds 0 and D' = b. We require b > b/(1 + c)0+1 b/(1 + E). This holds since b fo. 1} and 1 + E 1. Similarly, r' 2 r/(1 E). Therefore, the claim holds for leaves.
è' = 0 1050
Now, for the inductive step consider an inner node with height Ii, > O. Assume the claim holds for all children u, of v. Let ha, be the height of child u;, so he; S hn 1, Consider an exact label l. (e, formed at node by combining exact labels Lu, (bu., Twi Cu;) from subset
22

---

S S (I..... 4 of its children, plus the node v's own color. The exact counts and weighted cost are
bw: + beotor (v)
and
To Σ Top Toolor (v)
Cy Σ (cu, + www, ui).
By the inductive hypothesis applied to each child u, (for i S), there exists a label Ey Wursea Ta (yy)) kept in L such that: dy S Cu,, Vy, 2 / + +,,,, and r'y 2 raz/ (1 + te
The approximation algorithm node generates candidate label Ey = (b" To c by combining these kept labels Ey, from the children with
6" Σ by, + bootor (v) and r" =
-E r/ + Tcolor (v)
c E(d, + w(w, u.))
Now, for the costs we have c Eies(Cu, + w(w,uu)) s Eies(cu, u(v,u)) cy. Thus, dt S Cv. Moreover, for b" it follows
b Σ by, + (oolor()) 2 (1 E) + (1).
8
iES
iES
Since hwg S lbu 1, we have (1 + e) +1 < (1 + 8) 1)+1 = e)
b
boolor (v)
6
+ (1 + t)
(since (1 + (1+ /v 2 1)
(1 + E)u
iES
1
Σ bun + booloo(()) LiES
by
(1 Euuu
(1 + =)
Similarly, have r r + t)
Now, this candidate label 5 = rb", c falls into specific (b, r) r--bucket defined by the geometric grid. The algorithm selects one label ly (b,,, Th,, c,), from all candidates falling into this bucket to keep the final set L', specifically the one with the minimum cost d,
Since l was a candidate this bucket with cost cy the chosen label & must satisfy d, S c. Combined with c/'' S Cv. we get d, S Cu. proving part (i) of the claim for node
Because &, and E are in the same (b, bu-kkc defined by ratio (1 + E), their counts are related by the bucket definition: b, /1 + E) and r' 2 /1 + e). (If b" or r is O, the inequality holds trivially).
Combining the bounds we prove part (ii) with
6,
M 1 + 1te
6"
b + r)
by
and
T/ 2
!!
Tv
(1 (1+
I 1
(1 + 1)+
We are now ready prove Theorem 3.
Proof of Theorem: 3. Let Copt (Popt; Fopt, Copt) be optimal exact label at the root / (node height H) satisfying hopt 2 a|B) and rops 2 ar R By Lemma applied at the root node there exists label &' = (','', kept in the final approximate set I with e' & Copt which immediately verifies part (i). Moreover, it holds with { = (1 H+1 that
8' 2 bopt (lopt((1= (1+5) H+1 = E and
r'2 Toptt1 + +
H+ -ropt/S
For part (ii), from bopt a Bl and Topt 2 a| it follows 8' 2 (a|B))/E and r' (a|R))/E.
23

---

Proof of Theorem 4. edge activations, i.c.,
The cost of the final solution in the graph G is the total number of temporal
A S
Σ
Purl
E
do(u, v).
((),)).))Ar
can relate this cost to the optimal cost kg of the original FML problem in G using the properties
of the embedding and the weighted tree cost Cr Σ dr(u, v) optimized by tree algorithm.
By non-contraction (de (u, v) I (u, 1) for all u, v), we have
|AG
Σ
dc(u,e)
Σ
dr(u,v) CT.
((a,)),0)EA
((a,0),))E77
Let Ag be an optimal solution in with cost k2 = 1a This solution induces some temporal
structure the tree T. Let Cr(Ag) be the corresponding weighted cost the tree required to support the reachability of A
The expected stretch property implies (summing over the paths corresponding to X²):
Br-D(Cr(Ae)] & O(logn)
Σ
da(u, v) (log
((u,)),t)Exz
The optimal weighted cost on the tree, Cr.opts must satisfy CT S Cr())),, as X provides one way to achieve the required reachability on T.
Our tree algorithm finds a solution År with weighted cost OT such that CT CT either exactly, or via the approximation. Therefore, it follows Aal S Or S CT S Cr()))
Finally, by taking the expectations the random choice of the tree T ~ D, we have
[|| < E(Cr(Xa)) < Ollogn)kg.
Let G (V,E) with [V| n, E m. The distances in G and the FRT embedding can be computed in On)²). Using the exact DP of Section 5.1, the overall expected running time is
Texact (n, m) = (n²)
due to the exact tree DP, see Theorem 2. The projection back to G needs O(AAT) m) S O(n²) time.
Using the bicriteria (Ollog n), {) approxxximiioo the expected running time is
T Tapprox (n, m, E) Onn² no ==="'og"1)
where the second term is due to the step again fits in the same bound.
(1t log² n)² pairwise merges of label buckets. The projection
B Application Example
We give concrete high-impact application scenario: Consider medical AI initiative deployed a developing region to collect patient data for training a diagnostic model. The setting involves remote rural villages with limited connectivity and urban health hubs with better infrastructure. Devices operate under tight energy constraints and are duty-cycled, i.e., radios are only active during coordinated upload windows conserve battery.
Nodes V: Participants' smartphones, community health hubs, and the central server.
Groups VB, Vg: For example, urban (near, well-connected) vs. rural (remote) participants; we must connect an a--raction of each. Alternative groupings could capture other fairness dimensions, e.g., gender or ethnic communities (demographic fairness), users with high-end vs. low-end devices (resource fairness), or ooler-powered vs. grid-powered nodes (energy faireess).
24

---

Terminal t: The central server.
Edges E: Potential short-range (Bluetooth/Wi-FF Direct) links to hubs and long-range links from hubs to I.
Temporal labeling A: Each activated edge is assigned few global upload rounds, i.e., the only times radios are awake.
Cost: The total number of edge-time activations (each consumes energy when radios leave sleep mode).
Why temporality matters, Data must traverse time-respecting paths: if a rural phone u forwards to hub e in round TI, then must forward towards later round 72 >> т1- Simply picking a static path is insufficient; we need an ordered activation plan consistent with duty-cycling.
Outcome. FML computes sparse, globally scheduled activation plan with few rounds and few active links that guarantees at least ax Val and a Vil nodes can reach temporally, while minimizing total ups (edge-time labels). This aligns with real duty-cycled systems where communication is batch-scheduled to conserve energy and bandwidth.
25


Reviews:
[{"review_id": "SrRVwEanPH", "reviewer": "Reviewer_7pM4", "summary": "This paper introduces a new problem: Fair Minimum Labeling (FML) which lies in the intersection of temporal graph algorithms and fairness in decision making. The problem asks for the minimum cost for labeling edges, each at a set of timestamps, on a given graph, such that at least a fixed portion of nodes in each color group can \"temporally reach\" (meaning there exists a path of edges with ) a given set of terminal nodes. The paper then gives a concrete algorithm (and its more scalable approximation version) to solving such a problem in the case of two color groups and singleton terminal node. It completes the story with proving the hardness of the problem, even for singleton node case with only one terminal. The results are complemented with experiments with practical tasks.", "questions": "1. I don't have much temporal graph context. I can kind of see its practical use, but it would still be nice to have a concrete example where this kind of graph is used, and show what the nodes and the temporal activation of edges embody for a real-life problem, and why the temporal information matters.\n2. Are the results in Sec. 5 limited to the two-colors-plus-no-color case only? It seems the derivation of run-time uses that.\n3. Do you know how the run-time scales with size of graph on the real datasets? While theory suggests polynomial run-time, in practice it could be different. How did you choose the graph size in the experiments?\n4. Do you have the de-composition of your algorithms? They seem to be taking way more time than the baselines with improvements in performance. Do we know if the tree-embedding or the labeling algorithm takes more time?\n5. If I understand things correctly, in the case of singleton terminal, essentially we are solving a fair connectivity problem on the static graph. While the reduction is simple and effective, the algorithm itself is not concerned with any temporal information. Is that correct? Hence we kind of lose the temporal aspect of the problem. Have you any thoughts on how to solve this problem in the multi-node terminal case?\n6. If the terminal is singleton, is this problem essentially equivalent to finding a minimum cost tree that spans at least a given portion of nodes of both colors? The resulting chosen edges seem to always form a tree that connects a chosen set of nodes to the terminal node.", "limitations": "Yes.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths:\n- The problem is new and seems to have practical application, so I think it is definitely worth studying. Especially, introducing fairness into problem formulation should be important for such a problem.\n- The study is quite complete (at least with the given assumptions). The authors have proposed the problem, proved the hardness the found solutions that match the performance bounds. \n- The algorithm seems easy to implement, so potentially usable.\n\nWeaknesses:\n- The experiments are somewhat less convincing than the theory. My major concern is that it seems too slow, especially compared to the benchmarks. Further, the self-synthesized datasets seem a bit too extreme, as it is generating two clusters of points that are in general very far away from each other. As a result GREEDY completely overlooks one of them. \n- The baselines are limited, partially attributed to this problem being newly proposed. However, the chosen baselines clearly have some deficiency in either the fairness or cost perspective. GREEDY is bad for fairness because it doesn't account for it. CLOSEST is bad for cost because it blindly activates the edges along the shortest path (so it can use the same edge multiple times). Is there no simple baseline that seems to make sense for both?\n- The algorithm uses some nice techniques. I'm not an expert in temporal graphs so I'm not sure how novel they are given the temporal graph contexts, but it seems to lack technical depth.", "was_revised": true, "final_justification": "I have read the authors' rebuttal and the response of other reviewers. The authors' response has better motivated the paper with a deeper discussion on the application and provided additional experiments. I will keep my current score as I remain reserved about the theoretical complexity and the level of restrictions imposed by the assumptions made in the paper.", "rebuttal": "Thank you for your thoughtful and constructive review. We address each of your points below.\n\n**W1.** We agree our methods (FMLAPPROX, FMLBIAPPROX) have higher runtime than simple heuristics. This is expected: FML is NP-hard and log-approximation hard. Our algorithms offer provable guarantees, while GREEDY and CLOSEST are fast precisely because they ignore fairness or efficiency/costs. As shown in Table 1 and Figure 2, FMLBIAPPROX achieves near-identical solution quality to the exact DP, but with significantly reduced runtime.\n\nThe synthetic dataset is intentionally challenging. It simulates structural inequality (e.g., rural vs. urban access), where fairness-agnostic methods fail. This contrast highlights the need for principled algorithms like FML.\n\nWe additionally added new experiments on a larger real-world data set (see answer of **Q3**).\n\n\n\n**W2.** We agree that the set of direct competitors is limited. This is a direct consequence of the novelty of the FML problem formulation, which, to our knowledge, is the first to formally combine temporal reachability, group fairness constraints, and minimum activation cost.\n\nThe question of a \"simple baseline that seems to make sense for both\" is an excellent one. However, designing such a baseline is non-trivial and quickly approaches the complexity of the FML problem itself. Our chosen baselines represent the most natural starting points:\n\n - GREEDY: What happens if you ignore fairness entirely and focus only on cost? (Result: unfairness).\n - CLOSEST/ALTERNATING: What are the simplest, most direct ways to enforce fairness? (Result: high cost).\n\nThey define the performance extremes, illustrating why FML’s principled approach is needed.\n\nWe will add a short clarification to highlight these design choices and their limitations in Section 6.\n\n**W3.**  While our approach builds on known techniques (tree embeddings, dynamic programming), our main contribution lies in their novel integration to tackle the FML problem which is a new and challenging formulation that unifies fairness, temporal reachability, and cost minimization. We introduce:\n\n -  The first formal definition of FML, capturing a real-world trade-off previously unaddressed;\n -   A probabilistic tree embedding to make fairness-constrained temporal reachability tractable;\n -   Exact and bicriteria DP algorithms that minimize activation cost while enforcing multi-group coverage;\n -   Provable approximation guarantees that match the problem’s hardness lower bound in expectation.\n  \nTo our knowledge, this is the first framework to address fairness in temporal network design with rigorous algorithmic and theoretical guarantees.\n\n  \n\n**Q1:** Consider a medical AI initiative deployed in a developing region to collect patient data for training a diagnostic model. The setting involves remote rural villages with limited connectivity and urban health hubs with better infrastructure. Devices operate under tight energy constraints and are duty-cycled, i.e., radios are only active during coordinated upload windows to conserve battery.\n\n-   Nodes V: Participants’ smartphones, community health hubs, and the central server.\n    \n-   Groups $V_B$, $V_R$​: Urban (near, well-connected) vs. rural (remote) participants; we must connect an $\\alpha$-fraction of each (groups could also represent, e.g., demographic or ethnic divisions)\n    \n-   Terminal $t$: The central server.\n    \n-   Edges $E$: Potential short-range radio signal (e.g., Wi-Fi Direct) links to hubs and long-range links from hubs to t.\n    \n-   Temporal labeling $\\lambda$: Each activated edge is assigned a few global upload rounds, i.e., the only times radios are awake.\n    \n-   Cost: The total number of edge–time activations (each consumes energy when radios leave sleep mode).\n    \n-   Why temporality matters. Data must traverse time-respecting paths: if a rural phone $u$ forwards to hub $v$ in round $\\tau_1$​, then $v$ must forward towards $t$ in a later round $\\tau_2>\\tau_1$​. Simply picking a static path is insufficient; we need an ordered activation plan consistent with duty-cycling.\n    \n\nFML computes a sparse, globally scheduled activation plan with a few rounds and few active links that guarantees at least $\\alpha|V_B|$ and $\\alpha|V_R|$ nodes can reach t temporally, while minimizing total wake-ups (edge–time labels). This aligns with real duty-cycled systems where communication is batch-scheduled to conserve energy and bandwidth.\n\n  \n\n**Q2:** Yes, the algorithms and the specific complexity analysis presented in Section 5 are for the two-group (plus no-color) case. The $O(n^5)$ runtime of the exact DP, for instance, arises from merging labels of the form $(b, r, c)$, where the state space for $(b, r)$ is $O(n^2)$.\n\nHowever, the framework is generalizable. For $k$ distinct groups, the DP label would become $(g_1, g_2, \\ldots, g_k, c)$, where $g_i$ is the count of covered nodes from group $i$. The state space for the counts would become $O(n^k)$. The pairwise merge operation would take $O((n^k)^2) = O(n^{2k})$ time. With $n$ nodes, the total runtime for the exact DP would be $O(n^{2k+1})$. This is polynomial for any fixed $k$, but the dependency on $k$ is exponential. This is a standard characteristic of such multi-parameter dynamic programming solutions. Our focus on $k=2$ provides a clear and practical starting point for this new problem area.\n\nWe will briefly discuss this generalization and its complexity in the revised version.\n  \n\n**Q3:** This is an excellent question about practical scalability. To address it directly, we ran our algorithm on a large, 20,000-node real-world network. We conducted an additional set of experiments on a real-world social network. Specifically, we sampled a connected 20,000-node induced subgraph (201,900 edges) from the Pokec dataset (available at SNAP). We randomly selected one node as the terminal and colored 10% of the remaining nodes (balanced 50/50) using the binary gender attribute (Blue = male, Red = female). We then ran FMLBIAPPROX with full coverage requirement ($\\alpha = 1.0$) and two precision settings ($\\varepsilon = 0.01$ and $\\varepsilon = 0.001$) in ten independent runs.\n\nThe results are summarized below:\n\n| Epsilon | Runtime ± Std (s) | Accuracy (%) |\n|---------|-------------------|-------------------|\n| 0.01 | 3625.0 ± 420.7 | 93.1 |\n| 0.001 | 4661.5 ± 991.3 | 99.3 |\n\n  \n\nAccuracy here represents the ratio of achieved coverage to the required coverage. These real-world experiments confirm the practical scalability and effectiveness of our FMLBIAPPROX algorithm. Even on a complex social network with 20,000 nodes and nearly 202,000 edges, the algorithm achieves high accuracy under both precision settings. The results demonstrate that our method not only handles synthetic benchmark graphs efficiently but also performs reliably in realistic, large-scale settings, and hence supporting its applicability to real-world fairness-aware network design tasks. We will include this experiment and its results in the revised manuscript.\n\n  \n\n**Q4:** The majority of the runtime, more than 99.9% across all settings, is spent on solving the dynamic program on the FRT tree. The time spent on tree embedding is negligible in comparison. This confirms that our approach already minimizes preprocessing overhead and that future runtime improvements should focus on accelerating the labeling phase.\n\n  \n\n**Q5:**   While the setting simplifies with a single terminal, the temporal aspect remains essential. The solution is a temporal labeling $\\lambda$ assigning timestamps to edges, and the cost is the total number of such activations. The projection step (Section 5.3) constructs time-respecting paths from the tree back to the original graph. Although the input graph is static, the constraints, objective, and solution are inherently temporal.\n    \nExtending to multiple terminals is a promising but non-trivial direction. The notion of coverage would shift from \"reaches $t$\" to \"reaches a fraction $\\rho$ of terminals\", requiring the DP to track which terminals are reachable or use more complex reachability structures. This would substantially increase the state space and the complexity of the merge step.\n\nWe will mention multi-terminal extensions and associated challenges as a future direction.\n\n**Q6:** With a single terminal $t$, FML does boil down to “pick a minimum‑cost structure that lets at least an $\\alpha$-fraction of blue and red nodes reach $t$.” In fact, the paper’s algorithms root a tree at $t$ and solve the problem on that tree before projecting the result back to the original graph.\n\nHowever, it is not strictly the same as a plain “minimum-cost tree spanning quotas of each color” (a quota/colored Steiner-type problem), because:\n\n-   Cost is per timestamped activation, not just per edge. An edge can be used multiple times at different timestamps and each use counts toward the cost.\n-   Feasibility depends on temporal order (strictly increasing times along each path). That constraint doesn’t exist in standard Steiner variants.\n-   After solving on an embedded tree, the solution is projected back to $G$ via shortest paths, which can introduce additional edges and is not guaranteed to stay a single static tree.\n    \n-   The problem is NP-complete even in this single-terminal setting, with $\\Omega(\\log n)$ hardness of approximation which is stronger hardness than many classic tree problems.  \n      \n    \n\nYour intuition that “the chosen edges seem to form a tree” is still largely right: with one sink, any cycles are wasteful, so an optimal (or near-optimal) labeling can be made cycle-free in the underlying static graph. But the temporal labeling/cost model is what keeps FML from being literally equivalent to a rooted quota Steiner tree. The paper itself notes connections to Steiner-type problems and the Balanced Connected Subgraph problem, but emphasizes the extra temporal and fairness structure."}, {"review_id": "I6ihRqHrQh", "reviewer": "Reviewer_dR4R", "summary": "This paper introduces the Fair Minimum Labeling (FML) problem, motivated by applications like fair data collection or model updates in edge-cloud systems. The authors prove FML is NP-hard, then propose probabilistic approximation algorithms achieving tight approximation bound. Empirical evaluation on multi-source learning tasks shows that FML-based methods enforce group fairness with significantly lower activation cost than baseline heuristics while maintaining high accuracy across groups.", "questions": "a) Can this work be extended with more approximation/assumptions can be applied to make it more practical in runtime?\n\nb) Can this work be used to real-world scale of network topology?\n\nNote: I am not an expert in this area and my review focuses on the practical impact of this theoretical work. I am neutral accepting the paper, and would love more discussions from other reviewers.", "limitations": "Yes", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strength**\n\n+) This paper proposes an interesting and practical problem which can be used in multiple real scenrios\n\n+) This paper proved NP-hardness and found an algorithm to reach the theoretical bound\n\n+) The effectiveness of the method is verified on practical problems\n\n\n**Weakness**\n\n-) Experiments are limited to synthetic random geometric graphs with two synthetic data groups. It would be better to evalute on real-world network topologies.\n\n-) Even the approximate algorithm has runtimes quadratically which may prevent it usage in practice. It would be better to discuss if more approximation/assumptions can be applied to make it more practical?", "was_revised": true, "final_justification": "After reading the rebuttal, i maintain my scoring of weak accept as the authors address my concerns about the practical impact of this work.", "rebuttal": "Thank you for your thoughtful and constructive feedback. We appreciate the opportunity to address your concerns and answer your questions.\n\n**Q (a)/W2:** Yes, and we view this as a promising direction for future work. Our primary goal in this paper is to introduce the FML problem, prove its theoretical hardness, and present the first approximation algorithms with formal fairness and cost guarantees. The proposed bicriteria method already improves scalability substantially (from $O(n^5)$ to $O(n^2 + n\\varepsilon^{-4}\\log^4 n))$ while preserving strong fairness guarantees in practice.\n\nFurther runtime improvements could be achieved through stronger approximations or assumptions, e.g., by:\n\n-   Leveraging network structure (e.g., low treewidth, geometric constraints);\n    \n-   Applying sketching methods for reducing the input size.\n\nThese directions are beyond the scope of the current paper, which focuses on establishing FML as a rigorous and practically relevant framework. Nonetheless, our work lays the foundation for such future advances.\n\n**Q (b)/W1:** This is a fair point. To demonstrate the practical scalability of our approach, we conducted a new experiment on a large real-world network. Specifically, we sampled a connected 20,000-node induced subgraph (201,900 edges) from the Pokec dataset (available at SNAP). We randomly selected one node as the terminal and colored 10% of the remaining nodes (balanced 50/50) using the binary gender attribute (Blue = male, Red = female). We then ran FMLBIAPPROX with full coverage requirement ($\\alpha = 1.0$) and two precision settings ($\\varepsilon = 0.01$ and $\\varepsilon = 0.001$) in ten independent runs.\n\n| Epsilon | Runtime ± Std (s) | Accuracy (%) |\n|---------|-------------------|-------------------|\n| 0.01 | 3625.0 ± 420.7 | 93.1 |\n| 0.001 | 4661.5 ± 991.3 | 99.3 |\n\n   \n\nAccuracy here represents the ratio of achieved coverage to the required coverage. These real-world experiments confirm the practical scalability and effectiveness of our FMLBIAPPROX algorithm. Even on a complex social network with 20,000 nodes and nearly 202,000 edges, the algorithm achieves high accuracy under both precision settings. The results demonstrate that our method not only handles synthetic benchmark graphs efficiently but also performs reliably in realistic, large-scale settings—supporting its applicability to real-world fairness-aware network design tasks. We will include this experiment and its results in the revised manuscript."}, {"review_id": "RuCzkdKpbD", "reviewer": "Reviewer_CC3x", "summary": "The paper proposes a new framework, termed Fair Minimum Labeling, for finding minimum-cost (temporal) paths between sources and target nodes in a graph while ensuring that the number of source nodes from different groups (types) is fair (are similar). The paper shows that the underlying optimization is NP-hard and proposes two approximate algorithms to solve the problem above. The numerical results show the method's effectiveness in lower cost and fair coverage.", "questions": "I would like to see an experiment on a real-world case, not just with simulation data. I think verifying the method in a more realistic dataset will strengthen the submission. I am open to increasing the score with stronger numerical results, with a real dataset (not necessarily something demanding considering the short time of the rebuttal)", "limitations": "Yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths: \n- The paper is well-written, and the problem statement is clear. The problem of network optimization with fairness constraints is timely and well-motivated from a theoretical and practical perspective.\n- The proofs and the math look ok. The theoretical results are precise and essential to motivate the design of approximated algorithms. \n- The solution based on probabilistic tree embeddings is principled, which leverages tools from metric space for solving optimization problems on graphs.\n- The authors provide code to reproduce the experiments.\n\nWeaknesses: \n- Lack of numerical experiments on real data to support the results and additional experiments to showcase the method's utility.\n- Complexity of order $O(n^5)$.  Although the bicriteria approximation reduces the complexity, this comes at the cost of a dependency on the guarantees of the tree height\n- The proposed solutions are limited to a single terminal and two distinct groups, making the whole introduction too complex for the final method.\n- The paper assumes a central controller can decide when communication links are active. This significant assumption may not hold in decentralized or uncoordinated settings, such as classical federated learning, where device participation is often uncoordinated. \n- A few citations on fairness on graphs are missing [1], [2]\n\n[1] Navarro, Madeline, et al. \"Fair GLASSO: Estimating Fair Graphical Models with Unbiased Statistical Behavior.\" Advances in Neural Information Processing Systems, 2024\n[2] Zhou, Zhuoping, et al. \"Fairness-aware estimation of graphical models.\" Advances in Neural Information Processing Systems, 2024", "was_revised": true, "final_justification": "The paper introduces an interesting problem and studies in detail a simple instance of this problem. Overall, this can be a nice addition to the conference.", "rebuttal": "Thank you for your thoughtful and constructive feedback. We address your points below and have added new experiments as you suggested, which we hope will merit a re-evaluation of our work.\n\n**W1/Q1:** To demonstrate practical relevance, we conducted an additional set of experiments on a real-world social network. Specifically, we sampled a connected 20,000-node induced subgraph (201,900 edges) from the Pokec dataset (available at SNAP). We randomly selected one node as the terminal and colored 10% of the remaining nodes (balanced 50/50) using the binary gender attribute (Blue = male, Red = female). We then ran FMLBIAPPROX with full coverage requirement ($\\alpha = 1.0$) and two precision settings ($\\varepsilon = 0.01$ and $\\varepsilon = 0.001$) in ten independent runs.\n\n| Epsilon | Runtime ± Std (s) | Accuracy (%) |\n|---------|-------------------|-------------------|\n| 0.01 | 3625.0 ± 420.7 | 93.1 |\n| 0.001 | 4661.5 ± 991.3 | 99.3 |\n\n  \n  \n\nAccuracy here represents the ratio of achieved coverage to the required coverage. These real-world experiments confirm the practical scalability and effectiveness of our FMLBIAPPROX algorithm. Even on a complex social network with 20,000 nodes and nearly 202,000 edges, the algorithm achieves high accuracy under both precision settings. The results demonstrate that our method not only handles synthetic benchmark graphs efficiently but also performs reliably in realistic, large-scale settings—supporting its applicability to real-world fairness-aware network design tasks. We will include this experiment and its results in the revised manuscript.\n\n  \n  \n\n**W2:** You raised an excellent point about the bicriteria guarantee's dependency on tree height H. We investigated this on our new Pokec dataset. Over 10 runs, the average tree height was exceptionally small, H≈6.68. Our theoretical analysis provides a worst-case coverage guarantee of $(1+ε)^{-(H+1)}$. For $\\varepsilon=0.01$, this guarantees at least $(1.01)^{-7.68} ≈ 92.6\\%$ coverage. Our empirically measured accuracy was 93.1%. This demonstrates that our algorithm robustly meets its formal theoretical guarantee in a real-world setting and that the small H prevents significant degradation. The dependency is not a practical weakness but a well-behaved aspect of our scalable method.\n\n  We will include this empirical validation of the coverage bound in Section 6.\n  \n\n**W3:** You make a fair point about the scope of our proposed solution relative to the broader problem motivated in the introduction. This was a deliberate methodological choice. Our goal with this initial work was to establish the theoretical foundations for the new and challenging FML problem. By focusing on the core, non-trivial instance of two groups and a single terminal, we were able to:\n\n-   Prove its computational hardness (NP-hard and hard to approximate).\n    \n-   Design the first tractable approximation algorithms with formal guarantees.\n    \n\nThe introduction aims to lay out the full, practical scope of the FML problem, while our algorithms provide the first concrete and provably correct solution for a foundational version of it. We believe this approach (motivating the general problem while rigorously solving a core instance) provides a solid and necessary base for future work to build upon, such as extending the methods to the more general multi-terminal and multi-group scenarios.\n\n  \n  \n\n**W4:** This is a key modeling choice we made for this foundational work. The assumption of a central controller is common when first tackling complex network optimization problems, as it allows for the derivation of formal guarantees. This setting is directly applicable to many real-world scenarios, such as:\n\n-   Duty-cycled sensor networks, where a central base station computes a global activation schedule to wake up specific sensors for data collection, minimizing energy consumption across the network (see answer of **Q1** of reviewer 7pM4 for a concrete example)\n    \n-   Edge-cloud systems, where a central orchestrator manages bandwidth by deciding which edge devices can push updates to the cloud at specific times.\n    \n\nWe acknowledge in our limitations section that this assumption does not cover fully decentralized settings like classical federated learning, and that extending our framework to such environments is an important direction for future research.\n\n  \n  \n\n**W5:** Thank you for pointing out the missing references. They are indeed relevant, and we will add citations and discussion of [1] and [2] to our related work section in the revised manuscript. While their objectives differ from ours, they underscore the broader interest in equitable representation in graph-based learning, reinforcing the relevance of FML."}, {"review_id": "6xlDyp3pgT", "reviewer": "Reviewer_68A7", "summary": "This paper introduces the Fair Minimum Labeling (FML) problem, addressing group-wise temporal reachability under resource constraints. It proposes a probabilistic approximation framework using tree embeddings, ensuring efficient cost and fairness for two distinct groups reaching a single terminal.", "questions": "- Have the authors explored more potential strategies or optimizations that could reduce the computational overhead?\n- Include a more dedicated discussion on the limitations of the current assumptions and explore how they might be relaxed or adapted to more realistic environments like the mentioned distributed and federated learning.\n- Double-check and ensure consistency across all quantitative results and textual interpretations.", "limitations": "yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "# Strengths\n- The paper addresses a task with clear real-world motivation and potential application value.\n- The theoretical formulation of FML and its solution is detailed and well-articulated, demonstrating a strong analytical foundation, which contribute meaningfully to the understanding of the proposed method.\n# Weaknesses\n- The current FML assumptions and the experiment setup appear somewhat idealized, raising questions about the general applicability and robustness of the method in practical settings.\n- The proposed approach introduces a notable increase in computational time, as shown in Table 1, which could become a limiting factor for real-time or resource-constrained applications. This trade-off between performance and efficiency should be more clearly discussed.\n- There seems to be a discrepancy between the results reported in Table 1 (specifically for the \"approx\" and \"biapprox\" variants) and the corresponding description in Line 344 of the manuscript.", "was_revised": true, "final_justification": "The rebuttal from the authors have basically address my concerns. I have also carefully reviewed the discussions of other reviewers. From my perspective, this work is slightly above the acceptance borderline in light of the clarifications in the rebuttal and the promise to revise the manuscript from the authors.", "rebuttal": "We thank the reviewer for their thoughtful and constructive feedback. Below, we address each of the identified weaknesses (W1–W3) and related questions (Q1–Q3).\n\n**W1/Q2:** This is an important concern, and we appreciate the opportunity to clarify. \nOur theoretical results and experiments deliberately focus on a core, minimal setting: two groups, a single terminal, and centralized scheduling. This allowed us to prove NP-hardness, establish approximation lower bounds, and design the first efficient algorithms with fairness and cost guarantees.\n \nTo address the question of real-world applicability, we conducted a new large-scale experiment on a 20,000-node subgraph from the Pokec dataset (available at SNAP). We randomly selected one node as the terminal and colored 10% of the remaining nodes (balanced 50/50) using the binary gender attribute (Blue = male, Red = female). We then ran FMLBIAPPROX with full coverage requirement ($\\alpha = 1.0$) and two precision settings ($\\varepsilon = 0.01$ and $\\varepsilon = 0.001$) in ten independent runs.\n\nThe results are summarized below:\n\n| Epsilon | Runtime ± Std (s) | Accuracy (%) |\n|---------|-------------------|-------------------|\n| 0.01 | 3625.0 ± 420.7 | 93.1 |\n| 0.001 | 4661.5 ± 991.3 | 99.3 |\n\nThese results show that FMLBIAPPROX maintains high coverage accuracy and scales well to large, real-world networks. We will include this experiment and its results in the revised manuscript.\n\n**Regarding the centralized model:**\nWe agree that the centralized model is a limitation for some settings. However, many practical systems do fit this paradigm, e.g.:\n - Duty-cycled sensor networks managed by a base station,\n - Edge-cloud orchestration in bandwidth-constrained environments.\n\nConsider a medical AI initiative deployed in a developing region to collect patient data for training a diagnostic model. The setting involves remote rural villages with limited connectivity and urban health hubs with better infrastructure. Devices operate under tight energy constraints and are duty-cycled, i.e., radios are only active during coordinated upload windows to conserve battery.\n\n-   Nodes V: Participants’ smartphones, community health hubs, and the central server.\n    \n-   Groups $V_B$, $V_R$​: Urban (near, well-connected) vs. rural (remote) participants; we must connect an $\\alpha$-fraction of each (groups could also represent, e.g., demographic or ethnic divisions).\n    \n-   Terminal $t$: The central server.\n    \n-   Edges $E$: Potential short-range (Bluetooth/Wi-Fi Direct) links to hubs and long-range links from hubs to t.\n    \n-   Temporal labeling $\\lambda$: Each activated edge is assigned a few global upload rounds, i.e., the only times radios are awake.\n    \n-   Cost: The total number of edge–time activations (each consumes energy when radios leave sleep mode).\n    \n-   Why temporality matters. Data must traverse time-respecting paths: if a rural phone $u$ forwards to hub $v$ in round $\\tau_1$​, then $v$ must forward towards $t$ in a later round $\\tau_2>\\tau_1$​. Simply picking a static path is insufficient; we need an ordered activation plan consistent with duty-cycling.\n    \n\nFML computes a sparse, globally scheduled activation plan with a few rounds and few active links that guarantees at least $\\alpha|V_B|$ and $\\alpha|V_R|$ nodes can reach t temporally, while minimizing total wake-ups (edge–time labels). This aligns with real duty-cycled systems where communication is batch-scheduled to conserve energy and bandwidth.\n\nWe will extend the discussionin the revised version.\n\n\n**W2/Q1:** This is an important and valid point. The FML problem is provably hard (NP-complete and log-approximation hard), so a computational trade-off is inevitable when seeking fairness with guarantees. Our baseline algorithms are fast precisely because they ignore fairness or cost optimization, making them inappropriate for equitable design.\n\nNevertheless, our bicriteria algorithm FMLBIAPPROX significantly improves scalability:\n-   It reduces the runtime from $O(n^5)$ (exact DP) to $O(n^2 + n\\varepsilon^{-4}\\log^4 n)$;\n-   It scales to real-world graphs with 20k nodes, as demonstrated in the new Pokec experiment;\n-   More than 99.9% of the runtime is spent in the labeling phase, suggesting optimization efforts should focus there.\n    \nFor time-critical settings, we plan to explore in future works:\n-   Structure-aware techniques, e.g., exploiting low treewidth or planarity;\n-   Sketching and sparsification to reduce problem size;\n-   Parallelization of the DP step.\n    \nWe will add a discussion of these trade-offs, future acceleration strategies, and clarify the current computational bottlenecks.\n\n\n**W3/Q3:** We thank the reviewer for noting the inconsistency between Table 1 and the corresponding discussion in Line 344. Upon careful review, we identified that the labels of the FMLAPPROX and FMLBIAPPROX rows were inadvertently swapped during table formatting. The numerical results themselves are correct and consistent (i.e., FMLBIAPPROX is faster than FMLAPPROX). This has now been corrected in the revised version, and we emphasize that it does not affect any findings or interpretations in the manuscript."}, {"review_id": "cIzhuXbfQd", "reviewer": "Reviewer_tPNL", "summary": "This paper introduces the Fair Minimum Labeling (FML) problem, which aims to compute temporally sparse edge activation schedules in dynamic networks while ensuring fair group-wise reachability to a central terminal under global resource constraints. The FML framework formalizes the trade-off between minimizing the number of activated edges and satisfying fairness constraints across multiple groups, specifically requiring that a fixed fraction of nodes in each group temporally reach the terminal. \n\nThe authors show that the problem is NP-hard and logarithmically hard to approximate. To address this, they propose a randomized approximation framework based on probabilistic tree embeddings, leading to two algorithms: (1) an exact method on trees and (2) a more scalable bicriterial approximation that allows bounded fairness violations. \n\nBoth methods are evaluated in a multi-source learning task under resource constraints, demonstrating that FML-based solutions outperform fairness-agnostic baselines in terms of cost-efficiency and fairness. The paper also discusses practical limitations and outlines future directions, including extensions to multi-terminal and distributed settings.", "questions": "* The current cost model treats all edge activations equally by summing $|\\lambda(e)|$ across edges. However, in real-world scenarios, activation costs may vary—e.g., long-distance links may consume more energy, low-bandwidth edges may incur higher latency, or peak-time activations may be costlier. Can the FML framework be extended to support weighted activation costs, and what challenges might arise in doing so?\n* The current model enforces strictly increasing timestamps along temporal paths. In practice, however, multiple edges may be traversed simultaneously, or edge activations may involve delays (e.g., arriving at time $\\tau + d$). Have you considered relaxing this assumption to allow non-strict time progression or modeling delays explicitly? \n* The approximation factor of $O(\\log n)$ is shown to be tight in expectation via FRT embeddings. Can you clarify whether this tightness carries over in worst-case performance as well?\n* The framework uses a shared $\\alpha$ for all groups. Can different coverage ratios (e.g., $\\alpha_B$, $\\alpha_R$) be supported? Would this affect the approximation guarantees or algorithm design?\n* The fairness guarantee depends on tree height $H$. Do you have empirical data (e.g., typical values of $H$ or fairness violation) showing how this impacts coverage in practice?\n* The terminal node $t$ is fixed. Since terminal placement affects reachability and cost, have you studied how the choice of $t$ (e.g., central vs. peripheral) influences fairness and performance?\n* The exact DP algorithm has $O(n^5)$ time complexity, and the bicriteria method improves this to $O(n^2 + n\\varepsilon^{-4} \\log^4 n)$. Do you have empirical benchmarks on runtime and scalability, especially for larger graphs (e.g., $n > 10^4$)? Could sparsity or graph structure be exploited to further improve scalability?\n* The current model supports only two groups and one terminal. Can it be extended to multiple groups or terminals? What new challenges would this introduce, and how would it affect scalability?\n* The model assumes a static node set. In dynamic environments (e.g., nodes dropping out), how robust is FML? Can it be adapted to handle such changes without full recomputation?", "limitations": "Yes.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 4, "strengths_and_weaknesses": "Strength:\n* The paper introduces the Fair Minimum Labeling (FML) problem, which uniquely captures temporal fairness constraints in dynamic networks—a formulation not addressed in prior work.\n* The authors provide formal NP-hardness and approximation lower bounds for the problem, and derive approximation algorithms, indicating tight theoretical contributions.\n* The use of probabilistic tree embeddings, combined with both exact and bicriteria approximation algorithms, demonstrates a thoughtful adaptation of known techniques to a new fairness-driven setting.\n* The experiments are clearly motivated and show that FML-based solutions outperform baselines in both activation cost and fairness, with controlled runtime tradeoffs.\n\nWeakness:\n* While the FML framework is motivated by real-world applications such as federated data collection, edge-cloud communication, and fair infrastructure restoration, the current formulation only supports two demographic groups and a single terminal. This limitation restricts the applicability of the proposed methods to more complex, realistic settings that involve multiple groups or multiple target nodes.\n* The FML framework assumes centralized control and fixed fairness thresholds, which may not directly translate to more dynamic, decentralized environments commonly seen in federated or edge settings.\n* The exact dynamic programming solution has a runtime of $\\mathcal{O}(n^5)$, making it impractical for large-scale networks without further optimization. The bicriteria algorithm sacrifices exact fairness, and its violation factor grows logarithmically with the graph size, which may be undesirable in sensitive applications. \n* The framework focuses solely on group-level static fairness (i.e., coverage quotas), without addressing finer-grained notions such as fairness over time or at the individual level.\n* While synthetic experiments are reasonable, the evaluation would be stronger if applied to a real-world temporal network with fairness-sensitive requirements.", "was_revised": true, "final_justification": "After considering the rebuttal and discussion, I believe the authors have adequately addressed nearly all of my concerns. Below are the key points informing my final recommendation:\n\n * _Scalability_: The authors provided a convincing clarification on the scalability of their approach, along with additional analysis and justification.\n * _Extensions_: The authors acknowledged the limitations I pointed out and offered well-reasoned explanations for how these could be addressed or extended in future work.", "rebuttal": "We thank the reviewer for their comprehensive feedback and excellent suggestions for future work. For this paper, we focused on making a foundational contribution: introducing the Fair Minimum Labeling (FML) problem, establishing its hardness, and proposing the first algorithms with theoretical guarantees. We agree that the extensions you've suggested, such as multiple terminals and decentralized settings, are important and exciting future directions. We hope our work provides a solid platform for that research.\n\n\n**W1:** This is a fair and important limitation. For clarity and tractability, we focus on the minimal yet representative case of two groups and a single terminal, which already captures a meaningful fairness–cost trade-off and enables rigorous algorithmic design and analysis. As addressed in **Q8**, our dynamic programming formulation generalizes naturally to multiple groups by extending the state space, and the approximation guarantees remain valid. Extending to multiple terminals introduces significant algorithmic complexity, which we leave for future work and will highlight more clearly in the revised manuscript.\n\n**W2:** We agree this limits applicability in some settings, especially in fully decentralized or federated systems. However, many real-world scenarios, such as sensor networks or edge-cloud orchestration do involve centralized coordination or batch scheduling, often for energy efficiency (see also **Q1** of reviewer 7pM4). We will better emphasize these motivating examples.\n\n**W3:** The FML problem is NP-hard and log-approximation hard, so a computational trade-off is unavoidable. Our goal is not just efficiency but fairness with guarantees. While heuristic baselines are faster, they fail to ensure group-wise fairness and can yield extreme imbalance, as shown in our experiments.\nThat said, our bicriteria algorithm (FMLBIAPPROX) significantly improves scalability, reducing runtime from $O(n^5)$ to near-quadratic, and handles graphs with 20k nodes efficiently (see **Q7**).  \n\n**W4:** See  answer of **Q4**.\n\n**W5:** See  answer of **Q7**.\n\n**Q1:** This is an excellent question. Our framework can indeed be extended to support arbitrary, non-uniform activation costs $w(e)$, while fully preserving the $O(\\log n)$ approximation guarantee. The extension is quite natural. The key is to define the metric for the FRT embedding using these costs. First, we compute a shortest-path metric $d(u,v)$ where the distance between nodes is defined as the minimum cost of a path between them, using the activation costs $w(e)$ as the edge weights. We then use FRT to embed this weighted metric into a tree T. Our DP algorithm then runs on the tree $T$, and because the tree distances being optimized are already low-distortion approximations of the minimum activation costs, the $O(\\log n)$ guarantee on the final, total weighted cost holds directly. This requires no fundamental change to our algorithmic framework, demonstrating its flexibility. We will clarify this in the revised manuscript.\n  \n\n**Q2:** Allowing non-strict timestamps would fundamentally change the definition of a temporal path and could introduce cycles, making reachability more complex. While our current framework does not support this, it is a well-studied variant in the temporal graph literature, and adapting our reachability definitions would be a non-trivial but interesting future direction.\n\n  \n\n**Q3:** The $O(\\log n)$ approximation factor holds in expectation over the random FRT embedding, which is the best known bound for tree embeddings. In the worst case for a single sampled tree, the guarantee may degrade, but the standard remedy is to sample multiple trees and select the best. Empirically, we observe low variance and high consistency across runs (see also Q5).\n\n**Q4:** Our DP formulation explicitly supports a per-group requirement function $f_c$, and therefore handles heterogeneous thresholds (e.g.,$\\alpha_A \\neq \\alpha_B$) without modification. The approximation guarantees are unaffected as they apply pointwise per group.\n\n**Q5:** You raised an excellent point about our bicriteria algorithm's fairness guarantee, which depends on the tree height H. We investigated this on a real-world Pokec dataset (20k nodes) (see Q7). Over 10 runs, the average tree height H was exceptionally small with H≈6.68. Our theoretical analysis provides a worst-case guarantee on coverage of $(1+ε)^{-(H+1)}$. For $\\varepsilon=0.01$, this guarantees a coverage of at least $(1.01)^{-7.68} ≈ 92.6\\%$.\n\nOur empirically measured accuracy was 93.1%. It demonstrates that our algorithm robustly meets and even slightly exceeds its formal theoretical guarantee in a real-world setting. And, it confirms that the guarantee itself is strong, as the small tree height H prevents significant degradation. The dependency on H is not a practical weakness but a well-behaved aspect of our scalable algorithm, providing strong and reliable fairness assurances.\n\nWe will include this empirical validation of the coverage bound in Section 6.\n  \n**Q6:** This is an excellent point. The terminal's placement is critical and directly influences the costs associated with reaching different groups. We studied this in two ways:\n\nOur main experiment in Section 6.1 explores this by defining groups B and R based on spatial proximity to the terminal $t$ (\"near\" vs. \"far\"). The failure of the GREEDY baseline to cover the \"far\" group ($Coverage_R=0$) starkly illustrates how terminal placement creates cost disparities. FML is specifically designed to find low-cost solutions that overcome these structural biases.\n\nWe also ran additional experiments on Barabási-Albert graphs $(n=1024)$ where we explicitly placed the terminal at either a central (high-degree) or peripheral (low-degree) node. Our bicriteria algorithm (FMLBIAPPROX) proved highly effective in both scenarios, consistently achieving over 98% of the required coverage. This demonstrates that our method is robust to the terminal's location, successfully finding fair and efficient solutions even when the terminal is not in a structurally advantageous position.\n\nWe will add these observations to our empirical analysis section.\n  \n**Q7:** To demonstrate practical relevance, we conducted an additional set of experiments on a real-world social network. Specifically, we sampled a connected 20,000-node induced subgraph (201,900 edges) from the Pokec dataset (available at SNAP). We randomly selected one node as the terminal and colored 10% of the remaining nodes (balanced 50/50) using the binary gender attribute (Blue = male, Red = female). We then ran FMLBIAPPROX with full coverage requirement ($\\alpha = 1.0$) and two precision settings ($\\varepsilon = 0.01$ and $\\varepsilon = 0.001$) in ten independent runs.\n\nThe results are summarized below:\n\n| Epsilon | Runtime ± Std (s) | Accuracy (%) |\n|---------|----------|-------|\n| 0.01 | 3625.0 ± 420.7 | 93.1 |\n| 0.001 | 4661.5 ± 991.3 | 99.3 |\n\nAccuracy here represents the ratio of achieved coverage to the required coverage. These real-world experiments confirm the practical scalability and effectiveness of our FMLBIAPPROX algorithm. Even on a complex social network with 20,000 nodes and nearly 202,000 edges, the algorithm achieves high accuracy under both precision settings. The results demonstrate that our method not only handles synthetic benchmark graphs efficiently but also performs reliably in realistic, large-scale settings—supporting its applicability to real-world fairness-aware network design tasks. We will include this experiment and its results in the revised manuscript.\n\nFor a more systematic analysis, Figure 2a in our paper benchmarks the runtime on synthetic graphs up to $n=4096$. This plot clearly illustrates the empirical scaling and demonstrates that FMLBIAPPROX is significantly more scalable than the exact-on-tree method (FMLAPPROX), consistently outperforming it by an order of magnitude on larger instances. This confirms the practical benefit of our bicriteria algorithm, which reduces the complexity from $O(n^5)$ to a much more manageable, near-quadratic runtime in practice, as discussed in Theorem 4.\n\nExploiting sparsity or graph structure for further scalability is also a very insightful point and a promising direction for future work. Our current framework already implicitly benefits from sparsity. The initial shortest-path metric computation on a sparse graph (where $m = O(n)$) is much faster than on a dense one.\n\nHowever, more explicit exploitation of structure could be possible. For instance:\n\n-   For graphs with low treewidth, specialized dynamic programming algorithms could potentially solve the problem much more efficiently, avoiding the need for tree embeddings altogether.\n    \n-   The structure of planar or geometric graphs (like our synthetic data) could be used to design more efficient, specialized tree embeddings or decomposition methods.\n    \n\nWhile these specialized approaches are beyond the scope of this paper, which focuses on providing guarantees for general graphs, they represent a key avenue for achieving even greater scalability in specific application domains.\n\n  \n\n**Q8:** Extending our algorithm to $>2$ groups is conceptually straightforward: the DP state tracks coverage for each group individually, at the cost of increased dimensionality. Multiple terminals, however, introduce additional complexity. We intentionally focus on the single-terminal case to retain tractability, and clearly state this in our contribution scope.\n\n\n**Q9:** In dynamic environments (e.g., node failures or departures), partial recomputation of our labeling is feasible. The DP can be rerun locally on affected subtrees, and minor changes in the graph structure often preserve the validity of the tree embedding. While full dynamic adaptation is beyond the scope of our current work, the methods lend themselves to such extensions.\n\nWe will discuss this as a natural direction for future extensions."}]

Author rebuttal:

Meta-review: This paper proposes a new temporal edge activation problem in networks with fairness constraints that ensure that a proportion of each group has access to terminal nodes. This problem is shown to be hard to approximate even within a logarithmic factor. Approximation algorithms are provided for the two-group single terminal node case.
A main contribution of this paper is to introduce the fair minimum labeling problem, which is important, novel, and well-motivated. The algorithms make an interesting use of probabilistic tree embeddings and achieve strong theoretical guarantees, either exact or bi-criteria.
The restriction to the algorithms only being for two groups and a single terminal is a weakness.
Decision: Accept (poster)