Fractional matching

In graph theory, a fractional matching is a generalization of a matching in which, intuitively, each vertex may be broken into fractions that are matched to different neighbor vertices.

Definition

Given a graph ${\displaystyle G=(V,E)}$ , a fractional matching in ${\displaystyle G}$  is a function that assigns, to each edge ${\displaystyle e\in E}$ , a fraction ${\displaystyle f(e)\in [0,1]}$ , such that for every vertex ${\displaystyle v\in V}$ , the sum of fractions of edges adjacent to ${\displaystyle v}$  is at most one:^[1] $${\displaystyle \forall v\in V:\sum _{e\ni v}f(e)\leq 1}$$  A matching in the traditional sense is a special case of a fractional matching, in which the fraction of every edge is either zero or one: ${\displaystyle f(e)=1}$  if ${\displaystyle e}$  is in the matching, and ${\displaystyle f(e)=0}$  if it is not. For this reason, in the context of fractional matchings, usual matchings are sometimes called integral matchings.

Size

The size of an integral matching is the number of edges in the matching, and the matching number ${\displaystyle \nu (G)}$  of a graph ${\displaystyle G}$  is the largest size of a matching in ${\displaystyle G}$ . Analogously, the size of a fractional matching is the sum of fractions of all edges. The fractional matching number of a graph ${\displaystyle G}$  is the largest size of a fractional matching in ${\displaystyle G}$ . It is often denoted by ${\displaystyle \nu ^{*}(G)}$ .^[2] Since a matching is a special case of a fractional matching, the integral matching number of every graph ${\displaystyle G}$  is less than or equal to the fractional matching number of ${\displaystyle G}$ ; in symbols:$${\displaystyle \nu (G)\leq \nu ^{*}(G).}$$ A graph in which ${\displaystyle \nu (G)=\nu ^{*}(G)}$  is called a stable graph.^[3] Every bipartite graph is stable; this means that in every bipartite graph, the fractional matching number is an integer and it equals the integral matching number.

In an arbitrary graph, ${\displaystyle \nu (G)>{\tfrac {2}{3}}\nu ^{*}(G).}$  The fractional matching number is either an integer or a half-integer.^[4]

Matrix presentation

For a bipartite graph ${\displaystyle G=(X,Y,E)}$ , a fractional matching can be presented as a matrix with ${\displaystyle |X|}$  rows and ${\displaystyle |Y|}$  columns. The value of the entry in row ${\displaystyle x}$  and column ${\displaystyle y}$  is the fraction of the edge ${\displaystyle (x,y)}$ .

Perfect fractional matching

A fractional matching is called perfect if the sum of weights adjacent to each vertex is exactly one. The size of a perfect matching is exactly ${\displaystyle |V|/2}$ .

In a bipartite graph ${\displaystyle G=(X,Y,E)}$ , a fractional matching is called ${\displaystyle X}$ -perfect if the sum of weights adjacent to each vertex of ${\displaystyle X}$  is exactly one. The size of an ${\displaystyle X}$ -perfect fractional matching is exactly ${\displaystyle |X|}$ .

For a bipartite graph ${\displaystyle G=(X,Y,E)}$ , the following are equivalent:

• ${\displaystyle G}$  admits an ${\displaystyle X}$ -perfect integral matching,
• ${\displaystyle G}$  admits an ${\displaystyle X}$ -perfect fractional matching, and
• ${\displaystyle G}$  satisfies the condition to Hall's marriage theorem.

The first condition implies the second because an integral matching is a fractional matching. The second implies the third because, for each subset ${\displaystyle W\subset X}$ , the sum of weights incident to vertices of ${\displaystyle W}$  is ${\displaystyle W}$ , so the edges adjacent to them are necessarily adjacent to at least ${\displaystyle W}$  vertices of ${\displaystyle Y}$ . By Hall's marriage theorem, the last condition implies the first one.^[5]

In a general graph, the above conditions are not equivalent – the largest fractional matching can be larger than the largest integral matching. For example, a 3-cycle admits a perfect fractional matching of size ${\displaystyle {\tfrac {3}{2}}}$  (the fraction of every edge is ${\displaystyle {\tfrac {3}{2}}}$ ), but does not admit a perfect integral matching – its largest integral matching is of size one.

Algorithmic aspects

A largest fractional matching in a graph can be found by linear programming, or alternatively by a maximum flow algorithm. In a bipartite graph, it is possible to convert a maximum fractional matching to a maximum integral matching of the same size. This leads to a polynomial-time algorithm for finding a maximum matching in a bipartite graph.^[6]

If ${\displaystyle G=(X,Y,E)}$  is a bipartite graph with ${\displaystyle |X|=|Y|=n}$ , and ${\displaystyle M}$  is a perfect fractional matching, then the matrix representation of ${\displaystyle M}$  is a doubly stochastic matrix – the sum of elements in each row and each column is one. Birkhoff's algorithm can be used to decompose the matrix into a convex sum of at most ${\displaystyle n^{2}-2n+2}$  permutation matrices. This corresponds to decomposing ${\displaystyle M}$  into a convex combination of at most ${\displaystyle n^{2}-2n+2}$  perfect matchings.

Maximum-cardinality fractional matching

A fractional matching of maximum cardinality (i.e., maximum sum of fractions) can be found by linear programming. There is also a strongly-polynomial time algorithm,^[7] using augmenting paths, that runs in time ${\displaystyle O(|V|\cdot |E|)}$ .

Maximum-weight fractional matching

