Rambling on Graphs

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