Skip to content

Contraction and Explosion

June 17, 2019


Different ways of recursing on graphs

TutteBletchley
Bletchley Park 2017 source

William Tutte was a British combinatorialist and codebreaker. He worked in a different group at Bletchley Park from that of Alan Turing. He supplied several key insights and algorithms for breaking the Lorenz cipher machine. His algorithms were implemented alongside Turing’s on Colossus code-breaking computers.

Today we discuss graph recursions discovered by Tutte and Hassler Whitney.

Tutte wrote a doctoral thesis after the war on graph theory and its generalization into matroid theory. We will follow the same arc in this and a followup post. He joined the faculty of the universities of Toronto and then Waterloo, where he was active long beyond his retirement.

For more on Tutte and his work, see this article and lecture by Graham Farr, who is a professor at Monash University and a longtime friend of Ken’s from their Oxford days. We covered some of Tutte’s other work here.

Deletion and Contraction

The two most basic recursion operations are deleting and contracting a chosen edge {e} in a given graph {G = (V,E)}:

deletion_contraction

These operations produce graphs denoted by {G \setminus e} and {G/e}, respectively. A motive for them harks back to Gustav Kirchhoff’s counting of spanning trees:

  • A spanning tree of {G} avoids using edge {e} if and only if it is a spanning tree of the graph {G \setminus e} with {e} deleted.

  • A spanning tree of {G} uses edge {e} if and only if the rest of it is a spanning tree of the graph {G/e} after contracting {e}.

Well, this is not how Kirchhoff counted trees. Counting via the recursion would take exponential time. Our whole object will be telling which cases of the recursions can be computed more directly.

Note that contracting one edge of the triangle graph {C_3} produces a multi-graph {C_2} with one double-edge. Then contracting one edge of {C_2} yields the loop graph {C_1}.


triangle


Thus contraction yields non-simple undirected graphs, but the logic of counting their spanning trees remains valid.

The order of edges does not matter as long as one avoids disconnecting the graph, and the base case is a tree (ignoring any loops) which contributes {1}.

Tutte’s Polynomial

A similar recursion counts colorings {c: V \rightarrow \{1,...,k\}} that are proper, meaning that for each edge {e = (u,v)}, {c(u) \neq c(v)}.

  • A proper coloring {c} of {G \setminus e} makes {c(u) \neq c(v)} iff it is a proper coloring of {G}.

  • A proper coloring {c} of {G \setminus e} makes {c(u) = c(v)} iff it induces a proper coloring of {G/e}.

This leads to the recursive definition of the chromatic polynomial:

\displaystyle    P_G(x) = P_{G\setminus e}(x) - P_{G/e}(x).

The base cases are that an isolated vertex contributes {x}, whereas an isolated loop contributes {0} since its single edge is never properly colored. The final rule is that {P_G(x)} is always the product of {P_H(x)} over all connected components {H} of {G}. Then {P_G(k)} counts the number of proper {k}-colorings.

This is like the recursion for coutning spanning terees except for the minus sign. Tutte’s brilliant insight, which was anticipated by Whitney in less symbolic form, was that the features can be combined by using two variables {x} and {y}. Call an edge a bridge if it is not part of any cycle. If {e} is not a bridge, the recursion is

\displaystyle    T_G(x,y) = T_{G \setminus e}(x,y) + T_{G/e}(x,y).

The base case is now a graph {G} with some number {k} of bridges and some number {\ell} of loops, which gives {T_G(x,y) = x^k y^\ell}. An important feature is that all {n}-vertex trees have the same Tutte polynomial {x^{n-1}}, since there are {n-1} edges and they are all bridges. The following are just some of the beautiful rules that {T_G} follows. Let {c = c_G} stand for the number of connected components of {G}.

  • {T_G(1,1)} counts the number of spanning trees forests. This counts the number of spanning trees if {G} is connected.

  • {T_G(1-x,0)}, when multiplied by {(-1)^{n-c} x^c}, yields the chromatic polynomial.

  • {T_G(1,2)} counts the number of spanning subgraphs.

  • {T_G(2,2)} is just {2^{|E|}}.

  • {T_G(x,\frac{1}{x})} gives the Jones polynomial of a knot related to {G}.

