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: 
Outside of complexity theory and the analysis of algorithms, the assumption that there can be only one solution forms the basis for some of the standard rules used to deduce the solution in Sudoku puzzles. These rules generally involve looking for ways in which parts of the puzzle might be able to have two or more solutions that don't interact with the rest of the puzzle. That can't happen in the actual solution, so if a pattern that threatens to cause this is found, then it must be broken, allowing the solver to deduce constraints on what the actual solution can look like. See <http://www.brainbashers.com/sudokuuniquerectangles.asp> for some examples of deduction rules based on uniqueness.
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.