The sandwich problem for cutsets: Clique cutset, kk-star cutset

Sandwich problems generalize graph recognition problems with respect to a property ΠΠ. A recognition problem has a graph as input, whereas a sandwich problem has two graphs as input. In a sandwich problem, we look for a third graph, whose edge set lies between the edge sets of two given graphs. This third graph is required to satisfy a property ΠΠ. We present sandwich results corresponding to the polynomial recognition problems: clique cutset, star cutset, and a generalization k  -star cutset. We note these graph cutset problems are of interest with respect to sandwich problems. We propose an O(n3)O(n3)-time polynomial algorithm for star cutset sandwich problem, and an O(n2+k)O(n2+k)-time polynomial algorithm for the k-star cutset sandwich problem. We propose an NP-completeness transformation from 1-in-3 3SAT (without negative literals) to clique cutset sandwich problem.