Distance-hereditary Graph - Algorithms

Algorithms

Distance-hereditary graphs may be recognized, and parsed into a sequence of pendant vertex and twin operations, in linear time.

Because distance-hereditary graphs are perfect, some optimization problems may be solved in polynomial time for them despite being NP-hard for more general classes of graphs. Thus, it is possible in polynomial time to find the maximum clique or maximum independent set in a distance-hereditary graph, or to find an optimal graph coloring of any distance-hereditary graph. Because distance-hereditary graphs are circle graphs, they inherit polynomial time algorithms for circle graphs; for instance, it is possible determine in polynomial time the treewidth of any circle graph and therefore of any distance-hereditary graph. Additionally, the clique-width of any distance-hereditary graph is at most three. As a consequence, efficient dynamic programming algorithms exist for many problems on these graphs.

Several other optimization problems may also be solved more efficiently using algorithms specifically designed for distance-hereditary graphs. As D'Atri & Moscarini (1988) show, a minimum connected dominating set (or equivalently a spanning tree with the maximum possible number of leaves) may be found in polynomial time on a distance-hereditary graph. A Hamiltonian cycle or Hamiltonian path of any distance-hereditary graph may also be found in polynomial time.