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

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

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

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 .

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

We study the minimum Monitoring Edge Geodetic Set (MEG-Set) problem introduced in [Foucaud et al., CALDAM'23]: given a graph G, we say that an edge is monitored by a pair u,v of vertices if all shortest paths between u and v traverse e; the goal is to find a subset M of vertices of G such that each edge of G is monitored by at least one pair of vertices in M, and |M| is minimized. In this paper, we prove that all polynomial-time approximation algorithms for the minimum MEG-Set problem must have an approximation ratio of Ω(log n), unless 𝖯 = NP. To the best of our knowledge, this is the first non-constant inapproximability result known for this problem. We also strengthen the known NP-hardness of the problem on 2-apex graphs by showing that the same result holds for 1-apex graphs. This leaves open the question of determining whether the problem remains NP-hard on planar (i.e., 0-apex) graphs. On the positive side, we design an algorithm that computes good approximate solutions for hereditary graph classes that admit efficiently computable balanced separators of truly sublinear size. This immediately yields polynomial-time approximation algorithms achieving an approximation ratio of O(n^{1/4} √{log n}) on planar graphs, graphs with bounded genus, and k-apex graphs with k = O(n^{1/4}). On graphs with bounded treewidth, we obtain an approximation ratio of O(log^{3/2} n). This compares favorably with the best-known approximation algorithm for general graphs, which achieves an approximation ratio of O(√{n log n}) via a simple reduction to the Set Cover problem.

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

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.

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.

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.

Abstract Reoptimization is a setting in which we are given a good approximate solution of an optimization problem instance and a local modification that slightly changes the instance. The main goal is that of finding a good approximate solution of the modified instance. We investigate one of the most studied scenarios in reoptimization known as Steiner tree reoptimization. Steiner tree reoptimization is a collection of strongly $$\textsf {NP}$$ NP -hard optimization problems that are defined on top of the classical Steiner tree problem and for which several constant-factor approximation algorithms have been designed in the last decades. In this paper we improve upon all these results by developing a novel technique that allows us to design polynomial-time approximation schemes. Remarkably, prior to this paper, no approximation algorithm better than recomputing a solution from scratch was known for the elusive scenario in which the cost of a single edge decreases. Our results are best possible since none of the problems addressed in this paper admits a fully polynomial-time approximation scheme, unless $$\textsf {P}=\textsf {NP}$$ P = NP

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. Network creation games are a well-known approach for explaining and analyzing the structure, quality, and dynamics of real-world networks that evolved via the interaction of selfish agents without a central authority. In these games selfish agents corresponding to nodes in a network strategically buy incident edges to improve their centrality. However, past research on these games only considered the creation of networks with unit-weight edges. In practice, e.g., when constructing a fiber-optic network, the choice of which nodes to connect and also the induced price for a link crucially depend on the distance between the involved nodes, and such settings can be modeled via edge-weighted graphs. We incorporate arbitrary edge weights by generalizing the well-known model by Fabrikant et al. [ Proceedings of PODC ’03, ACM, 2003, pp. 347–351] to edge-weighted host graphs and focus on the geometric setting where the weights are induced by the distances in some metric space. In stark contrast to the state of the art for the unit-weight version, where the price of anarchy is conjectured to be constant and where resolving this is a major open problem, we prove a tight nonconstant bound on the price of anarchy for the metric version and a slightly weaker upper bound for the nonmetric case. Moreover, we analyze the existence of equilibria, the computational hardness, and the game dynamics for several natural metrics. The model we propose can be seen as the game-theoretic analogue of the classical network design problem. Thus, low-cost equilibria of our game correspond to decentralized and stable approximations of the optimum network design.

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.

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.

An f-edge fault-tolerant distance sensitive oracle (f-DSO) with stretch σ ≥ 1 is a data structure that preprocesses a given undirected, unweighted graph G with n vertices and m edges, and a positive integer f. When queried with a pair of vertices s, t and a set F of at most f edges, it returns a σ-approximation of the s-t-distance in G−F.

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.

We construct data structures for extremal and pairwise distances in directed graphs in the presence of transient edge failures. Henzinger et al. [ITCS 2017] initiated the study of fault-tolerant (sensitivity) oracles for the diameter and vertex eccentricities. We extend this with a special focus on space efficiency. We present several new data structures, among them the first fault-tolerant eccentricity oracle for dual failures in subcubic space. We further prove lower bounds that show limits to approximation vs. space and diameter vs. space trade-offs for fault-tolerant oracles. They highlight key differences between data structures for undirected and directed graphs. Initially, our oracles are randomized leaning on a sampling technique frequently used in sensitivity analysis. Building on the work of Alon, Chechik, and Cohen [ICALP 2019] as well as Karthik and Parter [SODA 2021], we develop a hierarchical framework to derandomize fault-tolerant data structures. We first apply it to our own diameter and eccentricity oracles and then show its versatility by derandomizing algorithms from the literature: the distance sensitivity oracle of Ren [JCSS 2022] and the Single-Source Replacement Path algorithm of Chechik and Magen [ICALP 2020]. This way, we obtain the first deterministic distance sensitivity oracle with subcubic preprocessing time.

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.

The study of fault-tolerant data structures for various network design problems is a prominent area of research in computer science. Likewise, the study of NP-Complete problems lies at the heart of computer science with numerous results in algorithms and complexity. In this paper we raise the question of computing fault tolerant solutions to NP-Complete problems; that is computing a solution that can survive the "failure" of a few constituent elements. This notion has appeared in a variety of theoretical and practical settings such as estimating network reliability, kernelization (aka instance compression), approximation algorithms and so on. In this paper, we seek to highlight these questions for further research. As a concrete example, we study the fault-tolerant version of the classical Feedback Vertex Set (FVS) problem, that we call Fault Tolerant Feedback Vertex Set (FT-FVS). Recall that, in FVS the input is a graph $G$ and the objective is to compute a minimum subset of vertices $S$ such that $G-S$ is a forest. In FT-FVS, the objective is to compute a minimum subset $S$ of vertices such that $G - (S \setminus \{v\})$ is a forest for any $v \in V(G)$. Here the vertex $v$ denotes a single vertex fault. We show that this problem is NP-Complete, and then present a constant factor approximation algorithm as well as an FPT-algorithm parameterized by the solution size. We believe that the question of computing fault tolerant solutions to various NP-Complete problems is an interesting direction for future research.

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.

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.

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.

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.

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

Understanding real-world networks is a core research endeavor within the last two decades. Network Creation Games are a promising approach for this from a game-theoretic 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. In our model edges are formed 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 mimic 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.

Given a graph with a source vertex $s$, the Single Source Replacement Paths (SSRP) problem is to compute, for every vertex $t$ and edge $e$, the length $d(s,t,e)$ of a shortest path from $s$ to $t$ that avoids $e$. A Single-Source Distance Sensitivity Oracle (Single-Source DSO) is a data structure that answers queries of the form $(t,e)$ by returning the distance $d(s,t,e)$. We show how to deterministically compress the output of the SSRP problem on $n$-vertex, $m$-edge graphs with integer edge weights in the range $[1,M]$ into a Single-Source DSO of size $O(M^{1/2}n^{3/2})$ with query time $\widetilde{O}(1)$. The space requirement is optimal (up to the word size) and our techniques can also handle vertex failures. Chechik and Cohen [SODA 2019] presented a combinatorial, randomized $\widetilde{O}(m\sqrt{n}+n^2)$ time SSRP algorithm for undirected and unweighted graphs. Grandoni and Vassilevska Williams [FOCS 2012, TALG 2020] gave an algebraic, randomized $\widetilde{O}(Mn^ω)$ time SSRP algorithm for graphs with integer edge weights in the range $[1,M]$, where $ω<2.373$ is the matrix multiplication exponent. We derandomize both algorithms for undirected graphs in the same asymptotic running time and apply our compression to obtain deterministic Single-Source DSOs. The $\widetilde{O}(m\sqrt{n}+n^2)$ and $\widetilde{O}(Mn^ω)$ preprocessing times are polynomial improvements over previous $o(n^2)$-space oracles. On sparse graphs with $m=O(n^{5/4-\varepsilon}/M^{7/4})$ edges, for any constant $\varepsilon > 0$, we reduce the preprocessing to randomized $\widetilde{O}(M^{7/8}m^{1/2}n^{11/8})=O(n^{2-\varepsilon/2})$ time. This is the first truly subquadratic time algorithm for building Single-Source DSOs on sparse graphs.

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.

How do rational agents self-organize when trying to connect to a common target? We study this question with a simple tree formation game which is related to the well-known fair single-source connection game by Anshelevich et al. (FOCS'04) and selfish spanning tree games by Gourvès and Monnot (WINE'08). In our game agents correspond to nodes in a network that activate a single outgoing edge to connect to the common target node (possibly via other nodes). Agents pay for their path to the common target, and edge costs are shared fairly among all agents using an edge. The main novelty of our model is dynamic edge costs that depend on the in-degree of the respective endpoint. This reflects that connecting to popular nodes that have increased internal coordination costs is more expensive since they can charge higher prices for their routing service. In contrast to related models, we show that equilibria are not guaranteed to exist, but we prove the existence for infinitely many numbers of agents. Moreover, we analyze the structure of equilibrium trees and employ these insights to prove a constant upper bound on the Price of Anarchy as well as non-trivial lower bounds on both the Price of Anarchy and the Price of Stability. We also show that in comparison with the social optimum tree the overall cost of an equilibrium tree is more fairly shared among the agents. Thus, we prove that self-organization of rational agents yields on average only slightly higher cost per agent compared to the centralized optimum, and at the same time, it induces a more fair cost distribution. Moreover, equilibrium trees achieve a beneficial trade-off between a low height and low maximum degree, and hence these trees might be of independent interest from a combinatorics point-of-view. We conclude with a discussion of promising extensions of our model.

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.

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.

Network Creation Games are a well-known approach for explaining and analyzing the structure, quality and dynamics of real-world networks like the Internet and other infrastructure networks which evolved via the interaction of selfish agents without a central authority. In these games selfish agents which correspond to nodes in a network strategically buy incident edges to improve their centrality. However, past research on these games has only considered the creation of networks with unit-weight edges. In practice, e.g. when constructing a fiber-optic network, the choice of which nodes to connect and also the induced price for a link crucially depends on the distance between the involved nodes and such settings can be modeled via edge-weighted graphs. We incorporate arbitrary edge weights by generalizing the well-known model by Fabrikant et al. [PODC'03] to edge-weighted host graphs and focus on the geometric setting where the weights are induced by the distances in some metric space. In stark contrast to the state-of-the-art for the unit-weight version, where the Price of Anarchy is conjectured to be constant and where resolving this is a major open problem, we prove a tight non-constant bound on the Price of Anarchy for the metric version and a slightly weaker upper bound for the non-metric case. Moreover, we analyze the existence of equilibria, the computational hardness and the game dynamics for several natural metrics. The model we propose can be seen as the game-theoretic analogue of a variant of the classical Network Design Problem. Thus, low-cost equilibria of our game correspond to decentralized and stable approximations of the optimum network design.

Given a 2-edge connected, unweighted, and undirected graph G with n vertices and m edges, a sigma-tree spanner is a spanning tree T of G in which the ratio between the distance in T of any pair of vertices and the corresponding distance in G is upper bounded by sigma. The minimum value of sigma for which T is a sigma-tree spanner of G is also called the stretch factor of T. We address the fault-tolerant scenario in which each edge e of a given tree spanner may temporarily fail and has to be replaced by a best swap edge, i.e. an edge that reconnects T-e at a minimum stretch factor. More precisely, we design an O(n^2) time and space algorithm that computes a best swap edge of every tree edge. Previously, an O(n^2 log^4 n) time and O(n^2+m log^2n) space algorithm was known for edge-weighted graphs [Bilò et al., ISAAC 2017]. Even if our improvements on both the time and space complexities are of a polylogarithmic factor, we stress the fact that the design of a o(n^2) time and space algorithm would be considered a breakthrough.

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.

Selfish Network Creation focuses on modeling real world networks from a game-theoretic point of view. One of the classic models by Fabrikant et al.[PODC'03] is the network creation game, where agents correspond to nodes in a network which buy incident edges for the price of alpha per edge to minimize their total distance to all other nodes. The model is well-studied but still has intriguing open problems. The most famous conjectures state that the price of anarchy is constant for all alpha and that for alpha >= n all equilibrium networks are trees. We introduce a novel technique for analyzing stable networks for high edge-price alpha and employ it to improve on the best known bounds for both conjectures. In particular we show that for alpha > 4n-13 all equilibrium networks must be trees, which implies a constant price of anarchy for this range of alpha. Moreover, we also improve the constant upper bound on the price of anarchy for equilibrium trees.

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.

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.

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.