HOME

TheInfoList



OR:

In
graph theory In mathematics, graph theory is the study of '' graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conn ...
and
computer science Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to Applied science, practical discipli ...
, 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 In computational complexity theory, a problem is NP-complete when: # it is a problem for which the correctness of each solution can be verified quickly (namely, in polynomial time) and a brute-force search algorithm can find a solution by trying ...
when Π is the property of being a
chordal graph In the mathematical area of graph theory, a chordal graph is one in which all cycles of four or more vertices have a ''chord'', which is an edge that is not part of the cycle but connects two vertices of the cycle. Equivalently, every induced ...
,
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. Comparability graphs have also been called transitively orientable graphs, partially orderable gra ...
,
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 ...
, chordal bipartite graph, 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 graphs,.
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 t ...
s, 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


Further reading

*{{citation , last1=Dantas, first1=Simone , last2 = de Figueiredo, first2 = Celina M.H. , last3 = da Silva, first3 = Murilo V.G. , last4 = Teixeira, first4 = Rafael B. , doi = 10.1016/j.dam.2010.11.010 , journal = Discrete Applied Mathematics , pages = 1717-1725 , title = On the forbidden induced subgraph sandwich problem , volume = 159 , year = 2011 , doi-access = free. Computational problems in graph theory