19
$\begingroup$

I was recently reading a very nice paper by Valiant and Vazirani which shows that if $\mathbf{NP \neq RP}$, then there can not be an efficient algorithm to solve SAT even under the promise that it is either unsatisfiable or has a unique solution. Thus showing that SAT does not admit an efficient algorithm even under the promise of there being at most one solution.

Through a parsimonious reduction (a reduction that preserves the number of solutions), it is easy to see that most NP-complete problems (I could think of) also do not admit an efficient algorithm even under the promise of there being at most one solution (unless $\mathbf{NP = RP}$). Examples would be VERTEX-COVER, 3-SAT, MAX-CUT, 3D-MATCHING.

Hence I was wondering if there was any NP-complete problem that was known to admit a poly-time algorithm under a uniqueness promise.

Improve this question
$\endgroup$
4
  • 17
    $\begingroup$ This isn't a very good answer, but there are many NP-complete problems whose instances always have either zero or more than one solution. Consider graph 3-coloring for example; the solutions come in groups of 6 since you can always permute the colors. Any such problem has a polynomial time algorithm under the promise of at most one solution. In particular, if there is at most one 3-coloring then there cannot be any, and so the algorithm can just reject. $\endgroup$
    – Mikhail Rudoy
    Commented Feb 14, 2017 at 9:24
  • 4
    $\begingroup$ Hamiltonian cycle problem admits faster (but still exponential) time algorithm under the uniqness promiss. It is not directly answering your question, because it's not polynomial, but at least this is a problem with differen tbehaviour then SAT $\endgroup$
    – ivmihajlin
    Commented Feb 14, 2017 at 9:53
  • 6
    $\begingroup$ As in Mikhail Rudoy's comment, testing for the existence of a Hamiltonian cycle in 3-regular graphs is trivial with a uniqueness assumption. Each edge participates in an even number of Hamiltonian cycles, so there can never be exactly one. $\endgroup$
    – David Eppstein
    Commented Feb 15, 2017 at 5:55
  • $\begingroup$ The link cc.gatech.edu/~Vijay.Vazirani/Unique.pdf in your question is broken. Is it citeseerx.ist.psu.edu/viewdoc/… ? $\endgroup$
    – Antoine Amarilli 'a3nm'
    Commented Apr 13, 2021 at 15:07

3 Answers 3

Reset to default
13
$\begingroup$

No NP-complete problem is known to admit a polynomial-time algorithm under uniqueness promise. Valiant and Vazirani theorem applies to any known natural NP-complete problem.

For all known NP-complete problems, there is a parsimonious reduction from 3SAT. Oded Goldreich states the fact that "all known reductions among natural $NP$-complete problems are either parsimonious or can be easily modified to be so". ( Computational Complexity: A Conceptual Perspective By Oded Goldreich).

Edit: This edit is solely to allow change of votes.

