Davide Bilò

TCS Journal 2026 Journal Article

On the approximability of graph visibility problems

• Davide Bilò
• Alessia Di Fonso
• Gabriele Di Stefano
• Stefano Leucci

Visibility problems have been investigated for a long time under different assumptions as they pose challenging combinatorial problems and are connected to robot navigation problems. The mutual-visibility problem in a graph G of n vertices asks to find the largest set of vertices X⊆V(G), also called μ-set, such that for any two vertices u, v ∈ X, there is a shortest u, v-path P where all internal vertices of P are not in X. This means that u and v are visible w. r. t. X. Variations of this problem are known as total, outer, and dual mutual-visibility problems, depending on the visibility property of vertices inside and/or outside X. The mutual-visibility problem and all its variants are known to be NP -complete on graphs of diameter 4. We design a polynomial-time algorithm that finds a μ-set of size Ω ( n / D ), where D is the average distance in G, we show inapproximability results for all visibility problems on graphs of diameter 2, and we strengthen the inapproximability ratios for graphs of diameter 3 or larger. More precisely, assuming P ≠ NP, the mutual-visibility and dual mutual-visibility problems are not approximable within a factor of n 1 / 3 − ε on graphs of diameter at least 3, while the outer and total mutual-visibility problems are not approximable within a factor of n 1 / 2 − ε, for any constant ε > 0. Finally, we study the relationship between the mutual-visibility number and the general position number, in which no three distinct vertices u, v, w of X belong to any shortest path of G.

JAAMAS Journal 2026 Journal Article

Temporal network creation games: the impact of non-locality and terminals

• Davide Bilò
• Sarel Cohen
• George Skretas

Abstract Our economy, communication, and even our social life crucially depend on networks. These typically emerge from the interaction of many entities, which is why researchers study agent-based models of network formation. In particular, Bilò et al. [1] recently introduced a model where a network is formed by selfish agents corresponding to nodes in a given host network with edges having labels denoting their availability over time. Each agent strategically selects local, i. e. , incident, edges to ensure temporal reachability towards everyone at low cost. We explore two novel conceptual features: agents can create non-incident edges, called the global setting, and agents might only want to ensure reachability of a subset of nodes, called the terminal model. For both, we study the existence, structure, and quality of equilibrium networks. For the terminal model, we prove that many properties depend on the number of terminals and we show how to translate equilibrium constructions from the non-terminal model. For the global setting, we show the surprising result that equilibria in the global and the local model are incomparable and we establish a high lower bound on the Price of Anarchy of the global setting that matches the upper bound of the local model. This shows the counter-intuitive fact that allowing agents more flexibility in edge creation does not improve the quality of equilibrium networks. Finally, all of our results hold for the general case where every edge can have multiple labels.

AAAI Conference 2025 Conference Paper

Efficient Fault-Tolerant Search by Fast Indexing of Subnetworks

• Davide Bilò
• Keerti Choudhary
• Sarel Cohen
• Tobias Friedrich
• Martin Schirneck

We design sensitivity oracles for error-prone networks. For a network problem Π, the data structure preprocesses a network G=(V,E) and sensitivity parameter f such that, for any set F of up to f link or node failures, it can report the solution of Π in G-F. We study three network problems Π. - L-Hop Shortest Path: Given s,t in V, is there a shortest s-t-path in G-F with at most L links? - k-Path: Does G-F contain a simple path with k links? - k-Clique: Does G-F contain a clique of k nodes? Our main technical contribution is a new construction of (L,f)-replacement path coverings ((L,f)-RPC) in the parameter realm where f = o(log L). An (L,f)-RPC is a family G' of subnetworks of G which, for every set F of at most f links, has a subfamily G'_F such that (i) no subnetwork in G'_F contains a link of F and (ii) for each s,t in V, if G-F contains a shortest s-t-path with at most L links, then some subnetwork in G'_F retains at least one such path. Our (L,f)-RPC has almost the same size as the one by Weimann and Yuster (2013) but it improves the time to query G'_F from Õ(f^2 L^f) to Õ(f^(5/2) L^o(1)). It also improves over the size and query time of the (L,f)-RPC by Karthik and Parter (2021) by nearly a factor of L. From this construction, we derive oracles for L-Hop Shortest Path, k-Path, and k-Clique. Notably, our solution for k-Path improves the query time of the one by Bilò for f=o(log k).

AAMAS Conference 2025 Conference Paper

Temporal Network Creation Games: The Impact of Non-Locality and Terminals

• Davide Bilò
• Sarel Cohen
• Tobias Friedrich
• Hans Gawendowicz
• Nicolas Klodt
• Pascal Lenzner
• George Skretas

