Tag Info

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