Part II : Hardness of Graph Isomorphism of Bounded TreeWidth Graphs

I did not expect that several researchers are interested in the theorems I announced in my previous post. Here is the proof of one of the theorems :

Theorem : Graph Isomorphism (GI) of graphs of treewidth >= 4 is -hard.

If you want to know the consequences of , read this question posted by Aaron Sterling.

Proof of Theorem : As mentioned in an earlier post, the best known hardness of GI is given by Jacobo Toran. He proved that GI is hard for . Lets focus on his proof of  hardness. He used the following gadget (also used in an earlier paper by Cai, Furer, Immerman) to simulate a parity gate. Let’s call this gadget . Toran proved the following lemma.

Lemma (Toran’2000) : For any , there is a unique automorphism in  mapping to and  to for . This automorphism maps  to

Given any  circuit we first transform the circuit into a tree (by arranging the fan-out connections in a tree-like fashion) and replace each parity gate by the gadget  and obtain a graph . Toran proved that certain automorphisms of graph simulate the precise behavior of the  circuit. See his paper (lemma 3.2 and theorem 3.3) for more details of this reduction. We will now prove the following theorem.

Theorem : Tree width of is four.

Part 1 : Tree-width of  is at most four. To prove this, we use the concept of elimination order. We repeat the following procedure on . Pick a vertex of degree at most 4, delete it and add a clique on its neighbors. This process always terminates on  (resulting in an empty graph), if we choose such vertices in a bottom-up fashion. This proves that is a partial 4-tree and hence its treewidth is at most 4.

Part 2 : Tree-width of  is at least four. To prove this, we will exhibit one of the forbidden minors of graphs of treewidth at most three. Consider the  circuit consisting of only three parity gates (say A, B, C). The outputs of A and B are the inputs to C. Convert this circuit into a graph by replacing the each gate A, B and C with the parity gadget . By contracting and deleting some edges of , we can show that the following graph is a minor of .

Now lets look at the set of all forbidden minors of graphs of tree width at most three. They are shown in the following figure. This figure is take from Wikipedia article, it is drawn by David Eppstein.

Now you can see that the minor we obtained from is isomorphic to one the above forbidden minors. Hence tree width of is at least four.

To prove -hardness for treewidth t >=5, we simply add an isolated clique to the graph . I proved the following stronger theorem for larger values of treewidth.

 Theorem : Graph Isomorphism of graphs of treewidth = t is hard. Here t >= 4 and f(t) is a linear function of t.

The proof of the above theorem is based on a new structural theorem about forbidden minors of graphs with larger treewidth. More details later in my paper.

Update : The above reduction works for parity formulas. I will add more details in the follow-up post.

Advertisement