6.889: Algorithms for Planar Graphs and Beyond (Fall 2011)

In this lecture, we discuss linear-time algorithms for planar graphs that find a small (O(√n)) subset of the nodes whose removal partitions the graph into disjoint subgraphs of size at most 3n/4.

Based on interdigitating trees from Lecture 2, we first devise fundamental-cycle separators. We then show how to reduce the length of these cycles (1) by cutting the graph into pieces with smaller diameter and, if time permits, (2) by merging faces.

In the previous lecture, we saw how to recursively separate a planar graph into small pieces with small total boundary. In this lecture, we see how to obtain a so-called r-division, where each individual piece is guaranteed to have small boundary (as opposed to small total boundary as in the previous lecture). We also discuss how to quickly compute such an r-division. Using an algorithm for fast r-division, we obtain a simple SSSP algorithm for planar graphs that's faster than Dijkstra's algorithm.

We then discuss an even faster algorithm for SSSP in planar graphs. Despite the algorithm being quite simple, somewhat surprisingly, a rather involved analysis proves that its running time is linear, which is asymptotically optimal! We analyze a simplified version running in time O(n log logn). The algorithm works a little bit like Dijkstra's algorithm with “limited attention span”: The simple version starts by decomposing the graph into pieces of size O(log⁴ n). Then, it repeatedly works on the piece with the current minimum for log n steps until the shortest-path distance to all nodes has been found. We (partially) analyze the running time of the simplified algorithm.

[HKRS97] M. R. Henzinger, P. N. Klein, S. Rao, S. Subramanian: Faster shortest path algorithms for planar graphs. In: Journal of Computer and System Sciences, vol. 55(1):pp. 3-23, 1997.
[RW09] B. Reed, D. R. Wood: A linear-time algorithm to find a separator in a graph excluding a minor. In: ACM Transactions on Algorithms, vol. 5(4):pp. 1-16, 2009.
[TM09] S. Tazari, M. Müller-Hannemann: Shortest paths in linear time on minor-closed graph classes, with an application to Steiner tree approximation. In: Discrete Applied Mathematics, vol. 157:pp. 673-684, 2009.
[Taz10, Chapter 5] S. Tazari: Algorithmic Graph Minor Theory: Approximation, Parameterized Complexity, and Practical Aspects. Doctoral Dissertation, Humboldt-Universität zu Berlin, 2010.

In this lecture, we focus on studying a result of Alon, Seymour, and Thomas, stating that every H-minor-free graph admits a small separator and such a separator can be found in polynomial (in fact, subquadratic) time. To this end, we introduce the notion of a haven and show that every graph with a haven of large order must contain a large clique as a minor. We will also briefly discuss how the concept of a knitted H-Partition introduced in the last lecture can be used to find a slightly larger separator in linear time.

Treewidth is a natural parameter of a graph and as we will see, if a graph has small treewidth, then we can solve a large number of NP-hard problems efficiently - regardless of the size of the graph. This takes us to the realm of parameterized complexity theory where we study problems not just with regard to the input size but together with a parameter. The goal is to find algorithms where we confine the exponential behavior to the parameter and remain efficient in the input size; hence, when the parameter is small, we still obtain very good algorithms. Another goal is to develop a robust negative theory that allows us to show that, in all likelihood, certain parameterized problems do not admit efficient algorithms in this sense.

We will then see how to generalize this idea from planar graphs to apex-minor-free graphs. To this end, we introduce the notion of local treewidth, one of the major concepts in algorithmic graph structure theory. For the generalization to H-minor-free graphs we will have to look at the Robertson-Seymour decomposition of H-minor-free graphs into clique-sums of almost embeddable graphs.

All in all, we obtain a clean and simple deletion decomposition theorem for all H-minor-free graphs that can be used to obtain many approximation algorithms, PTASes, and parameterized algorithms.

We discuss data structures that answer node-to-node shortest-path and distance queries in planar graphs. Such data structures are also known as distance oracles. These oracles consist of two algorithms: (1) given a graph G, a preprocessing algorithm constructs a data structure and (2) given the data structure and a pair of nodes (v,w), a query algorithm computes and outputs the distance d(v,w) with respect to G. Three quantities and their tradeoffs are of particular interest: the running times of the preprocessing and query algorithms, and the space requirement of the data structure. We shall see that, for any planar graph and for any integer 1<r<n, there is a distance oracle with preprocessing time and space O(n²/r) and query time O(√r) (up to logarithmic factors).

