# 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.