Graph Classes between Parity and Distance-Hereditary Graphs

摘要

Several graph problems (for example, Steiner tree, connected domination, Hamiltonian path, and isomorphism problem), which can be solved in polynomial time for distance-hereditary graphs, are NP-complete or have unknown complexity for parity graphs. Moreover, the metric characterizations of these two graph classes suggest an excessive gap between them. We introduce a family of classes forming an infinite lattice with respect to inclusion, whose extreme points are exactly parity and distance-hereditary classes. Then, we characterize these classes using Cunningham decomposition and use such a characterization in order to show efficient algorithms for the recognition and isomorphism problems.