To obtain these data structures, we shall use r-divisions, MSSP, and an efficient implementation of Dijkstra's algorithm, which we refer to as FR-Dijkstra (due to Fakcharoenphol and Rao). FR-Dijkstra is executed on a rather dense graph with the nodes being the boundary nodes of some pieces of an r-division and the edges representing the shortest paths within these pieces (so-called dense distance graphs). This particular implementation requires time (almost) proportional to the number of nodes only (as opposed to the number of edges, which is much bigger). The edges not considered are redundant and they can be safely ignored due to the Monge property, which essentially says that some shortest paths in planar graphs do not cross.

The efficient implementation of Dijkstra's algorithm and variants thereof also play a crucial role in subsequent lectures on shortest paths with negative lengths and maximum flow.

We discuss data structures that answer approximate node-to-node shortest-path and distance queries in planar graphs. Such data structures are also known as approximate distance oracles. Analogously to exact distance oracles, approximate distance oracles consist of two algorithms: (1) given a graph G and an approximation parameter ε, a preprocessing algorithm constructs a data structure and (2) given the data structure and a pair of nodes (v,w), a query algorithm computes and outputs an estimate for the distance d(v,w) with respect to G. The estimate is supposed to be at most (1+ε) times larger than the actual shortest-path distance (and no smaller).

We shall see that, for any planar graph and for any ε>0, there is a (1+ε)-approximate distance oracle with preprocessing time O((n/ε) log² n) and space O((n/ε) log n) and query time O((1/ε) log n).

To obtain these data structures, we recursively separate the graph by shortest paths. On these path separators, we carefully select a set of portals, through which we approximate shortest paths that intersect with the separator path.

In the Traveling Salesman Problem (TSP) we need to find a shortest tour visiting all the nodes of a graph. For general graphs, there have been recent algorithmic breakthroughs: researchers have found polynomial-time algorithms with approximation ratio strictly below 3/2.

TSP is NP-hard even for planar graphs. In this lecture, we discuss a linear-time approximation scheme for planar graphs. For any constant ε>0, there is an algorithm that finds a tour of length at most (1+ε) times the optimal length of a tour. (Unless P=NP, such an approximation scheme cannot exist for general graphs.)

The TSP algorithm also serves as a beautiful example of a more general framework for efficient approximation schemes in planar graphs.

It may be helpful to review (/ first watch) some of the materials of Lecture 8 on approximation schemes in planar graphs.

In the previous lecture we got acquainted with Klein's framework for designing PTASes in planar graphs and applied it to the TSP problem. In this lecture, we review this framework and see how to apply it to the Steiner tree problem. We will see that the most difficult step is to obtain a spanner. We study the so called mortar graph-brick decomposition and how it gives rise to a spanner. This decomposition has been applied to further problems as well and has been generalized to bounded-genus graphs.

In Lecture 16 we will describe the algorithm and its correctness based on a structure theorem. The structure theorem itself is presented in Lecture 17.

In this lecture we introduce the notion of a tree-cotree decomposition for bounded genus graphs (analogous to interdigitating trees in planar graphs) and use it to obtain a spanner for Steiner tree in bounded genus graphs. Together with the contraction decomposition theorem of Lecture 23 and Klein's PTAS framework, this results in an O(n log n) PTAS for Steiner tree in bounded genus graphs.

Afterwards, we draw a bigger picture of all graph classes we have studied so far and take a peek at graph classes beyond H-minor-free graphs, in particular, classes of bounded expansion and nowhere dense classes of graphs. To understand these classes, we introduce the notion of shallow minors.

Indeed, structural graph theory does not end at H-minor-free graphs!

We revisit the shortest paths problem, considering the case where the input is a directed minor-free graph with negative arc lengths (but no negative-length cycles).

In Lecture 14, we saw almost-linear-time algorithms for the case of planar and bounded-genus graphs. Currently, comparable bounds for minor-free graphs are not known. We shall discuss Goldberg's algorithm, a shortest-path algorithm for general graphs with integer lengths, whose running time depends logarithmically on the magnitude of the largest negative arc length. By exploiting separators (Lecture 6), it runs faster on minor-free graphs than on general graphs, but it still requires superlinear time.