Maximum-weight matching with a bounded number of fractional edges

Question

In graphs with odd cycles, the maximum weight of a fractional matching may be higher than that of a standard matching. For example, in a cycle of length 3, where all edges have weight 1, the maximum-weight matching contains a single edge so its weight is 1, but the maximum-weight fractional matching contains 50% of each edge so its weight is 1.5. So, allowing some edges to be fractional can improve the total matching weight.

Suppose we want to allow only a limited number of edges to be fractional (e.g. at most three edges). What is a polynomial-time algorithm for finding a maximum-weight fractional matching with this constraint?

When the bound on the number of fractional edges is 0, the problem can be solved by Edmonds' algorithm in time $O(n^2 m)$ (where $n$ is the number of vertices and $m$ the number of edges). When the bound is $m$, the problem can be solved in polynomial time by solving a linear program. Based on this, I believe that for any limit between 0 and $m$, the problem should be solvable in polynomial time. But so far I could not find any polynomial-time algorithm.

---

EDIT: xskxzr commented on a paper by Bourjolly and Pulleyblank, which is indeed closely-related. Its focus is on minimum fractional vertex cover (min-FVC), which is the dual of maximum fractional matching (max-FM; the linear program of min-FVC is the dual of the linear program of max-FM). What I understood from their paper is the following:

• There is an algorithm (in Section 4) for finding a max-FM in a general graph in time $O(|V| |E|)$.
• The same algorithm finds sets of vertices $V_0,V_1$ that have a weight of $0$ ($1$) in any min-FVC.
• They can find a set $F$ of vertices that have a fractional weight in any min-FVC.
• They have an algorithm (in Section 5) for finding a min-FVC in which only the vertices of $F$ are fractional; therefore, the number of fractional vertices is minimized, subject to finding a globally-minimum FVC. The run-time, if I understand correctly, is $O(|V| |E|)$.

This raises two follow-up questions:

1. Suppose we are given an integer $k$, which is smaller than $|F|$, and we want to find an FVC with at most $k$ fractional vertices. The size of this FVC will, by definition, be larger than the min-FVC. Can we find an FVC of minimum cardinality, subject to the constraint of at most $k$ fractional vertices? Ideally, the run-time should not depend on $k$.

2. Is it possible to find a set of edges that must have a fractional weight in every max-FM? Is it possible to find a max-FM in which only these edges are fractional?

3. Is it possible to solve problem 1 for max-FM?

Answer 1

Let $S$ be the subset of edges that are "really fractional" (i.e., in (0, 1)) in the optimal solution. Since you only allow a constant number of edges to be fractional, you can try every possibility of $S$. Given $S$, let $V(S)$ denote the vertices incident to edges in $S$, you can then remove all edges incident to $V(S)$ but not in $S$. Now you can do maximum fractional matching on $S$ and maximum integral matching on edges not in $S$ seperately.