We live in a world full of networks where our economy, our communication, and even our social life crucially depends on them. These networks typically emerge from the interaction of many entities, which is why researchers study agent-based models of network formation. While traditionally static networks with a fixed set of links were considered, a recent stream of works focuses on networks whose behavior may change over time. In particular, Bilò et al. (IJCAI 2023) recently introduced a game-theoretic network formation model that embeds temporal aspects in networks. More precisely, a network is formed by selfish agents corresponding to nodes in a given host network with edges having labels denoting their availability over time. Each agent strategically selects local, i. e. , incident, edges to ensure temporal reachability towards everyone at low cost. In this work we set out to explore the impact of two novel conceptual features: agents are no longer restricted to creating incident edges, called the global setting, and agents might only want to ensure that they can reach a subset of the other nodes, called the terminal model. For both, we study the existence, structure, and quality of equilibrium networks. For the terminal model, we prove that many core properties crucially depend on the number of terminals. We also develop a novel tool that allows translating equilibrium constructions from the non-terminal model to the terminal model. For the global setting, we show the surprising result that equilibria in the global and the local model are incomparable and we establish a high lower bound on the Price of Anarchy of the global setting that matches the upper bound of the local model. This shows the counter-intuitive fact that allowing agents more flexibility in edge creation does not improve the quality of equilibrium networks. This work is licensed under a Creative Commons Attribution International 4. 0 License. Proc. of the 24th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2025), Y. Vorobeychik, S. Das, A. Nowé (eds.), May 19 – 23, 2025, Detroit, Michigan, USA. © 2025 International Foundation for Autonomous Agents and Multiagent Systems (www. ifaamas. org). Finally, in contrast to Bilò et al. (IJCAI 2023) where the authors restrict the model to single labels per connection, all of our results hold for the restricted case and the generalized case where every edge can have multiple labels.

TCS Journal 2025 Journal Article

Uniform-budget solo chess with only rooks or only knights is hard

• Davide Bilò
• Luca Di Donato
• Luciano Gualà
• Stefano Leucci

We study the Solo-Chess problem which has been introduced in [Aravind et al. , FUN 2022]. This is a single-player variant of chess in which the player must clear all but one piece from the board via a sequence captures while ensuring that each piece performs at most as many captures as its budget allows. The time complexity of finding a winning sequence of captures has already been pinpointed for several combinations of piece types and initial budgets. We contribute to a better understanding of the computational landscape of Solo-Chess by closing two problems left open in [Aravind et al. , FUN 2022]. Namely, we show that Solo-Chess is hard even when all pieces are restricted to only rooks with budget exactly 2, or only knights with budget exactly 11.

FOCS Conference 2024 Conference Paper

Improved Distance (Sensitivity) Oracles with Subquadratic Space

• Davide Bilò
• Shiri Chechik
• Keerti Choudhary
• Sarel Cohen
• Tobias Friedrich 0001
• Martin Schirneck

A distance oracle (DO) for a graph $G$ is a data structure that, when queried with vertices $s, t$, returns an estimate $\widehat{d}(s, t)$ of their distance in $G$. The oracle has stretch $(\alpha, \beta)$ if the estimate satisfies $d(s, t)\leqslant \widehat{d}(s, t)\leqslant \alpha\cdot d(s, t)+\beta$. An $f-\mathbf{edge}$ fault-tolerant distance sensitivity oracle $(f-\mathbf{DSO})$ additionally receives a set $F$ of up to $f$ edges and estimates the distance in $G-F$. Our first contribution is the design of new distance oracles with subquadratic space for undirected graphs. We show that introducing a small additive stretch $\beta > 0$ allows one to make the multiplicative stretch $\alpha$ arbitrarily small. This sidesteps a known lower bound of $\alpha\geqslant 3$ (for $\beta=0$ and subquadratic space) [Thorup & Zwick, JACM 2005]. We present a DO for graphs with edge weights in $[0, W]$ that, for any positive integer $\ell$ and any $c\in(0, \ell/2]$, has stretch $(1+\frac{1}{\ell}, 2W)$, space $\widetilde{O}(n^{2-\frac{c}{\ell}})$, and query time $O(n^{c})$, generalizing results by Agarwal and Godfrey [SODA 2013] to arbitrarily dense graphs. Our second contribution is a framework that turns an $(\alpha, \beta)- \mathbf{stretch}$ DO for unweighted graphs into an $(\alpha(1+\varepsilon), \beta)-\mathbf{stretch}. f-\mathbf{DSO}$ with sensitivity $f=o(\log(n)/\log\log n)$ retaining sub-quadratic space. This generalizes a result by Bilò, Chechik, Choudhary, Cohen, Friedrich, Krogmann, and Schirneck [TheoretiCS 2024]. Combining the framework with our new DO gives an $f-\mathbf{DSO}$ that, for any $\gamma\in(0, (\ell+1)/2]$, has stretch $((1+\frac{1}{\ell})(1+\varepsilon), 2)$, space $n^{2-\frac{\gamma}{(t+1)(f+1)}+o(1)}/\varepsilon^{f+2}$, and query time $\widetilde{O}(n^{\gamma}/\varepsilon^{2})$. This is the first $f-\mathbf{DSO}$ with subquadratic space, near-additive stretch, and sublinear query time.

