For an integer k ≥ 1 , the objective of k -Geodesic Center is to find a set C of k isometric paths such that the maximum distance between any vertex v and C is minimised. Introduced by Gromov, δ-hyperbolicity measures how treelike a graph is from a metric point of view. Our main contribution in this paper is to provide an additive O ( δ ) -approximation algorithm for k -Geodesic Center on δ -hyperbolic graphs. On the way, we define a coarse version of the pairing property introduced by Gerstel & Zaks (Networks, 1994) and show it holds for δ -hyperbolic graphs. This result allows to reduce the k -Geodesic Center problem to its rooted counterpart, a main idea behind our algorithm. We also adapt a technique of Dragan & Leitert, (TCS, 2017) to show that for every k ≥ 1 , k - Geodesic Center is NP-hard even on partial grids.

A set $S$ of isometric paths of a graph $G$ is ``$v$-rooted'', where $v$ is a vertex of $G$, if $v$ is one of the endpoints of all the isometric paths in $S$. The isometric path complexity of a graph $G$, denoted by $ipco{G}$, is the minimum integer $k$ such that there exists a vertex $v\in V(G)$ satisfying the following property: the vertices of any single isometric path $P$ of $G$ can be covered by $k$ many $v$-rooted isometric paths. First, we provide an $O(n^2 m)$-time algorithm to compute the isometric path complexity of a graph with $n$ vertices and $m$ edges. Then we show that the isometric path complexity remains bounded for graphs in three seemingly unrelated graph classes, namely, hyperbolic graphs, (theta, prism, pyramid)-free graphs, and outerstring graphs. There is a direct algorithmic consequence of having small isometric path complexity. Specifically, we show that if the isometric path complexity of a graph $G$ is bounded by a constant, then there exists a polynomial-time constant-factor approximation algorithm for ISOMETRIC PATH COVER, whose objective is to cover all vertices of a graph with a minimum number of isometric paths. This applies to all the above graph classes.

Abstract In this article, we consider the problem of optimizing the connectivity of a landscape under a budget constraint, by improving habitat areas and ecological corridors between them. We model this problem as a discrete optimization problem over graphs, in which vertices represent the habitat areas and arcs represent the connections between them. We propose a new flow‐based integer linear programming formulation that improves upon the existing models for this problem. By following an approach similar to Catanzaro et al. for the robust shortest path problem, we design an improved preprocessing algorithm that reduces the size of the graphs on which we compute generalized flows. Computational experiments show the benefits of both contributions, by enabling to solve instances of the problem larger than previous models. These experiments also show that several versions of greedy algorithms perform relatively well in practice, while returning arbitrarily bad solutions in the worst case.

Abstract. One of the open problems in machine learning is whether any set-family of VC-dimension [Formula: see text] admits a sample compression scheme of size [Formula: see text]. In this paper, we study this problem for balls in graphs. For a ball [Formula: see text] of a graph [Formula: see text], a realizable sample for [Formula: see text] is a signed subset [Formula: see text] of [Formula: see text] such that [Formula: see text] contains [Formula: see text] and is disjoint from [Formula: see text]. A proper sample compression scheme of size [Formula: see text] consists of a compressor and a reconstructor. The compressor maps any realizable sample [Formula: see text] to a subsample [Formula: see text] of size at most [Formula: see text]. The reconstructor maps each such subsample [Formula: see text] to a ball [Formula: see text] of [Formula: see text] such that [Formula: see text] includes [Formula: see text] and is disjoint from [Formula: see text]. For balls of arbitrary radius [Formula: see text], we design proper labeled sample compression schemes of size 2 for trees, of size 3 for cycles, of size 4 for interval graphs, of size 6 for trees of cycles, and of size 22 for cube-free median graphs. For balls of a given radius, we design proper labeled sample compression schemes of size 2 for trees and of size 4 for interval graphs. We also design approximate sample compression schemes of size 2 for balls of [Formula: see text]-hyperbolic graphs.

