Another useful concept in simple graph theory is *contraction* and its result, *minors*
of graphs. The idea is that there are several ways of simplifying a graph in order to study
its properties: cutting edges, removing vertices, and decomposing a graph are all methods we’ve seen before. Contraction is a different technique that works by *merging* vertices, rather than removing them.
Here’s how contraction works. Suppose you have a graph G. Pick a pair of vertices v and w
which are adjacent in G. You can create a graph G’ which is a contraction of G by
replacing v and w with a *single* vertex, and taking any edge in G which is incident on
either v or w, and making it incident on the newly contracted node.
It’s much clearer
in a picture: for example, look at the series of graphs to the right. The first one is
the original graph. Below it, we create a new graph by contracting vertices D and K. D
was adjacent to B, K, and E; K was adjacent to F, G, and D. We *merge* D and K by contracting along the edge connecting them, and the new vertex is adjacent on B, E, F, and G – the union of the adjacencies of D and K.
Then we contract again – this time doing two contractions at once – first contracting
A,B, and and the merged AB with C. The resulting contracted vertices has the union of the adjacencies of A, B, and C, which are the two vertices DK and F.
Finally, we do one more contraction merging H and J.
Contraction allows us to define a relationship, called *minor*, which can be used to define a partial order over graphs: If we have a graph G, and it can be made isomorphic to a graph
H by some series of contractions, then H is called a *minor* of G.
The ordering is based directly on minors: if H is a minor of G, then H≤G.
There are some really interesting theorems that allow us to define
properties of graph structures in terms of minors. For example, there’s
a theorem called Wagner’s theorem, which says that a graph is planar if and
only if it has neither K5 nor K3,3 as minors. Let’s look
at one example:
We start with an eight-node non-planar graph. To show that it’s non-planar, we can
first contract A,B, and then contract E,G – and we end up with K3,3, which
means that K3,3 is a minor of the original, which proves that it’s non-planar.
Another neat theorem involves minors and snarks – and a mistake from a post a couple of days ago. Every snark has Petersen’s graph as a *minor*. (I said *subgraph* the other day.) Of course, it’s not necessarily easy to find the series of contractions. For example,
here’s a nice 20-vertex snark, with the vertices nicely labeled, and a copy of Petersen’s graph next to it. This snark can be contracted to Petersen’s graph in 10 contractions. See if you can figure out which
vertex-pairs to contract.
Mark,
All this can be written in algebraic topology language. If the graph is regarded as a 1-dimensional CW complex, then being a minor of a graph is equivalent to being a (CW)-quotient of the graph as a complex. All these questions then can be framed as questions about relations between cohomology groups (since cohomology is contravariant, the quotient map trasforms to a map between the cohomology of the minor and the cohomology of the original graph). So my question is:
1) Can we write Wagner’s theorem as a theorem on cohomology groups and subgroups?
2) Does this make anything simpler, or is this simply an abstract nonsense transformation which helps us write in a nifty way (for me at least) but has no advantages?
My knowledge about minor theory in graphs is limited. All I know there is series of papers due to Robertson and Seymour. Is it possible to find any minor in a graph efficiently? Considering the minor K_3,_3 in the example above it appears that this is not the case. In other way how one can order the edges to be contracted in order to find the minor?
PM:
Yes, it can be written in the language of algebraic topology. And some of the time, I think that parts of graph theory can be made more clear by recognizing the fact that they’re just special cases of general topology. Sometimes the discreteness of graphs is an advantage, and the graph theory version is easier to work with; sometimes the discreteness can obscure large structural properties, and the topological approach is easier.
Personally, though, I’ve always struggled with topology (as the number of problems
in my topology posts showed 🙂 ). I actually find the graph theory easier to understand. For me, when I’m trying to grasp a topological point, the way that I often work it out is to find the graph theory equivalent, figure that out, and then use my understanding of that as a handle to wrap my head around the topology.
I’m not sure about Wagner’s theory though. It’s working by exploiting the discrete structure to narrow things down to a small family of excluded cases. I’m not sure how that would scale into the more general world of topology.
Cahit:
That’s a surprisingly difficult question.
A lot of people were convinced that minor-testing was NP-complete. But then a couple of mathematicians by the names of Robertson and Seymour managed to use a *non*-constructive proof to show that it’s possible to do a minor test in O(n3) – a *truly* annoying result. They showed that an algorithm to do it in n3 time must exist – but they didn’t show the algorithm.
To my knowledge, a truly general version of the algorithm is still unknown. (The algorithm relies on something called obstruction sets; if you have the necessary obstruction sets, then you can do the minor test. But I don’t know of any work that
finds the obstruction sets in P-time, although it should be possible.)
Anyway – I’ll be writing more about R-S later, so hold tight, and you’ll see some more details.
Bah, I thought I’d answered your riddle (I’d contracted it down to two linked pentagons), but that can’t quite be manipulated into star-and-pentagon. Curses!
And dammit, now I can’t get anything to work out correctly. >_
Xanthir:
Yeah, it’s really frustrating, isn’t it?
I did it with an unlabeled version of the graph, and then realized that without labeling, it wouldn’t be useful, so I rebuilt the labeled graph – and I haven’t been able to figure out what I did the first time. The closest I’ve been able to get is *almost* petersens – but instead of each point of the star being adjacent to one vertex of the outer pentagon, they’re adjacent to 2.
It’s a fun puzzle, but it’s a *lot* more difficult than it looks.
Xanthir, it helps if you first move the ABCDE pentagon to the outside of the graph. From there, the rest becomes really obvious.
Well, nuts, I just noticed that my preliminary solution has a problem in it. Back to the drawing board (though I think my error was in the second set of 5 contractions….)
🙂 “Consider a finite sets of mathematicians…”
G Barnett, I think you were right. My very first inclination was to move ABCDE outside, because they are no cross-connected, just like the outer pentagon in the Petersen’s graph. Then, it did become very obvious.
My geek pride compels me to post it, but I don’t want to ruin it for others. Quel dilemme!
I would post it in white, but apparently the FONT tag is not recognized in comments by the blog software.
And now I have to sheepishly take back my confidence from before. I just realized my solution leaves the inner star as a pentacle, instead of just a star.
Yeah, we’re all stumbling across the same solutions. Either we get the star, but it’s actually a pentacle, or we get a pentagon which can’t be twisted into a star without ruining the rest of the graph.
Or we just get an unwieldy mess with some 6-vertices. Man, that’s annoying.
Contraction seems to be doing a bitwise OR on the rows of an adjacency matrix for the two merged vertices. What about other binary bitwise operations? Would doing an AND or XOR instead ever be a useful graph operation?
Mark Chu-Carroll:
I strongly suggest the paper
“Algorithmic Graph Minor Theory: Improved Grid Minor Bounds and Wagner’s Contraction” by Erik D. Demaine, MohammadTaghi Hajiaghayi and Ken-ichi Kawarabayashi
for the problems on going research of the algorithmic aspect of graph minor theory.
Jesse:
I don’t know whether it has any use (someone probably has tried), but:
Using AND would correspond to using OR on the graph with the same vertices, but edges exactly where the original graph has none.
Using XOR would preserve total parity. Interestingly, you may not be able to do contractions in any order then: If you have a triangular graph and identify two of the vertices, then the last vertex gets disconnected!