Suppose each edge on the graph has a weight. A fractional matching of maximum weight in a graph can be found by linear programming. In a bipartite graph, it is possible to convert a maximum-weight fractional matching to a maximum-weight integral matching of the same size, in the following way:^[8]

• Let ${\displaystyle f}$  be the fractional matching.
• Let ${\displaystyle H}$  be a subgraph of ${\displaystyle G}$  containing only the edges ${\displaystyle e}$  with non-integral fraction, ${\displaystyle 0<f(e)<1}$ .
• If ${\displaystyle H}$  is empty, then ${\displaystyle f}$  already describes an integral matching.
• if ${\displaystyle H}$  has a cycle, then it must be even-length (since the graph is bipartite). One can construct a new fractional matching ${\displaystyle f_{1}}$  by transferring a small fraction ${\displaystyle \varepsilon }$  from edges in even positions around the cycle to edges in odd positions, and a new fractional matching ${\displaystyle f_{2}}$  by transferring ${\displaystyle \varepsilon }$  from odd edges to even edges. Since ${\displaystyle f}$  is the average of ${\displaystyle f_{1}}$  and ${\displaystyle f_{2}}$ , the weight of ${\displaystyle f}$  is the average between the weight of ${\displaystyle f_{1}}$  and of ${\displaystyle f_{2}}$ . Since ${\displaystyle f}$  has maximum weight, all three matchings must have the same weight. There exists a choice of ${\displaystyle \varepsilon }$  for which at least one of ${\displaystyle f_{1}}$  and ${\displaystyle f_{2}}$  has fewer edges with non-integral fraction. Continuing in the same way leads to an integral matching of the same weight.
• Supposing that ${\displaystyle H}$  has no cycle, let ${\displaystyle P}$  be a longest path in ${\displaystyle H}$ . As above, one can construct two matchings ${\displaystyle f_{1}}$  and ${\displaystyle f_{2}}$  by transferring ${\displaystyle \varepsilon }$  from edges in even positions along the path to edges in odd positions, or vice versa. Because ${\displaystyle P}$  is a longest path, its endpoints have no other edges of ${\displaystyle H}$  incident to them, and any incident edges in ${\displaystyle G\setminus H}$  must have zero as their fraction, so this transfer cannot overload these vertices. Again ${\displaystyle f_{1}}$  and ${\displaystyle f_{2}}$  must have maximum weight, and at least one of them has fewer non-integral fractions.

Fractional matching polytope

Given a graph ${\displaystyle G=(V,E)}$ , the fractional matching polytope of ${\displaystyle G}$  is a convex polytope that represents all possible fractional matchings of ${\displaystyle G}$ . It is a polytope in ${\displaystyle \mathbb {R} ^{|E|}}$  – the ${\displaystyle |E|}$ -dimensional Euclidean space. Each point ${\displaystyle (x_{1},\dots ,x_{|E|})}$  in the polytope represents a matching in which, for some numbering of the edges as ${\displaystyle e_{1},\dots ,e_{|E|}}$ , the fraction of each edge is ${\displaystyle f(e_{i})=x_{i}}$ . This polytope is defined by ${\displaystyle |E|}$  non-negativity constraints (${\displaystyle x_{i}\geq 0}$  for all ${\displaystyle i=1,\dots ,|E|}$ ) and ${\displaystyle |V|}$  vertex constraints (the sum of ${\displaystyle x_{i}}$ , for all edges ${\displaystyle e_{i}}$  that are adjacent to a vertex ${\displaystyle v}$ , is at most one).

For a bipartite graph, this is the matching polytope, the convex hull of the points in ${\displaystyle \mathbb {R} ^{|E|}}$  that correspond to integral matchings. Thus, in this case, the vertices of the polytope are all integral. For a non-bipartite graph, the fractional matching polytope is a superset of the matching polytope.

References

1. Aharoni, Ron; Kessler, Ofra (1990-10-15). "On a possible extension of Hall's theorem to bipartite hypergraphs". Discrete Mathematics. 84 (3): 309–313. doi:10.1016/0012-365X(90)90136-6. ISSN 0012-365X.
2. Liu, Yan; Liu, Guizhen (2002). "The fractional matching numbers of graphs". Networks. 40 (4): 228–231. doi:10.1002/net.10047. ISSN 1097-0037. S2CID 43698695.
3. Beckenbach, Isabel; Borndörfer, Ralf (2018-10-01). "Hall's and Kőnig's theorem in graphs and hypergraphs". Discrete Mathematics. 341 (10): 2753–2761. doi:10.1016/j.disc.2018.06.013. ISSN 0012-365X. S2CID 52067804.
4. Füredi, Zoltán (1981-06-01). "Maximum degree and fractional matchings in uniform hypergraphs". Combinatorica. 1 (2): 155–162. doi:10.1007/BF02579271. ISSN 1439-6912. S2CID 10530732.
5. Aharoni, Ron (1985). "Matchings in n-partite n-graphs". Graphs and Combinatorics. 1 (4): 303–304. doi:10.1007/BF02582958. MR 0951021.
6. Gärtner, Bernd; Matoušek, Jiří (2006). Understanding and Using Linear Programming. Berlin: Springer. ISBN 3-540-30697-8.
7. Bourjolly, Jean-Marie; Pulleyblank, William R. (1989-01-01). "König-Egerváry graphs, 2-bicritical graphs and fractional matchings". Discrete Applied Mathematics. 24 (1): 63–82. doi:10.1016/0166-218X(92)90273-D. ISSN 0166-218X.
8. Vazirani, Umesh (2012). "Maximum Weighted Matchings" (PDF). U. C. Berkeley.

See also

• Fractional coloring