I don't see the equivalence to the travelling salesman problem. I think the following works for acyclic networks:
Split every node $v$ except start and end node into two copies $v^-$ and $v^+$, and add the arcs $(v^-,v^+)$. An arc $(v,w)$ of the original network is replaced by the arc $(v^+,w^-)$ with cost equal to the cost of $(v,w)$. Then your problem should be equivalent to finding a min cost flow with upper and lower capacity equal to one for the arcs of the form $(v^-,v^+)$.
[edited]
It seems this question is NP-Complete.
The general idea:
In a graph which is a 3-regular graph minus an edge,
a spanning tree that minimizes $\max x_i$ is (more or less) an Hamiltonian Path.
Some more work is needed in order to make it an Hamiltonian Cycle;
finding an Hamiltonian Cycle in a 3-regular bipartite graph is NP-complete.
Assume there is an algorithm for finding such a set $C$ for any bipartite graph.
Consider only the subclass of graphs with $v_1 = v_2$, that are also 3-regular.
Consider a 3-regular bipartite graph $G$.
Add two vertices to the graph, $a_1\in V_1$, $a_2 \in V_2$.
We repeat the rest for every choice of an edge $(b_1,b_2) \in E$:
Split $(b_1,b_2)$ into the two edges $(a_1, b_2)$ and $(b_1, a_2)$;
mark the new graph as $G'=(V,E')$.
Run the algorithm on $G'$ to find a set $C$ of edges that minimizes $\max x_i$.
If the value returned is $1$, then $E' \setminus C$ induces an
Hamiltonian Cycle in $G$;
if a value greater than $1$ is always returned, no such cycle exists in $G$.
From the new vertices, $a_1$ and $a_2$,
the algorithm cannot remove an edge, as it will leave them disconnected.
From any other vertex, it must remove at one edge in average,
as every other vertex has degree 3.
The algorithm can find a set $C$ with $\min \max x_i = 1$
iff its complement $E' \setminus C$ is an Hamiltonian Path connecting $b_1$ and $b_2$;
this path induces an Hamiltonian Cycle in $G$.
Finding an Hamiltonian Cycle in a 3-regular bipartite graphs is NP-Complete (see this article), which completes the proof.
Best Answer
Suresh suggested DFS, MRA pointed out that it's not clear that works. Here's my attempt at a solution following that thread of comments. If the graph has $m$ edges, $n$ nodes, and $p$ paths from the source $s$ to the target $t$, then the algorithm below prints all paths in time $O((np+1)(m+n))$. (In particular, it takes $O(m+n)$ time to notice that there is no path.)
The idea is very simple: Do an exhaustive search, but bail early if you've gotten yourself into a corner.
Without bailing early, MRA's counter-example shows that exhaustive search spends $\Omega(n!)$ time even if $p=1$: The node $t$ has only one adjacent edge and its neighbor is node $s$, which is part of a complete (sub)graph $K_{n-1}$.
Push s on the path stack and call search(s):
Here search does the exhaustive search and stuck could be implemented in DFS style (as here) or in BFS style.