Constant Approximation Algorithms for Embedding Graph Metrics into Trees and Outerplanar Graphs

In this paper, we present a simple factor 6 algorithm for approximating the optimal multiplicative distortion of embedding a graph metric into a tree metric (thus improving and simplifying the factor 100 and 27 algorithms of Bǎdoiu et al. (Proceedings of the eighteenth annual ACM–SIAM symposium on discrete algorithms (SODA 2007), pp. 512–521, 2007) and Bǎdoiu et al. (Proceedings of the 11th international workshop on approximation algorithms for combinatorial optimization problems (APPROX 2008), Springer, Berlin, pp. 21–34, 2008)). We also present a constant factor algorithm for approximating the optimal distortion of embedding a graph metric into an outerplanar metric. For this, we introduce a general notion of a metric relaxed minor and show that if G contains an α-metric relaxed H-minor, then the distortion of any embedding of G into any metric induced by a H-minor free graph is ≥α. Then, for H=K _2,3, we present an algorithm which either finds an α-relaxed minor, or produces an O(α)-embedding into an outerplanar metric.     

Eigenvalue bracketing for discrete and metric graphs

We develop eigenvalue estimates for the Laplacians on discrete and metric graphs using various types of boundary conditions at the vertices of the metric graph. Via an explicit correspondence of the equilateral metric and discrete graph spectrum (also in the “exceptional” values of the metric graph corresponding to the Dirichlet spectrum) we carry over these estimates from the metric graph Laplacian to the discrete case. We apply the results to covering graphs and present examples where the covering graph Laplacians have spectral gaps.     

Spectral Convergence of Quasi-One-Dimensional Spaces

We consider a family of non-compact manifolds X_ε (“graph-like manifolds”) approaching a metric graph X₀ and establish convergence results of the related natural operators, namely the (Neumann) Laplacian and the generalized Neumann (Kirchhoff) Laplacian on the metric graph. In particular, we show the norm convergence of the resolvents, spectral projections and eigenfunctions. As a consequence, the essential and the discrete spectrum converge as well. Neither the manifolds nor the metric graph need to be compact, we only need some natural uniformity assumptions. We provide examples of manifolds having spectral gaps in the essential spectrum, discrete eigenvalues in the gaps or even manifolds approaching a fractal spectrum. The convergence results will be given in a completely abstract setting dealing with operators acting in different spaces, applicable also in other geometric situations. Communicated by Claude Alain Pillet Submitted: December 21, 2005 Accepted: January 30, 2006     

Gromov–Wasserstein Distances and the Metric Approach to Object Matching

This paper discusses certain modifications of the ideas concerning the Gromov–Hausdorff distance which have the goal of modeling and tackling the practical problems of object matching and comparison. Objects are viewed as metric measure spaces, and based on ideas from mass transportation, a Gromov–Wasserstein type of distance between objects is defined. This reformulation yields a distance between objects which is more amenable to practical computations but retains all the desirable theoretical underpinnings. The theoretical properties of this new notion of distance are studied, and it is established that it provides a strict metric on the collection of isomorphism classes of metric measure spaces. Furthermore, the topology generated by this metric is studied, and sufficient conditions for the pre-compactness of families of metric measure spaces are identified. A second goal of this paper is to establish links to several other practical methods proposed in the literature for comparing/matching shapes in precise terms. This is done by proving explicit lower bounds for the proposed distance that involve many of the invariants previously reported by researchers. These lower bounds can be computed in polynomial time. The numerical implementations of the ideas are discussed and computational examples are presented.     

Sur la forme de la boule unité de la norme stable unidimensionnelle

We study the stable norm on the first homology of a Riemannian polyhedron. In the one-dimensional case (metric graphs), the geometry of the unit ball of this norm is completely described by the combinatorial structure of the graph. For a smooth manifold of dimension ≥3 and using polyhedral techniques, we show that a large class of polytopes appears as unit ball of the stable norm associated to some metric conformal to a given one. Received: 18 March     

On some problems of guaranteed search on graphs

Pursuit-evasion differential games on graphs with no information on the evader are considered. Special attention is given to the following ɛ-search problem posed by Golovach. A topological graph embedded in three-dimensional Euclidean space is considered. For simplicity, its edges are assumed to be polygonal, only simple motions of the pursuers and the evader are allowed, and the graph is a phase constraint for all players. The goal of the pursuers is to construct a program depending only on the structure of the graph which ensures capturing the invisible evader, i.e., approaching the evader at a distance of at most ɛ (in the intrinsic metric of the graph), where ɛ is a given nonnegative number. The problem consists in finding the minimum number of pursuers (called the ɛ-search number) needed to capture the evader. Properties of the Golovach function, which assigns the ɛ-search number to every nonnegative ɛ, are investigated. Golovach and Petrov proved that the Golovach function for the complete graph on more than five vertices may have non-unit jumps. The authors of this paper are aware of examples of similar degeneration for trees. These examples disprove the conjecture that the Golovach function of any planar graph has only unit jumps. A subclass of trees for which the Golovach function has only unit jumps is distinguished.     

