Orientation-compatible w-vertex cover
From Egres Open
Given a digraph D=(V,A) and non-negative even-valued arc weights [math]w_a\ (a \in A)[/math], can we find in polynomial time a w-vertex cover [math]x[/math] of the underlying undirected graph with the additional property that for every node v with [math]x_v\gt0[/math] there is an arc [math]uv\in A[/math] with [math]x_u+x_v=w_a[/math]?
Remarks
It was shown by T. Király and J. Pap [1] using a polyhedral version of Sperner's Lemma that a w-vertex cover with this property always exists. They also showed that it can be found in polynomial time if each node has in-degree 1.
