4
$\begingroup$

For the maximum matching problem, we can find the fractional matching which I understand involves some sort of weighting for the edges. However, I cannot seem to find an exact and simple explanation of what a fractional matching is. How does it compare to an integral matching?

If this question seems too basic, could I please have a link to somewhere that explains it?

$\endgroup$
  • $\begingroup$ "involves some sort of weighting for the edges" It quite literally is a weighting for the edges, with suitable constraints. Could you explain what it is you do not understand about that? Otherwise, I'm not quite sure what you're asking. $\endgroup$ – Discrete lizard Apr 18 at 11:25
  • $\begingroup$ Can you give a reference or the full problem where you encoutered the "fractional matching" notion ? $\endgroup$ – Vince Apr 18 at 11:28
  • $\begingroup$ I suppose I'm looking for a clear definition of fractional matching. What exactly constitutes a matching that is fractional? With a normal matching, it's a set of edges that have no common vertices. How does that differ in a fractional matching? Sorry if it's unclear. $\endgroup$ – monadoboi Apr 18 at 11:30
8
$\begingroup$

Given a graph $G=(V,E)$, we can represent a matching as a function $f$ from the edges $E$ to $\{0,1\}$ such that for each vertex $v\in V$, we have $\sum_{w\in N(v)} f(v,w) \leq1$, where $N(v)$ is the neighbourhood of $v$, i.e. the set of its adjacent vertices. (We have equality for a perfect matching) In this representation, $f(e)=1$ means the edge $e$ is part of the matching.

A fractional matching can then be represented by a function $f'$ from the edges $E$ to the continuous interval $[0,1]$, with the same constraint, i.e. $\sum_{w\in N(v)} f'(v,w) \leq1$. So, intuitively, each vertex is 'divided' over its incident edges such that it is participating in at most one edge 'in total'.

$\endgroup$
6
$\begingroup$

To add to Discrete lizard's answer, I would recommend you look into mathematical programming and optimization. The matching problem can be modelled as what is called an integer program (in fact the constraints that $\sum_{w\in N(v)} f(v,w) \leq1$ for all $v \in V$ are the constraints that define the matching problem where for each $e \in E$, $f(e)$ is a variable. Furthermore, an integer program demands that the variables be integers. But you can see a natural relaxation of the integer program into a linear program by allowing your variables to take non-integer values. Solutions to this relaxed optimization problem are what we call fractional matchings.

A lot of problems on graphs can be modelled as integer programs, and relaxing them to linear programs is a common technique, so it might be worth looking into.

$\endgroup$
  • 2
    $\begingroup$ Indeed, integer programming (IP) is related, but I'd like to add a few remarks. First, solving IPs in general is an NP-hard problem, while a maximum cardinality matching can be found in polynomial time with the Hungarian algorithm. The IP formulation still has its uses, however, in case there are additional constraints that can nicely be encoded in an IP. Second, if (and only if) our graph is bipartite, the matrix describing the IP is totally unimodular, which means that the IP has the same solution as the relaxed LP and in particular that therefore there are no optimal fractional matchings. $\endgroup$ – Discrete lizard Apr 18 at 14:19
  • 1
    $\begingroup$ Welcome to the site! $\endgroup$ – David Richerby Apr 18 at 16:13
4
$\begingroup$

The formal definitions are very nice, but here's a simplier more intuitive explanation. In a fractional matching, every edge has a number. The sum all all the edge numbers connected to any vertex must be less than 1.

$\endgroup$
  • $\begingroup$ This is what I meant by the last sentence of my answer, but you have phrased it a bit better. $\endgroup$ – Discrete lizard Apr 21 at 13:16

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.