Graph sandwich problem
Encyclopedia
In graph theory
and computer science
, the graph sandwich problem is the study of incomplete models of pairwise relations between objects from a certain collection, and how to complete them.
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, G2 if
E1 ⊆ E ⊆ E2.
The graph sandwich problem for property Π is defined as follows:
Graph Sandwich Problem for Property Π:
Instance: Vertex set V and edge sets
E1 ⊆ E2 ⊆ V × V.
Question: Is there a graph G = (V, E) such that
E1 ⊆ E ⊆ E2 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
E1 = E2, that is, the optional edge set is empty.
Graph sandwich problems have attracted much attention lately because of many
applications and as a natural generalization of recognition problems.
The computational complexity of the Graph Sandwich Problem is NP-complete
for the following graph families: chordal graph
, comparability graph
, permutation graph
, a chordal bipartite graph, and chain graph. It can be solved in polynomial time for split graph
and threshold graph
.
Graph theory
In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...
and computer science
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
, the graph sandwich problem is the study of incomplete models of pairwise relations between objects from a certain collection, and how to complete them.
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, G2 if
E1 ⊆ E ⊆ E2.
The graph sandwich problem for property Π is defined as follows:
Graph Sandwich Problem for Property Π:
Instance: Vertex set V and edge sets
E1 ⊆ E2 ⊆ V × V.
Question: Is there a graph G = (V, E) such that
E1 ⊆ E ⊆ E2 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
E1 = E2, that is, the optional edge set is empty.
Graph sandwich problems have attracted much attention lately because of many
applications and as a natural generalization of recognition problems.
The computational complexity of the Graph Sandwich Problem is NP-complete
NP-complete
In computational complexity theory, the complexity class NP-complete is a class of decision problems. A decision problem L is NP-complete if it is in the set of NP problems so that any given solution to the decision problem can be verified in polynomial time, and also in the set of NP-hard...
for the following graph families: chordal graph
Chordal graph
In the mathematical area of graph theory, a graph is chordal if each of its cycles of four or more nodes has a chord, which is an edge joining two nodes that are not adjacent in the cycle. An equivalent definition is that any chordless cycles have at most three nodes...
, comparability graph
Comparability graph
In graph theory, a comparability graph is an undirected graph that connects pairs of elements that are comparable to each other in a partial order...
, permutation graph
Permutation graph
In areas of mathematics influenced by graph theory, a permutation graph is the intersection graph of a family of line segments that connect two parallel lines in the Euclidean plane...
, a chordal bipartite graph, and chain graph. It can be solved in polynomial time for split graph
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...
and threshold graph
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....
.