
The \emph{UndecidedState Dynamics} is a wellknown 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
UndecidedState 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.

A tree $\sigma$spanner of a positively realweighted $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, setup 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 wellestablished 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.

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 nontree 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 treebased 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 setup costs. In this
paper, we solve the ABSE problem for the case in which $T$ is a
\emph{singlesource shortestpath 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{edgefaulttolerant singlesource 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.

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 worstcase permanent faults provided that the number of nonfaulty
agents is $\Omega(n)$. As far as we know, our protocol is the first solution
which avoids any alltoall communication, thus resulting in $o(n^2)$ message
complexity.

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 setup costs, a network should be small in size, and this
conflicts with the requirement of being resilient. In this paper we address
this tradeoff for the prominent case of the {\em broadcasting} routing scheme,
and we build efficient (i.e., sparse and fast) \emph{faulttolerant approximate
shortestpath trees}, for both the edge and vertex \emph{singlefailure} case.
In particular, for an $n$vertex nonnegatively 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
edgefailure case of size $O(n)$ and stretch factor 3, and for the
vertexfailure 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
faulttolerant approximate \emph{breadthfirstsearch trees}.

Let $s$ denote a distinguished source vertex of a nonnegatively real
weighted and undirected graph $G$ with $n$ vertices and $m$ edges. In this
paper we present two efficient \emph{singlesource approximatedistance
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 2approximate 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
singlesource \emph{additivelystretched} sensitivity oracles, which is helpful
to realize the hardness of designing compact oracles of this type.

Network creation games have been extensively studied, both from economists
and computer scientists, due to their versatility in modeling individualbased
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 gametheoretic 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{localknowledge 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.

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 SolitaireReachability and SolitaireArmy. 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 NPcomplete. Regarding
SolitaireArmy, 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.

Let $G$ be an $n$node and $m$edge positively realweighted undirected
graph. For any given integer $f \ge 1$, we study the problem of designing a
sparse \emph{fedgefaulttolerant} ($f$EFT) $\sigma${\em approximate
singlesource shortestpath 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 $(2F+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{singlesource 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
$(2F+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. [...]

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{faulttolerant} 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 faulttolerant
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
faulttolerant additive spanners, based on clustering techniques. This way we
decrease the additive stretch without any asymptotic increase in their size. We
also obtain improved faulttolerant additive spanners for the case of one
vertex failure, and for the case of $f$ edge failures.

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 \apxhard 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 \apxhardness 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 nonnegative \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 rootleaf path contains at most $h$ edges,
then the problem admits a $(2h+\epsilon)$approximation algorithm, for any
$\epsilon > 0$.

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 counterintuitive 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
2dimensional 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)=n1+k$, with $k=O(1)$), we prove that the PoA is $O(1)$, for any
$\alpha$.

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{tilematching matchthree 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 \NPHard. 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 webbased
implementation of our reduction.

A network creation game simulates a decentralized and noncooperative
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 NPhard problem. Next, we show that when
distance bounds associated with players are nonuniform, 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}})}$.