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. [1]
More precisely, given a vertex set V, a mandatory edge set E1, and a larger edge set E2, a graph G = (V, E) is called a sandwich graph for the pair G1 = (V, E1), G2 = (V, E2) if E1 ⊆ E ⊆ E2. The graph sandwich problem for property Π is defined as follows: [2] [3]
The recognition problem for a class of graphs (those satisfying a property Π) is equivalent to the particular graph sandwich problem where E1 = E2, that is, the optional edge set is empty.
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. [2] [4] It can be solved in polynomial time for split graphs, [2] [5] threshold graphs, [2] [5] and graphs in which every five vertices contain at most one four-vertex induced path. [6] The complexity status has also been settled for the H-free graph sandwich problems for each of the four-vertex graphs H. [7]
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. [1]
More precisely, given a vertex set V, a mandatory edge set E1, and a larger edge set E2, a graph G = (V, E) is called a sandwich graph for the pair G1 = (V, E1), G2 = (V, E2) if E1 ⊆ E ⊆ E2. The graph sandwich problem for property Π is defined as follows: [2] [3]
The recognition problem for a class of graphs (those satisfying a property Π) is equivalent to the particular graph sandwich problem where E1 = E2, that is, the optional edge set is empty.
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. [2] [4] It can be solved in polynomial time for split graphs, [2] [5] threshold graphs, [2] [5] and graphs in which every five vertices contain at most one four-vertex induced path. [6] The complexity status has also been settled for the H-free graph sandwich problems for each of the four-vertex graphs H. [7]