STOC Conference 2023 Conference Paper

Approximate Distance Sensitivity Oracles in Subquadratic Space

• Davide Bilò
• Shiri Chechik
• Keerti Choudhary
• Sarel Cohen
• Tobias Friedrich 0001
• Simon Krogmann
• Martin Schirneck

IJCAI Conference 2023 Conference Paper

Schelling Games with Continuous Types

• Davide Bilò
• Vittorio Bilò
• Michelle Döring
• Pascal Lenzner
• Louise Molitor
• Jonas Schmidt

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.

IJCAI Conference 2023 Conference Paper

Temporal Network Creation Games

• Davide Bilò
• Sarel Cohen
• Tobias Friedrich
• Hans Gawendowicz
• Nicolas Klodt
• Pascal Lenzner
• George Skretas

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.

TCS Journal 2022 Journal Article

Almost optimal algorithms for diameter-optimally augmenting trees

• Davide Bilò

We consider the problem of augmenting an n-vertex tree with one shortcut in order to minimize the diameter of the resulting graph. The tree is embedded in an unknown space and we have access to an oracle that, when queried on a pair of vertices u and v, reports the weight of the shortcut ( u, v ) in constant time. Previously, the problem was solved in O ( n 2 log 3 ⁡ n ) time for general weights [Oh and Ahn, ISAAC 2016], in O ( n 2 log ⁡ n ) time for trees embedded in a metric space [Große et al. , Int. J. FCS], and in O ( n log ⁡ n ) time for paths embedded in a metric space [Wang, Comput. Geom. ]. Very recently an algorithm for general weights requiring O ( n 2 log ⁡ n ) time and O ( n ) space has been developed [Wang and Zhao, Theor. Comp. Science]. Finally, a ( 1 + ε ) -approximation algorithm running in O ( n + 1 / ε 3 ) has been designed for paths embedded in R d, for constant values of d [Große et al. , Int. J. FCS]. In this paper we design an asymptotic time-optimal algorithm for trees and general edge-weights that requires O ( n 2 ) time and O ( n log ⁡ n ) space. Moreover, for trees embedded in a metric space, we design (i) an exact O ( n log ⁡ n ) -time algorithm and (ii) a ( 1 + ε ) -approximation algorithm that runs in O ( n + ε − 1 log ⁡ ε − 1 ) time.

TCS Journal 2022 Journal Article

Cutting bamboo down to size

• Davide Bilò
• Luciano Gualà
• Stefano Leucci
• Guido Proietti
• Giacomo Scornavacca

