A hierarchical graph 𝒢 consists of a vertex set V(𝒢) and L pairwise disjoint edge sets E_1, … , E_L. Such a structure naturally defines a hierarchy of L unweighted graphs, where the 𝓁-th graph is G_𝓁 = (V, ⋃_{i=1}^𝓁 E_i). In this paper, we initiate the study of hierarchical spanners, namely subgraphs of 𝒢 that approximately preserve distances among a given set of pairs of vertices in V(𝒢) at every level of the hierarchy. This notion generalizes classical spanners, and thus all known lower bounds extend to this setting; however, it is not clear whether the same size-stretch trade-offs can be achieved. We investigate this question by devising both upper and lower bounds for hierarchical spanners under various types of stretch and pairs of vertices of interest whose approximate (or exact) distances are to be maintained. On the positive side, a trivial adaptation of the greedy construction yields (2k-1)-spanners of size O(n^{1+1/k}), matching the classical bounds. However, the non-hierarchical bounds do not extend to the hierarchical case when additive or nearly-additive spanners are considered. For instance, we prove that any β-additive single-pair hierarchical spanner must have size Ω (n √{n/(β+1)}) in the worst case. This bound is tight, as we provide a matching upper bound for every β ≥ 0, which in turn implies a O(n√n)-size single-pair hierarchical preserver. Finally, we present additional positive results among which a 4-additive all-pairs hierarchical spanner of size Õ(n^{5/3}), an (essentially tight) single-source hierarchical (1+ε)-spanner of size Õ(n/ε), an all-pairs hierarchical spanner of size Õ(n√{n/(ε)}) achieving stretch (1+ε,2), for any constant value of ε > 0, and a subsetwise hierarchical preserver of size O(n √{n|S|}), where S ⊆ V(𝒢).

We consider the task of performing Jaccard similarity queries over a large collection of items that are dynamically updated according to a streaming input model. An item here is a subset of a large universe U of elements. A well-studied approach to address this important problem in data mining is to design fast-similarity data sketches. In this paper, we focus on global solutions for this problem, i.e., a single data structure which is able to answer both Similarity Estimation and All-Candidate Pairs queries, while also dynamically managing an arbitrary, online sequence of element insertions and deletions received in input.

In the k-Diameter-Optimally Augmenting Tree Problem we are given a tree T of n vertices embedded in an unknown metric space. An oracle can report the cost of any edge in constant time, and we want to augment T with k shortcuts to minimize the resulting diameter. When k = 1 , O ( n log ⁡ n ) -time algorithms exist for paths and trees. We show that o ( n 2 ) queries cannot provide a better than 10/9-approximation for trees when k ≥ 3 . For any constant ε > 0 , we design a linear-time ( 1 + ε ) -approximation algorithm for paths when k = o ( log ⁡ n ) , thus establishing a dichotomy between paths and trees for k ≥ 3 . Our algorithm employs an ad-hoc data structure, which we also use in a linear-time 4-approximation algorithm for trees, and to compute the diameter of (possibly non-metric) graphs with n + k − 1 edges in time O ( n k log ⁡ n ) .

In this work, we propose, analyze and empirically validate a lazy-update approach to maintain accurate approximations of the 2-hop neighborhoods of dynamic graphs resulting from sequences of edge insertions. We first show that under random input sequences, our algorithm exhibits an optimal trade-off between accuracy and insertion cost: it only performs [EQUATION] (amortized) updates per edge insertion, while the estimated size of any vertex's 2-hop neighborhood is at most a factor ε away from its true value in most cases, regardless of the underlying graph topology and for any ε > 0. As a further theoretical contribution, we explore adversarial scenarios that can force our approach into a worst-case behavior at any given time t of interest. We show that while worst-case input sequences do exist, a necessary condition for them to occur is that the girth of the graph released up to time t be at most 4. Finally, we conduct extensive experiments on a collection of real, incremental social networks of different sizes, which typically have low girth. Empirical results are consistent with and typically better than our theoretical analysis anticipates. This further supports the robustness of our theoretical findings: forcing our algorithm into a worst-case behavior not only requires topologies characterized by a low girth, but also carefully crafted input sequences that are unlikely to occur in practice. Combined with standard sketching techniques, our lazy approach proves an effective and efficient tool to support key neighborhood queries on large, incremental graphs, including neighborhood size, Jaccard similarity between neighborhoods and, in general, functions of the union and/or intersection of 2-hop neighborhoods.

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.