One of the open problems in machine learning is whether any set-family of VC-dimension d admits a sample compression scheme of size O(d). In this paper, we study this problem for balls in graphs. For balls of arbitrary radius r, we design proper sample compression schemes of size 4 for interval graphs, of size 6 for trees of cycles, and of size 22 for cube-free median graphs. We also design approximate sample compression schemes of size 2 for balls of δ-hyperbolic graphs.

The median of a set of vertices P of a graph G is the set of all vertices x of G minimizing the sum of distances from x to all vertices of P. In this paper, we present a linear time algorithm to compute medians in median graphs, improving over the existing quadratic time algorithm. We also present a linear time algorithm to compute medians in the 𝓁₁-cube complexes associated with median graphs. Median graphs constitute the principal class of graphs investigated in metric graph theory and have a rich geometric and combinatorial structure. Our algorithm is based on the majority rule characterization of medians in median graphs and on a fast computation of parallelism classes of edges (Θ-classes or hyperplanes) via Lexicographic Breadth First Search (LexBFS). To prove the correctness of our algorithm, we show that any LexBFS ordering of the vertices of G satisfies the following fellow traveler property of independent interest: the parents of any two adjacent vertices of G are also adjacent.

In this paper, we study Gromov hyperbolicity and related parameters, that represent how close (locally) a metric space is to a tree from a metric point of view. The study of Gromov hyperbolicity for geodesic metric spaces can be reduced to the study of graph hyperbolicity. Our main contribution in this note is a new characterization of hyperbolicity for graphs (and for complete geodesic metric spaces). This characterization has algorithmic implications in the field of large-scale network analysis, which was one of our initial motivations. A sharp estimate of graph hyperbolicity is useful, {e.g.}, in embedding an undirected graph into hyperbolic space with minimum distortion [Verbeek and Suri, SoCG'14]. The hyperbolicity of a graph can be computed in polynomial-time, however it is unlikely that it can be done in subcubic time. This makes this parameter difficult to compute or to approximate on large graphs. Using our new characterization of graph hyperbolicity, we provide a simple factor 8 approximation algorithm for computing the hyperbolicity of an n-vertex graph G=(V,E) in optimal time O(n^2) (assuming that the input is the distance matrix of the graph). This algorithm leads to constant factor approximations of other graph-parameters related to hyperbolicity (thinness, slimness, and insize). We also present the first efficient algorithms for exact computation of these parameters. All of our algorithms can be used to approximate the hyperbolicity of a geodesic metric space.

We investigate the impact the negative curvature has on the traffic congestion in large-scale networks. We prove that every Gromov hyperbolic network G admits a core, thus answering in the positive a conjecture by Jonckheere, Lou, Bonahon, and Baryshnikov, Internet Mathematics, 7 (2011) which is based on the experimental observation by Narayan and Saniee, Physical Review E, 84 (2011) that real-world networks with small hyperbolicity have a core congestion. Namely, we prove that for every subset X of vertices of a graph with δ-thin geodesic triangles (in particular, of a δ-hyperbolic graph) G there exists a vertex m of G such that the ball B(m, 4δ) of radius 4δ centered at m intercepts at least one half of the total flow between all pairs of vertices of X, where the flow between two vertices x,y ∊ X is carried by geodesic (or quasi-geodesic) (x, y)-paths. Moreover, we prove a primal- dual result showing that, for any commodity graph R on X and any r ≥ 8δ, the size στ(R) of the least r-multi-core (i.e., the number of balls of radius r) intercepting all pairs of R is upper bounded by the maximum number of pairwise (2r – 5δ)- apart pairs of R and that an r-multi-core of size σr–5δ (R) can be computed in polynomial time for every finite set X. Our result about total r-multi-cores is based on a Helly-type theorem for quasiconvex sets in δ-hyperbolic graphs (this is our second main result). Namely, we show that for any finite collection Q of pairwise intersecting ∊-quasiconvex sets of a δ-hyperbolic graph G there exists a single ball B(c, 2∊ + 5δ) intersecting all sets of Q. More generally, we prove that if Q is a collection of 2r-close (i.e., any two sets of Q are at distance ≤ 2r) ε-quasiconvex sets of a δ-hyperbolic graph G, then there exists a ball B(c,r*) of radius r* := max{2e + 5δ, r + e + 3δ} intersecting all sets of Q. These kind of Helly-type results are also useful in geometric group theory. Using the Helly theorem for quasiconvex sets and a primal-dual approach, we show algorithmically that the minimum number of balls of radius 2∊ + 5δ intersecting all sets of a family Q of ∊-quasiconvex sets does not exceed the packing number of Q (maximum number of pairwise disjoint sets of Q). We extend the covering and packing result to set-families KQ in which each set is a union of at most κ ε-quasiconvex sets of a δ-hyperbolic graph G. Namely, we show that if r ≥ ∊ + 2δ and nr (κ Q) is the maximum number of mutually 2r-apart members of κ Q, then the minimum number of balls of radius r + 2∊ + 6δ intersecting all members of KQ is at most 2K2nr(KQ) and such a hitting set and a packing can be constructed in polynomial time for every finite KQ (this is our third main result). For set- families consisting of unions of κ balls in δ-hyperbolic graphs a similar result was obtained by Chepoi and Estellon (2007). In case of δ = 0 (trees) and ∊ = r = 0, (subtrees of a tree) we recover the result of Alon (2002) about the transversal and packing numbers of a set-family in which each set is a union of at most κ subtrees of a tree.

In the bidirected minimum Manhattan network problem, given a set T of n terminals in the plane, no two terminals on the same horizontal or vertical line, we need to construct a network N(T) of minimum total length with the property that the edges of N(T) belong to the axis-parallel grid defined by T and are oriented in a such a way that every ordered pair of terminals is connected in N(T) by a directed Manhattan path. In this article, we present a polynomial factor 2-approximation algorithm for the bidirected minimum Manhattan network problem. © 2016 Wiley Periodicals, Inc. NETWORKS, Vol. 69(2), 167–178 2017

In the classical cop and robber game, two players, the cop $\mathcal{C}$ and the robber $\mathcal{R}$, move alternatively along edges of a finite graph $G=(V,E)$. The cop captures the robber if both players are on the same vertex at the same moment of time. A graph G is called cop win if the cop always captures the robber after a finite number of steps. Nowakowski and Winkler [Discrete Math., 43 (1983), pp. 235–239] and Quilliot [Problèmes de jeux, de point fixe, de connectivité et de représentation sur des graphes, des ensembles ordonnés et des hypergraphes, Thèse de doctorat d'état, Université de Paris VI, Paris, 1983] characterized the cop-win graphs as graphs admitting a dismantling scheme. In this paper, we characterize in a similar way the class $\mathcal{CWFR}(s,s')$ of cop-win graphs in the game in which the robber and the cop move at different speeds s and $s'$, $s'\leq s$. We also establish some connections between cop-win graphs for this game with $s'1$. In particular, we characterize the graphs which are cop-win for any value of k.

δ-Hyperbolic metric spaces have been defined by M. Gromov via a simple 4-point condition: for any four points u,v,w,x, the two larger of the sums d(u,v)+d(w,x), d(u,w)+d(v,x), d(u,x)+d(v,w) differ by at most 2δ. Given a finite set S of points of a δ-hyperbolic space, we present simple and fast methods for approximating the diameter of S with an additive error 2δ and computing an approximate radius and center of a smallest enclosing ball for S with an additive error 3δ. These algorithms run in linear time for classical hyperbolic spaces and for δ-hyperbolic graphs and networks. Furthermore, we show that for δ-hyperbolic graphs G=(V,E) with uniformly bounded degrees of vertices, the exact center of S can be computed in linear time O(|E|). We also provide a simple construction of distance approximating trees of δ-hyperbolic graphs G on n vertices with an additive error O(δlog2 n). This construction has an additive error comparable with that given by Gromov for n-point δ-hyperbolic spaces, but can be implemented in O(|E|) time (instead of O(n2)). Finally, we establish that several geometrical classes of graphs have bounded hyperbolicity.

In this paper, we consider a class of cellular networks, called irregular cellular networks, which may have a non-uniform distribution of base stations and a non-uniform cell size. The communications (between base stations) graph of such a cellular network forms a so-called trigraph, i.e., a plane triangulation with inner vertices of degree at least six. We show that each trigraph with n vertices admits a labeling that assigns O(log/sup 2/ n) bit labels to vertices of the graph such that the distance between any two vertices u and v can be determined in constant time by merely inspecting the labels of u and v, without using any other information about the graph. Furthermore, we show that there is a labeling, assigning labels of size O(log/sup 2/ n) bits to vertices, which allows, given the label of a source vertex and the label of a destination, to compute in constant time the port number of the edge from the source that heads in the direction of the destination. These two results for trigraphs provide elegant solutions to a few problems in irregular cellular networks. The distance labeling scheme allows efficient implementation of the distance-based tracking protocol, by providing information, generally not available to the user, and means for accurate cell distance determination. Our routing and distance labeling schemes provide compact and efficient routing and connection re-routing protocols. Although these results are primarily developed for cellular networks, they may find applications also in other types of wireless networks that have a fixed backbone infrastructure.

Abstract The eccentricity lowering problem is to reduce the eccentricity of a network by upgrading some nodes (that is, shrinking the lengths of the edges incident to such nodes). We consider two types of node‐upgrading strategies, that is, a continuous upgrading strategy and a discrete upgrading strategy, where the improvement under the first strategy is a continuous variable, and the improvement under the second strategy is a fixed amount. These problems are hard even to approximate, for general graphs. Therefore, we restrict our attention to graphs with simple structures. Assuming that the graph G = (V,E) is a tree, we show that the eccentricity lowering problem under the continuous node‐upgrading strategy can be reduced to the eccentricity lowering problem under the continuous edge‐upgrading strategy, and can be solved by an O(|V| log |V|) time algorithm. We also show that the problem for a tree is NP‐hard under the discrete upgrading strategy, but admits a fully polynomial approximation scheme, if the graph is a line. © 2005 Wiley Periodicals, Inc. NETWORKS, Vol. 45(4), 232–239 2005

Summary form only given. Triangular systems are the subgraphs of the regular triangular grid which are formed by a simple circuit of the grid and the region bounded by this circuit. They are used to model cellular networks where nodes are base stations. We propose an addressing scheme for triangular systems by employing their isometric embeddings into the Cartesian product of three trees. This embedding provides a simple representation of any triangular system with only three small integers per vertex, and allows to employ the compact labeling schemes for trees for distance queries and routing. We show that each such system with n vertices admits a labeling that assigns O(log/sup 2/n) bit labels to vertices of the system such that the distance between any two vertices u and v can be determined in constant time by merely inspecting the labels of u and v, without using any other information about the system. Furthermore, there is a labeling, assigning labels of size O(log n) bits to vertices, which allows, given the label of a source vertex and the label of a destination, to compute in constant time the port number of the edge from the source that heads in the direction of the destination. These results are used in solving some problems in cellular networks. Our addressing and distance labeling schemes allow efficient implementation of distance and movement based tracking protocols in cellular networks, by providing information, generally not available to the user, and means for accurate cell distance determination. Our routing and distance labeling schemes provide elegant and efficient routing and connection rerouting protocols for cellular networks.

Abstract Given a tree T = (V, E) endowed with a length function l and a cost function c, the diameter lowering problem consists in finding the reals 0 ≤ x(e) ≤ l(e), e ∈ E such that the tree obtained from T by decreasing the length of every edge e by x(e) units has a minimal diameter subject to the constraint ∑e∈Ec(e)x(e) ≤ B, where B is the available budget (analogously, one can minimize the cost of lowering subject to a diameter constraint). We present an O(|V|2) algorithm for solving this problem by developing and using algorithms of similar complexity for related eccentricity lowering problems. © 2002 Wiley Periodical, Inc.