There are many further relations. The Jones polynomial has many applications including in quantum physics.

Contraction With a Twist

Recall our definition of the “amplitude” {a(G)} of an undirected {n}-vertex graph {G} from the “Net-Zero Graphs” post:

\displaystyle    a(G) = \frac{c_0 - c_1}{2^n},

where {c_0} is the number of black-and-white 2-colorings that make an even number of edges have both nodes colored black, and {c_1} for an odd number.

There does not seem to be a simple recursion for {a(G)} from {G \setminus e} and {G/e}. We can, however, obtain one by using another kind of contraction that adds a loop at the combined vertex:

inchworm_contraction

We denote this by {G/\!/e}. We have not found a simple reference for this. We obtain the following recursive formula:

\displaystyle    a(G) = a(G\backslash e) + \frac{1}{2}a(G/\!/e) - \frac{1}{2}a(G/e).

This recursion allows {e} to be a bridge, so the base cases are {1} for an isolated vertex and {0} for a loop. More generally, the basis is {1} for a node with an even number of loops, {0} for odd. Here is an example for the ‘star graph’ {S_4} on 4 vertices:


starGraph


The diagram would need another layer to get down to (products of) base cases, which we have shortcut by putting values of {a(H)} for each graph {H} at a leaf. Adding the products over all branches gives {a(G)}. For the star graph,

\displaystyle    a(S_4) = \frac{1}{2} + \frac{1}{4} - \frac{1}{4} + \frac{1}{4} + \frac{1}{8} - \frac{1}{8} - \frac{1}{4} - \frac{1}{8} + \frac{1}{8} = \frac{1}{2}.


Clearly this brute-force recursion grows as {3^n}. This is slower than the order-{2^n} time of using the coloring definition directly, but what all this underscores is how singular it is to be able to compute {a(G)} in polynomial time, indeed {O(n^\omega)} time. The search for a more-efficient recursion, one that might apply to {\mathsf{NP}}-hard quantities, leads us to consider a more-drastic operation on edges.

Exploding Edges

The new recursion operation is well illustrated by this figure:


explosionSolo


Two vertices disappear, not just one. Not only does the edge {e = (u,v)} disappear, but any other edge incident to {u} or {v} from a vertex {w \neq u,v} gets “recoiled” into a loop at {w}. We denote this operation by {G \backslash\!\backslash e} to connote that {e} is not just deleted but “exploded.”

Properly speaking, we need to specify what happens if there are other edges between {u} and {v} or loops at {u} or {v}. In an upcoming post we will see that those become circles in a graphical polymatroid which generalizes the notion of a graph. For now, however, it suffices to let {r} be the total number of vaporized edges, including {e}. Then we obtain a two-term recursive formula:

\displaystyle    a(G) = a(G \backslash e) + \frac{(-1)^r}{2} a(G\backslash \!\backslash e).   \ \ \ \ \ (1)

