The problem: Exact Cover by 3-Sets (X3C)

The definition: Given a set X, with |X| = 3q (so, the size of X is a multiple of 3), and a collection C of 3-element subsets of X. Can we find a subset C’ of C where every element of X occurs in exactly one member of C’? (So, C’ is an “exact cover” of X).

The class US (Unique Polynomial-Time) is the class of decision problems solvable by an NP machine such that the answer is 'yes' if and only if exactly one computation path accepts.

UNIQUE-3SAT is the problem of deciding whether the 3CNF Boolean formulas have a unique solution. UNIQUE-3SAT is a known US-complete problem.

Is the version of problem Exact Cover by 3-Sets(UNIQUE-X3C) when the instances have a unique solution a US-complete problem? (which means there is a unique subset C’ as solution)

Thanks in advance!!!

  • $\begingroup$ This sounds very similar to 3-dimensional matching. $\endgroup$ – Yuval Filmus Feb 18 '17 at 22:40
  • $\begingroup$ I think the right term of this class is UP? $\endgroup$ – Willard Zhan Feb 19 '17 at 9:14
  • $\begingroup$ @WillardZhan : ​ That's just a different class. ​ ​ ​ ​ $\endgroup$ – user12859 Feb 20 '17 at 0:21
  • $\begingroup$ @RickyDemer Oh, I see. Multiple certificates in this class indicate a 'no' instance. $\endgroup$ – Willard Zhan Feb 20 '17 at 2:04

Yes, it is.

This scanned chapter 3 from Garey-Johnson classic book describe a parsimonious reduction from 3SAT to 3DM. And X3C is a generalization of 3DM. So, the same reduction can be used to parsimoniously reduce 3SAT to 3DM.

Thus, $\mathrm{UNIQUE-3SAT}$ many-one reduces to $\mathrm{UNIQUE-X3C}$. As a consequence, $\mathrm{UNIQUE-X3C}$ is $\mathrm{US}$-complete.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.