How can I reduce a product of transpositions?
I suspect your problem is NP-hard, but if you need to solve it in practice, I recommend using a SAT solver to help you.

Algorithms

I suggest you solve this using a SAT solver.  The problem can be expressed in a fairly straightforward way as an instance of SAT, and then you can apply an off-the-shelf SAT solver.

Let's solve the following problem:

Input: $\ell \in \mathbb{N}$; a set $T$ of $m$ transpositions; a permutation $\pi$
Question: Does there exist a way to express $\pi$ as a product of $\le \ell$ transpositions?

We'll construct a way to solve this problem using SAT, then apply binary search over $\ell$ to find the optimal solution.

For simplicity, add the identity element to $T$.  Then we can replace "$\le \ell$" with "exactly $\ell$".  Now the question can be expressed in a rather straightforward way as a CNF formula.

In particular, introduce boolean unknowns $x_{i,\tau}$ (for each $i=1,2,\dots,\ell$ and each $\tau \in T$), with the intended meaning that $x_{i,\tau}=1$ means that $\tau$ is the $i$th transposition in the output sequence.  Also, introduce boolean unknowns $y_{i,j,k}$, where $y_{i,j,k}=1$ is intended to mean that the first $i$ transpositions in the output sequence map $j$ to $k$.  We add constraints:


For each $i$, we require that exactly one of the $x_{i,\tau}$ is 1.
We require that the product of the transpositions yields $\pi$, i.e., $y_{\ell,j,\pi(j)}=1$ for all $j$.
We require that the $x$'s and $y$'s are consistent, e.g.,

$$y_{i+1,j,k} = \bigvee_{\tau} y_{i,j,\tau^{-1}(k)} \land x_{i,\tau}.$$
We require that $y_{0,j,j}=1$ for all $j$ and $y_{0,j,k}=0$ for $j \ne k$.


Now feed this to a SAT solver.  This should be satisfiable if and only if there's a way to express $\pi$ as a product of $\ell$ transpositions from $T$.

Finally, use binary search on $\ell$, as mentioned above, to find the shortest possible way to express $\pi$ as a product of transpositions from $T$.

(There are many different ways to express this problem as SAT, and those choices might affect the performance of the SAT solver.  So, if you need to solve this in practice, you might experiment with different ways of encoding the constraints into SAT.)

Hardness

I suspect your problem is NP-hard.

Researchers have studied a natural generalization of this problem where the set $T$ is allowed to contain arbitrary permutations, rather than just transpositions:

Inputs: $\ell \in \mathbb{N}$; a set $S$ of permutations; a permutation $\pi$
Question: Is there a way to express $\pi$ as a product of $\le \ell$ permutations from $S$?

This problem is NP-hard, as proven in the following paper:

The Minimum-Length Generator Sequence Problem is NP-Hard.  S. Even, O. Goldreich.  Journal of Algorithms, vol 2, pp.311-313, 1981.

This problem remains NP-hard even if \ell is specified in unary (i.e., there is not likely to be an algorithm that is polynomial in the length of the output).  Subsequent work showed that the problem is PSPACE-complete if $\ell$ is specified in binary.  That's not the same problem as yours, because you have the extra condition that $T$ contains only transpositions, but it is related.

A subsequent paper showed that if $T$ generates a transitive group, then the problem is NP-hard.  In your case, this corresponds to the condition that the underlying graph be connected.  I suspect you're dealing with a connected graph (otherwise you can trivially decompose into connected components and the complexity will depend on the size of the largest connected component).  As a result, this appears to imply that your problem is NP-hard.

This hardness result is mentioned in Section 4 of the following paper:

The complexity of finding minimum-length generator sequences.  Mark R. Jerrum.  Theoretical Computer Science, vol 36, pp.265--289, 1985.

Assuming this is right, your options are to either look for a heuristic that will be always-efficient but not-always-optimal, or look for an always-optimal algorithm whose running time is not guaranteed to be always-efficient (e.g., by using a SAT solver).

Caveat: I don't have 100% confidence in my reasoning here.  If I understand things correctly, it seems to contradict another claim in the same paper (namely, the one mentioned below about adjacent transpositions; those generate a transitive group, yet the corresponding problem isn't NP-hard).  So I don't have full confidence that the problem is NP-hard.  It's entirely possible I've misunderstood something or mis-applied the paper's results.

Other resources

Subsequent work has also shown that certain special cases can be solved in polynomial time, e.g., where $T$ contains all transpositions, or where $T$ contains all adjacent transpositions $(i,i+1)$, or where $T$ contains all cyclicly adjacent transpositions (i.e., all transpositions of the form $(i,i+1)$ together with $(n,1)$).  However, that's probably not useful to you, as those correspond to rather trivial graphs (the complete graph, a line graph, or a $n$-cycle $C_n$).

You might also be interested in https://cstheory.stackexchange.com/q/21899/5038