Davide Bilò

Davide Bilò, Keerti Choudhary, Sarel Cohen et al.

Given two vertex sets $S$ and $T$ in a graph, the $ST$-diameter is the maximum $s$-$t$-distance between vertices $s \in S$ and $t \in T$. We study the problem of estimating the $ST$-diameter of graphs that are subject to a small number of transient edge failures. An $f$-edge fault-tolerant $ST$-diameter oracle ($f$-FDO-$ST$) is a data structure that preprocesses a graph $G$, sets $S$, $T$, and a positive integer $f$. When queried with a set $F$ of at most $f$ failing edges, the oracle returns an estimate $\widehat{D}$ of the $ST$-diameter in $G-F$. The oracle is said to have stretch $σ\geq 1$ if $\operatorname{diam}(G{-}F,S,T) \leq \widehat{D} \leq σ\cdot \operatorname{diam}(G{-}F,S,T)$. We design new $f$-FDO-$ST$s by reducing their construction to that of all-pairs and single-source distance sensitivity oracles ($f$-DSOs). These are data structures that estimate the pairwise graph distances, or respectively the distances from a distinguished source, under up to $f$ failures. We obtain several new trade-offs between the size of the $ST$-diameter oracles, their stretch guarantees, query and preprocessing times by combining our black-box reductions with $f$-DSO results from the literature. We further provide a lower bound on the space requirement of approximate $ST$-diameter oracles. We prove that there exists a family of graphs for which any $f$-FDO-$ST$ with sensitivity $f \ge 2$ and stretch better than $5/3$ requires $Ω(n^{3/2})$ bits of space, regardless of the query time.

Davide Bilò, Shiri Chechik, Keerti Choudhary et al.

An important tool in the design of fault-tolerant graph data structures are $(L,f)$-replacement path coverings (RPCs). An RPC is a family $\mathcal{G}$ of subgraphs of a given graph $G$ such that, for every set $F$ of at most $f$ edges, there is a subfamily $\mathcal{G}_F \,{\subseteq}\, \mathcal{G}$ with the following properties. (1) No subgraph in $\mathcal{G}_F$ contains an edge of $F$. (2) For each pair of vertices $s,t$ that have a shortest path in $G-F$ with at most $L$ edges, one such path also exists in some subgraph in $\mathcal{G}_F$. The covering value of the RPC is the total number $|\mathcal{G}|$ of subgraphs. The query time is the time needed to compute the subfamily $\mathcal{G}_F$ given the set $F$. Weimann and Yuster [TALG'13] devised a randomized RPC with covering value $\widetilde{O}(fL^f)$ and query time $\widetilde{O}(f^2 L^f)$. This was derandomized by Karthik and Parter [TALG'24], who also reduced the query time to $\widetilde{O}(f^2 L)$. Their approach uses some heavy algebraic machinery involving error-correcting codes and an increased covering value of $O((cfL \log n)^{f+1})$ for some constant $c > 1$. We instead devise a much simpler derandomization via conditional expectations that lowers the covering value back to $\widetilde{O}(fL^{f+o(1)})$ and decreases the query time to $\widetilde{O}(f^{5/2}L^{o(1)})$, assuming $f = o(\log L)$. We also investigate the optimal covering value of any $(L,f)$-replacement path covering (deterministic or randomized) for different parameter ranges. We provide a new randomized construction as well as improving a known lower bound, also by Karthik and Parter. For example, for $f = o(\log L)$, we give an RPC with $\widetilde{O}( (L/f)^f L^{o(1)})$ subgraphs and show that this is tight up to the $L^{o(1)}$ term.

Davide Bilò, Sarel Cohen, Tobias Friedrich et al.

Most networks are not static objects, but instead they change over time. This observation has sparked rigorous research on temporal graphs within the last years. In temporal graphs, we have a fixed set of nodes and the connections between them are only available at certain time steps. This gives rise to a plethora of algorithmic problems on such graphs, most prominently the problem of finding temporal spanners, i.e., the computation of subgraphs that guarantee all pairs reachability via temporal paths. To the best of our knowledge, only centralized approaches for the solution of this problem are known. However, many real-world networks are not shaped by a central designer but instead they emerge and evolve by the interaction of many strategic agents. This observation is the driving force of the recent intensive research on game-theoretic network formation models. In this work we bring together these two recent research directions: temporal graphs and game-theoretic network formation. As a first step into this new realm, we focus on a simplified setting where a complete temporal host graph is given and the agents, corresponding to its nodes, selfishly create incident edges to ensure that they can reach all other nodes via temporal paths in the created network. This yields temporal spanners as equilibria of our game. We prove results on the convergence to and the existence of equilibrium networks, on the complexity of finding best agent strategies, and on the quality of the equilibria. By taking these first important steps, we uncover challenging open problems that call for an in-depth exploration of the creation of temporal graphs by strategic agents.

Davide Bilò, Vittorio Bilò, Michelle Döring et al.

In most major cities and urban areas, residents form homogeneous neighborhoods along ethnic or socioeconomic lines. This phenomenon is widely known as residential segregation and has been studied extensively. Fifty years ago, Schelling proposed a landmark model that explains residential segregation in an elegant agent-based way. A recent stream of papers analyzed Schelling's model using game-theoretic approaches. However, all these works considered models with a given number of discrete types modeling different ethnic groups. We focus on segregation caused by non-categorical attributes, such as household income or position in a political left-right spectrum. For this, we consider agent types that can be represented as real numbers. This opens up a great variety of reasonable models and, as a proof of concept, we focus on several natural candidates. In particular, we consider agents that evaluate their location by the average type-difference or the maximum type-difference to their neighbors, or by having a certain tolerance range for type-values of neighboring agents. We study the existence and computation of equilibria and provide bounds on the Price of Anarchy and Stability. Also, we present simulation results that compare our models and shed light on the obtained equilibria for our variants.