Subtree overlap graphs and the maximum independent set problem
Eowyn Čenek · Library and Archives Canada (Government of Canada) · 1998
A graph G is a subtree overlap graph if there exists a tree T and a set of subtrees fT i g so that there exists a one-to-one mapping between vertices and subtrees and two subtrees overlap if and only if their respective vertices are adjacent. The class of subtree overlap graphs is proven to contain the classes of circle, spider or circle polygon, and chordal graphs. An upper bound on the size of the subtree overlap model is proven to be 3m. As well a general algorithm to find the maximum independent set for any class of overlap graph is given, provided testing for containment and intersection in the overlap graph can be done in polynomial time, and the maximumweight independent set problem is solved for the related class of intersection graph. The complexities of the Hamiltonian Cycle, several domination problems, isomorphism and colouring are shown to be as hard for subtree overlap graphs as they are for graphs in general.