Roundness Properties of Groups

Roundness of metric spaces was introduced by Per Enflo as a tool to study uniform structures of linear topological spaces. The present paper investigates geometric and topological properties detected by the roundness of general metric spaces. In particular, we show that geodesic spaces of roundness 2 are contractible, and that a compact Riemannian manifold with roundness >1 must be simply connected. We then focus our investigation on Cayley graphs of finitely generated groups. One of our main results is that every Cayley graph of a free Abelian group on ⩾ 2 generators has roundness =1. We show that if a group has no Cayley graph of roundness =1, then it must be a torsion group with every element of order 2,3,5, or 7 Partially supported by a Canisius College Summer Research Grant     

(2,k)-Factor-Critical Graphs and Toughness

 A graph is (r,k)-factor-critical if the removal of any set of k vertices results in a graph with an r-factor (i.e. with an r-regular spanning subgraph). We show that every τ-tough graph of order n with τ≥2 is (2,k)-factor-critical for every non-negative integer k≤min{2τ−2, n−3}, thus proving a conjecture as well as generalizing the main result of Liu and Yu in [4]. Received: December 16, 1996 / Revised: September 17, 1997     

A Combinatorial Algorithm for the Minimum (2, r)-Metric Problem and Some Generalizations

be a graph with nonnegative integer capacities c(e) of the edges , and let μ be a metric that establishes distances on the pairs of elements of a subset . In the minimum 0-extension problem (*), one is asked for finding a (semi)metric m on V such that m coincides with μ within T, each is at zero distance from some , and the value is as small as possible. This is the classical minimum (undirected) cut problem when and , and the minimum (2, r)-metric problem when μ is the path metric of the complete bipartite graph . It is known that the latter problem can be solved in strongly polynomial time by use of the ellipsoid method. We develop a polynomial time algorithm for the minimum (2, r)-metric problem, using only ``purely combinatorial' means. The algorithm simultaneously solves a certain associated integer multiflow problem. We then apply this algorithm to solve (*) for a wider class of metrics μ, present other results and raise open questions. Received: June 11, 1998     

List-colourings of graphs

In this paper, we go some way towards proving a conjecture of Albertson and Tucker. Among other results, we show that ifc>11/6 and Δ is sufficiently large, then a graph of maximum degree Δ with a list of cardinality [cΔ] assigned to each edge may be edge-coloured so that each edge is coloured with an element of its list.     

Lower bounds on static Lovász-Schrijver calculus proofs for Tseitin tautologies

An exponential lower bound on the size of static Lovász-Schrijver proofs of Tseitin tautologies is established. Several techniques, such as translating a static LS₊ proof into a Positivstellensatz proof, extracting a “good” expander out of a given graph by removing edges and vertices, and proving a linear lower bound on the degree of Positivstellensatz proofs for Tseitin tautologies, are used. Bibliography: 22 titles. __________ Translated from Zapiski Nauchnykh Seminarov POMI, Vol. 340, 2006, pp. 10–32.     

Correction to “All regular Landsberg metrics are Berwald”

Just recently, incompleteness in the proof of the theorem appearing in the title [published in Szabó (Ann Glob Anal Geom, to appear, 2008)] has been discovered. Without this problematic part, the theorem is established only in the following restricted form: “A regular Finsler metric is Berwald if and only if it satisfies the dual Landsberg condition.” The incompleteness appears in proving that the original Landsberg condition implies the dual one.     

Rank-determining sets of metric graphs

A metric graph is a geometric realization of a finite graph by identifying each edge with a real interval. A divisor on a metric graph Γ is an element of the free abelian group on Γ. The rank of a divisor on a metric graph is a concept appearing in the Riemann-Roch theorem for metric graphs (or tropical curves) due to Gathmann and Kerber, and Mikhalkin and Zharkov. We define a rank-determining set of a metric graph Γ to be a subset A of Γ such that the rank of a divisor D on Γ is always equal to the rank of D restricted on A. We show constructively in this paper that there exist finite rank-determining sets. In addition, we investigate the properties of rank-determining sets in general and formulate a criterion for rank-determining sets. Our analysis is based on an algorithm to derive the v₀-reduced divisor from any effective divisor in the same linear system.     

Combinatorial conditions that imply word-hyperbolicity for 3-manifolds

