The graph sandwich problem for 1-join composition is NP-complete (Q1613390): Difference between revisions

A graph \(G=(V,E)\) is a 1-join (or split) composition if there is a partition \((A,B,C,D)\) of \(V\) such that \(\{uv : uv \in E, u \in A \cup B, v \in C \cup D\} = \{uv : u \in B, v \in C\}\). Given two graphs \((V,E_1)\) and \((V,E_2)\), is there a 1-join composition \((V,E)\) such that \(E_1 \subseteq E \subseteq E_2\)? This is the graph sandwich problem for 1-join composition, which is proved to be NP-complete. In contrast, the graph sandwich problem for modular composition (\(A=\emptyset\) or \(D=\emptyset\)) is solvable in polynomial time [\textit{M. R. Cerioli, H. Everett, C. M. H. de Figueiredo} and \textit{S. Klein}, The homogeneous set sandwich problem, Inf. Process. Lett. 67, 31-35 (1998)] just like the recognition problem for 1-join compositions (\(E_1=E_2\)); see \textit{T.-H. Ma} and \textit{J. Spinrad} [J. Algorithms 16, 145-160 (1994; Zbl 0803.68092)].