<p>Yes, there is a natural NP-complete problem for which uniqueness makes it easy: <span class="math-container">$k$</span>-edge coloring for <span class="math-container">$k\ge 4$</span>. 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.</p>
<p>All graphs have edge-colorings with one more color than degree by Vizing's theorem, so the problem is trivial unless <span class="math-container">$k$</span> equals the maximum degree <span class="math-container">$\Delta$</span>. And the only graphs that have a unique partition with <span class="math-container">$k=\Delta$</span> are the stars: see</p>
<p>Thomason, A. G. (1978), &quot;<a href="https://doi.org/10.1016/S0167-5060(08)70511-9" rel="noreferrer">Hamiltonian cycles and uniquely edge colourable graphs</a>&quot;,
<em>Ann. Discrete Math.</em> 3: 259–268.</p>
<p>So the algorithm for the promise problem is: if <span class="math-container">$\Delta&lt;k\le m$</span> or <span class="math-container">$G$</span> is a star, return yes, otherwise return no.</p>

CC BY-SA 4.0
2021-04-04T04:35:16.890Z
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
CC BY-SA 4.0
2021-04-04T06:44:42.077Z
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
CC BY-SA 4.0
2021-04-04T13:48:52.217Z
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
CC BY-SA 4.0
2021-04-06T07:10:36.777Z
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
CC BY-SA 4.0
2021-04-06T19:29:03.840Z
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
CC BY-SA 4.0
2021-04-06T19:59:12.737Z
@DavidEppstein What is $m$?
Mohammad Al-Turkistany
CC BY-SA 4.0
2021-04-06T23:28:37.077Z
The usual and standard notation for the number of edges in an input graph.
David Eppstein
CC BY-SA 4.0
2021-04-06T23:30:45.910Z
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
CC BY-SA 4.0
2021-04-03T21:02:18.210Z
2021-04-03T23:42:43.503Z
2021-04-03T23:42:43.503Z
David Eppstein
<p>Yes, there is such a problem. While the problem is arguably not &quot;natural&quot;, it is certainly NP-complete.</p>
<p>The problem is: for a degree 3 graph <span class="math-container">$G$</span>, is <span class="math-container">$G$</span> either planar or Hamiltonian (i.e., has a Hamiltonian cycle)?</p>
<p>If <span class="math-container">$G$</span> 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, <span class="math-container">$G$</span> must be planar. And there is a polynomial-time algorithm for planarity, so if we are guaranteed that <span class="math-container">$G$</span> has a unique solution, we can solve this problem.</p>
<p>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.</p>
<p>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).</p>
<p>Original answer:</p>
<p>The problem is: does graph <span class="math-container">$G$</span> either have a 3-coloring or a perfect matching?</p>
<p>If <span class="math-container">$G$</span> has a three-coloring, then it has at least six 3-colorings (permute the colors). Thus, if it has a unique solution, <span class="math-container">$G$</span> must have a perfect matching. And there is a polynomial-time algorithm for perfect matchings, so if we are guaranteed that <span class="math-container">$G$</span> has a unique solution, we can find it.</p>
<p>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.)</p>

