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]

Problem statement

More precisely, given a vertex set V, a mandatory edge set E¹, and a (potentially) 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: ^{[2] [3]}

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.

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

1. Golumbic, Martin Charles; Trenk, Ann N. (2004), "Chapter 4. Interval probe graphs and sandwich problems", Tolerance Graphs, Cambridge, pp. 63–83.
2. Golumbic, Martin Charles; Kaplan, Haim; Shamir, Ron (1995), "Graph sandwich problems", J. Algorithms, 19 (3): 449–473, doi:10.1006/jagm.1995.1047 .
3. Golumbic, Martin Charles (2004), Algorithmic Graph Theory and Perfect Graphs, Annals of Discrete Mathematics, vol. 57 (2nd ed.), Elsevier, p. 279, ISBN   978-0-08-052696-6 .
4. 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 .
5. Mahadev, N.V.R.; Peled, Uri N. (1995), Threshold Graphs and Related Topics, Annals of Discrete Mathematics, vol. 57, North-Holland, pp. 19–22, ISBN   978-0-08-054300-0 .
6. Dantas, S.; Klein, S.; Mello, C.P.; Morgana, A. (2009), "The graph sandwich problem for P₄-sparse graphs", Discrete Mathematics , 309 (11): 3664–3673, doi: 10.1016/j.disc.2008.01.014 .
7. 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, 182: 15–24, 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 (16): 1717–1725, doi: 10.1016/j.dam.2010.11.010 .