An official website of the United States government
Given a set P of n points in the plane, the unit-disk graph Gr(P) with respect to a parameter r is an undirected graph whose vertex set is P such that an edge connects two points p, q in P if the Euclidean distance between p and q is at most r (the weight of the edge is 1 in the unweighted case and is the distance between p and q in the weighted case). Given a value \lambda>0 and two points s and t of P, we consider the following reverse shortest path problem: computing the smallest r such that the shortest path length between s and t in Gr(P) is at most \lambda. In this paper, we present an algorithm of O(\lfloor \lambda \rfloor \cdot n log n) time and another algorithm of O(n^{5/4} log^{7/4} n) time for the unweighted case, as well as an O(n^{5/4} log^{5/2} n) time algorithm for the weighted case. We also consider the L1 version of the problem where the distance of two points is measured by the L1 metric; we solve the problem in O(n log^3 n) time for both the unweighted and weighted cases.
more »
« less
Improved Reconstruction of Random Geometric Graphs
Embedding graphs in a geographical or latent space, i.e. inferring locations for vertices in Euclidean space or on a smooth manifold or submanifold, is a common task in network analysis, statistical inference, and graph visualization. We consider the classic model of random geometric graphs where n points are scattered uniformly in a square of area n, and two points have an edge between them if and only if their Euclidean distance is less than r. The reconstruction problem then consists of inferring the vertex positions, up to the symmetries of the square, given only the adjacency matrix of the resulting graph. We give an algorithm that, if r = n^α for α > 0, with high probability reconstructs the vertex positions with a maximum error of O(n^β) where β = 1/2-(4/3)α, until α ≥ 3/8 where β = 0 and the error becomes O(√{log n}). This improves over earlier results, which were unable to reconstruct with error less than r. Our method estimates Euclidean distances using a hybrid of graph distances and short-range estimates based on the number of common neighbors. We extend our results to the surface of the sphere in ℝ³ and to hypercubes in any constant dimension.
more »
« less
- Award ID(s):
- 1838251
- PAR ID:
- 10359467
- Editor(s):
- Bojanczyk, M. et
- Date Published:
- Journal Name:
- 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Given a set S of n points in the plane and a parameter ε>0, a Euclidean (1+ε) -spanner is a geometric graph G=(S,E) that contains a path of weight at most (1+ε)∥pq∥2 for all p,q∈S . We show that the minimum weight of a Euclidean (1+ε)-spanner for n points in the unit square [0,1]2 is O(ε−3/2n−−√), and this bound is the best possible. The upper bound is based on a new spanner algorithm that sparsifies Yao-graphs. It improves upon the baseline O(ε−2n−−√), obtained by combining a tight bound for the weight of an MST and a tight bound for the lightness of Euclidean (1+ε)-spanners, which is the ratio of the spanner weight to the weight of the MST. The result generalizes to d-space for all d∈N : The minimum weight of a Euclidean (1+ε)-spanner for n points in the unit cube [0,1]d is Od(ε(1−d2)/dn(d−1)/d), and this bound is the best possible. For the n×n section of the integer lattice, we show that the minimum weight of a Euclidean (1+ε)-spanner is between Ω(ε−3/4n2) and O(ε−1log(ε−1)n2). These bounds become Ω(ε−3/4n−−√) and O(ε−1log(ε−1)n−−√) when scaled to a grid of n points in [0,1]2. .more » « less
-
null (Ed.)We introduce and study the problem of constructing geometric graphs that have few vertices and edges and that are universal for planar graphs or for some sub-class of planar graphs; a geometric graph is universal for a class H of planar graphs if it contains an embedding, i.e., a crossing-free drawing, of every graph in H . Our main result is that there exists a geometric graph with n vertices and O(nlogn) edges that is universal for n-vertex forests; this extends to the geometric setting a well-known graph-theoretic result by Chung and Graham, which states that there exists an n-vertex graph with O(nlogn) edges that contains every n-vertex forest as a subgraph. Our O(nlogn) bound on the number of edges is asymptotically optimal. We also prove that, for every h>0 , every n-vertex convex geometric graph that is universal for the class of the n-vertex outerplanar graphs has Ωh(n2−1/h) edges; this almost matches the trivial O(n2) upper bound given by the n-vertex complete convex geometric graph. Finally, we prove that there is an n-vertex convex geometric graph with n vertices and O(nlogn) edges that is universal for n-vertex caterpillars.more » « less
-
Chan, Timothy; Fischer, Johannes; Iacono, John; Herman, Grzegorz (Ed.)We describe a simple deterministic near-linear time approximation scheme for uncapacitated minimum cost flow in undirected graphs with positive real edge weights, a problem also known as transshipment. Specifically, our algorithm takes as input a (connected) undirected graph G = (V, E), vertex demands b ∈ R^V such that ∑_{v ∈ V} b(v) = 0, positive edge costs c ∈ R_{≥ 0}^E, and a parameter ε > 0. In O(ε^{-2} m log^{O(1)} n) time, it returns a flow f such that the net flow out of each vertex is equal to the vertex’s demand and the cost of the flow is within a (1 ± ε) factor of optimal. Our algorithm is combinatorial and has no running time dependency on the demands or edge costs. With the exception of a recent result presented at STOC 2022 for polynomially bounded edge weights, all almost- and near-linear time approximation schemes for transshipment relied on randomization to embed the problem instance into low-dimensional space. Our algorithm instead deterministically approximates the cost of routing decisions that would be made if the input were subject to a random tree embedding. To avoid computing the Ω(n²) vertex-vertex distances that an approximation of this kind suggests, we also take advantage of the clustering method used in the well-known Thorup-Zwick distance oracle.more » « less
-
A $(β,δ,Δ)$-padded decomposition of an edge-weighted graph $G = (V,E,w)$ is a stochastic decomposition into clusters of diameter at most $$Δ$$ such that for every vertex $$v\in V$$, the probability that $$\rm{ball}_G(v,γΔ)$$ is entirely contained in the cluster containing $$v$$ is at least $$e^{-βγ}$$ for every $$γ\in [0,δ]$$. Padded decompositions have been studied for decades and have found numerous applications, including metric embedding, multicommodity flow-cut gap, multicut, and zero extension problems, to name a few. In these applications, parameter $$β$$, called the padding parameter, is the most important parameter since it decides either the distortion or the approximation ratios. For general graphs with $$n$$ vertices, $$β= Θ(\log n)$$. Klein, Plotkin, and Rao showed that $$K_r$$-minor-free graphs have padding parameter $β= O(r^3)$, which is a significant improvement over general graphs when $$r$$ is a constant. A long-standing conjecture is to construct a padded decomposition for $$K_r$$-minor-free graphs with padding parameter $$β= O(\log r)$$. Despite decades of research, the best-known result is $β= O(r)$, even for graphs with treewidth at most $$r$$. In this work, we make significant progress toward the aforementioned conjecture by showing that graphs with treewidth $$\rm{tw}$$ admit a padded decomposition with padding parameter $$O(\log \rm{tw})$$, which is tight. As corollaries, we obtain an exponential improvement in dependency on treewidth in a host of algorithmic applications: $$O(\sqrt{ \log n \cdot \log(\rm{tw})})$$ flow-cut gap, max flow-min multicut ratio of $$O(\log(\rm{tw}))$$, an $$O(\log(\rm{tw}))$$ approximation for the 0-extension problem, an $$\ell^{O(\log n)}_\infty$$ embedding with distortion $$O(\log \rm{tw})$$, and an $$O(\log \rm{tw})$$ bound for integrality gap for the uniform sparsest cut. 39 pages. This is the TheoretiCS journal versionmore » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- The DOI is not currently available.
