Let $G(V,A,W):\ |V| = n,\ A=V\times V\setminus \lbrace (v,\ v)\rbrace,\ W\in\mathbb{R}_+^{n\times n},\ W^T\ne W $ be a complete directed graph with asymmetric weights.
Questions:
What is the complexity of determining the maximal oriented spanner $H\subset G$ with minimal difference between indegree and outdegree per vertex, i.e. for which $(u,v)\in H\iff (v,u)\notin H$ and $|deg(v)^+-deg(v)^-|\le 1$ for all $v\in V$ holds, that has minimal sum of arcweights?
Does $H$ contain the Vertex Cycle Cover of minimal weight?
The reason for asking is that is mentioned in the linked Wikipeda article that:
"Finding a vertex-disjoint cycle cover of a directed graph can also be performed in polynomial time by a similar reduction to perfect matching. However, adding the condition that each cycle should have length at least 3 makes the problem NP-hard"
and I wonder if it may simplify matters if one first determines the lightest maximal oriented subgraph as a preprocessing step even if it only serves for simpler/better heuristics.
As the Wikipedia article provides no further information about the NP-hard variant of the Vertex Cycle Cover problem, pointers to freely accessible online resources would be great.
Edit:
meanwhile I found out that finding the cheapest maximal oriented spanner with minimal maximal difference between the indegrees and outdegrees of the vertices is, in the case when the underlying graph with unoriented edges is eulerian, equivalent to the windy postman problem and can be solved in polynomial time as Zaw Win has shown.
