New answers tagged unique-solution
11
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 ...
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 ...
Top 50 recent answers are included
