graph theory In mathematics and computer science, graph theory is the study of ''graph (discrete mathematics), graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of ''Vertex (graph ...

and

computer science Computer science is the study of computation, information, and automation. Computer science spans Theoretical computer science, theoretical disciplines (such as algorithms, theory of computation, and information theory) to Applied 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''¹, and a (potentially) larger edge set ''E''², a graph ''G'' = (''V'', ''E'') is called a ''sandwich'' graph for the pair ''G''¹ = (''V'', ''E''¹), ''G''² = (''V'', ''E''²) if ''E''¹ ⊆ ''E'' ⊆ ''E''². The ''graph sandwich problem'' for property Π is defined as follows:. :Graph Sandwich Problem for Property Π: :Instance: Vertex set ''V'' and edge sets ''E''¹ ⊆ ''E''² ⊆ ''V'' × ''V''. :Question: Is there a graph ''G'' = (''V'', ''E'') such that ''E''¹ ⊆ ''E'' ⊆ ''E''² 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''¹ = ''E''², that is, the optional edge set is empty.

Computational complexity

The graph sandwich problem is

NP-complete In computational complexity theory, NP-complete problems are the hardest of the problems to which ''solutions'' can be verified ''quickly''. Somewhat more precisely, a problem is NP-complete when: # It is a decision problem, meaning that for any ...

when Π is the property of being a chordal graph,

comparability graph In graph theory and order theory, a comparability graph is an undirected graph that connects pairs of elements that are comparable to each other in a partial order. Comparability graphs have also been called transitively orientable graphs, partial ...

permutation graph In the mathematical field of graph theory, a permutation graph is a graph whose vertices represent the elements of a permutation, and whose edges represent pairs of elements that are reversed by the permutation. Permutation graphs may also be d ...

chordal bipartite graph In the mathematical area of graph theory, a chordal bipartite graph is a bipartite graph ''B'' = (''X'',''Y'',''E'') in which every cycle of length at least 6 in ''B'' has a ''chord'', i.e., an edge that connects two vertices that are a ...

, or

chain graph In graph theory, a mixed graph is a graph consisting of a set of vertices , a set of (undirected) edges , and a set of directed edges (or arcs) . Definitions and notation Consider adjacent vertices u,v \in V. A directed edge, called an arc, ...

. It can be solved in polynomial time for

split graph In graph theory, a branch of mathematics, a split graph is a graph in which the vertices can be partitioned into a clique and an independent set. Split graphs were first studied by , and independently introduced by , where they called these ...

s,.

threshold graph In graph theory, a threshold graph is a graph that can be constructed from a one-vertex graph by repeated applications of the following two operations: # Addition of a single isolated vertex to the graph. # Addition of a single dominating vertex ...

s, and graphs in which every five vertices contain at most one four-vertex

induced path In the mathematical area of graph theory, an induced path in an undirected graph is a path that is an induced subgraph of . That is, it is a sequence of vertices in such that each two adjacent vertices in the sequence are connected by an edge ...

. The complexity status has also been settled for the ''H''-free graph sandwich problems for each of the four-vertex graphs ''H''..

Problem statement

Computational complexity

References

Further reading