Maximum weight bounded fractional matching

Definitions and mathematical statement

Let $G=(V,E)$ be a finite undirected graph. Its perfect-matching polytope is \[ P(G)=\operatorname{conv}\{\mathbf1_M:M\text{ is a perfect matching of }G\}. \] An empty family gives an empty feasible polytope. Given nonnegative rational edge weights $w_e$ and capacities $u_e$, solve \[ \max\left\{\sum_{e\in E}w_ex_e: x\in P(G),\ 0\le x\le u\right\}, \] or correctly report infeasibility.

The requested algorithm is combinatorial and strongly polynomial. Its number of arithmetic operations and comparisons must be bounded by a polynomial in $|V|+|E|$, independent of numerical magnitudes, with intermediate encoding lengths polynomial in the input size. The source further specifies linear dependence of arithmetic on the capacity data: additions, comparisons and multiplication by constants independent of those capacities, rather than products of varying capacity quantities. This requirement distinguishes the target from general-purpose rational linear programming.

The vector $x$ is allowed to be fractional, but it must lie in the convex hull of actual perfect matchings. The simpler constraints $x\ge0$ and $x(\delta(v))=1$ alone do not describe this polytope in general nonbipartite graphs. Nor is $x$ required to be one capacity- respecting perfect matching; convex combinations can be feasible even when no individual perfect matching obeys the same capacities.

Short English statement

Can capacity-constrained optimization over the perfect-matching polytope be solved by a combinatorial strongly polynomial algorithm linear in the capacity data?

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 3000053 (AMR-029-0053), 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: Maximum weight bounded fractional matching. Original source indexed by AMR-029-0053. https://oldlemon.cs.elte.hu/egres/open/List_of_open_problems.
• S3 EGRES Open, Maximum weight bounded fractional matching. Individual source page and explanatory remarks. https://lemon.cs.elte.hu/egres/open/Maximum_weight_bounded_fractional_matching.