GRAPH SANDWICH PROBLEMS

The graph sandwich problem for property Pi: is defined as follows: Given two graphs G(1) = (V, E(1)) and G(2) = (V, E(2)) such that E(1) subset of or equal to E(2), is there a graph G = (V, E) such that E(1) subset of or equal to E subset of or equal to E(2) which satisfies property Pi? Such problems generalize recognition problems and arise in various applications. Concentrating mainly on properties characterizing subfamilies of perfect graphs, we give polynomial algorithms for several properties and prove the NP-completeness of others. We describe polynomial time algorithms for threshold graphs, split graphs, and cographs. For the sandwich problem for threshold graphs, the only case in which a previous algorithm existed, we obtain a faster algorithm. NP-completeness proofs are given for comparability graphs, permutation graphs, and several other families. For Eulerian graphs; one Version of the problem is polynomial and another is NP-complete. (C) 1995 Academic Press, Inc.