A spanner is a sparse subgraph of a given graph $G$ which preserves distances, measured w.r.t.\ some distance metric, up to a multiplicative stretch factor. This paper addresses the problem of constructing graph spanners w.r.t.\ the group Steiner metric, which generalizes the recently introduced beer distance metric. In such a metric we are given a collection of groups of required vertices, and we measure the distance between two vertices as the length of the shortest path between them that traverses at least one required vertex from each group. We discuss the relation between group Steiner spanners and classic spanners and we show that they exhibit strong ties with sourcewise spanners w.r.t.\ the shortest path metric. Nevertheless, group Steiner spanners capture several interesting scenarios that are not encompassed by existing spanners. This happens, e.g., for the singleton case, in which each group consists of a single required vertex, thus modeling the setting in which routes need to traverse certain points of interests (in any order). We provide several constructions of group Steiner spanners for both the all-pairs and single-source case, which exhibit various size-stretch trade-offs. Notably, we provide spanners with almost-optimal trade-offs for the singleton case. Moreover, some of our spanners also yield novel trade-offs for classical sourcewise spanners. Finally, we also investigate the query times that can be achieved when our spanners are turned into group Steiner distance oracles with the same size, stretch, and building time.

In a temporal forest each edge has an associated set of time labels that specify the time instants in which the edges are available. A temporal path from vertex $u$ to vertex $v$ in the forest is a selection of a label for each edge in the unique path from $u$ to $v$, assuming it exists, such that the labels selected for any two consecutive edges are non-decreasing. We design linear-size data structures that maintain a temporal forest of rooted trees under addition and deletion of both edge labels and singleton vertices, insertion of root-to-node edges, and removal of edges with no labels. Such data structures can answer temporal reachability, earliest arrival, and latest departure queries. All queries and updates are handled in polylogarithmic worst-case time. Our results can be adapted to deal with latencies. More precisely, all the worst-case time bounds are asymptotically unaffected when latencies are uniform. For arbitrary latencies, the update time becomes amortized in the incremental case where only label additions and edge/singleton insertions are allowed as well as in the decremental case in which only label deletions and edge/singleton removals are allowed. To the best of our knowledge, the only previously known data structure supporting temporal reachability queries is due to Brito, Albertini, Casteigts, and Travençolo [Social Network Analysis and Mining, 2021], which can handle general temporal graphs, answers queries in logarithmic time in the worst case, but requires an amortized update time that is quadratic in the number of vertices, up to polylogarithmic factors.

We introduce the notions of blackout-tolerant temporal α-spanner of a temporal graph G which is a subgraph of G that preserves the distances between pairs of vertices of interest in G up to a multiplicative factor of α, even when the graph edges at a single time-instant become unavailable. In particular, we consider the single-source, single-pair, and all-pairs cases and, for each case we look at three quality requirements: exact distances (i.e., α=1), almost-exact distances (i.e., α=1+ε for an arbitrarily small constant ε>0), and connectivity (i.e., unbounded α). We provide almost tight bounds on the size of such spanners for general temporal graphs and for temporal cliques, showing that they are either very sparse (i.e., they have O˜(n) edges) or they must have size Ω(n2) in the worst case, where n is the number of vertices of G. We also investigate multiple blackouts and k-edge fault-tolerant temporal spanners.

Abstract We study the problem of designing a resilient data structure maintaining a tree under the Faulty-RAM model [Finocchi and Italiano, STOC’04] in which up to $$\delta $$ δ memory words can be corrupted by an adversary. Our data structure stores a rooted dynamic tree that can be updated via the addition of new leaves, requires linear size, and supports resilient (weighted) level ancestor queries, lowest common ancestor queries, and bottleneck vertex queries in $$O(\delta )$$ O ( δ ) worst-case time per operation.

