Rambling on Graphs

Computing Diameter of Unit Disk Graphs

This post is about my recent preprint with Hsien-Chih Chang and Jie Gao, on the problem of computing diameter of unit disk graphs. (I have not written about my recent papers, and I think I should write more, especially about things that are not included in the papers.)

A unit disk graph with \(n\) vertices is the intersection graph of \(n\) disks on the plane: two vertices have an edge if their two corresponding disks intersect. Here is an example of a unit disk graph; the figure is by David Eppstein on wikipedia:

A unit disk graph could have \(\Omega(n^2)\) edges and hence we often work with its disk representation that only has \(O(n)\) space, hoping to also design algorithms with \(O(n\mathrm{polylog}(n))\) time. For example, single-source shortest path in unit disk graphs can be solved in \(O(n\log n)\) time. Could we design an algorithm for computing diameter with the same running time? This problem currently seems out of reach. An easier problem is to compute the diameter of unit disk graphs in truly subquadratic time. This turns out to be a long-standing open problem.

read more

Exciting Recent Progress on Steiner Point Removal Problem

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.

read more

DIMACS Workshop on Modern Techniques in Graph Algorithms

I attended the workshop in mid-June, and it is one of the best that I’ve ever attended. Thanks to the organizers, Nicole, Zihan, Prantar, and the DIMACS staff, for working on the logistics and booking flights for all the speakers.

I missed several talks, mostly on the 1st and the last day of the workshop, due to travel constraints. The talks I attended were all excellent. Here I give my brief take on each talk, which is likely erroneous and incomplete.

read more

Separator Theorems

The separator theorem for planar graphs Lipton and Tarjan is the cornerstone of planar graph algorithms: any planar graph of \(n\) vertices can be separated into connected components of size at most \(2(n)/3\) each by removing \(O(\sqrt{n})\) vertices. (An earlier separator theorem by Ungar has a slightly larger size of about \(\sqrt{n}\log^{3/2}n\).) The proof is beautiful but does rquire a non-trivial introduction to planar embedding and its properties, such as the interdigitating tree. My motivation for this post is to look for a proof that does not requires planar embedding. There are many other proofs of the (variants) of the planar separator theorem—see the excellent book chapter by Sariel Har-Peled—but none fits into what I am looking for: a self-contained proof that does not require planar embedding.

To be more precise, I look for a proof that only requires the input graph excluding a fixed minor, \(K_5\) for example in the case of planar graphs. There are two proofs that I particularly like: one by Plotkin, Rao, and Smith [2] and another by Alon, Seymour, and Thomas [1], which work for any graph excluding a fixed minor. I will present both. The central concept is a \(K_h\)-minor model.

\(K_h\)-minor model: a \(K_h\)-minor model of a graph \(G\) is a collection of \(h\) vertex-disjoint connected subgraphs \({\mathcal K} = \{C_1,C_2,\ldots, C_h\}\) of \(G\) such that there is an edge between any two subgraphs. Parameter \(h\) is called the model size.

Figure 1: A graph (left) and its \(K_5\)-minor model (right).

A graph is \(K_h\)-minor-free if it does not have a \(K_h\)-minor model. The Kuratowski’s theorem implies that planar graphs are \(K_5\)-minor-free (and \(K_{3,3}\)-minor-free). Herein we assume that the input graph is \(K_h\)-minor-free, and think of \(h\) as a small constant.

A balanced separator of a graph \(G = (V,E)\) is a subset of vertices \(S\subseteq V\) such that every connected component of \(G\setminus S\) has size at most \(2n/3\). There is nothing special about the constant \(2/3\); any constant smaller than \(1\), for example \(4/5\), works. In some places of this post, we will be handwavy on the constant.

Basic ideas: We will maintain a minor model \({\mathcal K}\) of size \(r\) for some \(r\leq h-1\). At each step, we either increase the model size by \(1\) or find a subset of vertices to add to the separator. This could be achieved, say, by considering a BFS tree rooted at some vertex \(v\), say \(T_v\). There are two cases:

  1. \(T_v\) has low depth, then we add a subtree of \(T_v\) to the current minor model \({\mathcal K}\). Furthermore, the subtree has a small size since we only need to connect the root \(v\) to at most \(h-1\) other subgraphs, each by a (short) path in \(T_v\).
  2. \(T_v\) has alarge depth, then some layer of \(T_v\) will have a small size, and we could add this layer to the separator.

In the end, we find either a \(K_h\)-minor model, certifying that the input graph is not \(K_h\)-minor-free, or a balanced separator of small size. We will also add some vertices in the current minor model to the separator and hence, the fact that subgraphs of the minor model have a small size will help.

Figure 2: (a) Found a tree of small depth rooted at a vertex \(v\), then (b) add a new subgraph to the current \(K_3\)-model to obtain a \(K_4\)-model. (c) The tree rooted at \(v\) has large depth, then (d) find a layer \(X\) of small size to add to the separator.

A major subtlety in this basic strategy is to account for the size of the separator in the 2nd case, as the number of iterations could be very large. Two algorithms presented below have very different accounting techniques. Plotkin, Rao, and Smith [2] use charging: they charge the size of the separator (which basically is a BFS layer) to a smaller component after removing the separator, as the algorithm will recurse on the bigger component. Alon, Seymour, and Thomas [1] incorporated the separator directly to the minor model. The end result is that the algorithm by Plotkin, Rao, and Smith produces a larger separator by a factor of \(\sqrt{\log(n)}\) for a constant \(h\).

