Computational complexity of compaction to reflexive cycles
In this paper, we solve a widely publicized open problem posed by Peter Winkler in 1988. The problem is to decide whether or not it is possible to partition the vertices of a graph into four distinct nonempty sets A, B, C, and D, such that there is no edge between the sets A and C, and between the sets B and D, and that there is at least one edge between any other pair of distinct sets. Winkler asked whether this problem is NP-complete. We show in this paper that it is NP-complete. We study the problem as the compaction problem for a reflexive 4-cycle. We also show in this paper that the compaction problem for a reflexive k-cycle is NP-complete for all k greater than or equal to 4.
computational complexity compaction graph coloring homomorphism retraction