Search

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\c{c}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., Comment: ISAAC 2024

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. We introduce and provide an in-depth analysis of a dynamic, buffered version of the well-known $k$-MinHash sketch. This buffered version better manages critical update operations thus significantly reducing the number of times the sketch needs to be rebuilt from scratch using expensive recovery queries. We prove that the buffered $k$-MinHash uses $O(k \log |U|)$ memory words per subset and that its amortized update time per insertion/deletion is $O(k \log |U|)$ with high probability. Moreover, our data structure can return the $k$-MinHash signature of any subset in $O(k)$ time, and this signature is exactly the same signature that would be computed from scratch (and thus the quality of the signature is the same as the one guaranteed by the static $k$-MinHash). Analytical and experimental comparisons with the other, state-of-the-art global solutions for this problem given in [Bury et al.,WSDM'18] show that the buffered $k$-MinHash turns out to be competitive in a wide and relevant range of the online input parameters.

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 the \emph{$k$-Diameter-Optimally Augmenting Tree Problem} we are given a tree $T$ of $n$ vertices as input. The tree is embedded in an unknown \emph{metric} space and we have unlimited access to an oracle that, given two distinct vertices $u$ and $v$ of $T$, can answer queries reporting the cost of the edge $(u,v)$ in constant time. We want to augment $T$ with $k$ shortcuts in order to minimize the diameter of the resulting graph. For $k=1$, $O(n \log n)$ time algorithms are known both for paths [Wang, CG 2018] and trees [Bil\`o, TCS 2022]. In this paper we investigate the case of multiple shortcuts. We show that no algorithm that performs $o(n^2)$ queries can provide a better than $10/9$-approximate solution for trees for $k\geq 3$. For any constant $\varepsilon > 0$, we instead design a linear-time $(1+\varepsilon)$-approximation algorithm for paths and $k = o(\sqrt{\log n})$, thus establishing a dichotomy between paths and trees for $k\geq 3$. We achieve the claimed running time by designing an ad-hoc data structure, which also serves as a key component to provide a linear-time $4$-approximation algorithm for trees, and to compute the diameter of graphs with $n + k - 1$ edges in time $O(n k \log n)$ even for non-metric graphs. Our data structure and the latter result are of independent interest., Comment: 22 pages, 6 figures, WADS 2023

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 $\alpha$-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 $\alpha$. 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 $\Omega(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 $\Omega(n^2)$ edges. We extend our analysis to prove an upper bound of $\tilde{O}(n^2/\beta)$ on the size of any temporal $\beta$-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., Comment: 25 pages, 9 figures

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., Comment: 22 pages, 4 figures, full version of the paper accepted at ISAAC 2021

Let $G$ be a directed graph with $n$ vertices, $m$ edges, and non-negative edge costs. Given $G$, a fixed source vertex $s$, and a positive integer $p$, we consider the problem of computing, for each vertex $t\neq s$, $p$ edge-disjoint paths of minimum total cost from $s$ to $t$ in $G$. Suurballe and Tarjan~[Networks, 1984] solved the above problem for $p=2$ by designing a $O(m+n\log n)$ time algorithm which also computes a sparse \emph{single-source $2$-multipath preserver}, i.e., a subgraph containing $2$ edge-disjoint paths of minimum total cost from $s$ to every other vertex of $G$. The case $p \geq 3$ was left as an open problem. We study the general problem ($p\geq 2$) and prove that any graph admits a sparse single-source $p$-multipath preserver with $p(n-1)$ edges. This size is optimal since the in-degree of each non-root vertex $v$ must be at least $p$. Moreover, we design an algorithm that requires $O(pn^2 (p + \log n))$ time to compute both $p$ edge-disjoint paths of minimum total cost from the source to all other vertices and an optimal-size single-source $p$-multipath preserver. The running time of our algorithm outperforms that of a natural approach that solves $n-1$ single-pair instances using the well-known \emph{successive shortest paths} algorithm by a factor of $\Theta(\frac{m}{np})$ and is asymptotically near optimal if $p=O(1)$ and $m=\Theta(n^2)$. Our results extend naturally to the case of $p$ vertex-disjoint paths., Comment: 18 pages, 7 figures

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\k{a}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 $\frac{3+\sqrt{5}}{2} < 2.62$ for $x=1+\frac{1}{\sqrt{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)., Comment: 17 pages, 5 figures, FUN 2020

We investigate strong Nash equilibria in the \emph{max $k$-cut game}, where we are given an undirected edge-weighted graph together with a set $\{1,\ldots, k\}$ of $k$ colors. Nodes represent players and edges capture their mutual interests. The strategy set of each player $v$ consists of the $k$ colors. When players select a color they induce a $k$-coloring or simply a coloring. Given a coloring, the \emph{utility} (or \emph{payoff}) of a player $u$ is the sum of the weights of the edges $\{u,v\}$ incident to $u$, such that the color chosen by $u$ is different from the one chosen by $v$. Such games form some of the basic payoff structures in game theory, model lots of real-world scenarios with selfish agents and extend or are related to several fundamental classes of games. Very little is known about the existence of strong equilibria in max $k$-cut games. In this paper we make some steps forward in the comprehension of it. We first show that improving deviations performed by minimal coalitions can cycle, and thus answering negatively the open problem proposed in \cite{DBLP:conf/tamc/GourvesM10}. Next, we turn our attention to unweighted graphs. We first show that any optimal coloring is a 5-SE in this case. Then, we introduce $x$-local strong equilibria, namely colorings that are resilient to deviations by coalitions such that the maximum distance between every pair of nodes in the coalition is at most $x$. We prove that $1$-local strong equilibria always exist. Finally, we show the existence of strong Nash equilibria in several interesting specific scenarios., Comment: A preliminary version of this paper will appear in the proceedings of the 45th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM'19)

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 $\Omega(\epsilon^{-2} n)$ lower bound on the number of rounds needed for Broadcast is proved by Boczkowski et al. [PLOS Comp. Bio. 2018] in one such model (noisy uniform PULL, where $\epsilon$ is a parameter that measures the amount of noise). In such model, we prove a new $\Theta(\epsilon^{-2} n \log n)$ bound for Broadcast and a $\Theta(\epsilon^{-2} \log n)$ bound for binary Consensus, thus establishing an exponential gap between the number of rounds necessary for Consensus versus Broadcast.

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., Comment: 17 pages, 4 figures, ISAAC 2017

Computing \emph{all best swap edges} (ABSE) of a spanning tree $T$ of a given $n$-vertex and $m$-edge undirected and weighted graph $G$ means to select, for each edge $e$ of $T$, a corresponding non-tree edge $f$, in such a way that the tree obtained by replacing $e$ with $f$ enjoys some optimality criterion (which is naturally defined according to some objective function originally addressed by $T$). Solving efficiently an ABSE problem is by now a classic algorithmic issue, since it conveys a very successful way of coping with a (transient) \emph{edge failure} in tree-based communication networks: just replace the failing edge with its respective swap edge, so as that the connectivity is promptly reestablished by minimizing the rerouting and set-up costs. In this paper, we solve the ABSE problem for the case in which $T$ is a \emph{single-source shortest-path tree} of $G$, and our two selected swap criteria aim to minimize either the \emph{maximum} or the \emph{average stretch} in the swap tree of all the paths emanating from the source. Having these criteria in mind, the obtained structures can then be reviewed as \emph{edge-fault-tolerant single-source spanners}. For them, we propose two efficient algorithms running in $O(m n +n^2 \log n)$ and $O(m n \log \alpha(m,n))$ time, respectively, and we show that the guaranteed (either maximum or average, respectively) stretch factor is equal to 3, and this is tight. Moreover, for the maximum stretch, we also propose an almost linear $O(m \log \alpha(m,n))$ time algorithm computing a set of \emph{good} swap edges, each of which will guarantee a relative approximation factor on the maximum stretch of $3/2$ (tight) as opposed to that provided by the corresponding BSE. Surprisingly, no previous results were known for these two very natural swap problems., Comment: 15 pages, 4 figures, SIROCCO 2017

The \emph{Undecided-State Dynamics} is a well-known protocol for distributed consensus. We analyze it in the parallel \pull\ communication model on the complete graph for the \emph{binary} case (every node can either support one of \emph{two} possible colors, or be in the undecided state). An interesting open question is whether this dynamics \emph{always} (i.e., starting from an arbitrary initial configuration) reaches consensus \emph{quickly} (i.e., within a polylogarithmic number of rounds) in a complete graph with $n$ nodes. Previous work in this setting only considers initial color configurations with no undecided nodes and a large \emph{bias} (i.e., $\Theta(n)$) towards the majority color. In this paper we present an \textit{unconditional} analysis of the Undecided-State Dynamics that answers to the above question in the affirmative. We prove that, starting from \textit{any} initial configuration, the process reaches a monochromatic configuration within $O(\log n)$ rounds, with high probability. This bound turns out to be tight. Our analysis also shows that, if the initial configuration has bias $\Omega(\sqrt{n\log n})$, then the dynamics converges toward the initial majority color, with high probability.

The \emph{rational fair consensus problem} can be informally defined as follows. Consider a network of $n$ (selfish) \emph{rational agents}, each of them initially supporting a \emph{color} chosen from a finite set $ \Sigma$. 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 \in \Sigma$. Furthermore, this fairness property must be guaranteed (with high probability) even in presence of any fixed \emph{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 \emph{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 \emph{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(\log^2n)$ 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 $\Omega(n)$. As far as we know, our protocol is the first solution which avoids any all-to-all communication, thus resulting in $o(n^2)$ message complexity., Comment: Accepted at IPDPS'17

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 \emph{single-source approximate-distance sensitivity oracles}, namely \emph{compact} data structures which are able to \emph{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\left(n\cdot \frac{1}{\epsilon} \log \frac{1}{\epsilon}\right)$, and which is able to report a $(1+\epsilon)$-approximate distance from $s$ to any vertex of $G$ in $O\left(\log n\cdot \frac{1}{\epsilon} \log \frac{1}{\epsilon}\right)$ 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 \emph{additively-stretched} sensitivity oracles, which is helpful to realize the hardness of designing compact oracles of this type., Comment: 19 pages, 3 figures. ESA 2016

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. In their several variants, these games model the tension of a player between her two antagonistic goals: to be as close as possible to the other players, and to activate a cheapest possible set of links. However, the generally adopted assumption is that players have a \emph{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 complete knowledge of the network structure only up to a given radius $k$, which is one of the most qualified \emph{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$, and for the two classic variants of the game, namely those in which a player's cost --- besides the activation cost of the owned links --- depends on the maximum/sum of all the distances to the other nodes in the network, respectively. These bounds are finally assessed through an extensive set of experiments., Comment: 26 pages, 10 figures, ACM Transactions on parallel Computing. A preliminary version appeared in the proceedings of SPAA 2014

Despite its long history, the classical game of peg solitaire continues to attract the attention of the scientific community. In this paper, we consider two problems with an algorithmic flavour which are related with this game, namely Solitaire-Reachability and Solitaire-Army. In the first one, we show that deciding whether there is a sequence of jumps which allows a given initial configuration of pegs to reach a target position is NP-complete. Regarding Solitaire-Army, the aim is to successfully deploy an army of pegs in a given region of the board in order to reach a target position. By solving an auxiliary problem with relaxed constraints, we are able to answer some open questions raised by Cs\'ak\'any and Juh\'asz (Mathematics Magazine, 2000). To appreciate the combinatorial beauty of our solutions, we recommend to visit the gallery of animations provided at http://solitairearmy.isnphard.com., Comment: Conference version

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 \emph{f-edge-fault-tolerant} ($f$-EFT) $\sigma${\em -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 at most by a factor of $\sigma$. To this respect, we provide an algorithm that efficiently computes an $f$-EFT $(2|F|+1)$-ASPT of size $O(f n)$. Our structure improves on a previous related construction designed for \emph{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 \emph{single-source distance oracle} (SSDO), that can be built in $\widetilde{O}(f m)$ time, has size $O(fn \log^2 n)$, and is able to report, after the failure of the edge set $F$, in $O(|F|^2 \log^2 n)$ time a $(2|F|+1)$-approximate distance from the source to any node, and a corresponding approximate path in the same amount of time plus the path's size. Such an oracle is obtained by handling another fundamental problem, namely that of updating a \emph{minimum spanning forest} (MSF) of $G$ after that a \emph{batch} of $k$ simultaneous edge modifications (i.e., edge insertions, deletions and weight changes) is performed. For this problem, we build in $O(m \log^3 n)$ time a \emph{sensitivity} 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. [...], Comment: 16 pages, 4 figures

Let $G$ be an unweighted $n$-node undirected graph. A \emph{$\beta$-additive spanner} of $G$ is a spanning subgraph $H$ of $G$ such that distances in $H$ are stretched at most by an additive term $\beta$ w.r.t. the corresponding distances in $G$. A natural research goal related with spanners is that of designing \emph{sparse} spanners with \emph{low} stretch. In this paper, we focus on \emph{fault-tolerant} additive spanners, namely additive spanners which are able to preserve their additive stretch even when one edge fails. We are able to improve all known such spanners, in terms of either sparsity or stretch. In particular, we consider the sparsest known spanners with stretch $6$, $28$, and $38$, and reduce the stretch to $4$, $10$, and $14$, respectively (while keeping the same sparsity). Our results are based on two different constructions. On one hand, we show how to augment (by adding a \emph{small} number of edges) a fault-tolerant additive \emph{sourcewise spanner} (that approximately preserves distances only from a given set of source nodes) into one such spanner that preserves all pairwise distances. On the other hand, we show how to augment some known fault-tolerant additive spanners, based on clustering techniques. This way we decrease the additive stretch without any asymptotic increase in their size. We also obtain improved fault-tolerant additive spanners for the case of one vertex failure, and for the case of $f$ edge failures., Comment: 17 pages, 4 figures, ESA 2015

Let be given a graph $G=(V,E)$ whose edge set is partitioned into a set $R$ of \emph{red} edges and a set $B$ of \emph{blue} edges, and assume that red edges are weighted and form a spanning tree of $G$. Then, the \emph{Stackelberg Minimum Spanning Tree} (\stack) 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. \stack \ is known to be \apx-hard already when the number of distinct red weights is 2. In this paper we analyze some meaningful specializations and generalizations of \stack, which shed some more light on the computational complexity of the problem. More precisely, we first show that if $G$ is restricted to be \emph{complete}, then the following holds: (i) if there are only 2 distinct red 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 + \epsilon$, for any $\epsilon > 0$. Afterwards, we define a natural extension of \stack, namely that in which blue edges have a non-negative \emph{activation cost} associated, and it is given a global \emph{activation budget} that must not be exceeded when pricing blue edges. 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 $(2h+\epsilon)$-approximation algorithm, for any $\epsilon > 0$., Comment: 22 pages, 7 figures

In this paper we study a generalization of the classic \emph{network creation game} in the scenario in which the $n$ players sit on a given arbitrary \emph{host graph}, which constrains the set of edges a player can activate at a cost of $\alpha \geq 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 its \emph{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 several basic classes of host graphs. More precisely, we first exhibit a lower bound of $\Omega (\sqrt{ n / (1+\alpha)})$ for any $\alpha = o(n)$. Notice that this implies a counter-intuitive lower bound of $\Omega(\sqrt{n})$ for very small values of $\alpha$ (i.e., edges can be activated almost for free). Then, we show that when the host graph is restricted to be either $k$-regular (for any constant $k \geq 3$), or a 2-dimensional grid, the PoA is still $\Omega(1+\min\{\alpha, \frac{n}{\alpha}\})$, which is proven to be tight for $\alpha=\Omega(\sqrt{n})$. On the positive side, if $\alpha \geq n$, we show the PoA is $O(1)$. 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 $\alpha$., Comment: 17 pages, 4 figures

The resiliency of a network is its ability to remain \emph{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 {\em broadcasting} routing scheme, and we build efficient (i.e., sparse and fast) \emph{fault-tolerant approximate shortest-path trees}, for both the edge and vertex \emph{single-failure} case. In particular, for an $n$-vertex non-negatively weighted graph, and for any constant $\varepsilon >0$, we design two structures of size $O(\frac{n \log n}{\varepsilon^2})$ which guarantee $(1+\varepsilon)$-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 \log n)$ and stretch factor 3. Moreover, we also focus on the unweighted case, and we prove that an ordinary $(\alpha,\beta)$-spanner can be slightly augmented in order to build efficient fault-tolerant approximate \emph{breadth-first-search trees}., Comment: 20 pages, 4 figures

The twentieth century has seen the rise of a new type of video games targeted at a mass audience of "casual" gamers. Many of these games require the player to swap items in order to form matches of three and are collectively known as \emph{tile-matching match-three games}. Among these, the most influential one is arguably \emph{Bejeweled} in which the matched items (gems) pop and the above gems fall in their place. Bejeweled has been ported to many different platforms and influenced an incredible number of similar games. Very recently one of them, named \emph{Candy Crush Saga} enjoyed a huge popularity and quickly went viral on social networks. We generalize this kind of games by only parameterizing the size of the board, while all the other elements (such as the rules or the number of gems) remain unchanged. Then, we prove that answering many natural questions regarding such games is actually \NP-Hard. These questions include determining if the player can reach a certain score, play for a certain number of turns, and others. We also \href{http://candycrush.isnphard.com}{provide} a playable web-based implementation of our reduction., Comment: 21 pages, 12 figures

A network creation game simulates a decentralized and non-cooperative building of a communication network. Informally, there are $n$ players sitting on the network nodes, which attempt to establish a reciprocal communication by activating, incurring a certain cost, any of their incident links. The goal of each player is to have all the other nodes as close as possible in the resulting network, while buying as few links as possible. According to this intuition, any model of the game must then appropriately address a balance between these two conflicting objectives. Motivated by the fact that a player might have a strong requirement about its centrality in the network, in this paper we introduce a new setting in which if a player maintains its (either maximum or average) distance to the other nodes within a given associated bound, then its cost is simply equal to the number of activated edges, otherwise its cost is unbounded. We study the problem of understanding the structure of associated pure Nash equilibria of the resulting games, that we call MaxBD and SumBD, respectively. For both games, we show that computing the best response of a player is an NP-hard problem. Next, we show that when distance bounds associated with players are non-uniform, then equilibria can be arbitrarily bad. On the other hand, for MaxBD, we show that when nodes have a uniform bound $R$ on the maximum distance, then the Price of Anarchy (PoA) is lower and upper bounded by 2 and $O(n^{\frac{1}{\lfloor\log_3 R\rfloor+1}})$ for $R \geq 3$, while for the interesting case R=2, we are able to prove that the PoA is $\Omega(\sqrt{n})$ and $O(\sqrt{n \log n})$. For the uniform SumBD we obtain similar (asymptotically) results, and moreover we show that the PoA becomes constant as soon as the bound on the average distance is $n^{\omega(\frac{1}{\sqrt{\log n}})}$., Comment: 17 pages, 2 figures