Graph sandwich problem

In graph theory and computer science, the graph sandwich problem is a problem of fitting a graph to incomplete information about its edges, subject to constraints about the properties of the resulting graph.

Given a vertex set V, a mandatory edge set E¹, and a 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. Graph sandwich problems have attracted attention because of their applications and as a natural generalization of recognition problems.

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. It can be solved in polynomial time for split graphs and threshold graphs. The complexity status has also been settled for the H-free graph sandwich problems for each of the four vertex graphs H.

References

• Bondy, J.A.; Murty, U.S.R. (2008), Graph Theory, Springer, ISBN 978-1-84628-969-9.

• 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.

• 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.

• Dantas, S.; Klein, S.; Mello, C.P.; Morgana, A. (2009), "The graph sandwich problem for P₄-sparse graphs", Discrete Math, 309: 3664–3673.

• Golumbic, Martin Charles (1980), Algorithmic Graph Theory and Perfect Graphs, Academic Press, ISBN 0-444-51530-5 Second edition, Annals of Discrete Mathematics 57, Elsevier, 2004.

• 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; Trenk, Ann N. (2004), Tolerance Graphs, Cambridge.

• Mahadev, N.V.R.; Peled, Uri N. (1995), Threshold Graphs and Related Topics, North-Holland.