Complexity on Forbidden-Minor Planets?

Erik Demaine is a theorist with many interests: from Origami, to games and puzzles; from computational graph theory, to many other areas of mathematics. He is reportedly the youngest assistant professor ever at MIT—he joined the faculty at the age of 20. According to information on his website he has been appointed a full professor effective next month, so we congratulate him.

Today I want to discuss how to extend the theory of minor-free graphs, and get potentially new results.

Restricting inputs to graphs without certain minors, forbidden minors, is like doing complexity theory on a different planet, as many famous hard problems drop down to polynomial time. The old and famous science-fiction movie Forbidden Planet features a “Plastic Educator” device that greatly enhances a human’s cognitive power; forbidding minors seems to do the same for algorithms. Perhaps Demaine has used the device himself.

Demaine’s work that is most relevant to our discussion is on algorithmic graph theory, especially that part that is based on the theory of graph minors. Still he found time to write a quite beautiful book on the complexity theory of one, two, and more player games. This is joint with Robert Hearn and is a delightful read—as Peter Winkler says on the back cover:

this beautifully composed and fascinating volume

The book is clear, insightful, and filled with colorful figures and diagrams. If you want to understand why playing a game is hard, this is the book to read.

Graph Minors

A graph is a minor of a graph provided there is a series of contractions of edges that when performed on eventually yield . This is well known to be a partial order on the space of finite undirected graphs. The following show the notion in a simple case:

Here are the contractions:

Forbidden

The beautiful theory of graph minors, thanks to the brilliant work of Neil Robertson and Paul Seymour, allows theorems of the following kind to be proved:

Theorem: If is a graph that does not have as a minor, then there is an algorithm that runs in polynomial time and can

The is always something that we cannot perform fast on general graphs. It can be a faster exact solution, or can be a better approximation result than what is known for general graphs. For example, Demaine, Mohammadtaghi Hajiaghayi, and Ken-ichi Kawarabayashi proved:

Theorem: For any fixed graph , there is a polynomial-time algorithm that given any graph that does not have as a minor, can find a coloring of with at most colors.

Here is the number of colors needed to vertex-color the graph.

One way to view these wonderful results is as a vast, general improvement over results showing that computing something on a planar graph is easier than on a general graph. Planar graphs are characterized as ones that don’t have the 5-clique or the complete bipartite graph on 3+3 nodes as a minor. It is amazing that the results hold regardless of which graph actually is.

To paraphrase a Mark Twain quotation, there is a charm about the forbidden that makes it unspeakably powerful. Note that if is an edge (i.e., 2-clique) then can be only a trivial graph with no edges, while if is a triangle (3-clique) then is restricted to be a tree. The genius of the results is that forbidding any particular restricts the kind of embeddings a graph may require, and this puts a lid on the complexity.

Not Forbidden—But Restricted

Another way to state the results in an area that is now called the algorithmic theory of graph minors is to use this notion: a graph is –free provided is not a minor of the graph . Thus the last theorem shows that restricting attention to graphs that are -free for a fixed graph yields much better approximate colorings. Indeed proving a theorem without the restriction to graphs that do not contain a forbidden minor would show that .

The simple idea that I wish to discuss is the following: many of the existing results on graphs without a forbidden minor can be generalized. The idea is to allow to have as a minor, but not to allow to have too many copies of . Suppose for the moment that is the number of copies of as a minor in —I will define what I mean in a moment. Here is a sample theorem:

Theorem: If is a general graph, then there is an algorithm that runs in polynomial time and can find a coloring of with at most colors.

Clearly if there are no copies of , then and this is the old theorem. But if there are relatively few copies of , then this is an improvement. Note that the number of copies can be quite large, and still the result will be interesting.

Somehow this idea reminds me of the following dialogue from Pirates of the Caribbean: The Curse of the Black Pearl. Elizabeth is Miss Turner and Barbossa is the “evil” pirate captain.

Elizabeth: Wait! You have to take me to shore. According to the Code of the Order of the Brethren

Barbossa: First, your return to shore was not part of our negotiations nor our agreement so I must do nothing. And secondly, you must be a pirate for the pirate’s code to apply and you’re not. And thirdly, the code is more what you’d call “guidelines” than actual rules. Welcome aboard the Black Pearl, Miss Turner.

Being minor-free is not a rule, it’s more like a guideline.

The Proof

Let be the graph we wish to color, and let be a fixed graph. The algorithm operates in two stages. The first stage is:

1. Let and be an empty set of edges. During the following will always be a subgraph of and a set of edges of .
2. Check if is -free. If it is, then stop and return .
3. Find an embedding of into and remove one edge. Let be the graph created after deleting this edge and put the edge into .

When this halts—it must—note that is -free. For the next stage, use the existing algorithm to color . This uses at most

colors. But we must color , not . So we put back each edge of to , which eventually yields . But as we place the edges back we must make sure that the graph is properly colored. If on placing an edge back its endpoints have the same colo,r then we simply use a new color for one of the endpoints. This method uses at most

colors.

The same idea will work for many other algorithms that rely on a graph having a forbidden minor. For another very different type of result, we claim:

Theorem: Suppose that is fixed. Then graph isomorphism can be done on a pair of graphs in time:

This is based on a wonderful theorem of Martin Grohe—see here.

The Definition

Let’s now define the notion precisely. It is not that hard, but does require some care. The goal is to make the above method work. Usually we define notions, then prove theorems. But in research that is not how things often go. Often we craft a definition so that some theorem will become true. This happens more often than you might realize.

The lemma we want to make true is:

Lemma: For any there is an algorithm that given any removes at most edges from to yield a graph that is -free.

Here is our definition. Let be graphs. Suppose that . Say that is –embedded in provided that after performing contractions on all the edges not in , the graph that remains is isomorphic to . Define to be the number of sets so that is -embedded in . I claim that the above lemma is true for this definition.

An important observation: the definition works, I believe, as claimed. However, it can be very weak in some cases, which suggest that there should be a better definition. For example, consider the graph that is an cycle. Also let be a triangle. Then, is cubic in —yet the removal of one edge is enough to eliminate all minors.

Open Problems

What theorems can we prove with this method? I also wonder whether the bounds on the coloring result can be improved. More precisely, can one improve to ? Also, is there a better definition of the key notion ?