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[edit]
Given a graph G = (V, E), a fractional matching in G is a function that assigns, to each edge e in E, a fraction f(e) in [0, 1], such that for every vertex v in V, the sum of fractions of edges adjacent to v is at most 1:[1]
The size of an integral matching is the number of edges in the matching, and the matching number of a graph G is the largest size of a matching in G. Analogously, the size of a fractional matching is the sum of fractions of all edges. The fractional matching number of a graph G is the largest size of a fractional matching in G. It is often denoted by .[2] Since a matching is a special case of a fractional matching, for every graph G one has that the integral matching number of G is less than or equal to the fractional matching number of G; in symbols:
In a general graph, The fractional matching number is either an integer or a half-integer.[4]
Matrix presentation[edit]
For a bipartite graph G = (X+Y, E), a fractional matching can be presented as a matrix with |X| rows and |Y| columns. The value of the entry in row x and column y is the fraction of the edge (x,y).
Perfect fractional matching[edit]
A fractional matching is called perfect if the sum of weights adjacent to each vertex is exactly 1. The size of a perfect matching is exactly |V|/2.
In a bipartite graph G = (X+Y, E), a fractional matching is called X-perfect if the sum of weights adjacent to each vertex of X is exactly 1. The size of an X-perfect fractional matching is exactly |X|.
For a bipartite graph G = (X+Y, E), the following are equivalent:
- G admits an X-perfect integral matching,
- G admits an X-perfect fractional matching, and
- 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 W of X, the sum of weights near vertices of W is |W|, so the edges adjacent to them are necessarily adjacent to at least |W| vertices of Y. By Hall's marriage theorem, the last condition implies the first one.[5][better source needed]
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 3/2 (the fraction of every edge is 1/2), but does not admit perfect integral matching - the largest integral matching is of size 1.
Algorithmic aspects[edit]
A largest fractional matching in a graph can be easily 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 simple polynomial-time algorithm for finding a maximum matching in a bipartite graph.[6]
If G is a bipartite graph with |X| = |Y| = n, and M is a perfect fractional matching, then the matrix representation of M is a doubly stochastic matrix - the sum of elements in each row and each column is 1. Birkhoff's algorithm can be used to decompose the matrix into a convex sum of at most n2-2n+2 permutation matrices. This corresponds to decomposing M into a convex sum of at most n2-2n+2 perfect matchings.
Maximum-cardinality fractional matching[edit]
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 .
Maximum-weight fractional matching[edit]
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 f be the fractional matching.
- Let H be a subgraph of G containing only the edges e with non-integral fraction, 0<f(e)<1.
- If H is empty, then we are done.
- if H has a cycle, then it must be even-length (since the graph is bipartite), so we can construct a new fractional matching f1 by transferring a small fraction ε from even edges to odd edges, and a new fractional matching f2 by transferring ε from odd edges to even edges. Since f is the average of f1 and f2, the weight of f is the average between the weight of f1 and of f2. Since f has maximum weight, all three matchings must have the same weight. There exists a choice of ε for which at least one of f1 or f2 has less non-integral fractions. Continuing in the same way leads to an integral matching of the same weight.
- Suppose H has no cycle, and let P be a longest path in H. The fraction of every edge adjacent to the first or last vertex in P must be 0 (if it is 1 - the first / last edge in P violates the fractional matching condition; if it is in (0,1) - then P is not the longest). Therefore, we can construct new fractional matchings f1 and f2 by transferring ε from odd edges to even edges or vice versa. Again f1 and f2 must have maximum weight, and at least one of them has less non-integral fractions.
Fractional matching polytope[edit]
Given a graph G = (V,E), the fractional matching polytope of G is a convex polytope that represents all possible fractional matchings of G. It is a polytope in R|E| - the |E|-dimensional Euclidean space. Each point (x1,...,x|E|) in the polytope represents a matching in which the fraction of each edge e is xe. The polytope is defined by |E| non-negativity constraints (xe ≥ 0 for all e in E) and |V| vertex constraints (the sum of xe, for all edges e that are adjacent to a vertex v, is at most 1). In a bipartite graph, the vertices of the fractional matching polytope are all integral.
References[edit]
- ^ 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.
- ^ 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.
- ^ 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.
- ^ 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.
- ^ "co.combinatorics - Fractional Matching version of Hall's Marriage theorem". MathOverflow. Retrieved 2020-06-29.
- ^ Gärtner, Bernd; Matoušek, Jiří (2006). Understanding and Using Linear Programming. Berlin: Springer. ISBN 3-540-30697-8.
- ^ 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.
- ^ Vazirani, Umesh (2012). "Maximum Weighted Matchings" (PDF). U. C. Berkeley.