CC BY-SA 4.0
2021-04-03T14:49:14.033Z
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
CC BY-SA 4.0
2021-04-03T15:33:04.340Z
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 
CC BY-SA 4.0
2021-04-03T17:49:27.653Z
@PeterShor Aren't those six colorings induce the same partition of the vertex set?
Mohammad Al-Turkistany
CC BY-SA 4.0
2021-04-03T18:05:32.503Z
@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 
CC BY-SA 4.0
2021-04-03T18:09:21.323Z
@PeterShor Technically, your point is valid, but from practical viewpoint, all those six colorings are just one partition.
Mohammad Al-Turkistany
CC BY-SA 4.0
2021-04-03T18:12:16.650Z
@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
CC BY-SA 4.0
2021-04-03T18:18:31.060Z
@MohammadAl-Turkistany: I've modified my answer to circumvent these objections.
Peter Shor 
CC BY-SA 4.0
2021-04-03T18:20:01.283Z
Hamiltonian Cycle is NP-complete for cubic planar bipartite graphs.
Mohammad Al-Turkistany
CC BY-SA 4.0
2021-04-03T18:22:41.710Z
The input could be planar graph with even number of Hamiltonian cycles.
Mohammad Al-Turkistany
CC BY-SA 4.0
2021-04-03T19:35:03.450Z
Why is the planar embedding unique?
Mohammad Al-Turkistany
CC BY-SA 4.0
2021-04-03T20:19:25.837Z
@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 
CC BY-SA 4.0
2021-04-03T20:52:52.853Z
So for planar embeddings, different embeddings are congruent (up to orderings)?
Mohammad Al-Turkistany
CC BY-SA 4.0
2021-04-04T10:44:29.393Z
@MohammadAl-Turkistany: for 3-connected planar graphs, yes.
Peter Shor 
CC BY-SA 4.0
2021-04-13T15:29:16.480Z
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.)
Antoine Amarilli 'a3nm'
CC BY-SA 4.0
2021-04-14T14:17:26.297Z
@a3nm: That's right.
Peter Shor 
CC BY-SA 4.0
2021-04-03T13:34:11.697Z
2021-04-03T18:24:01.583Z
2021-04-03T18:24:01.583Z
Peter Shor 
<p>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.</p>
<p>For all known NP-complete problems, there is a parsimonious reduction from 3SAT. Oded Goldreich states the fact that &quot;all known reductions among <strong>natural</strong> <span class="math-container">$NP$</span>-complete problems are either parsimonious or can be easily modified to be so&quot;. ( <a href="http://books.google.com.sa/booksid=EuguvAw5OEC&amp;pg=PA204&amp;lpg=PA204&amp;dq=natural+problem+parsimonious+reduction&amp;source=bl&amp;ots=ORhA93Hr6i&amp;sig=3Oi_F70aiaVOZ2aYlQENBteqwV4&amp;hl=en&amp;sa=X&amp;ei=dUBeVK3oHbGu7Abui4DQBQ&amp;ved=0CB0Q6AEwAA#v=onepage&amp;q=natural%20problem%20parsimonious%20reduction&amp;f=false" rel="nofollow noreferrer">Computational Complexity: A Conceptual Perspective By Oded Goldreich</a>).</p>
<p><strong>Edit</strong>: This edit is solely to allow change of votes.</p>

CC BY-SA 3.0
2017-02-14T13:36:05.460Z
See also theorem 2.1: http://www.wisdom.weizmann.ac.il/~oded/PSX/prpr-r.pdf
Mohammad Al-Turkistany
CC BY-SA 4.0
2021-04-03T14:56:46.010Z
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
CC BY-SA 4.0
2021-04-03T17:44:24.667Z
@AndrasFarago You can't impose uniqueness promise on the solution set of those examples. It is never unique.
Mohammad Al-Turkistany
CC BY-SA 4.0
2021-04-05T21:36:20.857Z
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
CC BY-SA 4.0
2021-04-06T07:12:17.457Z
@AndrasFarago When $k \gt \Delta$, Are there Uniquely colorable graphs? See my comment on David's answer.
Mohammad Al-Turkistany
CC BY-SA 4.0
2021-04-13T15:30:36.703Z
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.
Antoine Amarilli 'a3nm'
CC BY-SA 4.0
2021-04-13T15:42:20.203Z
@a3nm Done as requested.
Mohammad Al-Turkistany
CC BY-SA 4.0
2021-04-13T15:43:29.713Z
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?
Antoine Amarilli 'a3nm'
CC BY-SA 4.0
2021-04-13T16:26:02.673Z
@a3nm I still support Goldreich's claim. To me, the other proposed problems seem to be artificial.
Mohammad Al-Turkistany
CC BY-SA 4.0
2021-04-13T17:20:37.780Z
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?
Antoine Amarilli 'a3nm'
CC BY-SA 4.0
2021-04-13T17:45:12.233Z
@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
CC BY-SA 4.0
2021-04-13T18:48:27.083Z
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.
Antoine Amarilli 'a3nm'
CC BY-SA 4.0
2021-04-13T19:47:01.360Z
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
CC BY-SA 4.0
2021-04-13T20:03:36.933Z
So it is subjective depending on your interpretation of what "natural" means.
Mohammad Al-Turkistany
CC BY-SA 4.0
2021-04-14T06:50:28.577Z
@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
CC BY-SA 4.0
2021-04-14T14:21:07.400Z
@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 
CC BY-SA 4.0
2021-04-14T21:47:50.777Z
@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
CC BY-SA 4.0
2021-04-20T15:16:44.940Z
@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 
CC BY-SA 4.0
2017-02-14T13:21:28.050Z
2021-04-13T15:41:52.517Z
2021-04-13T15:41:52.517Z
Mohammad Al-Turkistany
<p>I was recently reading a very nice paper by <a href="http://www.cc.gatech.edu/~Vijay.Vazirani/Unique.pdf">Valiant and Vazirani</a> 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.</p>

<p>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.</p>

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

