Gianlorenzo D'Angelo

Temporal graphs represent networks in which connections change over time, with edges available only at specific moments. Motivated by applications in logistics, multi-agent information spreading, and wireless networks, we introduce the D-Temporal Multi-Broadcast (D-TMB) problem, which asks for scheduling the availability of edges so that a predetermined subset of sources reach all other vertices while optimizing the worst-case temporal distance D from any source. We show that D-TMB generalizes ReachFast (arXiv:2112.08797). We then characterize the computational complexity and approximability of D-TMB under six definitions of temporal distance D, namely Earliest-Arrival (EA), Latest-Departure (LD), Fastest-Time (FT), Shortest-Traveling (ST), Minimum-Hop (MH), and Minimum-Waiting (MW). For a single source, we show that D-TMB can be solved in polynomial time for EA and LD, while for the other temporal distances it is NP-hard and hard to approximate within a factor that depends on the adopted distance function. We give approximation algorithms for FT and MW. For multiple sources, if feasibility is not assumed a priori, the problem is inapproximable within any factor unless P = NP, even with just two sources. We complement this negative result by identifying structural conditions that guarantee tractability for EA and LD for any number of sources.

In a temporal graph the edge set dynamically changes over time according to a set of time-labels associated with each edge that indicates at which time-step the edge is available. Two vertices are connected if there is a path connecting them in which the edges are traversed in increasing order of their labels. We study the problem of scheduling the availability time of the edges of a temporal graph in such a way that all pairs of vertices are connected within a given maximum allowed time a and the overall number of labels is minimum. The problem, called Minimum Aged Labeling (MAL), has several applications in logistics, distribution scheduling, and information spreading in social networks, where carefully choosing the time-labels can significantly reduce infrastructure costs, fuel consumption, or greenhouse gases. Problem MAL has previously been proved to be NP-complete on undirected graphs and APX-hard on directed graphs. In this paper, we extend our knowledge on the complexity and approximability of MAL in several directions. We first show that the problem cannot be approximated within a factor better than O(log n) when a >= 2, unless P = NP, and a factor better than 2^[log^(1-ε) n] when a >= 3, unless NP is contained in DTIME(2^(polylog(n))), where n is the number of vertices in the graph. Then we give a set of approximation algorithms that, under some conditions, almost match these lower-bounds. In particular, we show that the approximation depends on a relation between a and the diameter of the input graph. We further establish a connection with a foundational optimization problem on static graphs called Diameter Constrained Spanning Subgraph (DCSS) and show that our hardness results also apply to DCSS.

Fairness in influence maximization has been a very active research topic recently. Most works in this context study the question of how to find seeding strategies (deterministic or probabilistic) such that nodes or communities in the network get their fair share of coverage. Different fairness criteria have been used in this context. All these works assume that the entity that is spreading the information has an inherent interest in spreading the information fairly, otherwise why would they want to use the developed fair algorithms? This assumption may however be flawed in reality -- the spreading entity may be purely efficiency-oriented. In this paper we propose to study two optimization problems with the goal to modify the network structure by adding links in such a way that efficiency-oriented information spreading becomes automatically fair. We study the proposed optimization problems both from a theoretical and experimental perspective, that is, we give several hardness and hardness of approximation results, provide efficient algorithms for some special cases, and more importantly provide heuristics for solving one of the problems in practice. In our experimental study we then first compare the proposed heuristics against each other and establish the most successful one. In a second experiment, we then show that our approach can be very successful in practice. That is, we show that already after adding a few edges to the networks the greedy algorithm that purely maximizes spread surpasses all fairness-tailored algorithms in terms of ex-post fairness. Maybe surprisingly, we even show that our approach achieves ex-post fairness values that are comparable or even better than the ex-ante fairness values of the currently most efficient algorithms that optimize ex-ante fairness.