Title: Computing Graph Roots

Speaker: Lap Chi Lau

University of Toronto

Date: Friday Oct 14, 2005
Time 11-12 Venue: Room 3464, HKUST   


Abstract 
Root and root finding are concepts familiar to most branches of mathematics.
In graph theory, 
graph H  is a root of graph G if there  
exists a positive integer K such that
x and y are adjacent in G if and only if their distance 
in H is at most K
Generally, it is a difficult task to determine whether a given graph 
G has a K-th root or not;
Motwani and Sudan proved the NP-completeness of recognizing squares of graphs, 
and conjectured the NP-completeness of recognizing squares of bipartite graphs.
On the other hand, until recently, 
trees are the only non-trivial family of graphs where the 
power recognition problem is known to have a polynomial time algorithm.
The following are the main results presented in this talk:
o   Contrary to Motwani and Sudan's conjecture, we show that
   recognizing bipartite squares can be solved in polynomial time.
   We complement the above result by proving the NP-completeness
   of recognizing cubes of bipartite graphs.
o  Extending the techniques developed, 
   we show that computing a graph k-th root
   with girth 3k+1, if it exists, can be solved in polynomial time.
   This, as a consequence, gives an algorithmic proof that 
   graph square roots with girth 7 are unique up to isomorphism.
   (Joint work with Babak Farzad.)
o  We present the first polynomial time algorithm to recognize 
   k'th-th powers of proper interval graphs for every fixed k
   On the other hand, 
   we show that several variants of this problem are NP-complete.
   (Joint work with Derek Corneil.)
We end this talk with open problems and discussions.