[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.
How about the Monte Carlo method? Generate $k\gg 1$ graphs at random, count how many of them have a path from $u$ to $v$, then divide by $k$.
This is about the best polynomial-time approximation known for the general problem, "s-t reliability". In particular it is not known whether there is a fully polynomial randomised approximation scheme. See Rico Zenklusen's PhD dissertation for more information.
Best Answer
The answer to both questions is negative, if one wants to have an acyclic digraph that is strongly connected, in the sense that any two nodes have a directed path between them in one direction or the other.
A counterexample is provided by any tree having at least three leaves. It must be that two of the leaves are sources, or two are sinks, and in either case, there is no directed path between those two leaves.
If you drop the connectivity requirement, as you have suggested, then it is easy: place any linear order on the vertices of the original graph, and simply orient the edges to conform with that order. This is called a grading. Since you asked for a reference, graded digraphs are used in Every model of set theory embeds into its own constructible universe, where I develop a little of the theory in section 2, but I assume this is a standard topic in graph theory and there must be other references.