19

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.

Mohammad Al-Turkistany
  • 20,928
  • 5
  • 63
  • 149
Devil
  • 419
  • 2
  • 9
  • 16
    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. – Mikhail Rudoy Feb 14 '17 at 09:24
  • 4
    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 – ivmihajlin Feb 14 '17 at 09:53
  • 6
    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. – David Eppstein Feb 15 '17 at 05:55
  • The link http://www.cc.gatech.edu/~Vijay.Vazirani/Unique.pdf in your question is broken. Is it https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.92.7457&rep=rep1&type=pdf ? – a3nm Apr 13 '21 at 15:07

3 Answers3

12

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.

Mohammad Al-Turkistany
  • 20,928
  • 5
  • 63
  • 149
  • 2
    See also theorem 2.1: http://www.wisdom.weizmann.ac.il/~oded/PSX/prpr-r.pdf – Mohammad Al-Turkistany Feb 14 '17 at 13:36
  • 2
    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.) – Andras Farago Apr 03 '21 at 14:56
  • 2
    @AndrasFarago You can't impose uniqueness promise on the solution set of those examples. It is never unique. – Mohammad Al-Turkistany Apr 03 '21 at 17:44
  • 1
    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." – Andras Farago Apr 05 '21 at 21:36
  • @AndrasFarago When $k \gt \Delta$, Are there Uniquely colorable graphs? See my comment on David's answer. – Mohammad Al-Turkistany Apr 06 '21 at 07:12
  • I have upvoted this answer and the vote is now locked in, but judging from the other answers, now I'm sorry that I did -- the claim cited in the answer just seems to be false. I'd appreciate an edit pointing out that the question is false, or at least making it possible to change the vote. – a3nm Apr 13 '21 at 15:30
  • @a3nm Done as requested. – Mohammad Al-Turkistany Apr 13 '21 at 15:42
  • Thanks a lot! But, as the initial asker of this nice question, I'd be also interested in your opinion -- do you agree that Goldreich's claim is mistaken as the other answers point out, or do you still disagree with them? – a3nm Apr 13 '21 at 15:43
  • @a3nm I still support Goldreich's claim. To me, the other proposed problems seem to be artificial. – Mohammad Al-Turkistany Apr 13 '21 at 16:26
  • Hmm, but then "No NP-complete problem is known to admit a polynomial-time algorithm under uniqueness promise" is incorrect, right? Maybe this is true for "natural" problems and we can argue about what it means to be natural; but factually the claim is not true right? – a3nm Apr 13 '21 at 17:20
  • @a3nm Is this an interesting algorithm? "if Δ<k≤m or G is a star, return yes, otherwise return no". Compare it to the algorithm of deciding Horn SAT. – Mohammad Al-Turkistany Apr 13 '21 at 17:45
  • But it is a polynomial-time algorithm, right? Sorry, I still don't understand how the statement "No NP-complete problem is known to admit a polynomial-time algorithm under uniqueness promise." isn't factually incorrect as explained in the other answers. – a3nm Apr 13 '21 at 18:48
  • It is correct for "natural" NP-complete problems. Natural here means problems that people care to solve. There is no practical real interest in the given examples . – Mohammad Al-Turkistany Apr 13 '21 at 19:47
  • So it is subjective depending on your interpretation of what "natural" means. – Mohammad Al-Turkistany Apr 13 '21 at 20:03
  • @a3nm Also, in both given examples, there is a version of the problem where the problem remains NP-complete under randomized reductions. Hamiltonian cycle problem for general graph and 3-edge coloring problem. – Mohammad Al-Turkistany Apr 14 '21 at 06:50
  • 1
    @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. – Peter Shor Apr 14 '21 at 14:21
  • @PeterShor Isn't it sufficient to give parsimonious reduction from 3SAT problem to Hamiltonian cycle problem in general graphs? In my opinion, the nonexistence of parsimonious reduction from Hamiltonian cycle problem to Hamiltonian cycle problem in 3-regular graphs does not disprove Goldreich's claim. I suggest that existence of parsimonious reduction from 3SAT problem to some NP-complete problem is necessary condition for it to be "Natural" NP-complete problem. – Mohammad Al-Turkistany Apr 14 '21 at 21:47
  • @MohammadAl-Turkistany: If you define "natural" NP-complete problems as ones that have a parsimonious reduction from 3SAT, then all natural NP-complete problems have a parsimonious reduction from 3SAT. But I don't consider that a natural definition. – Peter Shor Apr 20 '21 at 15:16
