4
$\begingroup$

Given a graph $G=(V,E)$. A fractional matching, say $f$, assigns every edge $e \in E$ to a fraction $f(e) \in [0,1]$, with the constraint: for $v \in V$, $\sum_{e \ni v}f(e) \leq 1 $.

My question is : does the fractional matching give a matching that we know (of $G$) i.e. with no conflicting edges? I am confused, since there is no criteria for choosing a fraction $f(e) \in [0,1]$, for every $e \in E$. For example, if we have $e_{1}, e_{2} \in E$ such that $v \in e_{1}, e_{2} $ and I assign $f(e_{1})=1/4$ and $f(e_{2})= 1/2$, then $f(e_{1})+f(e_{2})=3/4 \leq 1 $, hence both $e_{1}$ and $e_{2}$ should belong to the fractional matching.

Thank you in advance.

$\endgroup$
2
$\begingroup$

It is not possible to get a maximum matching from any fractional matching by only looking at the values of the fractional matching. Consider the undirected triangle graph with vertices $v_1,v_2,v_3$ and edges $e_1=(v_1,v_2), e_2=(v_1,v_3), e_3=(v_2,v_3)$. If we assign $f(e_1)=f(e_2)=f(e_3)=\frac{1}{2}$, this is a valid fractional matching. However, an actual matching can only contain one of the edges, so we cannot distinguish these edges by their value.

It is of course always possible to obtain a matching from a fractional matching by first selecting all edges with at least a certain fraction and then removing edges such that you end up with a matching. This matching, however, is usually not a maximum matching.

$\endgroup$

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.