A temporal graph is an undirected graph $G=(V,E)$ along with a function that assigns a time-label to each edge in $E$. A path in $G$ with non-decreasing time-labels is called temporal path and the distance from $u$ to $v$ is the minimum length (i.e., the number of edges) of a temporal path from $u$ to $v$. A temporal $α$-spanner of $G$ is a (temporal) subgraph $H$ that preserves the distances between any pair of vertices in $V$, up to a multiplicative stretch factor of $α$. The size of $H$ is the number of its edges. In this work we study the size-stretch trade-offs of temporal spanners. We show that temporal cliques always admit a temporal $(2k-1)-$spanner with $\tilde{O}(kn^{1+\frac{1}{k}})$ edges, where $k>1$ is an integer parameter of choice. Choosing $k=\lfloor\log n\rfloor$, we obtain a temporal $O(\log n)$-spanner with $\tilde{O}(n)$ edges that has almost the same size (up to logarithmic factors) as the temporal spanner in [Casteigts et al., JCSS 2021] which only preserves temporal connectivity. We then consider general temporal graphs. Since $Ω(n^2)$ edges might be needed by any connectivity-preserving temporal subgraph [Axiotis et al., ICALP'16], we focus on approximating distances from a single source. We show that $\tilde{O}(n/\log(1+\varepsilon))$ edges suffice to obtain a stretch of $(1+\varepsilon)$, for any small $\varepsilon>0$. This result is essentially tight since there are temporal graphs for which any temporal subgraph preserving exact distances from a single-source must use $Ω(n^2)$ edges. We extend our analysis to prove an upper bound of $\tilde{O}(n^2/β)$ on the size of any temporal $β$-additive spanner, which is tight up to polylogarithmic factors. Finally, we investigate how the lifetime of $G$, i.e., the number of its distinct time-labels, affects the trade-off between the size and the stretch of a temporal spanner.

Let $G$ be a directed graph with $n$ vertices and $m$ edges, and let $s \in V(G)$ be a designated source vertex. We consider the problem of single source reachability (SSR) from $s$ in presence of failures of edges (or vertices). Formally, a spanning subgraph $H$ of $G$ is a {\em $k$-Fault Tolerant Reachability Subgraph ($k$-FTRS)} if it has the following property. For any set $F$ of at most $k$ edges (or vertices) in $G$, and for any vertex $v\in V(G)$, the vertex $v$ is reachable from $s$ in $G-F$ if and only if it is reachable from $s$ in $H - F$. Baswana et.al. [STOC 2016, SICOMP 2018] showed that in the setting above, for any positive integer $k$, we can compute a $k$-FTRS with $2^k n$ edges. In this paper, we give a much simpler algorithm for computing a $k$-FTRS, and observe that it extends to higher connectivity as well. Our results follow from a simple application of \emph{important separators}, a well known technique in Parameterized Complexity.

Let G be an n-node and m-edge positively real-weighted undirected graph. For any given integer $$f \ge 1$$ , we study the problem of designing a sparse f-edge-fault-tolerant (f-EFT) $$\sigma $$ -approximate single-source shortest-path tree ( $$\sigma $$ -ASPT), namely a subgraph of G having as few edges as possible and which, following the failure of a set F of at most f edges in G, contains paths from a fixed source that are stretched by a factor of at most $$\sigma $$ . To this respect, we provide an algorithm that efficiently computes an f-EFT $$(2|F|+1)$$ -ASPT of size O(fn). Our structure improves on a previous related construction designed for unweighted graphs, having the same size but guaranteeing a larger stretch factor of $$3(f+1)$$ , plus an additive term of $$(f+1) \log n$$ . Then, we show how to convert our structure into an efficient f-EFT single-source distance oracle, that can be built in $$O(f m\, \alpha (m,n)+fn \log ^3 n)$$ time, has size $$O(fn \log ^2 n)$$ , and in $$O(|F|^2 \log ^2 n)$$ time is able to report a $$(2|F|+1)$$ -approximate distance from the source to any node in $$G-F$$ . Moreover, our oracle can return a corresponding approximate path in the same amount of time plus the path’s size. The oracle is obtained by tackling another fundamental problem, namely that of updating a minimum spanning forest (MSF) of G following a batch of k simultaneous modification (i.e., edge insertions, deletions and weight changes). For this problem, we build in $$O(m \log ^3 n)$$ time an oracle of size $$O(m \log ^2 n)$$ , that reports in $$O(k^2 \log ^2 n)$$ time the (at most 2k) edges either exiting from or entering into the MSF. Finally, for any integer $$k \ge 1$$ , we complement all our results with a lower bound of $$\Omega \left( n^{1+\frac{1}{k}}\right) $$ to the size of any f-EFT $$\sigma $$ -ASPT with $$f \ge \log n$$ and $$\sigma < \frac{3k+1}{k+1}$$ , that holds if the Erdős’ girth conjecture is true.

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

We study the problem of designing a \emph{resilient} data structure maintaining a tree under the Faulty-RAM model [Finocchi and Italiano, STOC'04] in which up to $\delta$ memory words can be corrupted by an adversary. Our data structure stores a rooted dynamic tree that can be updated via the addition of new leaves, requires linear size, and supports \emph{resilient} (weighted) level ancestor queries, lowest common ancestor queries, and bottleneck vertex queries in $O(\delta)$ worst-case time per operation.

Consensus and Broadcast are two fundamental problems in distributed computing, whose solutions have several applications. Intuitively, Consensus should be no harder than Broadcast, and this can be rigorously established in several models. Can Consensus be easier than Broadcast? In models that allow noiseless communication, we prove a reduction of (a suitable variant of) Broadcast to binary Consensus, that preserves the communication model and all complexity parameters such as randomness, number of rounds, communication per round, etc., while there is a loss in the success probability of the protocol. Using this reduction, we get, among other applications, the first logarithmic lower bound on the number of rounds needed to achieve Consensus in the uniform GOSSIP model on the complete graph. The lower bound is tight and, in this model, Consensus and Broadcast are equivalent. We then turn to distributed models with noisy communication channels that have been studied in the context of some bio-inspired systems. In such models, only one noisy bit is exchanged when a communication channel is established between two nodes, and so one cannot easily simulate a noiseless protocol by using error-correcting codes. An Ω(ε^{-2} n) lower bound is proved by Boczkowski et al. [PLOS Comp. Bio. 2018] on the convergence time of binary Broadcast in one such model (noisy uniform PULL), where ε is a parameter that measures the amount of noise). We prove an O(ε^{-2} log n) upper bound on the convergence time of binary Consensus in such model, thus establishing an exponential complexity gap between Consensus versus Broadcast. We also prove our upper bound above is tight and this implies, for binary Consensus, a further strong complexity gap between noisy uniform PULL and noisy uniform PUSH. Finally, we show a Θ(ε^{-2} n log n) bound for Broadcast in the noisy uniform PULL.

A tree $$\sigma $$ -spanner of a positively real-weighted n-vertex and m-edge undirected graph G is a spanning tree T of G which approximately preserves (i.e., up to a multiplicative stretch factor $$\sigma $$ ) distances in G. Tree spanners with provably good stretch factors find applications in communication networks, distributed systems, and network design. However, finding an optimal or even a good tree spanner is a very hard computational task. Thus, if one has to face a transient edge failure in T, the overall effort that has to be afforded to rebuild a new tree spanner (i.e., computational costs, set-up of new links, updating of the routing tables, etc.) can be rather prohibitive. To circumvent this drawback, an effective alternative is that of associating with each tree edge a best possible (in terms of resulting stretch) swap edge—a well-established approach in the literature for several other tree topologies. Correspondingly, the problem of computing all the best swap edges of a tree spanner is a challenging algorithmic problem, since solving it efficiently means to exploit the structure of shortest paths not only in G, but also in all the scenarios in which an edge of T has failed. For this problem we provide a very efficient solution, running in $$O(n^2 \log ^4 n)$$ time, which drastically improves (almost by a quadratic factor in n in dense graphs) on the previous known best result.

Real life graphs and networks are prone to failure of nodes (vertices) and links (edges). In particular, for a pair of nodes s and t and a failing edge e in an n-vertex unweighted graph G=(V(G),E(G)), the replacement path pi_{G-e}(s,t) is a shortest s-t path that avoids e. In this paper we present several efficient constructions that, for every (s,t) \in S x T, where S, T \subseteq V(G), and every e \in E(G), maintain the collection of all pi_{G-e}(s,t), either implicitly (i.e., through compact data structures a.k.a. distance sensitivity oracles (DSO)), or explicitly (i.e., through sparse subgraphs a.k.a. fault-tolerant preservers (FTP)). More precisely, we provide the following results: (1) DSO: For every S,T \subseteq V(G), we construct a DSO for maintaining S x T distances under single edge (or vertex) faults. This DSO has size tilde{O}(n\sqrt{|S||T|}) and query time of O(\sqrt{|S||T|}). At the expense of having quasi-polynomial query time, the size of the oracle can be improved to tilde{O}(n|S|+|T|\sqrt{|S|n}), which is optimal for |T| = Omega(sqrt{n|S|}). When |T| = Omega(n^frac{3}{4} |S|^frac{1}{4}), the construction can be further refined in order to get a polynomial query time. We also consider the approximate additive setting, and show a family of DSOs that exhibits a tradeoff between the additive stretch and the size of the oracle. Finally, for the meaningful single-source case, the above result is complemented by a lower bound conditioned on the Set-Intersection conjecture. This lower bound establishes a separation between the oracle and the subgraph settings. (2) FTP: We show the construction of a path-reporting DSO of size tilde{O}(n^{4/3}(|S||T|)^{1/3}) reporting pi_{G-e}(s,t) in O(|pi_{G-e}(s,t)|+(n|S||T|)^{1/3}) time. Such a DSO can be transformed into a FTP having the same size, and moreover it can be elaborated in order to make it optimal (up to a poly-logarithmic factor) both in space and query time for the special case in which T=V(G). Our FTP improves over previous constructions when |T|=O(sqrt{|S|n}) (up to inverse poly-logarithmic factors). (3) Routing and Labeling Schemes: For the well-studied single-source setting, we present a novel routing scheme, that allows to route messages on pi_{G-e}(s,t) by using edge labels and routing tables of size tilde{O}(\sqrt{n}), and a header message of poly-logarithmic size. We also present a labeling scheme for the setting which is optimal in space up to constant factors.

The rational fair consensus problem can be informally defined as follows. Consider a network of n (selfish) rational agents, each of them initially supporting a color chosen from a finite set Σ. The goal is to design a protocol that leads the network to a stable monochromatic configuration (i.e. a consensus) such that the probability that the winning color is c is equal to the fraction of the agents that initially support c, for any c ∈ Σ. Furthermore, this fairness property must be guaranteed (with high probability) even in presence of any fixed coalition of rational agents that may deviate from the protocol in order to increase the winning probability of their supported colors. A protocol having this property, in presence of coalitions of size at most t, is said to be a whp - t-strong equilibrium. We investigate, for the first time, the rational fair consensus problem in the GOSSIP communication model where, at every round, every agent can actively contact at most one neighbor via a push/pull operation. We provide a randomized GOSSIP protocol that, starting from any initial color configuration of the complete graph, achieves rational fair consensus within O(log n) rounds using messages of O(log2n) size, w.h.p. More in details, we prove that our protocol is a whp t-strong equilibrium for any t = o(n/ log n) and, moreover, it tolerates worst-case permanent faults provided that the number of non-faulty agents is Ω(n). As far as we know, our protocol is the first solution which avoids any all-to-all communication, thus resulting in o(n2) message complexity.

A tree ρ-spanner of a positively real-weighted n-vertex and m-edge undirected graph G is a spanning tree T of G which approximately preserves (i.e., up to a multiplicative stretch factor ρ) distances in G. Tree spanners with provably good stretch factors find applications in communication networks, distributed systems, and network design. However, finding an optimal or even a good tree spanner is a very hard computational task. Thus, if one has to face a transient edge failure in T, the overall effort that has to be afforded to rebuild a new tree spanner (i.e., computational costs, set-up of new links, updating of the routing tables, etc.) can be rather prohibitive. To circumvent this drawback, an effective alternative is that of associating with each tree edge a best possible (in terms of resulting stretch) swap edge -A well-established approach in the literature for several other tree topologies. Correspondingly, the problem of computing all the best swap edges of a tree spanner is a challenging algorithmic problem, since solving it efficiently means to exploit the structure of shortest paths not only in G, but also in all the scenarios in which an edge of T has failed. For this problem we provide a very efficient solution, running in O(n2log4n) time, which drastically improves (almost by a quadratic factor in n in dense graphs!) on the previous known best result.

The Undecided-State Dynamics is a well-known protocol that achieves Consensus in distributed systems formed by a set of n anonymous nodes interacting via a communication network. We consider this dynamics in the parallel PULL communication model on the complete graph for the binary case, i.e., when every node can either support one of two possible colors or stay in the undecided state. Previous work in this setting only considers initial color configurations with no undecided nodes and a large bias (i.e., Theta(n)) towards the majority color. A interesting open question here is whether this dynamics reaches consensus quickly, i.e. within a polylogarithmic number of rounds. In this paper we present an unconditional analysis of the Undecided-State Dynamics which answers to the above question in the affirmative. Our analysis shows that, starting from any initial configuration, the Undecided-State Dynamics reaches a monochromatic configuration within O(log^2 n) rounds, with high probability (w.h.p.). Moreover, we prove that if the initial configuration has bias Omega(sqrt(n log n)), then the dynamics converges toward the initial majority color within O(log n) round, w.h.p. At the heart of our approach there is a new analysis of the symmetry-breaking phase that the process must perform in order to escape from (almost-)unbiased configurations. Previous symmetry-breaking analysis of consensus dynamics essentially concern sequential communication models (such as Population Protocols) and/or symmetric updated rules (such as majority rules).

Let s denote a distinguished source vertex of a non-negatively real weighted and undirected graph G with n vertices and m edges. In this paper we present two efficient single-source approximate-distance sensitivity oracles, namely compact data structures which are able to quickly report an approximate (by a multiplicative stretch factor) distance from s to any node of G following the failure of any edge in G. More precisely, we first present a sensitivity oracle of size O(n) which is able to report 2-approximate distances from the source in O(1) time. Then, we further develop our construction by building, for any 0<epsilon<1, another sensitivity oracle having size O(n*1/epsilon*log(1/epsilon)), and is able to report a (1+epsilon)-approximate distance from s to any vertex of G in O(log(n)*1/epsilon*log(1/epsilon)) time. Thus, this latter oracle is essentially optimal as far as size and stretch are concerned, and it only asks for a logarithmic query time. Finally, our results are complemented with a space lower bound for the related class of single-source additively-stretched sensitivity oracles, which is helpful to realize the hardness of designing compact oracles of this type.

The resiliency of a network is its ability to remain effectively functioning also when any of its nodes or links fails. However, to reduce operational and set-up costs, a network should be small in size, and this conflicts with the requirement of being resilient. In this paper we address this trade-off for the prominent case of the broadcasting routing scheme, and we build efficient (i.e., sparse and fast) fault-tolerant approximate shortest-path trees, for both the edge and vertex single-failure case. In particular, for an n-vertex non-negatively weighted graph, and for any constant ε > 0, we design two structures of size O(nlogn/ε^2) which guarantee (1 + ε)-stretched paths from the selected source also in the presence of an edge/vertex failure. This favorably compares with the currently best known solutions, which are for the edge-failure case of size O(n) and stretch factor 3, and for the vertex-failure case of size O(n logn) and stretch factor 3. Moreover, we also focus on the unweighted case, and we prove that an ordinary (α,β)-spanner can be slightly augmented in order to build efficient fault-tolerant approximate breadth-first-search trees.

Network creation games have been extensively studied, both from economists and computer scientists, due to their versatility in modeling individual-based community formation processes, which in turn are the theoretical counterpart of several economics, social, and computational applications on the Internet. However, the generally adopted assumption is that players have a common and complete information about the ongoing network, which is quite unrealistic in practice. In this paper, we consider a more compelling scenario in which players have only limited information about the network they are embedded in. More precisely, we explore the game theoretic and computational implications of assuming that players have a view of the network restricted to their k-neighborhood, which is one of the most qualified ,local-knowledge models used in distributed computing. To this respect, we define a suitable equilibrium concept and we provide a comprehensive set of upper and lower bounds to the price of anarchy for the entire range of values of k.

Abstract In Stackelberg pricing a leader sets prices for items to maximize revenue from a follower purchasing a feasible subset of items. We consider computationally bounded followers who cannot optimize exactly over the range of all feasible subsets, but who apply publicly known algorithms to determine the items to purchase. This corresponds to general multidimensional pricing when customers cannot optimize their valuation functions efficiently but still aim to act rationally to the best of their ability. We consider two versions of this novel type of pricing problem. In the MIn‐KNAPSACK variant items are weighted objects and the follower seeks to purchase a min‐cost selection of objects of some bounded weight. When he uses a greedy 2‐approximation algorithm, we provide a polynomial‐time (2+ε) ‐approximation algorithm for the leader's revenue maximization problem based on so‐called near‐uniform price assignments. We also prove the problem to be strongly NP‐hard. In the SET‐COVER variant items are subsets of some ground set which the follower seeks to cover. When he uses a standard primal‐dual approach, we prove that exact revenue maximization is possible in polynomial time when elements have frequency 2 (VERTEX‐COVER variant). This stands in sharp contrast to APX‐hardness for the problem with elements of frequency 3. © 2011 Wiley Periodicals, Inc. NETWORKS, 2012

Let G=(V,E) be a graph modeling a network where each edge is owned by a selfish agent, which establishes the cost for using her edge by pursuing only her personal utility. In such a setting, several classic network optimization problems, like for instance many graph traversal problems, asks for solutions in which an edge of G can be used several times. In game-theoretic terms, these problems are known as one-parameter problems, but with a peculiarity: the workload of each agent is a natural number. In this paper we refine the classic notion of monotonicity of an algorithm so as to exactly capture this property, and we then provide a general technique to efficiently develop truthful mechanisms for this family of problems.

Abstract Let a communication network be modeled by an undirected graph $G=(V,E)$ of n nodes and m edges, and assume that edges are controlled by selfish agents, which privately hold the length of each owned edge. In this paper we analyze the problem of designing a truthful mechanism for computing one of the most popular network topologies, i.e. the single‐source shortest paths tree. More precisely, we study several realistic scenarios, in which each agent can own either a single edge or multiple edges of G. In particular, for the single‐edge scenario, we show that in the utilitarian case the problem can be efficiently solved in $O(mn \log{}\alpha(m,n))$ time, while in a meaningful non‐utilitarian case, namely that in which agents' valuation functions depend only on the edge lengths, it can be solved in $O(m + n \log n)$ time. On the other hand, for the multiple‐edge scenario, in the utilitarian case we show an $O(mn+n^2 \log n)$ time truthful mechanism, while in the same non‐utilitarian case we provide an n‐approximate truthful mechanism which can be implemented in $O(m n \,\alpha(m,n))$ time. We also show that in the special case in which, for every agent, the owned edges are all incident to the same node, then this latter mechanism has an almost optimal $O(m\,\alpha(m,n))$ runtime. Copyright © 2007 John Wiley & Sons, Ltd.