Isomorphism for Graphs of Bounded Distance Width

In this paper we study the GRAPH ISOMORPHISM problem on graphs of bounded treewidth, bounded degree, or bounded bandwidth. GRAPH ISOMORPHISM can be solved in polynomial time for graphs of bounded treewidth, pathwidth, or bandwidth, but the exponent depends on the treewidth, pathwidth, or bandwidth. Thus, we look for special cases where ``fixed parameter tractable'' polynomial time algorithms can be established. We introduce some new and natural graph parameters: the (rooted) path distance width, which is a restriction of bandwidth, and the (rooted) tree distance width, which is a restriction of treewidth. We give algorithms that solve GRAPH ISOMORPHISM in O(n ² ) time for graphs with bounded rooted path distance width, and in O(n ³ ) time for graphs with bounded rooted tree distance width. Additionally, we show that computing the path distance width of a graph is NP-hard, but both path and tree distance width can be computed in O(n ^k+1 ) time, when they are bounded by a constant k; the rooted path or tree distance width can be computed in O(ne) time. Finally, we study the relationships between the newly introduced parameters and other existing graph parameters.

Authors and Affiliations

1. Department of Computer Science, Gunmma University 1-5-1 Tenjin-cho, Kiryu, Gunma, 376 Japan. koichi@comp.cs.gunma-u.ac.jp., , , , , , JP

   K. Yamazaki

2. Department of Computer Science, Utrecht University, P.O. Box 80.089, 3508 TB Utrecht, The Netherlands. hansb@cs.uu.nl., , , , , , NL

   H. L. Bodlaender

3. CQM bv., P.O. Box 414, 5600 AK Eindhoven, The Netherlands. defluiter@cqm.nl., , , , , , NL

   B. de Fluiter

4. Department of Computer Science DC 2117, University of Waterloo, 200 University Avenue West, Waterloo, Ontario N2L 3G1, Canada. sedthilk@plg.uwaterloo.ca., , , , , , CA

   D. M. Thilikos

Received February 18, 1997; revised February 23, 1998.

Reprints and permissions