graph sandwich problem
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.{{citation|last1=Golumbic|first1=Martin Charles|last2=Trenk|first2=Ann N.|author2-link= Ann Trenk
|title=Tolerance Graphs|publisher=Cambridge|year=2004|contribution=Chapter 4. Interval probe graphs and sandwich problems|pages=63–83}}.
Problem statement
More precisely, given a vertex set V, a mandatory edge set E1,
and a (potentially) 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:{{citation
| last1=Golumbic|first1=Martin Charles
| last2 = Kaplan | first2 = Haim | last3 = Shamir | first3 = Ron
| journal = J. Algorithms
| pages = 449–473
| title = Graph sandwich problems
| volume = 19
| year = 1995 |issue=3
: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.
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.{{citation
| last1 = de Figueiredo | first1 = C. M. H.
| last2 = Faria | first2 = L.
| last3 = Klein | first3 = S.
| last4 = Sritharan | first4 = R.
| doi = 10.1016/j.tcs.2007.04.007
| issue = 1–3
| journal = Theoretical Computer Science
| mr = 2347393
| pages = 57–67
| title = On the complexity of the sandwich problems for strongly chordal graphs and chordal bipartite graphs
| volume = 381
| year = 2007| doi-access = free
}}. It can be solved in polynomial time for split graphs,{{citation|last1=Mahadev|first1=N.V.R.|last2=Peled|first2=Uri N.|title=Threshold Graphs and Related Topics|series=Annals of Discrete Mathematics|volume=57|publisher=North-Holland|year=1995|pages=19–22|isbn=978-0-08-054300-0 |url=https://books.google.com/books?id=nWfGo_VX5M8C&pg=PA19}}. threshold graphs, and graphs in which every five vertices contain at most one four-vertex induced path.{{citation
| last1 = Dantas | first1 = S.
| last2 = Klein | first2 = S.
| last3 = Mello| first3 = C.P.
| last4 = Morgana| first4 = A.
| doi = 10.1016/j.disc.2008.01.014
| journal = Discrete Mathematics
| pages = 3664–3673
| title = The graph sandwich problem for P4-sparse graphs
| volume = 309
| year = 2009| issue = 11
| doi-access = free
}}.
The complexity status has also been settled for the H-free graph sandwich problems
for each of the four-vertex graphs H.{{citation
| last1=Dantas|first1=Simone
| last2 = de Figueiredo| first2 = Celina M.H.
| last3 = Maffray| first3 = Frédéric
| last4 = Teixeira| first4 = Rafael B.
| journal = Discrete Applied Mathematics
| pages = 15–24
| title = The complexity of forbidden subgraph sandwich problems and the skew partition sandwich problem
| volume = 182
| year = 2013 | doi=10.1016/j.dam.2013.09.004| doi-access = free}}.
References
{{reflist}}
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 |issue=16
| doi-access = free}}.