The sandwich problem for cutsets

A graph G 1 = ( V , E 1 ) is a spanning subgraph of G 2 = ( V , E 2 ) if E 1 ⊆ E 2 ; and a graph G = ( V , E ) is a sandwich graph for the pair G1, G2 if E 1 ⊆ E ⊆ E 2 . A star cutset is a non-empty set C of vertices whose deletion results in a disconnected graph, and such that some vertex in C is adjacent to all the remaining vertices of C. A clique cutset is a vertex cutset which is also a clique. We present an O ( n 3 ) -time algorithm for star cutset sandwich problem; and we propose an NP-completeness transformation from 1-in-3 3SAT (without negative literals) to clique cutset sandwich problem.