Abstract: We study the following question: if A and B are disjoint NP-complete sets, then is A∪B NP-complete? We provide necessary and sufficient conditions under which the union of disjoint NP-complete sets remain complete.

Full Version:

• ACM Transactions on Computation Theory, Volume 6, Issue 1, Article No. 3, 2014.
  [DOI | PDF]

• Proceedings of the 17th Annual International Computing and Combinatorics Conference (Dallas, Texas, August 14-16, 2011), Lecture Notes in Computer Science 6842, pages 240-251. Springer-Verlag, 2011. Best paper award.
  [DOI]