The base cases for isolated vertices are the same as before, but explosion also needs a base case for pure emptiness. This contributes {1}. In the following example diagram, for the path graph {P_4} on four nodes, we denote such base cases by `w’ for “wisp”:

P3explosion

Note again the rule that when the recursion disconnects the graph, the component values multiply together. Thus the value is

\displaystyle    a(P_4) = (1 - \frac{1}{2})(1 - \frac{1}{2}) - 0 = \frac{1}{4}.

This is different from the amplitude {\frac{1}{2}} of the star graph. What this means is that {a(G)} does not obey the rules of the Tutte polynomial, which is the same for both of these 4-vertex trees.

To prove the recursion equation (1), for {e = (u,v)}, note that every coloring has the same odd/even parity of black-black edges for {G\setminus e} as for {G} except those that color both {u} and {v} black. Let {c_0^{uv}} denote the colorings among the latter that make an even number of black-black edges (including {e}) overall, {c_1^{uv}} for an odd number. Then

\displaystyle    a(G) = a(G \setminus e) + \frac{2}{2^n}(c_1^{uv} - c_0^{uv}).

Now if there are no other edges between or loops at {u} and {v}, then {c_1^{uv}} is the same as the number of colorings of {G \backslash\!\backslash e} that make an even number of black-black edges, and {c_0^{uv}} becomes the odd case in {G \backslash\!\backslash e} again because we subtracted {e}. Considering the sign change from other {(u,v)} edges or loops and {\frac{2}{2^n} = \frac{1/2}{2^{n-2}}} yields equation (1). It is also possible to “explode” a loop, and our readers may enjoy figuring out how to define it.

The Amplitude Polynomial

We can expand on this by defining a polynomial {Q_G(x)} such that {a(G) = Q_G(1)}. The base cases are {x} for an isolated vertex but still {1} for a “wisp” and {0} for a loop. The basis extends to give {x} for an isolated node with an even number of loops and {0} for odd. Another way to put it is that two edges with the same endpoints, or two loops at the same node, can be removed. The above diagram shows that for the path graph {P_4},

\displaystyle    Q_{P_4}(x) = (x^2 - \frac{1}{2})^2 = x^4 - x^2 + \frac{1}{4}.

Whereas, the recursion for the star graph—noting that the “star” {S_2} on two nodes is just a single edge—gives:

\displaystyle  \begin{array}{rcl}    Q_{S_4}(x) &=& xQ_{S_3}(x) - \frac{1}{2}0\\   &=& x^2 Q_{S_2}(x) - \frac{1}{2}0 - \frac{1}{2}0\\   &=& x^4 - x^2 \frac{1}{2}(1\!\cdot\! 1) - \frac{1}{2}0 - \frac{1}{2}0 = x^4 - \frac{1}{2}x^2.   \end{array}

This is not the same polynomial as {Q_{P_4}(x)}, again implying that {Q_G(x)} is not a specialization of the Tutte polynomial. We will show in the last post in this series that {Q_G(x)} does specialize the polynomial {S_G(x,y)} introduced in this 1993 paper titled, “A Characterization of Tutte Invariants of 2-Polymatroids” and covered further in this 2006 paper.

Open Problems

What other rules does our “amplitude polynomial” follow? We will explore this in the mentioned upcoming post. What other quantities can it be made to count?

What we called “explosion” is in fact attested as the natural form of contraction for the polymatroids considered in these papers. What further uses might “explosion” have in graph theory apart from polymatroids?

Advertisements
8 Comments leave one →
  1. June 17, 2019 7:32 am

    There’s a type of contraction operation that figures prominently in my application of cactus graphs to propositional calculus. It’s a rule of inference I call it the Spike Rule and it has the following shape:

    Cactus Graph Spike Rule

    I’ll add more links one at a time …

  2. Paul Beame permalink
    June 17, 2019 7:43 pm

    Surely, the photograph of Tutle should be tagged with the 1940’s rather than the date of his posthumous centenary celebration in 2017!

    • June 19, 2019 5:38 pm

      The source page dates to 2017 and was the 2017 celebration. We try to make the caption text line up with the desired photo size if possible…

  3. June 18, 2019 3:00 pm

    Why does the brute-force recursion give 3^n? It seems to me that you allow multiple loops on the same vertex, but this is unnecessary, it’s enough to count the parity. Wouldn’t this take down the time to 2^n?

    • June 19, 2019 5:42 pm

      The equation has a 3-way branch is all that was meant. Ah, what we wrote is indeed cavalier: on one hand, the first term is recursing on edges not “n” as in vertices; on the other, the recursions might overlap down the road.

Trackbacks

  1. A Matroid-Quantum Connection | Gödel's Lost Letter and P=NP

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s