In the Steiner Point Removal (SPR) problem, we are given an undirected, edge-weighted graph \(G=(V,E,w)\) and a subset of vertices \(K\subseteq V\), called terminals. Non-terminal vertices of \(G\) are called Steiner points. The goal is to find an (edge-weighted) minor \(M\) of \(G\) that only contains the terminal set \(K\) and (approximately) preserves the terminal distances:
\[d_G(t_1,t_2)\leq d_M(t_1,t_2) \leq \alpha \cdot d_G(t_1,t_2)\]
The constant \(\alpha\) is called the distortion of \(M\). We want to construct \(M\) such that \(\alpha\) is as small as possible, ideally \(\alpha = 1\). We call \(M\) the distance preserving minor. Since \(M\) only contains the terminals, by constructing \(M\), we effectively remove Steiner points from \(G\) and hence the name Steiner Point Removal (SPR).
We have the freedom to set the weights of the edges of \(M\) arbitrarily as long as the terminal distances are not contracted. In all known constructions, we often set the weight of each edge \((t_1,t_2) \in E(M)\) to be \(d_G(t_1,t_2)\).
So, what is a minor? The formal definition is: a minor of \(G\) is a graph obtained from \(G\) by deleting vertices, deleting edges, and contracting edges. However, this formal definition is often not useful in constructing a distance-preserving minor. A more intuitive way to think about minor is: every terminal \(t\in K\) has a corresponding subgraph \(H_t\) in \(G\) such that (a) all the graphs \(\{H_t: t\in K\}\) are pairwise vertex-disjoint and (b) there exists an edge \((x,y) \in E(M)\) if there is an edge \((u,v)\) in \(G\) connecting a vertex \(u\in H_x\) and a vertex \(v\in H_y\).
Figure 1: (a) Four terminals in a graph, (b) the disjoint subgraphs associated with each terminal, and (c) a distance-preserving minor. The distortion is \(4/3\) realized by the terminal pair \((t_2,t_3)\).
Why a distance-preserving minor? There are several ways one could construct a graph preserving distances, such as those studied in spanners and emulators literature. However, these graphs often do not preserve structural properties of \(G\): for example, if \(G\) is planar, then these graphs might not be planar. A distance-preserving minor aims to preserve both distances and minor structures: if \(G\) is planar or excludes a fixed minor, then \(M\) also has the same property.
Gupta was the first to study the problem of removing Steiner points in trees: given a set of terminals \(K\) in a tree \(T\), find another tree \(T_K\) spanning the terminals such that the terminals distances in \(T_K\) are approximately the same as the terminal distances in \(T\) up to a small distortion \(\alpha\). Gupta showed that \(\alpha = 8\) is achievable for trees and showed a lower bound \(\alpha\geq 4(1-o(1))\). Chan, Xia, Konjevod, and Richa observed that the tree \(T_K\) in Gupta’s construction is indeed a minor of \(T\), and further improved the lower bound of Gupta to \(\alpha\geq 8(1-o(1))\), matching the upper bound.
Since preserving the minor structure is central in distance-preserving minor, a natural question is:
Question 1: Does every \(K_r\)-minor-free graph for any fixed \(r\) admit a distance-preserving minor with a constant distortion?
This question was raised in the work of Chan, Xia, Konjevod, and Richa as well as an unpublished manuscript by Basu and Gupta.
One could ask same question for general graphs:
Question 2: What is the smallest distortion achieved for the SPR problem in general graphs?
Both questions have attracted significant research interest over the last decade. Until recently, Question 1 remained wide open: no constant upper bound, even for planar graphs. On the other hand, there has been steady progress on the upper bound of Question 2. Filtser showed the distortion \(O(\log \lvert K\rvert)\) for general graphs. However, the best lower bound remains 8 in both cases.
In this post, I am happy to report very recent progress on both questions. Our recent paper resolved Question 1 positively, while Chen and Tan showed the first non-constant lower bound of \(\tilde{\Omega}(\sqrt{\log \lvert K\rvert})\) for Question 2, narrowing the gap with the upper bound of \(O(\log \lvert K\rvert)\) by Filtser. Coincidentally, both papers will appear in SODA 2024.
SPR in Minor-Free Graphs
SPR in minor-free graphs is one of my favorite problems in grad school. I could not make any significant progress back then despite investing a non-trivial amount of time. An important intermediate step to Question 1 is planar graphs. This problem remains very difficult: we only know the answers for very special cases of planar graphs. Basu and Gupta showed a constant distortion for outer-planar graphs, in which every vertex is on the outerface. More than a decade later, Hershkowitz and Li solved the problem for series-parallel graphs. Series-parallel graphs are planar graphs of treewidth 2.
I largely forgot about the SPR problem in minor-free graphs due to the previous futile attempt. In recent years, I focused more on developing geometric techniques for designing algorithms in planar and minor-free graphs, as described in my recent talk. One key problem in this direction is the tree cover problem: covering planar metrics by as few trees as possible. Together with amazing co-authors — Hsien-Chih Chang, Jonathan Conroy, Lazar Milenkovic, Shay Solomon and Cuong Than— we are able to show that \(O(1)\) trees suffice; the paper will be presented in upcoming FOCS 23.
How does tree cover relate to SPR? To solve the tree cover problem, we developed a new kind of partition that we dubbed shortcut partition. Intuitively, a shortcut partition is a partition of the vertex set into clusters such that for every two vertices \(u\) and \(v\), there exists a low-hop path in the cluster graph connecting the cluster containing \(u\) and the cluster containing \(v\). The inspiration for the shortcut partition is the scattering partition introduced by Filtser. We could show that a shortcut partition exists in planar graphs, while it remains an open problem to construct a scattering partition. In the same paper introducing scattering partition, Filtser showed that a good scattering partition implies a good solution for the SPR problem. This is our starting point, and thanks to Hsien-Chih Chang and Jonathan Conroy, who suggested that shortcut partition may be used in place of scattering partition in the SPR problem. This turned out to be true, and we resolved the SPR problem in planar graphs.
At this point, it is clear to us that to resolve Question 1 fully, we only need to construct a shortcut partition for minor-free graphs. And this is exactly what we did in our latest paper mentioned above.
In the tree cover paper, we constructed a shortcut partition for planar graphs by working with a planar embedding, starting from the outer surface and working toward the inner part of the graph. For minor-free graphs, we have to get around this “planarity barrier”, and we do so by constructing a buffered cop decomposition, a variant of the cop decomposition of minor-free graphs. Our decomposition is inspired by the work of Abraham, Gavoille, Gupta, Neiman, and Talwar. The final shortcut partition construction is rather delicate, and the heavy lifting is largely due to Jonathan Conroy.
Before closing this section, I would like to mention that the shortcut partition has several other algorithmic applications: distance oracles, tree covers, and embedding into bounded treewidth graphs. Exploring these applications should be the topic of another post. In the meantime, do check out our papers for details.
SPR in General Graphs
Kamma,Krauthgamer, and Nguyễn were the first to make a significant headway on SPR for general graphs: they showed that the distortion is \(O(\log^5 \lvert K\rvert)\). Their result was later simplified and improved to \(O(\log^2 \lvert K\rvert)\) by Cheung. Filtser then improved the distortion to \(O(\log \lvert K\rvert)\).
Distortion \(O(\log \lvert K\rvert)\) seems to be the right answer for Question 2; problems that are somewhat related, such as padded decomposition or stochastic embeddings into trees, have logarithmic lower bounds. Of course, it is one thing to speculate on the lower bound; it is another thing to prove it formally. Until recently, the best distortion lower bound is \(8\), which holds for graphs as simple as trees. This is why the result of Chen and Tan is exciting: they showed a distortion lower bound \(\tilde{\Omega}(\sqrt{\log \lvert K\rvert})\). I take their result as a strong indication that the right answer to Question 2 is \(\Theta(\log \lvert K\rvert)\). What’s more interesting is that the proof of Chen and Tan is very clever and simple; the main argument is just about 3 pages. Any summarization of their argument will not be shorter than their full proof, so go ahead and read it.
Closing Thoughts
I must give a big shout-out to Arnold Filtser, who has consistently worked on SPR on both general and minor-free graphs for years. Arnold’s series of papers inspire and pave the way for the recent development. There are two interesting open problems:
-
Nailing down the exact distortion for the SPR problem in planar graphs. We showed \(O(1)\) distortion, but the constant is big, up to thousands. The current best lower bound is 8. I will stick my neck out to conjecture that 8 is the right distortion bound. I am happy to see either a proof or a disproof.
-
Improving the lower bound of Chen and Tan to \(\Omega(\log k)\). This will completely resolve Question 2.