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 [...]

Read Full Post »

Hardness of Graph Isomorphism of Bounded TreeWidth Graphs

If you read my earlier post you know that I am obsessed with the following open problem : Is there a logspace algorithm for Graph Isomorphism of bounded treewidth graphs ? This problem is at the intersection of three of my research interests (graph isomorphism, tree width and space-bounded computation. See my earlier posts (here, [...]

Read Full Post »