Improve this answer
$\endgroup$
18
  • 2
    $\begingroup$ See also theorem 2.1: wisdom.weizmann.ac.il/~oded/PSX/prpr-r.pdf $\endgroup$
    – Mohammad Al-Turkistany
    Commented Feb 14, 2017 at 13:36
  • 2
    $\begingroup$ How does this reconcile with the fact that some NP-complete problems become trivial with a uniqueness assumption? (See the comments at the original question.) $\endgroup$
    – Andras Farago
    Commented Apr 3, 2021 at 14:56
  • 2
    $\begingroup$ @AndrasFarago You can't impose uniqueness promise on the solution set of those examples. It is never unique. $\endgroup$
    – Mohammad Al-Turkistany
    Commented Apr 3, 2021 at 17:44
  • 1
    $\begingroup$ How about $k$-edge coloring for $k\geq 4$, with uniqueness promise? (See David Eppstein's answer below.) It seems to contradict the claim "No NP-complete problem is known to admit a polynomial-time algorithm under uniqueness promise." $\endgroup$
    – Andras Farago
    Commented Apr 5, 2021 at 21:36
  • 1
    $\begingroup$ @MohammadAl-Turkistany: If you stand by Oded Goldreich's claim, please give a natural parsimonious reduction of some NP-complete problem to Hamiltonian cycles in 3-regular graphs. $\endgroup$
    – Peter Shor
    Commented Apr 14, 2021 at 14:21
9
$\begingroup$

Yes, there is a natural NP-complete problem for which uniqueness makes it easy: $k$-edge coloring for $k\ge 4$. Here, to make uniqueness possible, a coloring is defined as a partition of the edges into nonempty matchings, irrespective of the ordering or labeling of the matchings in the partition.

All graphs have edge-colorings with one more color than degree by Vizing's theorem, so the problem is trivial unless $k$ equals the maximum degree $\Delta$. And the only graphs that have a unique partition with $k=\Delta$ are the stars: see

Thomason, A. G. (1978), "Hamiltonian cycles and uniquely edge colourable graphs", Ann. Discrete Math. 3: 259–268.

So the algorithm for the promise problem is: if $\Delta<k\le m$ or $G$ is a star, return yes, otherwise return no.

Improve this answer
$\endgroup$
8
  • 2
    $\begingroup$ Not unless BPP=NP, because 3SAT is NP-hard for unique instances under randomized reductions by Valiant–Vazirani (and known parsimonious reductions from SAT to 3SAT) and k-edge-coloring for k≥4 is P for unique instances by this answer. I think Goldreich is just mistaken. $\endgroup$
    – David Eppstein
    Commented Apr 4, 2021 at 6:44
  • 2
    $\begingroup$ I think, the following example also supports that the claim "all known reductions among natural NP-complete problems are either parsimonious or can be easily modified to be so" is not correct. Hamiltonian circle in 3-regular graphs is NP-complete, but cannot have a yes-instance with a unique solution. Therefore, it seems, the reduction of 3SAT to this problem cannot be made parsimonious, as 3SAT may have a yes-instance with a unique solution, but Hamiltonian circle in 3-regular graphs can never have such an instance. $\endgroup$
    – Andras Farago
    Commented Apr 4, 2021 at 13:48
  • 1
    $\begingroup$ Yes. For instance, every graph with $k=m$ is uniquely colorable. But the promise problem is still trivial, because all it has to do is answer yes whenever $\Delta<k\le m$. $\endgroup$
    – David Eppstein
    Commented Apr 6, 2021 at 19:29
  • 1
    $\begingroup$ The usual and standard notation for the number of edges in an input graph. $\endgroup$
    – David Eppstein
    Commented Apr 6, 2021 at 23:28
  • 1
    $\begingroup$ Also, by "trivial" I meant in the colloquial sense of not requiring any effort to solve, not in the technical sense of all instances having the same answer as each other. $\endgroup$
    – David Eppstein
    Commented Apr 6, 2021 at 23:30
6
$\begingroup$

Yes, there is such a problem. While the problem is arguably not "natural", it is certainly NP-complete.

The problem is: for a degree 3 graph $G$, is $G$ either planar or Hamiltonian (i.e., has a Hamiltonian cycle)?

If $G$ has a Hamiltonian cycle, then it has at least two Hamiltonian cycles (this is a theorem for degree 3 graphs; see the comments to the original answer). Thus, if it has a unique solution, $G$ must be planar. And there is a polynomial-time algorithm for planarity, so if we are guaranteed that $G$ has a unique solution, we can solve this problem.

Further, it is NP-complete to tell whether a degree-3 graph without a planar embedding is Hamiltonian, so the original problem is NP-complete in general.

NOTE: I've modified my original answer to show that the objections in the comments are not an issue, but I'm preserving my original answer below (so the comments will make sense).

Original answer:

The problem is: does graph $G$ either have a 3-coloring or a perfect matching?

If $G$ has a three-coloring, then it has at least six 3-colorings (permute the colors). Thus, if it has a unique solution, $G$ must have a perfect matching. And there is a polynomial-time algorithm for perfect matchings, so if we are guaranteed that $G$ has a unique solution, we can find it.

Further, it is NP-complete to tell whether graphs without perfect matchings are 3-colorable. (This is easy to see ... take a graph and add an isolated triangle.)

Improve this answer
$\endgroup$
15
  • 1
    $\begingroup$ I don't think that permuting the colors creates new solutions. A 3-coloring is just a partition into 3 independent sets. If we just re-name these sets, the partition does not change. If such re-naming would count as a new solution, then we could have infinitely many solutions, using arbitrary names for the colors. $\endgroup$
    – Andras Farago
    Commented Apr 3, 2021 at 14:49
  • $\begingroup$ If you don't think permuting the colors creates a new solution (by the technical definition of NP-completeness it does), use the problem: is a 3-regular graph either planar or Hamiltonian? By using the fact from the comments that any 3-regular path has at least two Hamiltonian cycles, this is solvable in polynomial time if it has a unique solution. $\endgroup$
    – Peter Shor
    Commented Apr 3, 2021 at 15:33
  • 1
    $\begingroup$ @MohammadAl-Turkistany: Yes. But why does that matter? A language $L$ is NP-complete if there is a Turing machine T so $\forall x \in L$, $\exists$ a witness $w$ where T accepts on input $(x,w)$. If there are six possible colorings, there are six different strings $w$ such that $(x,w)$ accepts. Now, you can modify your definition of $L$ to require that vertex $a$ is colored red and its neighbor vertex $b$ is colored blue, in which case you get one possible witness string (assuming there's a unique solution) which gives you a parsimonious reduction. But isn't that an artificial restriction? $\endgroup$
    – Peter Shor
    Commented Apr 3, 2021 at 18:05
  • 1
    $\begingroup$ @MohammadAl-Turkistany: I've modified my answer to circumvent these objections. $\endgroup$
    – Peter Shor
    Commented Apr 3, 2021 at 18:18
  • 2
    $\begingroup$ @a3nm: That's right. $\endgroup$
    – Peter Shor
    Commented Apr 14, 2021 at 14:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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