This paper studies the problem of programming a robotic panda gardener to keep a bamboo garden from obstructing the view of the lake by your house. The garden consists of n bamboo stalks with known daily growth rates and the gardener can cut at most one bamboo per day. As a computer scientist, you found out that this problem has already been formalized in [Gąsieniec et al. , SOFSEM'17] as the Bamboo Garden Trimming (BGT) problem, where the goal is that of computing a perpetual schedule (i. e. , the sequence of bamboos to cut) for the robotic gardener to follow in order to minimize the makespan, i. e. , the maximum height ever reached by a bamboo. Two natural strategies are Reduce-Max and Reduce-Fastest(x). Reduce-Max trims the tallest bamboo of the day, while Reduce-Fastest(x) trims the fastest growing bamboo among the ones that are taller than x. It is known that Reduce-Max and Reduce-Fastest(x) achieve a makespan of O ( log ⁡ n ) and 4 for the best choice of x = 2, respectively. We prove the first constant upper bound of 9 for Reduce-Max and improve the one for Reduce-Fastest(x) to 3 + 5 2 < 2. 62 for x = 1 + 1 5. Another critical aspect stems from the fact that your robotic gardener has a limited amount of processing power and memory. It is then important for the algorithm to be able to quickly determine the next bamboo to cut while requiring at most linear space. We formalize this aspect as the problem of designing a Trimming Oracle data structure, and we provide three efficient Trimming Oracles implementing different perpetual schedules, including those produced by Reduce-Max and Reduce-Fastest(x).

TCS Journal 2022 Journal Article

New approximation algorithms for the heterogeneous weighted delivery problem

• Davide Bilò
• Luciano Gualà
• Stefano Leucci
• Guido Proietti
• Mirko Rossi

We study the heterogeneous weighted delivery (HWD) problem introduced in [Bärtschi et al. , STACS'17] where k heterogeneous mobile agents (e. g. , robots, vehicles, etc.), initially positioned on vertices of an n-vertex edge-weighted graph G, have to deliver m messages. Each message is initially placed on a source vertex of G and needs to be delivered to a target vertex of G. Each agent can move along the edges of G and carry at most one message at any time. Each agent has a rate of energy consumption per unit of traveled distance and the goal is that of delivering all messages using the minimum overall amount of energy. This problem has been shown to be NP-hard even when k = 1, and is 4ρ-approximable where ρ is the ratio between the maximum and minimum energy consumption of the agents. In this paper, we provide approximation algorithms with approximation ratios independent of the energy consumption rates. First, we design a polynomial-time 8-approximation algorithm for k = O ( log ⁡ n ), closing a problem left open in [Bärtschi et al. , ATMOS'17]. This algorithm can be turned into an O ( k ) -approximation algorithm that always runs in polynomial-time, regardless of the values of k. Then, we show that HWD problem is 36-approximable in polynomial-time when each agent has one of two possible consumption rates. Finally, we design a polynomial-time O ˜ ( log 3 ⁡ n ) -approximation algorithm for the general case.

IJCAI Conference 2022 Conference Paper

Tolerance is Necessary for Stability: Single-Peaked Swap Schelling Games

• Davide Bilò
• Vittorio Bilò
• Pascal Lenzner
• Louise Molitor

Residential segregation in metropolitan areas is a phenomenon that can be observed all over the world. Recently, this was investigated via game-theoretic models. There, selfish agents of two types are equipped with a monotone utility function that ensures higher utility if an agent has more same-type neighbors. The agents strategically choose their location on a given graph that serves as residential area to maximize their utility. However, sociological polls suggest that real-world agents are actually favoring mixed-type neighborhoods, and hence should be modeled via non-monotone utility functions. To address this, we study Swap Schelling Games with single-peaked utility functions. Our main finding is that tolerance, i. e. , agents favoring fifty-fifty neighborhoods or being in the minority, is necessary for equilibrium existence on almost regular or bipartite graphs. Regarding the quality of equilibria, we derive (almost) tight bounds on the Price of Anarchy and the Price of Stability. In particular, we show that the latter is constant on bipartite and almost regular graphs.

JAAMAS Journal 2022 Journal Article

Topological influence and locality in swap schelling games

• Davide Bilò
• Vittorio Bilò
• Louise Molitor

Abstract Residential segregation is a wide-spread phenomenon that can be observed in almost every major city. In these urban areas residents with different racial or socioeconomic background tend to form homogeneous clusters. Schelling’s famous agent-based model for residential segregation explains how such clusters can form even if all agents are tolerant, i. e. , if they agree to live in mixed neighborhoods. For segregation to occur, all it needs is a slight bias towards agents preferring similar neighbors. Very recently, Schelling’s model has been investigated from a game-theoretic point of view with selfish agents that strategically select their residential location. In these games, agents can improve on their current location by performing a location swap with another agent who is willing to swap. We significantly deepen these investigations by studying the influence of the underlying topology modeling the residential area on the existence of equilibria, the Price of Anarchy and on the dynamic properties of the resulting strategic multi-agent system. Moreover, as a new conceptual contribution, we also consider the influence of locality, i. e. , if the location swaps are restricted to swaps of neighboring agents. We give improved almost tight bounds on the Price of Anarchy for arbitrary underlying graphs and we present (almost) tight bounds for regular graphs, paths and cycles. Moreover, we give almost tight bounds for grids, which are commonly used in empirical studies. For grids we also show that locality has a severe impact on the game dynamics.

AAAI Conference 2021 Conference Paper

Selfish Creation of Social Networks

• Davide Bilò
• Tobias Friedrich
• Pascal Lenzner
• Stefanie Lowski
• Anna Melnichenko

Understanding real-world networks has been a core research endeavor throughout the last two decades. Network Creation Games are a promising approach for this from a gametheoretic perspective. In these games, selfish agents corresponding to nodes in a network strategically decide which links to form to optimize their centrality. Many versions have been introduced and analyzed, but none of them fits to modeling the evolution of social networks. In real-world social networks, connections are often established by recommendations from common acquaintances or by a chain of such recommendations. Thus establishing and maintaining a contact with a friend of a friend is easier than connecting to complete strangers. This explains the high clustering, i. e. , the abundance of triangles, in real-world social networks. We propose and analyze a network creation model inspired by real-world social networks. Edges are formed in our model via bilateral consent of both endpoints and the cost for establishing and maintaining an edge is proportional to the distance of the endpoints before establishing the connection. We provide results for generic cost functions, which essentially only must be convex functions in the distance of the endpoints without the respective edge. For this broad class of cost functions, we provide many structural properties of equilibrium networks and prove (almost) tight bounds on the diameter, the Price of Anarchy and the Price of Stability. Moreover, as a proof-of-concept we show via experiments that the created equilibrium networks of our model indeed closely mimics real-world social networks. We observe degree distributions that seem to follow a power-law, high clustering, and low diameters. This can be seen as a promising first step towards game-theoretic network creation models that predict networks featuring all core real-world properties.

MFCS Conference 2021 Conference Paper

Space-Efficient Fault-Tolerant Diameter Oracles

• Davide Bilò
• Sarel Cohen
• Tobias Friedrich 0001
• Martin Schirneck

We design f-edge fault-tolerant diameter oracles (f-FDO, or simply FDO if f = 1). For a given directed or undirected and possibly edge-weighted graph G with n vertices and m edges and a positive integer f, we preprocess the graph and construct a data structure that, when queried with a set F of edges, where |F| ⩽ f, returns the diameter of G-F. An f-FDO has stretch σ ⩾ 1 if the returned value D^ satisfies diam(G-F) ⩽ D^ ⩽ σ diam(G-F). For the case of a single edge failure (f = 1) in an unweighted directed graph, there exists an approximate FDO by Henzinger et al. [ITCS 2017] with stretch (1+ε), constant query time, space O(m), and a combinatorial preprocessing time of Õ(mn + n^{1. 5} √{Dm/ε}), where D is the diameter. We present an FDO for directed graphs with the same stretch, query time, and space. It has a preprocessing time of Õ(mn + n²/ε), which is better for constant ε > 0. The preprocessing time nearly matches a conditional lower bound for combinatorial algorithms, also by Henzinger et al. With fast matrix multiplication, we achieve a preprocessing time of Õ(n^{2. 5794} + n²/ε). We further prove an information-theoretic lower bound showing that any FDO with stretch better than 3/2 requires Ω(m) bits of space. Thus, for constant 0 < ε < 3/2, our combinatorial (1+ε)-approximate FDO is near-optimal in all parameters. In the case of multiple edge failures (f > 1) in undirected graphs with non-negative edge weights, we give an f-FDO with stretch (f+2), query time O(f²log²{n}), Õ(fn) space, and preprocessing time Õ(fm). We complement this with a lower bound excluding any finite stretch in o(fn) space. Many real-world networks have polylogarithmic diameter. We show that for those graphs and up to f = o(log n/ log log n) failures one can swap approximation for query time and space. We present an exact combinatorial f-FDO with preprocessing time mn^{1+o(1)}, query time n^o(1), and space n^{2+o(1)}. When using fast matrix multiplication instead, the preprocessing time can be improved to n^{ω+o(1)}, where ω < 2. 373 is the matrix multiplication exponent.

MFCS Conference 2020 Conference Paper

Topological Influence and Locality in Swap Schelling Games

• Davide Bilò
• Vittorio Bilò
• Pascal Lenzner
• Louise Molitor

Residential segregation is a wide-spread phenomenon that can be observed in almost every major city. In these urban areas residents with different racial or socioeconomic background tend to form homogeneous clusters. Schelling’s famous agent-based model for residential segregation explains how such clusters can form even if all agents are tolerant, i. e. , if they agree to live in mixed neighborhoods. For segregation to occur, all it needs is a slight bias towards agents preferring similar neighbors. Very recently, Schelling’s model has been investigated from a game-theoretic point of view with selfish agents that strategically select their residential location. In these games, agents can improve on their current location by performing a location swap with another agent who is willing to swap. We significantly deepen these investigations by studying the influence of the underlying topology modeling the residential area on the existence of equilibria, the Price of Anarchy and on the dynamic properties of the resulting strategic multi-agent system. Moreover, as a new conceptual contribution, we also consider the influence of locality, i. e. , if the location swaps are restricted to swaps of neighboring agents. We give improved almost tight bounds on the Price of Anarchy for arbitrary underlying graphs and we present (almost) tight bounds for regular graphs, paths and cycles. Moreover, we give almost tight bounds for grids, which are commonly used in empirical studies. For grids we also show that locality has a severe impact on the game dynamics.

TCS Journal 2020 Journal Article

Tracking routes in communication networks

• Davide Bilò
• Luciano Gualà
• Stefano Leucci
• Guido Proietti

The minimum tracking set problem is an optimization problem that deals with monitoring communication paths that can be used for exchanging point-to-point messages using as few tracking devices as possible. More precisely, a tracking set of a given graph G and a set of source-destination pairs of vertices is a subset T of vertices of G such that the vertices in T traversed by any source-destination shortest path P uniquely identify P. The minimum tracking set problem has been introduced in Banik et al. , CIAC (2017) [1] for the case of a single source-destination pair. There, the authors show that the problem is APX-hard and that it can be 2-approximated for the class of planar graphs, even though no hardness result is known for this case. In this paper we focus on the case of multiple source-destination pairs and we present the first O ˜ ( n ) -approximation algorithm for general graphs. Moreover, we prove that the problem remains NP-hard even for cubic planar graphs and all pairs S × D, where S and D are the sets of sources and destinations, respectively. Finally, for the case of a single source-destination pair, we design an (exact) FPT algorithm w. r. t. the maximum number of vertices at the same distance from the source.

TCS Journal 2016 Journal Article

Exact and approximate algorithms for movement problems on (special classes of) graphs

• Davide Bilò
• Luciano Gualà
• Stefano Leucci
• Guido Proietti

When a large collection of objects (e. g. , robots, sensors, etc.) has to be deployed in a given environment, it is often required to plan a coordinated motion of the objects from their initial position to a final configuration enjoying some global property. In such a scenario, the problem of minimizing some function of the distance travelled, and therefore of reducing energy consumption, is of vital importance. In this paper we study several motion planning problems that arise when the objects initially sit on the vertices of a graph, and they must be moved so as that the final vertices that receive (at least) one object induce a subgraph enjoying a given property. In particular, we consider the notable properties of connectivity, independence, completeness, and finally that of being a vertex-cutset w. r. t. a pair of fixed vertices. We study these problems with the aim of minimizing a number of natural measures, namely the average/overall distance travelled, the maximum distance travelled, and the number of objects that need to be moved. To this respect, we provide several approximability and inapproximability results, most of which are tight.

TCS Journal 2015 Journal Article

Specializations and generalizations of the Stackelberg minimum spanning tree game

• Davide Bilò
• Luciano Gualà
• Stefano Leucci
• Guido Proietti

Let be given a graph G = ( V, E ) whose edge set is partitioned into a set R of red edges and a set B of blue edges, and assume that red edges are weighted and form a spanning tree of G. Then, the Stackelberg Minimum Spanning Tree (StackMST) problem is that of pricing (i. e. , weighting) the blue edges in such a way that the total weight of the blue edges selected in a minimum spanning tree of the resulting graph is maximized. StackMST is known to be APX-hard already when the number of distinct red edge weights is 2. In this paper we analyze some meaningful specializations and generalizations of StackMST, which shed some more light on the computational complexity of the problem. More precisely, we first show that if G is restricted to be complete, then the following holds: (i) if there are only 2 distinct red edge weights, then the problem can be solved optimally (this contrasts with the corresponding APX-hardness of the general problem); (ii) otherwise, the problem can be approximated within 7 / 4 + ϵ, for any ϵ > 0. Afterwards, we define a natural extension of StackMST, namely that in which blue edges are associated with a non-negative activation cost, and it is given a global activation budget that can be used (and must not be exceeded) in order to activate a subset of blue edges to be priced. Here, after showing that the very same approximation ratio as that of the original problem can be achieved, we prove that if the spanning tree of red edges can be rooted so as that any root-leaf path contains at most h edges, then the problem admits a ( 2 h + ϵ ) -approximation algorithm, for any ϵ > 0.

TCS Journal 2015 Journal Article

The max-distance network creation game on general host graphs

• Davide Bilò
• Luciano Gualà
• Stefano Leucci
• Guido Proietti

In this paper we study a generalization of the classic network creation game in the scenario in which the n players sit on a given arbitrary host graph, which constrains the set of edges a player can activate at a cost of α ≥ 0 each. This finds its motivations in the physical limitations one can have in constructing links in practice, and it has been studied in the past only when the routing cost component of a player is given by the sum of distances to all the other nodes. Here, we focus on another popular routing cost, namely that which takes into account for each player her maximum distance to any other player. For this version of the game, we first analyze some of its computational and dynamic aspects, and then we address the problem of understanding the structure of associated pure Nash equilibria. In this respect, we show that the corresponding price of anarchy (PoA) is fairly bad, even for very simple host graph topologies. More precisely, we first exhibit a lower bound of Ω ( n / ( 1 + α ) ) for any α = o ( n ). Notice that this implies a counter-intuitive lower bound of Ω ( n ) even for α = 0, i. e. , when edges can be activated for free. Then, we show that when the host graph is restricted to be either k-regular (for any constant k ≥ 3 ), or a 2-dimensional grid, the PoA is still Ω ( 1 + min ⁡ { α, n α } ), which is proven to be tight for α = Ω ( n ). On the positive side, if α ≥ n, we show that the PoA is at most 2. Finally, in the case in which the host graph is very sparse (i. e. , | E ( H ) | = n − 1 + k, with k = O ( 1 ) ), we prove that the PoA is O ( 1 ), for any α.

TCS Journal 2012 Journal Article

Improved approximability and non-approximability results for graph diameter decreasing problems

• Davide Bilò
• Luciano Gualà
• Guido Proietti

In this paper, we study two variants of the problem of adding edges to a graph so as to reduce the resulting diameter. More precisely, given a graph G = ( V, E ), and two positive integers D and B, the Minimum-Cardinality Bounded-Diameter Edge Addition (MCBD) problem is to find a minimum-cardinality set F of edges to be added to G in such a way that the diameter of G + F is less than or equal to D, while the Bounded-Cardinality Minimum-Diameter Edge Addition (BCMD) problem is to find a set F of B edges to be added to G in such a way that the diameter of G + F is minimized. Both problems are well known to be NP-hard, as well as approximable within O ( log n log D ) and 4 (up to an additive term of 2), respectively. In this paper, we improve these long-standing approximation ratios to O ( log n ) and to 2 (up to an additive term of 2), respectively. As a consequence, we close, in an asymptotic sense, the gap on the approximability of MCBD, which was known to be not approximable within c log n, for some constant c > 0, unless P = NP. Remarkably, as we further show in the paper, our approximation ratio remains asymptotically tight even if we allow for a solution whose diameter is optimal up to a multiplicative factor approaching 5 3. On the other hand, on the positive side, we show that at most twice of the minimal number of additional edges suffices to get at most twice of the required diameter. Some of our results extend to the edge-weighted version of the problems.

MFCS Conference 2012 Conference Paper

New Advances in Reoptimizing the Minimum Steiner Tree Problem

• Davide Bilò
• Anna Zych

Abstract In this paper we improve the results in the literature concerning the problem of computing the minimum Steiner tree given the minimum Steiner tree for a similar problem instance. Using a σ -approximation algorithm computing the minimum Steiner tree from scratch, we provide a \(\left(\frac{3 \sigma-1}{2 \sigma-1}+\epsilon\right)\) and a \(\left(\frac{2 \sigma-1}{\sigma}+\epsilon\right)\) -approximation algorithm for altering the instance by removing a vertex from the terminal set and by increasing the cost of an edge, respectively. If we use the best up to date σ = ln 4 + ε, our ratios equal 1. 218 and 1. 279 respectively.

TCS Journal 2010 Journal Article

Discovery of network properties with all-shortest-paths queries

• Davide Bilò
• Thomas Erlebach
• Matúš Mihalák
• Peter Widmayer

We consider the problem of discovering properties (such as the diameter) of an unknown network G = ( V, E ) with a minimum number of queries. Initially, only the vertex set V of the network is known. Information about the edges and non-edges of the network can be obtained by querying nodes of the network. A query at a node q ∈ V returns the union of all shortest paths from q to all other nodes in V. We study the problem as an online problem–an algorithm does not initially know the edge set of the network, and has to decide where to make the next query based on the information that was gathered by previous queries. We study how many queries are needed to discover the diameter, a minimal dominating set, a maximal independent set, the minimum degree, and the maximum degree of the network. We also study the problem of deciding with a minimum number of queries whether the network is 2-edge or 2-vertex connected. We use the usual competitive analysis to evaluate the quality of online algorithms, i. e. , we compare online algorithms with the optimum offline algorithms. For all properties except the maximal independent set, 2-vertex connectivity and minimum/maximum degree, we present and analyze online algorithms. Furthermore we show, for all the aforementioned properties, that “many” queries are needed in the worst case. As our query model delivers more information about the network than the measurement heuristics that are currently used in practice, these negative results suggest that a similar behavior can be expected in realistic settings, or in more realistic models derived from the all-shortest-paths query model.

MFCS Conference 2010 Conference Paper

Finding Best Swap Edges Minimizing the Routing Cost of a Spanning Tree

• Davide Bilò
• Luciano Gualà
• Guido Proietti

Abstract Given an n -node, undirected and 2-edge-connected graph G = ( V, E ) with positive real weights on its m edges, given a set of k source nodes S ⊆ V, and given a spanning tree T of G, the routing cost of T w. r. t. S is the sum of the distances in T from every source s ∈ S to all the other nodes of G. If an edge e of T undergoes a transient failure and connectivity needs to be promptly reestablished, then to reduce set-up and rerouting costs it makes sense to temporarily replace e by means of a swap edge, i. e. , an edge in G reconnecting the two subtrees of T induced by the removal of e. Then, a best swap edge for e is a swap edge which minimizes the routing cost of the tree obtained after the swapping. As a natural extension, the all-best swap edges problem is that of finding a best swap edge for every edge of T. Such a problem has been recently solved in O ( mn ) time and linear space for arbitrary k, and in O ( n 2 + m log n ) time and O ( n 2 ) space for the special case k = 2. In this paper, we are interested to the prominent cases k = O (1) and k = n, which model realistic communication paradigms. For these cases, we present a linear space and \(\widetilde O(m)\) time algorithm, and thus we improve both the above running times (but for quite dense graphs in the case k = 2, for which however it is noticeable we make use of only linear space). Moreover, we provide an accurate analysis showing that when k = n, the obtained swap tree is effective in terms of routing cost.

MFCS Conference 2010 Conference Paper

Improved Approximability and Non-approximability Results for Graph Diameter Decreasing Problems

• Davide Bilò
• Luciano Gualà
• Guido Proietti

Abstract In this paper we study two variants of the problem of adding edges to a graph so as to reduce the resulting diameter. More precisely, given a graph G = ( V, E ), and two positive integers D and B, the Minimum-Cardinality Bounded-Diameter Edge Addition (MCBD) problem is to find a minimum cardinality set F of edges to be added to G in such a way that the diameter of G + F is less than or equal to D, while the Bounded-Cardinality Minimum-Diameter Edge Addition (BCMD) problem is to find a set F of B edges to be added to G in such a way that the diameter of G + F is minimized. Both problems are well known to be NP -hard, as well as approximable within O (log n log D ) and 4 (up to an additive term of 2), respectively. In this paper, we improve these long-standing approximation ratios to O (log n ) and to 2 (up to an additive term of 2), respectively. As a consequence, we close, in an asymptotic sense, the gap on the approximability of the MCBD problem, which was known to be not approximable within c log n, for some constant c > 0, unless P = NP. Remarkably, as we further show in the paper, our approximation ratio remains asymptotically tight even if we allow for a solution whose diameter is optimal up to a multiplicative factor approaching \(\frac{5}{3}\). On the other hand, on the positive side, we show that at most twice of the minimal number of additional edges suffices to get at most twice of the required diameter.

TCS Journal 2009 Journal Article

Dynamic mechanism design

• Davide Bilò
• Luciano Gualà
• Guido Proietti

In this paper we address the question of designing truthful mechanisms for solving optimization problems on dynamic graphs with selfish edges. More precisely, we are given a graph G of n nodes, and we assume that each edge of G is owned by a selfish agent. The strategy of an agent consists in revealing to the system–at each time instant–the cost at the actual time for using its edge. Additionally, edges can enter into and exit from G. Among the various possible assumptions which can be made to model how this edge-cost modifications take place, we focus on two settings: (i) the dynamic, in which modifications can happen at any time, and for a given optimization problem on G, the mechanism has to maintain efficiently the output specification and the payment scheme for the agents; (ii) the time-sequenced, in which modifications happens at fixed time steps, and the mechanism has to minimize an objective function which takes into consideration both the quality and the set-up cost of a new solution. In both settings, we investigate the existence of exact and approximate truthful (w. r. t. to suitable equilibrium concepts) mechanisms. In particular, for the dynamic setting, we analyze the minimum spanning tree problem, and we show that if edge costs can only decrease and each agent adopts a myopic best response strategy (i. e. , its utility is only measured instantaneously), then there exists an efficient dynamic truthful (in myopic best response equilibrium) mechanism for handling a sequence of k declarations of edge-cost reductions having runtime O ( ( h + k ) log n ), where h is the overall number of payment changes.

TCS Journal 2008 Journal Article

On the complexity of minimizing interference in ad-hoc and sensor networks

• Davide Bilò
• Guido Proietti

One of the most critical factors for lifetime and operability of ad-hoc and sensor networks is the limited amount of available energy. To this respect, minimizing the interference in the network (i. e. , the overlapping of signals at network nodes) has certainly a positive effect, because it induces a reduction of the number of conflicting transmissions, and then results in an overall saving of energy consumption. Along this direction, in this paper we study the computational hardness of several interference minimization problems which arise while supporting some classic network communication patterns such as broadcasting (one-to-all), gossiping (all-to-all), and symmetric gossiping (symmetric all-to-all). In particular, concerning the non-approximability results, we prove that for any of the above communication patterns, the prominent problem of minimizing the maximum interference experienced by any node in the network is hard to approximate within better than a logarithmic factor, unless NP admits slightly superpolynomial time algorithms. On a positive side, we show that any approximation algorithm for the problem of minimizing the total transmission power assigned to the nodes in order to guarantee any of the above communication patterns, can be transformed, by maintaining the same performance ratio, into an approximation algorithm for the problem of minimizing the total interference experienced by all the nodes in the network.