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.[1]
Contents
1 Problem statement
2 Computational complexity
3 References
4 Further reading
Problem statement
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]
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.[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]
References
^ Golumbic, Martin Charles; Trenk, Ann N. (2004), "Chapter 4. Interval probe graphs and sandwich problems", Tolerance Graphs, Cambridge, pp. 63–83.mw-parser-output cite.citationfont-style:inherit.mw-parser-output .citation qquotes:"""""""'""'".mw-parser-output .citation .cs1-lock-free abackground:url("//upload.wikimedia.org/wikipedia/commons/thumb/6/65/Lock-green.svg/9px-Lock-green.svg.png")no-repeat;background-position:right .1em center.mw-parser-output .citation .cs1-lock-limited a,.mw-parser-output .citation .cs1-lock-registration abackground:url("//upload.wikimedia.org/wikipedia/commons/thumb/d/d6/Lock-gray-alt-2.svg/9px-Lock-gray-alt-2.svg.png")no-repeat;background-position:right .1em center.mw-parser-output .citation .cs1-lock-subscription abackground:url("//upload.wikimedia.org/wikipedia/commons/thumb/a/aa/Lock-red-alt-2.svg/9px-Lock-red-alt-2.svg.png")no-repeat;background-position:right .1em center.mw-parser-output .cs1-subscription,.mw-parser-output .cs1-registrationcolor:#555.mw-parser-output .cs1-subscription span,.mw-parser-output .cs1-registration spanborder-bottom:1px dotted;cursor:help.mw-parser-output .cs1-ws-icon abackground:url("//upload.wikimedia.org/wikipedia/commons/thumb/4/4c/Wikisource-logo.svg/12px-Wikisource-logo.svg.png")no-repeat;background-position:right .1em center.mw-parser-output code.cs1-codecolor:inherit;background:inherit;border:inherit;padding:inherit.mw-parser-output .cs1-hidden-errordisplay:none;font-size:100%.mw-parser-output .cs1-visible-errorfont-size:100%.mw-parser-output .cs1-maintdisplay:none;color:#33aa33;margin-left:0.3em.mw-parser-output .cs1-subscription,.mw-parser-output .cs1-registration,.mw-parser-output .cs1-formatfont-size:95%.mw-parser-output .cs1-kern-left,.mw-parser-output .cs1-kern-wl-leftpadding-left:0.2em.mw-parser-output .cs1-kern-right,.mw-parser-output .cs1-kern-wl-rightpadding-right:0.2em.
^ abcd Golumbic, Martin Charles; Kaplan, Haim; Shamir, Ron (1995), "Graph sandwich problems", J. Algorithms, 19: 449–473, doi:10.1006/jagm.1995.1047.
^ Golumbic, Martin Charles (2004), Algorithmic Graph Theory and Perfect Graphs, Annals of Discrete Mathematics, 57 (2nd ed.), Elsevier, p. 279.
^ de Figueiredo, C. M. H.; Faria, L.; Klein, S.; Sritharan, R. (2007), "On the complexity of the sandwich problems for strongly chordal graphs and chordal bipartite graphs", Theoretical Computer Science, 381 (1–3): 57–67, doi:10.1016/j.tcs.2007.04.007, MR 2347393.
^ ab Mahadev, N.V.R.; Peled, Uri N. (1995), Threshold Graphs and Related Topics, Annals of Discrete Mathematics, 57, North-Holland, pp. 19–22.
^ Dantas, S.; Klein, S.; Mello, C.P.; Morgana, A. (2009), "The graph sandwich problem for P4-sparse graphs", Discrete Mathematics, 309: 3664–3673, doi:10.1016/j.disc.2008.01.014.
^ Dantas, Simone; de Figueiredo, Celina M.H.; Maffray, Frédéric; Teixeira, Rafael B. (2013), "The complexity of forbidden subgraph sandwich problems and the skew partition sandwich problem", Discrete Applied Mathematics: Available online 11 October 2013, doi:10.1016/j.dam.2013.09.004.
Further reading
Dantas, Simone; de Figueiredo, Celina M.H.; da Silva, Murilo V.G.; Teixeira, Rafael B. (2011), "On the forbidden induced subgraph sandwich problem", Discrete Applied Mathematics, 159: 1717–1725, doi:10.1016/j.dam.2010.11.010.
