Computational complexity of compaction to irreflexive cycles

摘要

In this paper, we solve a long-standing problem that has been of interest since about 1988. The problem in general is to decide whether or not it is possible to partition the vertices of a graph into k distinct non-empty sets A0,A1,…,Ak−1, such that the vertices in Ai are independent and there is at least one edge between the pair of sets Ai and A(i+1)modk, for all i=0,1,2,…,k−1, k>2, and there is no edge between any other pair of sets. Determining the computational complexity of this problem, for any value of even k⩾6, has been of interest since about 1988 to various people, including Pavol Hell and Jaroslav Nesetril. We show in this paper that the problem is NP-complete, for all even k⩾6. We study the problem as the compaction problem for an irreflexive k-cycle.