I need to find a cost-optimal 1-factor in a positively weighted, directed, regular graph $G(V,A)$ without antiparallel arcs, i.e. given $$\text{deg}_{\text{in}}(u)=\text{deg}_{\text{in}}(v)=\text{deg}_{\text{out}}(v)=\text{deg}_{\text{out}}(u)\ \ \forall u,v\in V$$ $$a_{ij}\in G\implies a_{ji}\notin G$$ $$c_{ij}:= c(a_{ij}) \gt 0$$
determine $\alpha_{ij}\in\lbrace 0,1\rbrace$, so that
$$\sum_j{\alpha_{ij}}=\sum_i{\alpha_{ij}}=1$$
and
$$\sum{\alpha_{ij}c_{ij}} = \text{opt}$$
That problem can be easily solved without the integer constraints via linear programming.
It is also possible to solve it via negative cycle cancellation after vertex splitting.
Question:
can the above problem be solved without linear programming and without vertex splitting, using one of the graph theoretic algorithms for mincost flows?
