• Dynamic Matching Algorithms Under Vertex Updates
    Hung Le and Lazar Milenkovic and Shay Solomon and Virginia Vassilevska Williams
    [PDF Coming soon]
    Abstract Dynamic graph matching algorithms have been extensively studied, but mostly under edge updates. This paper concerns dynamic matching algorithms under vertex updates, where in each update step a single vertex is either inserted or deleted along with its incident edges.

    A basic setting arising in online algorithms and studied by Bosek et al. [FOCS'14] and Bernstein et al. [SODA'18] is that of dynamic approximate maximum cardinality matching (MCM) in bipartite graphs in which one side is fixed and vertices on the other side either arrive or depart via vertex updates. In the BASIC-incremental setting, vertices only arrive, while in the BASIC-decremental setting vertices only depart. When vertices can both arrive and depart, we have the BASIC-dynamic setting. In this paper we also consider the setting in which both sides of the bipartite graph are dynamic. We call this the MEDIUM-dynamic setting, and MEDIUM-decremental is the restriction when vertices can only depart. The GENERAL-dynamic setting is when the graph is not necessarily bipartite and the vertices can both depart and arrive.

    Denote by $K$ the total number of edges inserted and deleted to and from the graph throughout the entire update sequence. A well-studied measure, the recourse of a dynamic matching algorithm is the number of changes made to the matching per step.
    We largely focus on Maximal Matching (MM) which is a $2$-approximation to the MCM. Our main results are as follows.
    • In the BASIC-dynamic setting, there is a straightforward algorithm for maintaining a MM, with a total runtime of $O(K)$ and constant worst-case recourse. In fact, this algorithm never removes an edge from the matching; we refer to such an algorithm as irrevocable.
    • For the MEDIUM-dynamic setting we give a strong conditional lower bound that even holds in the MEDIUM-decremental setting: if for any fixed $\eta>0$, there is an irrevocable decremental MM algorithm with a total runtime of $O(K \cdot n^{1-\eta})$, this would refute the OMv conjecture; a similar (but weaker) hardness result can be achieved via a reduction from the Triangle Detection conjecture.
    • Next, we consider the GENERAL-dynamic setting, and design an MM algorithm with a total runtime of $O(K)$ and constant worst-case recourse. We achieve this result via a 1-revocable algorithm, which may remove just one edge per update step. As argued above, an irrevocable algorithm with such a runtime is not likely to exist.
    • Finally, back to the BASIC-dynamic setting, we present an algorithm with a total runtime of $O(K)$, which provides an $(\frac{e}{e-1})$-approximation to the MCM. To this end, we build on the classic "ranking" online algorithm by Karp et al. [STOC'90].
    Beyond the concrete results, our work draws connections between the areas of dynamic graph algorithms and online algorithms, and it proposes several open questions that seem to be overlooked thus far. </font> </details>
  • Near-Optimal Spanners for General Graphs in (Nearly) Linear Time
    Hung Le and Shay Solomon
    To appear in the 33rd Annual ACM-SIAM Symposium on Discrete Algorithms. SODA 2022.
    Abstract Let $G = (V,E,w)$ be a weighted undirected graph on $|V| = n$ vertices and $|E| = m$ edges, let $k \ge 1$ be any integer, and let $\epsilon < 1$ be any parameter. We present the following results on fast constructions of spanners with {near-optimal} sparsity and lightness,\footnote{The sparsity (respectively, lightness) is a normalized notion of size (resp., weight), where we divide the size (resp., weight) by the size $n-1$ of a spanning tree (resp., the weight $w(\mathrm{MST})$ of a minimum spanning tree $\mathrm{mst}$).} which culminate a long line of work in this area. (By near-optimal we mean optimal under Erdos' girth conjecture and disregarding the $\epsilon$-dependencies.)
    • There are (deterministic) algorithms for constructing $(2k-1)(1+\epsilon)$-spanners for $G$ with a near-optimal sparsity of $O(n^{1/k} \cdot \log(1/\epsilon)/\epsilon))$. The first algorithm can be implemented in the pointer-machine model within time $O(m\alpha(m,n) \cdot \log(1/\epsilon)/\epsilon) + \mathrm{SORT}(m))$, where $\alpha(\cdot,\cdot)$ is the two-parameter inverse-Ackermann function and $\mathrm{SORT}(m)$ is the time needed to sort $m$ integers. The second algorithm can be implemented in the \rdrm model within time $O(m \log(1/\epsilon)/\epsilon))$.
    • There is a (deterministic) algorithm for constructing a $(2k-1)(1+\epsilon)$-spanner for $G$ that achieves a near-optimal bound of $O(n^{1/k} \cdot \mathrm{poly}(1/\epsilon))$ on both sparsity and lightness. This algorithm can be implemented in the pointer-machine model within time $O(m\alpha(m,n) \cdot \mathrm{poly}(1/\epsilon) + \mathrm{SORT}(m))$ and in the \rdrm model within time $O(m \alpha(m,n) \cdot \mathrm{poly}(1/\epsilon))$.
    The previous fastest constructions of $(2k-1)(1+\epsilon)$-spanners with near-optimal sparsity incur a runtime of is $O(\min\{m(n^{1+1/k}) + n\log n,k \cdot n^{2+1/k}\})$, even regardless of the lightness. Importantly, the greedy spanner for stretch $2k-1$ has sparsity $O(n^{1/k})$ --- with no $\epsilon$-dependence whatsoever, but its runtime is $O(m(n^{1+1/k} + n\log n))$. Moreover, the state-of-the-art lightness bound of any $(2k-1)$-spanner (including the greedy spanner) is poor, even regardless of the sparsity and runtime.
  • Can’t See The Forest for the Trees: Navigating Metric Spaces by Bounded Hop-Diameter Spanners
    Omri Kahalon and Hung Le and Lazar Milenkovic and Shay Solomon
    Abstract Spanners for metric spaces have been extensively studied, both in general metrics and in restricted classes, perhaps most notably in low-dimensional Euclidean spaces--- due to their numerous applications. Euclidean spanners can be viewed as means of compressing the $\binom{n}{2}$ pairwise distances of a $d$-dimensional Euclidean space into $O(n) = O_{\epsilon,d}(n)$ spanner edges, so that the spanner distances preserve the original distances to within a factor of $1+\epsilon$, for any $\epsilon > 0$. Moreover, one can compute such spanners in optimal $O(n \log n)$ time. Once the spanner has been computed, it serves as a "proxy" overlay network, on which the computation can proceed, which gives rise to huge savings in space and other important quality measures.

    On the negative side, by working on the spanner rather than the original metric, one loses the key property of being able to efficiently "navigate" between pairs of points. While in the original metric, one can go from any point to any other via a direct edge, it is unclear how to efficiently navigate in the spanner: How can we translate the existence of a "good" path into an efficient algorithm finding it? Moreover, usually by "good" path we mean a path whose weight approximates the original distance between its endpoints --- but a priori the number of edges (or "hops") in the path could be huge. To control the hop-length of paths, one can try to upper bound the spanner's hop-diameter, but naturally bounded hop-diameter spanners are more complex than spanners with unbounded hop-diameter, which might render the algorithmic task of efficiently finding good paths more challenging.

    The original metric enables us to navigate optimally --- a single hop (for any two points) with the exact distance, but the price is high --- $\Theta(n^2)$ edges. Is it possible to efficiently navigate, on a sparse spanner, using $k$ hops and approximate distances, for $k$ approaching 1 (say $k=2$)? Surprisingly, this fundamental question has been overlooked despite the long line of work on spanners in metric spaces.

    We answer this question in the affirmative via a surprisingly simple observation on bounded hop-diameter spanners for tree metrics, which we apply on top of known {\em tree cover theorems}. Beyond its simplicity, the strength of our approach is two-fold:
    • Applicable: We present a variety of applications of our efficient navigation scheme, including a 2-hop routing scheme in Euclidean spaces with stretch $1+\epsilon$ using $O(\log^2 n)$ bits of memory for labels and routing tables --- to the best of our knowledge, all known routing schemes prior to this work use $\Omega(\log n)$ hops.
    • General: Our results extend beyond Euclidean spaces to doubling, planar and general metrics.
  • Greedy Spanners in Euclidean Spaces Admit Sublinear Separators
    Hung Le and Cuong Than
    To appear in the 33rd Annual ACM-SIAM Symposium on Discrete Algorithms. SODA 2022.
    Abstract The greedy spanner in a low dimensional Euclidean space is a fundamental geometric construction that has been extensively studied over three decades as it possesses the two most basic properties of a good spanner: constant maximum degree and constant lightness. Recently, Eppstein and Khodabandeh showed that the greedy spanner in $\mathbb{R}^2$ admits a sublinear separator in a strong sense: any subgraph of $k$ vertices of the greedy spanner in $\mathbb{R}^2$ has a separator of size $O(\sqrt{k})$. Their technique is inherently planar and is not extensible to higher dimensions. They left showing the existence of a small separator for the greedy spanner in $\mathbb{R}^d$ for any constant $d\geq 3$ as an open problem.

    In this paper, we resolve the problem of Eppstein and Khodabandeh by showing that any subgraph of $k$ vertices of the greedy spanner in $\mathbb{R}^d$ has a separator of size $O(k^{1-1/d})$. We introduce a new technique that gives a simple characterization for any geometric graph to have a sublinear separator that we dub \emph{$\tau$-lanky}: a geometric graph is $\tau$-lanky if any ball of radius $r$ cuts at most $\tau$ edges of length at least $r$ in the graph. We show that any $\tau$-lanky geometric graph of $n$ vertices in $\mathbb{R}^d$ has a separator of size $O(\tau n^{1-1/d})$. We then derive our main result by showing that the greedy spanner is $O(1)$-lanky. We indeed obtain a more general result that applies to unit ball graphs and point sets of low fractal dimensions in $\mathbb{R}^d$.

    Our technique naturally extends to doubling metrics. We use the $\tau$-lanky characterization to show that there exists a $(1+\epsilon)$-spanner for doubling metrics of dimension $d$ with a constant maximum degree and a separator of size $O(n^{1-\frac{1}{d}})$; this result resolves an open problem posed by Abam and Har-Peled a decade ago. We then introduce another simple characterization for a graph in doubling metrics of dimension $d$ to have a sublinear separator. We use the new characterization to show that the greedy spanner of an $n$-point metric space of doubling dimension $d$ has a separator of size $O((n^{1-\frac{1}{d}}) + \log\Delta)$ where $\Delta$ is the spread of the metric; the factor $\log(\Delta)$ is tightly connected to the fact that, unlike its Euclidean counterpart, the greedy spanner in doubling metrics has unbounded maximum degree. Finally, we discuss algorithmic implications of our results.
  • Towards a Unified Theory of Light Spanners I: Fast (Yet Optimal) Constructions
    Hung Le and Shay Solomon
    Abstract Seminal works on light spanners over the years provide spanners with optimal or near-optimal lightness in various graph classes, such as in general graphs, Euclidean spanners, and minor-free graphs. Two shortcomings of all previous works on light spanners are: (1) The techniques are ad hoc per graph class, and thus can't be applied broadly (e.g., some require large stretch and are thus suitable to general graphs, while others are naturally suitable to stretch $1 + \epsilon$). (2) The runtimes of these constructions are almost always sub-optimal, and usually far from optimal.

    This work aims at initiating a unified theory of light spanners by presenting a single framework that can be used to construct light spanners in a variety of graph classes. This theory is developed in two papers. The current paper is the first of the two --- it lays the foundations of the theory of light spanners and then applies it to design constructions with optimal lightness for several graph classes. Our new constructions are significantly faster than the state-of-the-art for every examined graph class; moreover, our runtimes are near-linear and usually optimal.

    Specifically, this paper includes the following results (for simplicity assume $\epsilon> 0$ is fixed):
    • In general graphs: A nearly linear-time algorithm for constructing light spanners. Specifically, for any $k \ge 2$, we construct a $(2k-1)(1+\epsilon)$-spanner with lightness $O(n^{1/k})$ in $O(m \alpha(m,n))$ time, where $\alpha(\cdot,\cdot)$ is the inverse-Ackermann function; the lightness bound is optimal assuming Erd\H{o}s' girth conjecture (up to the $\epsilon$-dependency). Since $O(m\alpha(m,n)) = O(m + n\log^{*}n)$, the runtime is \emph{linear} in $m$ when ${m = \Omega(n \log^* n)}$. The previous state-of-the-art runtime of such a spanner is super-quadratic in $n$.
    • In low-dimensional Euclidean spaces: An $O(n\log n)$-time construction of $(1+\epsilon)$-spanners with lightness and degree both bounded by constants in the basic algebraic computation tree (ACT) model. This construction is optimal (up to dependencies on $\epsilon$ and the dimension) with respect to all the involved quality measures --- runtime, lightness and degree --- and it resolves a major problem in the area of geometric spanners, which was open for three decades.
    • In unit-disk graphs in $\mathbb R^2$: An $O(n\log n)$-time construction of $(1+\epsilon)$-spanners with constant lightness and degree, in the ACT model. This construction too is optimal with respect to all the involved quality measures. This is the first $o(n^2)$-time spanner construction for unit disk graphs with a nontrivial lightness bound.
    • In minor-free graphs: A linear-time algorithm for constructing $(1+\epsilon)$-spanners with constant lightness. This is the first $o(n^2)$-time spanner construction for minor-free graphs (and even for some of its sub-classes, such as bounded treewidth graphs), with a nontrivial lightness bound.
  • Reliable Spanners: Locality-Sensitive Orderings Strike Back
    Arnold Filtser and Hung Le
    Abstract Chan, Har-Peled, and Jones [2020] recently developed locality-sensitive ordering (LSO), a new tool that allows one to reduce problems in the Euclidean space $\mathbb{R}^d$ to the $1$-dimensional line. They used LSO's to solve a host of problems. Later, Buchin, Har-Peled, and Ol{\'{a}}h [2019,2020] used the LSO of Chan {\em et al. } to construct very sparse \emph{reliable spanners} for the Euclidean space. A highly desirable feature of a reliable spanner is its ability to withstand a massive failure: the network remains functioning even if 90\% of the nodes fail. In a follow-up work, Har-Peled, Mendel, and Ol{\'{a}}h [2021] constructed reliable spanners for general and topologically structured metrics. Their construction used a different approach, and is based on sparse covers.

    In this paper, we develop the theory of LSO's to non-Euclidean metrics by introducing new types of LSO's suitable for general and topologically structured metrics. We then construct such LSO's, as well as constructing considerably improved LSO's for doubling metrics. Afterwards, we use our new LSO's to construct reliable spanners with improved stretch and sparsity parameters. Most prominently, we construct $\tilde{O}(n)$-size reliable spanners for trees and planar graphs with the optimal stretch of $2$. Along the way to the construction of LSO's and reliable spanners, we introduce and construct ultrametric covers, and construct $2$-hop reliable spanners for the line.
  • Optimal Approximate Distance Oracle for Planar Graphs
    Hung Le and Christian Wulff-Nilsen
    To appear in the 62st Annual Symposium on Foundations of Computer Science. FOCS 2021.
    [PDF Coming soon]
    Abstract A $(1+\epsilon)$-approximate distance oracle of an edge-weighted graph is a data structure that returns an approximate shortest path distance between any two query vertices up to a $(1+\epsilon)$ factor. Thorup (FOCS 2001, JACM 2004) and Klein (SODA 2002) independently constructed a $(1+\epsilon)$-approximate distance oracle with $O(n\log n)$ space, measured in number of words, and $O(1)$ query time when $G$ is an undirected planar graph with $n$ vertices and $\epsilon$ is a fixed constant. Many follow-up works gave $(1+\epsilon)$-approximate distance oracles with various trade-offs between space and query time. However, improving $O(n\log n)$ space bound without sacrificing query time remains an open problem for almost two decades. In this work, we resolve this problem affirmatively by constructing a $(1+\epsilon)$-approximate distance oracle with optimal $O(n)$ space and $O(1)$ query time for undirected planar graphs and fixed $\epsilon$. We also make substantial progress for planar digraphs with non-negative edge weights. For fixed $\epsilon > 0$, we give a $(1+\epsilon)$-approximate distance oracle with space $o(n\log(Nn))$ and $O(\log\log(Nn)$ query time; here $N$ is the ratio between the largest and smallest positive edge weight. This improves Thorup's (FOCS 2001, JACM 2004) $O(n\log(Nn)\log n)$ space bound by more than a logarithmic factor while matching the query time of his structure. This is the first improvement for planar digraphs in two decades, both in the weighted and unweighted setting.
  • A Unified and Fine-Grained Approach for Light Spanners
    Hung Le and Shay Solomon
    Abstract Seminal works on light spanners from recent years provide near-optimal tradeoffs between the stretch and lightness of spanners in general graphs, minor-free graphs and doubling metrics. In FOCS'19 the authors provided a ``truly optimal'' tradeoff (i.e., including the $\epsilon$-dependency, where $\epsilon$ appears in both the stretch and lightness) for Euclidean low-dimensional spaces. Some of these papers employ inherently different techniques than others (e.g., the technique of Chechik and Wulff-Nilsen [SODA20] requires large stretch while others are naturally suitable to stretch $1+\epsilon$). Moreover, the runtime of these constructions is rather high.
    In this work we present a unified and fine-grained approach for light spanners. Besides the obvious theoretical importance of unification, we demonstrate the power of our approach in obtaining (1) stronger lightness bounds, and (2) faster construction times. Our results include:
    • $K_r$-minor-free graphs:
      • A truly optimal spanner. We provide a $(1+\epsilon)$-spanner with lightness $\tilde{O}_{r,\epsilon}( \frac{r}{\epsilon} + \frac{1}{\epsilon^2})$, where $\tilde{O}_{r,\epsilon}$ suppresses $\mathsf{polylog}$ factors of $1/\epsilon$ and $r$, improving the lightness bound $\tilde{O}_{r,\epsilon}( \frac{r}{\epsilon^3})$ of Borradaile, Le and Wulff-Nilsen [FOCS17]. We complement our upper bound with a highly nontrivial lower bound construction, for which any $(1+\epsilon)$-spanner must have lightness $\Omega(\frac{r}{\epsilon} + \frac{1}{\epsilon^2})$.
      • A fast construction. Increasing the lightness bound by an additive term of $O(\frac{1}{\epsilon^4})$ allows us to achieve a runtime of $\tilde{O}_r(n r \alpha(nr, n))$, where $\alpha(.,.)$ is the inverse Ackermann function. The previous state-of-the-art runtime is $O(n^2 r)$.
    • General graphs:
      • A truly optimal spanner--- almost. We provide a $(2k-1)(1+\epsilon)$-spanner (for any $k \geq 2, \epsilon < 1$) with lightness $O(\frac{g(n,k)}{\epsilon})$, where $g(n,k)$ is the minimum sparsity of $n$-vertex graphs with girth $2k+1$. (Recall that $g(n,k) = O(n^{1/k})$ and Erdos' girth conjecture is that $g(n,k) = \Theta(n^{1/k})$.) The previous state-of-the-art lightness by Chechik and Wulff-Nilsen [SODA20] is $O(n^{1/k}\epsilon^{-(3+\frac{1}{k})})$.
      • A fast construction. A $(2k-1)(1+\epsilon)$-spanner with lightness $O_{\epsilon}(n^{1/k})$ can be constructed in $O_{\epsilon}(m \alpha(m,n))$ time; the lightness bound is optimal up to the $\epsilon$-dependency and assuming Erdos' girth conjecture. In particular, when $m = \Omega(n \log^* n)$, the runtime is linear in $m$. The previous state-of-the-art runtime of such a spanner is super-quadratic in $n$.
    • Low dimensional Euclidean spaces: For any point set in $\mathbb{R}^d$ and constant $d\geq 3$, we construct a Euclidean $(1+\epsilon)$-spanner with lightness $\tilde{O}_{\epsilon}(\epsilon^{-(d+1)/2})$ using \emph{Steiner points}. Our result implies that Steiner points help in reducing the lightness of Euclidean $(1+\epsilon)$-spanners almost quadratically. Previously, this fact was only known for point sets with small spread [LS,ESA20].
    • High dimensional Euclidean and normed spaces: We provide a construction of spanners that improves the previous state-of-the-art lightness and size.
  • Clan Embeddings into Trees, and Low Treewidth Graphs
    Arnold Filtser and Hung Le
    The 53rd Annual ACM Symposium on Theory of Computing. STOC 2021.
    Abstract In low distortion metric embeddings, the goal is to embed a host "hard" metric space into a "simpler" target space while approximately preserving pairwise distances. A highly desirable target space is that of a tree metric. Unfortunately, such embedding will result in a huge distortion. A celebrated bypass to this problem is stochastic embedding with logarithmic expected distortion. Another bypass is Ramsey-type embedding, where the distortion guarantee applies only to a subset of the points. However, both these solutions fail to provide an embedding into a single tree with a worst-case distortion guarantee on all pairs. In this paper, we propose a novel third bypass called \emph{clan embedding}. Here each point $x$ is mapped to a subset of points $f(x)$, called a \emph{clan}, with a special \emph{chief} point $\chi(x)\in f(x)$. The clan embedding has multiplicative distortion $t$ if for every pair $(x,y)$ some copy $y'\in f(y)$ in the clan of $y$ is close to the chief of $x$: $\min_{y'\in f(y)}d(y',\chi(x))\le t\cdot d(x,y)$. Our first result is a clan embedding into a tree with multiplicative distortion $O(\frac{\log n}{\epsilon})$ such that each point has $1+\epsilon$ copies (in expectation). In addition, we provide a "spanning" version of this theorem for graphs and use it to devise the first compact routing scheme with constant size routing tables.

    We then focus on minor-free graphs of diameter prameterized by $D$, which were known to be stochastically embeddable into bounded treewidth graphs with expected additive distortion $\epsilon D$. We devise Ramsey-type embedding and clan embedding analogs of the stochastic embedding. We use these embeddings to construct the first (bicriteria quasi-polynomial time) approximation scheme for the metric $\rho$-dominating set and metric $\rho$-independent set problems in minor-free graphs.
  • On Light Spanners, Low-treewidth Embeddings and Efficient Traversing in Minor-free Graphs
    Vincent Cohen-Addad and Arnold Filtser and Philip N. Klein and Hung Le
    The 61st Annual Symposium on Foundations of Computer Science. FOCS 2020.
    Abstract Understanding the structure of minor-free metrics, namely shortest path metrics obtained over a weighted graph excluding a fixed minor, has been an important research direction since the fundamental work of Robertson and Seymour. A fundamental idea that helps both to understand the structural properties of these metrics and lead to strong algorithmic results is to construct a ``small-complexity'' graph that approximately preserves distances between pairs of points of the metric. We show the two following structural results for minor-free metrics:
    • Construction of a light subset spanner. Given a subset of vertices called terminals, and $\epsilon$, in polynomial time we construct a subgraph that preserves all pairwise distances between terminals up to a multiplicative $1+\epsilon$ factor, of total weight at most $O_{\epsilon}(1)$ times the weight of the minimal Steiner tree spanning the terminals.
    • Construction of a stochastic metric embedding into low treewidth graphs with expected additive distortion $\epsilon D$. Namely, given a minor free graph $G=(V,E,w)$ of diameter $D$, and parameter $\epsilon$, we construct a distribution $\mathcal{D}$ over dominating metric embeddings into treewidth-$O_{\epsilon}(\log n)$ graphs such that $\forall u,v\in V$, $\mathbb{E}_{f\sim\mathcal{D}}[d_H(f(u),f(v))]\le d_G(u,v)+\epsilon D$.
    One of our important technical contributions is a novel framework that allows us to reduce both problems to problems on simpler graphs of bounded diameter that we solve using a new decomposition. Our results have the following algorithmic consequences: (1) the first efficient approximation scheme for subset TSP in minor-free metrics; (2) the first approximation scheme for vehicle routing with bounded capacity in minor-free metrics; (3) the first efficient approximation scheme for vehicle routing with bounded capacity on bounded genus metrics. En route to the latter result, we design the first FPT approximation scheme for vehicle routing with bounded capacity on bounded treewidth graphs (parameterized by the treewidth).
  • Light Euclidean Spanners with Steiner Points.
    Hung Le and Shay Solomon
    To appear in the 28th Annual European Symposium on Algorithms. ESA 2020.
    [PDF][Official version][Slides][Talk video]
    Abstract The FOCS'19 paper of Le and Solomon, culminating a long line of research on Euclidean spanners, proves that the lightness (normalized weight) of the greedy $(1+\epsilon)$-spanner in $\mathbb{R}^d$ is $\tilde{O}(\epsilon^{-d})$ for any $d = O(1)$ and any $\epsilon = \Omega(n^{-\frac{1}{d-1}})$ (where $\tilde{O}$ hides polylogarithmic factors of $\frac{1}{\epsilon}$), and also shows the existence of point sets in $\mathbb{R}^d$ for which any $(1+\epsilon)$-spanner must have lightness $\Omega(\epsilon^{-d})$. Given this tight bound on the lightness, a natural arising question is whether a better lightness bound can be achieved using Steiner points.

    Our first result is a construction of Steiner spanners in $\mathbb{R}^2$ with lightness $O(\epsilon^{-1} \log \Delta)$, where $\Delta$ is the spread of the point set. In the regime of $\Delta \ll 2^{1/\epsilon}$, this provides an improvement over the lightness bound of Le and Solomon [FOCS 2019]; this regime of parameters is of practical interest, as point sets arising in real-life applications (e.g., for various random distributions) have polynomially bounded spread, while in spanner applications $\epsilon$ often controls the precision, and it sometimes needs to be much smaller than $O(1/\log n)$. Moreover, for spread polynomially bounded in $1/\epsilon$, this upper bound provides a quadratic improvement over the non-Steiner bound of Le and Solomon [FOCS 2019], We then demonstrate that such a light spanner can be constructed in $O_{\epsilon}(n)$ time for polynomially bounded spread, where $O_{\epsilon}$ hides a factor of $\mathrm{poly}(\frac{1}{\epsilon})$. Finally, we extend the construction to higher dimensions, proving a lightness upper bound of $\tilde{O}(\epsilon^{-(d+1)/2} + \epsilon^{-2}\log \Delta)$ for any $3\leq d = O(1)$ and any $\epsilon = \Omega(n^{-\frac{1}{d-1}})$.
  • A PTAS for Subset TSP in Minor-free Graphs.
    Hung Le
    The 31st Annual ACM-SIAM Symposium on Discrete Algorithms. SODA 2020.
    Abstract We give the first polynomial time approximation scheme (PTAS) for the subset Traveling Salesperson Problem (TSP) in minor-free graphs. This resolves a long standing open problem in a long line of work on designing PTASes for TSP in minor-closed families initiated by Grigni, Koutsoupias, and Papadimitriou [FOCS'95]. The main technical ingredient in our PTAS is a construction of a nearly light subset $(1+\epsilon)$-spanner for any given edge-weighted minor-free graph. This construction is based on a necessary and sufficient condition given by sparse spanner oracles: light subset spanners exist if and only if sparse spanner oracles exist. This relationship allows us to obtain two new results:
    • A $(1+\epsilon)$-spanner with lightness $O(\epsilon^{-d+2})$ for any doubling metric of constant dimension $d$. This improves the earlier lightness bound $\epsilon^{-O(d)}$ obtained by Borradaile, Le and Wulff-Nilsen [SODA`19].
    • A $(1+\epsilon)$-spanner with sublinear lightness for any metric of constant correlation dimension. Previously, no spanner with non-trivial lightness was known.
  • Truly Optimal Euclidean Spanners.
    Hung Le and Shay Solomon
    The 60th Annual IEEE Symposium on Foundations of Computer Science. FOCS 2019.
    [PDF][ICERM Talk][FOCS Talk][Oded’s choices]
    [Invited to SICOMP Special Issue][Invited to HALG 2020]
    Abstract Euclidean spanners are important geometric structures, having found numerous applications over the years. Cornerstone results in this area from the late 80s and early 90s state that for any $d$-dimensional $n$-point Euclidean space, there exists a $(1+\epsilon)$-spanner with $ O(n\epsilon^{-d+1})$ edges and lightness (normalized weight) $O(\epsilon^{-2d})$. Surprisingly, the fundamental question of whether or not these dependencies on $\epsilon$ and $d$ for small $d$ can be improved has remained elusive, even for $d = 2$. This question naturally arises in any application of Euclidean spanners where precision is a necessity (thus $\epsilon$ is tiny). In the most extreme case $\epsilon$ is inverse polynomial in $n$, and then one could potentially improve the size and lightness bounds by factors that are polynomial in $n$.

    The state-of-the-art bounds $O(n\epsilon^{-d+1})$ and $O(\epsilon^{-2d})$ on the size and lightness of spanners are realized by the greedy spanner. In 2016, Filtser and Solomon [PODC 16] proved that, in low dimensional spaces, the greedy spanner is ``near-optimal''; informally, their result states that the greedy spanner for dimension $d$ is just as sparse and light as any other spanner but for dimension larger by a constant factor. Hence the question of whether the greedy spanner is truly optimal remained open to date.

    The contribution of this paper is two-fold.
    • We resolve these longstanding questions by nailing down the exact dependencies on $\epsilon$ and $d$ and showing that the greedy spanner is truly optimal. Specifically, for any $d= O(1), \epsilon = \Omega({n}^{-\frac{1}{d-1}})$:
      • We show that any $(1+\epsilon)$-spanner must have $\Omega(n\epsilon^{-d+1})$ edges, implying that the greedy (and other) spanners achieve the optimal size.
      • We show that any $(1+\epsilon)$-spanner must have lightness $\Omega(\epsilon^{-d})$, and then improve the upper bound on the lightness of the greedy spanner from $O(\epsilon^{-2d})$ to $O(\epsilon^{-d}\log \frac{1}{\epsilon})$.
    • We then complement our negative result for the size of spanners with a rather counterintuitive positive result: Steiner points lead to a quadratic improvement in the size of spanners! Our bound for the size of Steiner spanners is tight as well (up to lower-order terms).
  • Engineering a PTAS for Minimum Feedback Vertex Set in Planar Graphs
    Glencora Borradaile and Hung Le and Baigong Zheng
    The 17th International Symposium on Experimental Algorithms. SEA 2019.
    Abstract We investigate the practicality of approximation schemes for optimization problems in planar graphs based on balanced separators. The first polynomial-time approximation schemes (PTASes) for problems in planar graphs were based on balanced separators, wherein graphs are recursively decomposed into small enough pieces in which optimal solutions can be found by brute force or other methods. However, this technique was supplanted by the more modern and (theoretically) more efficient approach of decomposing a planar graph into graphs of bounded treewidth, in which optimal solutions are found by dynamic programming. While the latter approach has been tested experimentally, the former approach has not.

    To test the separator-based method, we examine the minimum feedback vertex set (FVS) problem in planar graphs. We propose a new, simple $O(n \log n)$-time approximation scheme for FVS using balanced separators and a {\em linear kernel}. The linear kernel reduces the size of the graph to be linear in the size of the optimal solution. In doing so, we correct a reduction rule in Bonamy and Kowalik's linear kernel for FVS. We implemented this PTAS and evaluated its performance on large synthetic and real-world planar graphs. Unlike earlier planar PTAS engineering results, our implementation guarantees the theoretical error bounds on all tested graphs.
  • Greedy Spanners are Optimal in Doubling Metrics
    Glencora Borradaile and Hung Le and Christian Wulff-Nilsen
    The 30th ACM-SIAM Symposium on Discrete Algorithms. SODA 2019.
    Abstract We show that the greedy spanner algorithm constructs a $(1+\epsilon)$-spanner of weight $\epsilon^{-O(d)}w(\mathrm{MST})$ for a point set in metrics of doubling dimension $d$, resolving an open problem posed by Gottlieb [FOCS 15]. Our result generalizes the result by Narasimhan and Smid who showed that a point set in $d$-dimension Euclidean space has a $(1+\epsilon)$-spanner of weight at most $\epsilon^{-O(d)}w(\mathrm{MST})$. Our proof only uses the packing property of doubling metrics and greatly simplifies the proof of the same result in Euclidean space.
  • Local Search is a PTAS for Feedback Vertex Set in Minor-free Graphs
    Hung Le and Baigong Zheng
    The 25th International Computing and Combinatorics Conference. COCOON 2019.
    [PDF][TCS][Invited to TCS Special Issue!]
    Abstract We show that an extremely simple local search gives a PTAS for the Feedback Vertex Set (FVS) problem in minor-free graphs. It keeps exchanging a constant number of vertices to improve the current solution until a local optimum is reached. The previous PTAS by Fomin, Lokshtanov, Raman and Saurabh, despite theoretical efficiency, is much more complicated in the sense that it combines many advanced algorithmic tools such as contraction decomposition framework by Demaine and Hajiaghayi, Courcelle's theorem and the Robertson and Seymour decomposition.

    Our main technical contribution is to show that the local optimum only differs the global optimum by a $(1+\epsilon)$ factor. We do so by introducing Steiner points, those who are not in the local and optimal solutions, to the standard analysis of local search. We believe that our technique is of independent interest.
  • Minor-free Graphs have Light Spanners
    Glencora Borradaile and Hung Le and Christian Wulff-Nilsen
    The 58th Annual IEEE Symposium on Foundations of Computer Science. FOCS 2017.
    Abstract We show that every $H$-minor-free graph has a light (1+ε)-spanner, resolving an open problem of Grigni and Sissokho and proving a conjecture of Grigni and Hung. Our lightness bound is: $$O(\frac{|V(H)\sqrt{\log |V(H)|}|}{\epsilon^3}\log\frac{1}{\epsilon})$$ That is, it has a practical dependency on the size of the minor H. Our result also implies that the polynomial time approximation scheme (PTAS) for the Travelling Salesperson Problem (TSP) in H-minor-free graphs by Demaine, Hajiaghayi and Kawarabayashi is an efficient PTAS whose running time is $2^{\mathrm{poly}(\frac{1}{\epsilon})}n^{O(1)}$ Our techniques significantly deviate from existing lines of research on spanners for H-minor-free graphs, but build upon the work of Chechik and Wulff-Nilsen for spanners of general graphs.
  • Embedded-width: A Variant of Treewidth for Plane Graphs.
    Glencora Borradaile and Jeff Erickson and Hung Le and Robbie Weber
    Abstract We define a special case of tree decompositions for planar graphs that respect a given embedding of the graph. We study the analogous width of the resulting decomposition we call the embedded-width of a plane graph. We show both upper bounds and lower bounds for the embedded-width of a graph in terms of its treewidth and describe a fixed parameter tractable algorithm to calculate the embedded-width of a plane graph. To do so, we give novel bounds on the size of matchings in planar graphs.
  • A Better Bound on the Largest Induced Forests in Triangle-free Planar Graphs.
    Hung Le
    Graphs and Combinatorics.
    Abstract It is well-known that there exists a triangle-free planar graph of $n$ vertices such that the largest induced forest has order at most $\frac{5n}{8}$. Salavatipour proved that there is a forest of order at least $\frac{5n}{9.41}$ in any triangle-free planar graph of $n$ vertices. Dross, Montassier and Pinlou improved Salavatipour's bound to $\frac{5n}{9.17}$. In this work, we further improve the bound to $\frac{5n}{9}$. Our technique is inspired by the recent ideas from Lukot'ka, Mazak and Zhu.
  • Large Induced Acyclic and Outerplanar Subgraphs of Low-treewidth Planar Graphs.
    Glencora Borradaile and Hung Le and Melissa Sherman-Bennett
    Graphs and Combinatorics.
    Abstract Albertson and Berman conjectured that every planar graph has an induced forest on half of its vertices. The best known lower bound, due to Borodin, is that every planar graph has an induced forest on two fifths of its vertices. In a related result, Chartran and Kronk, proved that the vertices of every planar graph can be partitioned into three sets, each of which induce a forest.

    We show tighter results for $2$-outerplanar graphs. We show that every $2$-outerplanar graph has an induced forest on at least half the vertices by showing that its vertices can be partitioned into two sets, each of which induces a forest. We also show that every $2$-outerplanar graph has an induced outerplanar graph on at least two-thirds of its vertices.
  • Light Spanners for Bounded Treewidth Graphs Imply Light Spanners for H-minor-free Graphs.
    Glencora Borradaile and Hung Le
    Abstract Grigni and Hung conjectured that $H$-minor-free graphs have $(1 + \epsilon)$-spanners that are light, that is, of weight $g(|H|,\epsilon)$ times the weight of the minimum spanning tree for some function $g$. This conjecture implies the efficient polynomial-time approximation scheme (PTAS) of the traveling salesperson problem in $H$-minor free graphs; that is, a PTAS whose running time is of the form $2^{f(\epsilon)}n^{O(1)}$ for some function f. The state of the art PTAS for TSP in H-minor-free- graphs has running time $n^{\mathrm{poly}(1/\epsilon)}$. We take a further step toward proving this conjecture by showing that if the bounded treewidth graphs have light greedy spanners, then the conjecture is true. We also prove that the greedy spanner of a bounded pathwidth graph is light and discuss the possibility of extending our proof to bounded treewidth graphs.
  • An Optimal Dynamic Program for r-Dominating Set over Tree Decompositions.
    Glencora Borradaile and Hung Le
    The 11th International Symposium on Parameterized and Exact Computation. IPEC 2016.
    Abstract There has been recent progress in showing that the exponential dependence on treewidth in dynamic programming algorithms for solving NP-hard problems are optimal under the Strong Exponential Time Hypothesis (SETH). We extend this work to $r$-domination problems. In $r$-dominating set, one wished to find a minimum subset S of vertices such that every vertex of $G$ is within $r$ hops of some vertex in $S$. In connected $r$-dominating set, one additionally requires that the set induces a connected subgraph of $G$. We give a $O((2r + 1)^{\mathrm{tw}}n)$ time algorithm for $r$-dominating set and a $O((2r + 2)^{\mathrm{tw}}n^{O(1)})$ time algorithm for connected $r$-dominating set in $n$-vertex graphs of treewidth $\mathrm{tw}$. We show that the running time dependence on $r$ and $\mathrm{tw}$ is the best possible under SETH. This adds to earlier observations that a "+1" in the denominator is required for connectivity constraints.