In graph theory and computer science, the graph sandwich problem is a problem of finding a graph that belongs to a particular family of graphs and is "sandwiched" between two other graphs, one of which must be a subgraph and the other of which must be a supergraph of the desired graph.
Graph sandwich problems generalize the problem of testing whether a given graph belongs to a family of graphs, and have attracted attention because of their
applications and as a natural generalization of recognition problems.
Problem statement.
More precisely, given a vertex set "V", a mandatory edge set "E"1, 
and a larger edge set "E"2, 
a graph "G" = ("V", "E") is called a "sandwich" graph for the pair 
"G"1 = ("V", "E"1), "G"2 = ("V", "E"2) if 
"E"1 ⊆ "E" ⊆ "E"2.
The "graph sandwich problem" for property Π is defined as follows:
Graph Sandwich Problem for Property Π:
Instance: Vertex set "V" and edge sets "E"1 ⊆ "E"2 ⊆ "V" × "V".
Question: Is there a graph "G" = ("V", "E") such that "E"1 ⊆ "E" ⊆ "E"2 and "G" satisfies property Π ?
The "recognition problem" for a class of graphs (those satisfying a property Π)
is equivalent to the particular graph sandwich problem where 
"E"1 = "E"2, that is, the optional edge set is empty. 
Computational complexity.
The graph sandwich problem is NP-complete when Π is the property of being a chordal graph, comparability graph, permutation graph, chordal bipartite graph, or chain graph. It can be solved in polynomial time for split graphs, threshold graphs, and graphs in which every five vertices contain at most one four-vertex induced path.
The complexity status has also been settled for the "H"-free graph sandwich problems
for each of the four-vertex graphs "H".
References.
 ;templatestyles src="Reflist/styles.css" / ;