Question: The complexity class $\mathsf{UP}$ consists of those $\mathsf{NP}$-problems that can be decided by a polynomial time nondeterministic Turing machine which has at most one accepting computational path. That is, the solution, if any, is *unique* in this sense. 
It is thought highly unlikely that all $\mathsf{UP}$-problems are in $\mathsf{P}$, because by the [Valiant-Vazirani Theorem](http://en.wikipedia.org/wiki/Valiant%E2%80%93Vazirani_theorem) this would imply the collapse $\mathsf{NP}=\mathsf{RP}$.

On the other hand, no $\mathsf{UP}$-problem is known to be $\mathsf{NP}$-complete, which suggests that the unique solution requirement still somehow makes them easier.

> 
> I am looking for examples, where the uniqueness assumption leads to a faster algorithm. 
> 
> 
> 

For example, looking at graph problems, can a maximum clique in a graph be found faster (though possibly still in exponential time), if we know that the graph has a *unique* maximum clique? How about unique $k$-colorability, unique Hamiltonian path, unique minimum dominating set etc.? 

In general, we can define a unique-solution version of *any* $\mathsf{NP}$-complete problem, scaling them down to $\mathsf{UP}$. Is it known for any of them that adding the uniqueness assumption leads to a faster algorithm? (Allowing that it still remains exponential.)

Answer: 
Shortest 2-Vertex disjoint path problem in undirected graphs [recently solved](http://thorehusfeldt.files.wordpress.com/2010/08/spdp-e5d5661.pdf) (ICALP14) by A. Bjorklund and T. Husfeldt. But the deterministic solution is for the case of existence of a unique solution. In the case that there are more than one solution, they showed that the problem belongs to **RP**. As authors of the paper mentioned, it is not known if the problem is in **P** in general scenario.
Mentioning another result by Björklund, if you are guaranteed that there is at most one Hamiltonian cycle in a graph, you can decide if a graph $G$ is Hamiltonian faster than you can in general.

The uniqeness assumption means that the parity of the number of Ham. paths is the same as deciding if the graph is Hamiltonian.

[Björklund's method](http://arxiv.org/pdf/1301.7250.pdf) deterministically computes the parity of the number of Hamiltonian cycles in $O(1.619^n)$ while the [best known randomized algorithm](http://arxiv.org/abs/1008.0541) for Undirected Hamiltonicity runs in $O^\*(1.657^n)$ , and the best deterministic algorithm for Directed Hamiltonicity (to the best of my knowledge) is still the 50 years old $O(n^22^n)$ dynamic programming algorithm by Bellman, Held and Karp.