The chain graph sandwich problem

The chain graph sandwich problem asks: Given a vertex set V, a mandatory edge set E ¹, and a larger edge set E ², is there a graph G=(V,E) such that E ¹⊆E⊆E ² with G being a chain graph (i.e., a 2K 2‐free bipartite graph)? We prove that the chain graph sandwich problem is NP‐complete. This result stands in contrast to (1) the case where E ¹ is a connected graph, which has a linear‐time solution, (2) the threshold graph sandwich problem, which has a linear‐time solution, and (3) the chain probe graph problem, which has a polynomial‐time solution.