Thurston conjectured that a closed triangulated 3-manifold in which every edge has degree 5 or 6, and no two edges of degree 5 lie in a common 2-cell, has word-hyperbolic fundamental group. We establish Thurston's conjecture by proving that such a manifold admits a piecewise Euclidean metric of non-positive curvature and the universal cover contains no isometrically embedded flat planes. The proof involves a mixture of computer computation and techniques from small cancellation theory.     

Lower Bounds on the Distortion of Embedding Finite Metric Spaces in Graphs

The main question discussed in this paper is how well a finite metric space of size n can be embedded into a graph with certain topological restrictions. The existing constructions of graph spanners imply that any n -point metric space can be represented by a (weighted) graph with n vertices and n ^{1 +O(1/r)} edges, with distances distorted by at most r . We show that this tradeoff between the number of edges and the distortion cannot be improved, and that it holds in a much more general setting. The main technical lemma claims that the metric space induced by an unweighted graph H of girth g cannot be embedded in a graph G (even if it is weighted) of smaller Euler characteristic, with distortion less than g/4 - 3/2 . In the special case when |V(G)| =|V(H)| and G has strictly less edges than H , an improved bound of g/3 - 1 is shown. In addition, we discuss the case χ(G) < χ(H) - 1 , as well as some interesting higher-dimensional analogues. The proofs employ basic techniques of algebraic topology. Received September 26, 1995, and in revised form March 18, 1996.     

Extended least action principle for steady flows under a prescribed flux

The extended principle of minimal action is described in the presence of prescribed source and sink points. Under the assumption of zero net flux, it leads to an optimal Monge–Kantorovich transport problem of metric type. We concentrate on action corresponding to a mechanical Lagrangian. The optimal solution turns out to be a measure supported on a graph composed of geodesic arcs connecting pairs of sources and sinks.     

Landmarks in graphs

Navigation can be studied in a graph-structured framework in which the navigating agent (which we shall assume to be a point robot) moves from node to node of a “graph space”. The robot can locate itself by the presence of distinctively labeled “landmark” nodes in the graph space. For a robot navigating in Euclidean space, visual detection of a distinctive landmark provides information about the direction to the landmark, and allows the robot to determine its position by triangulation. On a graph, however, there is neither the concept of direction nor that of visibility. Instead, we shall assume that a robot navigating on a graph can sense the distances to a set of landmarks.

Evidently, if the robot knows its distances to a sufficiently large set of landmarks, its position on the graph is uniquely determined. This suggests the following problem: given a graph, what are the fewest number of landmarks needed, and where should they be located, so that the distances to the landmarks uniquely determine the robot's position on the graph? This is actually a classical problem about metric spaces. A minimum set of landmarks which uniquely determine the robot's position is called a “metric basis”, and the minimum number of landmarks is called the “metric dimension” of the graph. In this paper we present some results about this problem. Our main new results are that the metric dimension of a graph with n nodes can be approximated in polynomial time within a factor of O(log n), and some properties of graphs with metric dimension two.     

An Extension of Set-Valued Contraction Principle for Mappings on a Metric Space with a Graph and Application

In this paper, we obtain an existence theorem for fixed points of contractive set-valued mappings on a metric space endowed with a graph. This theorem unifies and extends several fixed point theorems for mappings on metric spaces and for mappings on metric spaces endowed with a graph. As an application, we obtain a theorem on the convergence of successive approximations for some linear operators on an arbitrary Banach space. This result yields the well-known Kelisky–Rivlin theorem on iterates of the Bernstein operators on C[0,1].     

Pseudodifferential Operators on Periodic Graphs

The main aim of the paper is Fredholm properties of a class of bounded linear operators acting on weighted Lebesgue spaces on an infinite metric graph Γ which is periodic with respect to the action of the group \mathbb Zⁿ{{\mathbb {Z}}^n} . The operators under consideration are distinguished by their local behavior: they act as (Fourier) pseudodifferential operators in the class OPS ⁰ on every open edge of the graph, and they can be represented as a matrix Mellin pseudodifferential operator on a neighborhood of every vertex of Γ. We apply these results to study the Fredholm property of a class of singular integral operators and of certain locally compact operators on graphs.     

On the Metric Dimension of Infinite Graphs

A set of vertices S resolves a connected graph G if every vertex is uniquely determined by its vector of distances to the vertices in S. The metric dimension of a graph G is the minimum cardinality of a resolving set. In this paper we undertake the metric dimension of infinite locally finite graphs, i.e., those infinite graphs such that all its vertices have finite degree. We give some necessary conditions for an infinite graph to have finite metric dimension and characterize infinite trees with finite metric dimension. We also establish some general results about the metric dimension of the Cartesian product of finite and infinite graphs, and obtain the metric dimension of the Cartesian product of several families of graphs.