Computational complexity of compaction to irreflexive cycles

✍ Scribed by Narayan Vikas

• Publisher: Elsevier Science
• Year: 2004
• Tongue: English
• Weight: 295 KB
• Volume: 68
• Category: Article
• ISSN: 0022-0000
• DOI: 10.1016/s0022-0000(03)00034-5

✦ Synopsis

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 A 0 ; A 1 ; y; A kÀ1 ; such that the vertices in A i are independent and there is at least one edge between the pair of sets A i and A ðiþ1Þ mod k ; for all i ¼ 0; 1; 2; y; k À 1; k42; and there is no edge between any other pair of sets. Determining the computational complexity of this problem, for any value of even kX6; 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 kX6: We study the problem as the compaction problem for an irreflexive k-cycle.