9

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.

David Eppstein
  • 50,990
  • 3
  • 170
  • 278
  • Goldreich claims that all known reductions among natural NP-complete problems are either parsimonious or can be easily modified to be so (see Mohammad Al-Turkistany's answer). Is there a parsimonious reduction between 3SAT and this problem? – Andras Farago Apr 04 '21 at 04:35
  • 2
    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. – David Eppstein Apr 04 '21 at 06:44
  • 2
    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. – Andras Farago Apr 04 '21 at 13:48
  • When $k \gt \Delta$, Are there Uniquely colorable graphs other than stars? If yes, then the k-edge coloring is not trivial under uniqueness promise for $k \gt \Delta$. – Mohammad Al-Turkistany Apr 06 '21 at 07:10
  • 1
    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$. – David Eppstein Apr 06 '21 at 19:29
  • @DavidEppstein What is $m$? – Mohammad Al-Turkistany Apr 06 '21 at 19:59
  • 1
    The usual and standard notation for the number of edges in an input graph. – David Eppstein Apr 06 '21 at 23:28
  • 1
    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. – David Eppstein Apr 06 '21 at 23:30
5

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.)

Peter Shor
  • 24,763
  • 4
  • 93
  • 133
  • 1
    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. – Andras Farago Apr 03 '21 at 14:49
  • 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. – Peter Shor Apr 03 '21 at 15:33
  • @PeterShor Aren't those six colorings induce the same partition of the vertex set? – Mohammad Al-Turkistany Apr 03 '21 at 17:49
  • @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? – Peter Shor Apr 03 '21 at 18:05
  • @PeterShor Technically, your point is valid, but from practical viewpoint, all those six colorings are just one partition. – Mohammad Al-Turkistany Apr 03 '21 at 18:09
  • @PeterShor Sorry for my ignorance, but I am not sure whether your interpretation of 3-coloring is standard in the graph coloring literature. – Mohammad Al-Turkistany Apr 03 '21 at 18:12
  • @MohammadAl-Turkistany: I've modified my answer to circumvent these objections. – Peter Shor Apr 03 '21 at 18:18
  • Hamiltonian Cycle is NP-complete for cubic planar bipartite graphs. – Mohammad Al-Turkistany Apr 03 '21 at 18:20
  • The input could be planar graph with even number of Hamiltonian cycles. – Mohammad Al-Turkistany Apr 03 '21 at 18:22
  • Why is the planar embedding unique? – Mohammad Al-Turkistany Apr 03 '21 at 19:35
  • @MohammadAl-Turkistany: Any 3-connected planar graph has an essentially unique planar embedding (differing only by which face is the outer face and by reflections). Embedding it on the sphere takes care of the first problem, and specifying the embedding at one particular vertex will take care of the second. Technically, to make it unique, represent the planar embedding by the clockwise order of edges around each vertex, and specify the order for one particular vertex. – Peter Shor Apr 03 '21 at 20:19
  • So for planar embeddings, different embeddings are congruent (up to orderings)? – Mohammad Al-Turkistany Apr 03 '21 at 20:52
  • @MohammadAl-Turkistany: for 3-connected planar graphs, yes. – Peter Shor Apr 04 '21 at 10:44
  • Just to check I understand what a "solution" is (i.e., what the uniqueness guarantee applies to). The problem is: given $G$, produce either a Hamiltonian cycle of $G$ or a planar embedding of $G$ (tweaked to make it unique as explained in the earlier comments). Right? (This could be clearer from the text of the answer, but looks reasonable to me.) – a3nm Apr 13 '21 at 15:29
  • 1
    @a3nm: That's right. – Peter Shor Apr 14 '21 at 14:17