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.

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.