Edge-covering number of 2-polymatroids

Definitions and mathematical statement

Let $S$ be finite. A $2$-polymatroid rank function is a map $f:2^S\to\mathbb Z_{\ge0}$ with $f(\varnothing)=0$, monotone under inclusion, submodular, and satisfying $f(X)\le2|X|$. Submodularity means $f(X)+f(Y)\ge f(X\cap Y)+f(X\cup Y)$. Assume a matroid $M$ on $S\times\{1,2\}$, with rank function $r$, represents $f$: \[ r(X\times\{1,2\})=f(X). \] A circuit is an inclusion-minimal dependent set of $M$. Require that every circuit contain at most one member of each pair $\{(e,1),(e,2)\}$.

A matching of $f$ is $J\subseteq S$ with $f(J)=2|J|$. Let $\mathcal M$ be the family of these matchings and define \[ \beta(f)=\min\{t:S=J_1\cup\cdots\cup J_t, J_i\in\mathcal M\}, \] \[ \beta^*(f)=\min\left\{\sum_{J\in\mathcal M}z_J: z_J\ge0,\ \sum_{J\ni e}z_J\ge1\ (e\in S)\right\}. \] In the nonvacuous case where a cover exists, must $\beta(f)\le\beta^*(f)+1$ hold?

Coverability is equivalent to $f(\{e\})=2$ for every $e$; otherwise both covering problems are infeasible. Matchings in a cover may overlap, and fractional coefficients are arbitrary nonnegative reals. The circuit restriction is a hypothesis on the given representation and must not be discarded in favor of an arbitrary $2$-polymatroid. The claimed additive loss is one, rather than a multiplicative approximation.

Short English statement

For the specified matroid-representable 2-polymatroids, is the integral matching-cover number at most the fractional number plus one?

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 3000031 (AMR-029-0031), 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: Edge-covering number of 2-polymatroids. Original source indexed by AMR-029-0031. https://oldlemon.cs.elte.hu/egres/open/List_of_open_problems.
• S3 EGRES Open, Edge-covering number of 2-polymatroids. Individual source statement and remarks. https://lemon.cs.elte.hu/egres/open/Edge-covering_number_of_2-polymatroids.