Can transitive orientation make sandwich problems easier? (Q2370442)

A graph \(G_s=(V,E_s)\) is a sandwich for a pair of graphs \(G_t=(V,E_t)\) and \(G=(V,E)\) if \(E_t\subseteq E_s\subseteq E\). A sandwich problem asks for the existence of a sandwich graph having an expected property. The authors are especially interested in comparability and co-comparability graphs. Two different classes of problems are studied: the poset sandwich problem (PSP) and the directed sandwich problem (DSP). The following variations are shown to be polynomial: the series-parallel PSP, series-parallel DSP, interval PSP, interval DSP, transitive subchain PSP, and two-dimensional PSP. On contrary, the transitive subchain DSP is shown to be NP-complete.