We propose to study unweighted graphs of constant distance VC-dimension as a broad generalization of many graph classes for which we can compute the diameter in truly subquadratic-time. In particular for any fixed @math , the class of @math -minor free graphs has distance VC-dimension at most @math . Our first main result is that on graphs of distance VC-dimension at most @math , for any fixed @math we can either compute the diameter or conclude that it is larger than @math in time @math , where @math only depends on @math . Then as a byproduct of our approach, we get the first truly subquadratic-time algorithm for constant diameter computation on all the nowhere dense graph classes. Finally, we show how to remove the dependency on @math for any graph class that excludes a fixed graph @math as a minor. More generally, our techniques apply to any graph with constant distance VC-dimension and polynomial expansion. As a result for all such graphs one obtains a truly subquadratic-time algorithm for computing their diameter. Our approach is based on the work of Chazelle and Welzl who proved the existence of spanning paths with strongly sublinear stabbing number for every hypergraph of constant VC-dimension. We show how to compute such paths efficiently by combining the best known approximation algorithms for the stabbing number problem with a clever use of @math -nets, region decomposition and other partition techniques.
An early example of linear-time solvable special case for diameter computation is the class of interval graphs @cite_0 . For every interval graph @math and for any integer @math , if we first compute an interval representation for @math in linear-time @cite_31 then we can compute by dynamic programming, for every vertex @math , the contiguous segment of all the vertices at a distance @math from @math in @math . It takes almost linear-time and it implies a straightforward quasi linear-time algorithm for diameter computation. More efficient algorithms for diameter computation on interval graphs and related graph classes were proposed in @cite_23 . Nevertheless we will show in what follows that interval orderings are a powerful tool for diameter computation on more general geometric graph classes.
@cite_0 @cite_31 @cite_23
2102564932 9515613 2091612923
The Near-Bipartiteness problem is that of deciding whether or not the vertices of a graph can be partitioned into sets @math and @math , where @math is an independent set and @math induces a forest. The set @math in such a partition is said to be an independent feedback vertex set. Yang and Yuan proved that Near-Bipartiteness is polynomial-time solvable for graphs of diameter 2 and NP-complete for graphs of diameter 4. We show that Near-Bipartiteness is NP-complete for graphs of diameter 3, resolving their open problem. We also generalise their result for diameter 2 by proving that even the problem of computing a minimum independent feedback vertex is polynomial-time solvable for graphs of diameter 2. The computational problem of finding the center of a graph is motivated by a number of facility-location problems. We exploit a new characterization of interval graphs for the purpose of obtaining a linear-time algorithm for computing both the center and the diameter of an interval graph. For a positive parameter @math , the @math -bounded distance between a pair of vertices @math in a weighted undirected graph @math is the length of the shortest @math path in @math with at most @math edges, aka hops . For @math as above and @math , a @math -hopset of @math is a graph @math on the same vertex set, such that all distances in @math are @math -approximated by @math -bounded distances in @math . Hopsets are a fundamental graph-theoretic and graph-algorithmic construct, and they are widely used for distance-related problems in a variety of computational settings. Currently existing constructions of hopsets produce hopsets either with @math edges, or with a hopbound @math . In this paper we devise a construction of linear-size hopsets with hopbound @math . This improves the previous bound almost exponentially. We also devise efficient implementations of our construction in PRAM and distributed settings. The only existing PRAM algorithm EN16 for computing hopsets with a constant (i.e., independent of @math ) hopbound requires @math time. We devise a PRAM algorithm with polylogarithmic running time for computing hopsets with a constant hopbound, i.e., our running time is exponentially better than the previous one. Moreover, these hopsets are also significantly sparser than their counterparts from EN16 . We use our hopsets to devise a distributed routing scheme that exhibits near-optimal tradeoff between individual memory requirement @math of vertices throughout preprocessing and routing phases of the algorithm, and stretch @math , along with a near-optimal construction time @math , where @math is the hop-diameter of the input graph.