Orientation-compatible w-vertex cover

Definitions and mathematical statement

Let $D=(V,A)$ be a finite loopless digraph. Each arc $a=uv$ has a nonnegative even integer weight $w_a$, given in binary. A $w$-vertex cover is an integer vector $x\in\mathbb Z_{\ge0}^V$ satisfying \[ x_u+x_v\ge w_{uv}\quad(uv\in A). \] The inequality treats the endpoints symmetrically, even though the extra requirement below depends on the direction of the arc. Parallel arcs may carry different weights and must each be respected.

Find, in time polynomial in the encoded input size, such a cover with \[ x_v>0\ \Longrightarrow\ \text{there exists }uv\in A\text{ with }x_u+x_v=w_{uv} \qquad(v\in V). \] Every positive coordinate must therefore be supported by a tight incoming arc. In particular, a vertex with no incoming arc must have coordinate zero. A zero coordinate requires no witness.

The cited source proves that a cover satisfying these conditions exists for every permissible instance; the unresolved task is its polynomial-time construction. There is no objective of minimizing $\sum_v x_v$, and an arbitrary minimum vertex cover need not satisfy the directional witness condition. Fractional covers are not valid outputs: integrality and the even-weight hypothesis belong to the formulation. A running time polynomial in the numerical value of the largest weight alone would be pseudopolynomial, not the requested bound in its binary input length.

Short English statement

Find an integer weighted vertex cover in polynomial time so that every positive coordinate has a tight incoming arc.

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 3000062 (AMR-029-0062), AMR Open Problem Lists. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Egres Open - List of open problems, Open-problem page: Orientation-compatible w-vertex cover. Original source indexed by AMR-029-0062. https://oldlemon.cs.elte.hu/egres/open/List_of_open_problems.
• S3 EGRES Open, Orientation-compatible w-vertex cover. Individual source statement and remarks. https://lemon.cs.elte.hu/egres/open/Orientation-compatible_w-vertex_cover.