# Maximum-weight matching with a bounded number of fractional edges

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?

• Could you edit the question to specify all your requirements? Currently your question could be answered by giving an exponential-time algorithm and that would meet all stated requirements, but I doubt such an answer would be useful. Are you looking for a polynomial-time algorithm? Any algorithm that is faster than the best you already know of, and if so, what is the best algorithm you know of so far?
– D.W.
Oct 25, 2021 at 7:32
• @D.W. I clarified that the algorithm should be polynomial time. When the bound on the number of fractional edges is either 0 or $m$ (the total number of edges in the graph), it is well known that the problem can be solved in polynomial time, so I believe it should be polynomial also for any fixed number between 0 and $m$. But so far I could not find any such algorithm. Oct 26, 2021 at 9:26
• I think Bourjolly and Pulleyblank's algorithm should still work, though I don't verify it carefully. Nov 15, 2021 at 6:39
• @xskxzr thanks a lot, this paper is indeed very relevant! I added to the OP a summary of the paper, as I understood it. Nov 17, 2021 at 17:52

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.
• It is indeed polynomial-time when the number of fractional vertices is considered a fixed parameter (not part of the input). But if the number of fractional vertices is, say, $m/4$, then the run time is exponential in $m$. But if the number of fractional vertices is $m$, that the problem is again polynomial-time - which seems strange. Oct 30, 2021 at 20:01
• @ErelSegal-Halevi It's not strange. Many problems have similar structure. For example, the independent set problem is easy to solve if $k$ is a constant or $n$ minus a constant. By the way, I guess your problem is NP-hard in general cases, but it's not that easy to prove. Oct 31, 2021 at 2:51