Linear-size $\e$-Emulators for Planar Graphs
Hsien-Chih Chang  1@  
1 : Dartmouth College

We study vertex sparsification for distances, in the setting of planar graphs with distortion:
Given a planar graph $G$ (with edge weights) and a subset of $k$ terminal vertices, the goal is to construct an \emph{$\varepsilon$-emulator}, which is a small planar graph $G'$ that contains the terminals and preserves the distances between the terminals up to factor $1+\varepsilon$.

We design the first $\varepsilon$-emulators for planar graphs of linear size $k/\varepsilon^{O(1)}$.
In terms of $k$, this is a dramatic improvement over the previous quadratic upper bound of Cheung, Goranci and Henzinger [ICALP 2016], and breaks below known quadratic lower bounds for exact emulators (the case when $\varepsilon=0$).
Moreover, our emulators can be computed in near-linear time, with applications to fast $(1+\varepsilon)$-approximation algorithms for basic optimization problems on planar graphs such as minimum $(s,t)$-cut and diameter.

A central technical contribution is to carry out a \emph{spread reduction} for the all-terminal-pairs shortest path problem when the input graph is planar and the terminals all lie on the outerface (called a \emph{one-hole instance}); the \emph{spread} is defined to be the ratio between the largest and the smallest distances between terminals.
To construct an emulator for a one-hole instance $G$ we adapt a recursive \emph{split-and-combine} strategy.
We will attempt to split the input instance into multiple one-hole instances along some shortest paths that distribute the terminals evenly.
Every time we slice the graph $G$ open along a shortest path~$P$, we compute a small collection of vertices on $P$ called the \emph{portals}, that approximately preserve the distances from terminals in $G$ to the vertices on~$P$.
We need the portals to be dense enough so that only a small error term will be added to the distortion of the emulator after the gluing; at the same time, the number of portals cannot be too large, as they are added to the terminal set, causing the number of terminals per piece to go down slowly and creating too many pieces.
Even when the original input has a polynomial spread to start with, in general we cannot control the spread of all the pieces occurring during the split-and-combine process. Thus new ideas are needed. To this end we prove a combinatorial lemma counting the sum of degrees of big faces in the arrangement of non-crossing shortest paths within a disk.


Personnes connectées : 2 Vie privée
Chargement...