4
$\begingroup$

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?

$\endgroup$
4
  • $\begingroup$ 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? $\endgroup$
    – D.W.
    Oct 25, 2021 at 7:32
  • $\begingroup$ @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. $\endgroup$ Oct 26, 2021 at 9:26
  • 1
    $\begingroup$ I think Bourjolly and Pulleyblank's algorithm should still work, though I don't verify it carefully. $\endgroup$
    – xskxzr
    Nov 15, 2021 at 6:39
  • $\begingroup$ @xskxzr thanks a lot, this paper is indeed very relevant! I added to the OP a summary of the paper, as I understood it. $\endgroup$ Nov 17, 2021 at 17:52

1 Answer 1

2
+25
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ But OP asked for polynomial time algorithm. $\endgroup$ Oct 30, 2021 at 8:49
  • $\begingroup$ @InuyashaYagami Isn't this algorithm polynomial? $\endgroup$
    – xskxzr
    Oct 30, 2021 at 9:34
  • $\begingroup$ 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. $\endgroup$ Oct 30, 2021 at 20:01
  • 1
    $\begingroup$ @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. $\endgroup$
    – xskxzr
    Oct 31, 2021 at 2:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.