Title: The Isomorphism Problem for k-trees is Complete for Logspace
Speaker: Bireswar Das, IUSSTF Research Fellow-DIMACS
Date: Monday, February 24, 2014 11:00am - 12:00pm
Location: DIMACS Center, CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ
Abstract:
The Graph Isomorphism problem (GI) has received considerable attention since it is one of the few natural problems in NP that are neither known to be NP-complete nor known to be solvable in polynomial time. Though the complexity status of this problem for general graphs remains unknown, several efficient algorithms are known for restricted classes of graphs. In this talk we show that, for k constant, k-tree isomorphism can be decided in logarithmic space by giving an O(k log n) space algorithm. We also prove that k-tree isomorphism is complete for logspace. We show that the automorphism problem and the canonization problem from k-trees are also in deterministic logspace. This is a joint work with V. Arvind, J. Koebler, S. Kuhnert.