HiveBrain v1.2.0
Get Started
← Back to all entries
snippetMinor

How to construct an ordinary matching from a fractional matching?

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
fractionalordinaryhowconstructfrommatching

Problem

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.

Solution

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.

Context

StackExchange Computer Science Q#110454, answer score: 2

Revisions (0)

No revisions yet.