read more

Amazing Recent Advances on Shotcut Set and The Likes

Merav Parter gave a talk at UMass theory seminar last week titled “Reachability Shortcuts: New Bounds and Algorithms”. In the talk, Merav summarized recent developments in shortcut sets and related concepts. It was amazing to see all the results, and I cannot resist the attempt to share my take here in this blog post.

1. Shortcut set: what is it?

A \(d\)-shortcut set of a directed graph \(G=(V,E)\) is a set of directed edges \(E_H\) such that (i) the graph \(H = (V,E\cup E_H)\) has the same transitive closure as \(G\) and (ii) for every \(u\not=v\in V\), if \(v\) is reachable from \(u\), then there is directed \(u\)-to-\(v\) path of at most \(d\) edges (a.k.a. hops).

Figure: Adding two shortcuts (the red dashed edges) reduces the hop distance from \(u\) to \(v\) to 4. For a shortcut set of linear size, DAG is the most difficult instance: one can shortcut any strongly connected graph to diameter \(2\) by \(n-1\) edges.

The shortcut set problem was introduced by Thorup. The main goal is to understand the trade-off between the hop diameter \(d\) and the size of the shortcut set \(E_H\). The most well-studied regime is fixing \(\lvert E_H\rvert = \tilde{O}(n)\), and then minimizing \(d\). (Here, \(n\) is the number of vertices.) We will call this special regime the shortcut set problem.

read more

Halperin-Zwick Algorithm for Spanners

This post describes a simple linear time algorithm by Halperin-Zwick [6] for constructing a \((2k-1)\)-spanner of unweighted graphs for any given integer \(k\geq 1\). The spanner has \(O(n^{1+1/k})\) edges and hence is sparse. When \(k = \log n\), it only has \(O(n)\) edges. This sparsity makes spanners an important object in many applications.

This post was inspired by my past attempt to track down the detail of the Halperin-Zwick algorithm. Halperin and Zwick never published their algorithm, and all papers I am aware of cite their unpublished manuscript [6]. The algorithm by Halperin-Zwick is a simple modification of an earlier algorithm by Pelege and Schäffer [8], which, according to Uri Zwick, is the reason why they did not publish their result. The spanner by Pelege and Schäffer [8] has stretch \(4k-3\) for the same sparsity. The idea of Halperin-Zwick algorithm was given as Exercise 3 in Chapter 16 of the book by Peleg [7].

First, let’s define spanners. Graphs in this post are connected.

\(t\)-Spanner: Given a graph \(G\), a \(t\)-spanner is a subgraph of \(G\), denoted by \(H\), such that for every two vertices \(u,v\in V(G)\):

\[d_H(u,v)\leq t\cdot d_G(u,v)\]

Here \(d_H\) and \(d_G\) denote the graph distances in \(H\) and in \(G\), respectively. Graph \(G\) could be weighted or unweighted; we only consider unweighted graphs in this post. The distance constraint on \(H\) implies that \(H\) is connected and spanning.

Parameter \(t\) is called the stretch of the spanner. We often construct a spanner with an odd stretch: \(t = 2k-1\) for some integer \(k\geq 1\). Why not even stretches? Short answer: there is no gain in terms of the worst case bounds for even stretch [1].

read more

Shortcutting Trees

Over the past two years or so, I have been thinking about a cute problem, which turned out to be much more useful to my research than I initially thought. Here it is:

Tree Shortcutting Problem: Given an edge-weighted tree \(T\), add (weighted) edges to \(T\), called shortcuts, to get a graph \(K\) such that:

  1. \(d_K(u,v) = d_T(u,v)~\quad \forall u,v\in V(T)\). That is, \(K\) preserves distances in \(T\).
  2. For every \(u,v\in V(T)\), there exists a shortest path from \(u\) to \(v\) in \(K\) containing at most \(k\) edges for some \(k\geq 2\).

The goal is to minimize the product \(k \cdot \mathrm{tw}(K)\), where \(\mathrm{tw}(K)\) is the treewidth of \(K\).

read more

Sparsity of minor-free graphs

Planar graphs are sparse: any planar graph with \(n\) vertices has at most \(3n-6\) edges. A simple corollary of this sparsity is that planar graphs are \(6\)-colorable. There is simple and beautiful proof based on the Euler formula, which can easily be exteded to bounded genus graphs, a more general case: any graph embedddable in orientable surfaces of genus \(g\) with \(n\) vertices has at most \(3n + 6g-6\) edges.

How’s about the number of edges of \(K_r\)-minor-free graphs? This is a very challenging question. A reasonable speculation is \(O(r)\cdot n\): a disjoint union of \(n/(r-1)\) copies of \(K_{r-1}\) excludes a \(K_r\) minor and has \(\Theta(r)\cdot n\) edges. But this isn’t the case. And surprisingly, the correct bound is \(O(r\sqrt{\log r})n\), which will be the topic of this post.

Theorem 1: Any \(K_r\)-minor-free graphs with \(n\) vertices has at most \(O(r\sqrt{\log r})\cdot n\) edges.

read more