CC BY-SA 3.0
2017-02-14T09:24:01.683Z
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
CC BY-SA 3.0
2017-02-14T09:53:13.267Z
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
CC BY-SA 3.0
2017-02-15T05:55:19.600Z
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
CC BY-SA 4.0
2021-04-13T15:07:03.207Z
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 ?
Antoine Amarilli 'a3nm'
<np-hardness><np-complete><unique-solution><promise-problems>
NP-Complete problems that admit an efficient algorithm under the promise of a unique solution
Devil
# NP-Complete problems that admit an efficient algorithm under the promise of a unique solution

(Asked by: username_0 on 2017-02-14)

I was recently reading a very nice paper by [Valiant and Vazirani](http://www.cc.gatech.edu/~Vijay.Vazirani/Unique.pdf) 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.

**Tags:** np-hardness, np-complete, unique-solution, promise-problems

> **Comments:**
> **username_1**: 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.  
> **username_2**: 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  
> **username_3**: As in username_1'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.  
> **username_4**: 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 ?  

---

## 3 answers

### Answer by username_6 on 2017-02-14. Score: 13 | Accepted answer

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](http://books.google.com.sa/booksid=EuguvAw5OEC&pg=PA204&lpg=PA204&dq=natural+problem+parsimonious+reduction&source=bl&ots=ORhA93Hr6i&sig=3Oi_F70aiaVOZ2aYlQENBteqwV4&hl=en&sa=X&ei=dUBeVK3oHbGu7Abui4DQBQ&ved=0CB0Q6AEwAA#v=onepage&q=natural%20problem%20parsimonious%20reduction&f=false)).

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

> **Comments:**
> **username_6**: See also theorem 2.1: http://www.wisdom.weizmann.ac.il/~oded/PSX/prpr-r.pdf  
> **username_5**: 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.)  
> **username_6**: @AndrasFarago You can't impose uniqueness promise on the solution set of those examples. It is never unique.  
> **username_5**: How about $k$-edge coloring for $k\geq 4$, with uniqueness promise? (See username_3's answer below.) It seems to contradict the claim "No NP-complete problem is known to admit a polynomial-time algorithm under uniqueness promise."  
> **username_6**: @AndrasFarago When $k \gt \Delta$, Are there Uniquely colorable graphs? See my comment on David's answer.  
> **username_4**: 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.  
> **username_6**: @a3nm Done as requested.  
> **username_4**: 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?  
> **username_6**: @a3nm I still support Goldreich's claim. To me, the other proposed problems seem to be artificial.  
> **username_4**: 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?  
> **username_6**: @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.  
> **username_4**: 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.  
> **username_6**: 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 .  
> **username_6**: So it is subjective depending on your interpretation of what "natural" means.  
> **username_6**: @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.  
> **username_7**: @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.  
> **username_6**: @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.  
> **username_7**: @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.  

---

### Answer by username_3 on 2021-04-03. Score: 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](https://doi.org/10.1016/S0167-5060(08)70511-9)",
*Ann. Discrete Math.* 3: 259–268.

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

> **Comments:**
> **username_5**: Goldreich claims that all known reductions among natural NP-complete problems are either parsimonious or can be easily modified to be so (see username_6's answer). Is there a parsimonious reduction between 3SAT and this problem?  
> **username_3**: 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.  
> **username_5**: 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.  
> **username_6**: 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$.  
> **username_3**: 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$.  
> **username_6**: @DavidEppstein What is $m$?  
> **username_3**: The usual and standard notation for the number of edges in an input graph.  
> **username_3**: 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.  

---

### Answer by username_7 on 2021-04-03. Score: 6

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

> **Comments:**
> **username_5**: 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.  
> **username_7**: 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.  
> **username_6**: @PeterShor Aren't those six colorings induce the same partition of the vertex set?  
> **username_7**: @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?  
> **username_6**: @PeterShor Technically, your point is valid, but from practical viewpoint, all those six colorings are just one partition.  
> **username_6**: @PeterShor Sorry for my ignorance, but I am not sure whether your interpretation of 3-coloring is standard in the graph coloring literature.  
> **username_7**: @MohammadAl-Turkistany: I've modified my answer to circumvent these objections.  
> **username_6**: Hamiltonian Cycle is NP-complete for cubic planar bipartite graphs.  
> **username_6**: The input could be planar graph with even number of Hamiltonian cycles.  
> **username_6**: Why is the planar embedding unique?  
> **username_7**: @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.  
> **username_6**: So for planar embeddings, different embeddings are congruent (up to orderings)?  
> **username_7**: @MohammadAl-Turkistany: for 3-connected planar graphs, yes.  
> **username_4**: 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.)  
> **username_7**: @a3nm: That's right.  

---

