The polynomial dichotomy for three nonempty part sandwich problems ?
We classify into polynomial time or NP -complete all three nonempty part sandwich problems. This solves the polynomial dichotomy into polynomial time and NP -complete for this class of graph partition problems.
sandwich problems graph partitions graph algorithms computational complexity structural characterization of graphs np -complete np np np