Many one and One many reductions I do not have enough complexity theory background, but I was wondering about the kind of reductions that we normally do to show NP-Completeness. I think all of the reductions that I have seen are one-to-one; in that, given an instance $I_1$ of problem $P_1$, they map it to instance $I'_1$ of problem $P'_1$ such that $I'_1$ is a yes instance of $P'_1$ iff $I_1$ is a yes instance of $P_1$.
But I have never seen any reduction which can, say map an instance $I_1$ of $P_1$ to say $2$ or more instances of $P_2$ (in some sense, the mapping should involve creating some structure in $I_2$ where we have $2$ or more choices and we could pick any one arbitrarily). This will be kind of surprising (to me) if it exists, but nevertheless the following question bothers me even more.
Leaving that aside, I have never seen any reduction which might map $2$ or more (say YES instances) of a problem $P$ to the same instance of some problem $Q$.
I would appreciate if you can exhibit these reductions for NP-Complete problems.
NOTE: I understand that this is more of a cstheory question. But since this is certainly not research level, I decided to post it here.
Thanks,
-Akash
 A: For an example of one to many, from my answer here: Reduction from Hamiltonian cycle to Hamiltonian path
For a reduction from Hamiltonian Cycle to Hamiltonian Path.

Given a graph $G$ of which we need to
  find Hamiltonian Cycle, for a single
  edge $e = \{u,v\}$ add new vertices
  $u'$ and $v'$ such that $u'$ is
  connected only to $u$ and $v'$ is
  connected only to $v$ to give a new
  graph $G_e$.
$G_e$ has a hamiltonian path if and
  only if $G$ has a hamiltonian cycle
  with the edge $e=\{u,v\}$.
Run the Hamiltonian path algorithm on
  each $G_e$ for each edge $e \in G$. If
  all graphs have no hamiltonian path,
  then $G$ has no hamiltonian cycle. If
  at least one $G_e$ has a hamiltonian
  path, then $G$ has a hamiltonian cycle
  which contains the edge $e$.

A: The easiest way to get a many-to-one reduction is to partially solve the original problem.
For example, suppose we want to reduce CLIQUE to 3COLORABILITY. We get as input a pair $(G,k)$ and need to output $G'$ where $G'$ is 3-colorable iff $G$ has a clique of size exactly $k$. 
We will proceed as follows.


*

*If $k\leq 10$, solve CLIQUE by brute force in time O(n^10). If $G$ contains a clique of size $k$ output the trivial graph. Otherwise, output $K_4$.

*If $k>10$, then use the standard reduction.


Every graph of the form $(G,k)$, $k\leq 10$, reduces to the same 2 graphs.
I realize that this seems artificial (because it is). The reason that you rarely see such reductions in practice is that it's often easier to reason about a 1-1 reduction. After all, you're trying to show that $x\in P \Leftrightarrow f(x)\in Q$ and so the reverse implication is often easier that way.
