Isomorphism for graphs of bounded distance width

K. Yamazaki, H. L. Bodlaender, B. De Fluiter, D. M. Thilikos

Research output: Contribution to journalArticlepeer-review

Abstract

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(n2) time for graphs with bounded rooted path distance width, and in O(n3) 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(nk+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.

Original languageEnglish (US)
Pages (from-to)105-127
Number of pages23
JournalAlgorithmica (New York)
Volume24
Issue number2
DOIs
StatePublished - Jun 1999

Keywords

  • Distance pathwidth
  • Distance treewidth
  • Fixed parameter tractability
  • Graph isomorphism

ASJC Scopus subject areas

  • General Computer Science
  • Computer Science Applications
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'Isomorphism for graphs of bounded distance width'. Together they form a unique fingerprint.

Cite this