Fractional matching

Last updated September 07, 2022

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 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]

\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 0 or 1: f(e) = 1 if e is in the matching, and f(e) = 0 if it is not. For this reason, in the context of fractional matchings, usual matchings are sometimes called integral matchings.

The size of an integral matching is the number of edges in the matching, and the matching number $\nu (G)$ 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 $\nu ^{*}(G)$ .^[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:

\nu (G)\leq \nu ^{*}(G).

A graph in which $\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 a general graph, $\nu (G)>{\frac {2}{3}}\nu ^{*}(G).$ The fractional matching number is either an integer or a half-integer.^[4]

Matrix presentation

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

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

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 n²-2n+2 permutation matrices. This corresponds to decomposing M into a convex sum of at most n²-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 $O(|V||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 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 f₁ by transferring a small fraction ε from even edges to odd edges, and a new fractional matching f₂ by transferring ε from odd edges to even edges. Since f is the average of f₁ and f₂, the weight of f is the average between the weight of f₁ and of f₂. Since f has maximum weight, all three matchings must have the same weight. There exists a choice of ε for which at least one of f₁ or f₂ 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 f₁ and f₂ by transferring ε from odd edges to even edges or vice versa. Again f₁ and f₂ must have maximum weight, and at least one of them has less non-integral fractions.

Fractional matching polytope

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 (x₁,...,x_|E|) in the polytope represents a matching in which the fraction of each edge e is x_e. The polytope is defined by |E| non-negativity constraints (x_e ≥ 0 for all e in E) and |V| vertex constraints (the sum of x_e, 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.

Related Research Articles

In graph theory, a perfect matching in a graph is a matching that covers every vertex of the graph. More formally, given a graph $G =$ , a perfect matching in $G$ is a subset $M$ of edge set $E$ , such that every vertex in the vertex set $V$ is adjacent to exactly one edge in $M$ .

The assignment problem is a fundamental combinatorial optimization problem. In its most general form, the problem is as follows:

In mathematics, Hall's marriage theorem, proved by Philip Hall (1935), is a theorem with two equivalent formulations:

In the mathematical field of graph theory, a bipartite graph is a graph whose vertices can be divided into two disjoint and independent sets $and, that is every edge connects a vertex in to one in . Vertex sets and are usually called the parts of the graph. Equivalently, a bipartite graph is a graph that does not contain any odd-length cycles.$

This is a glossary of graph theory. Graph theory is the study of graphs, systems of nodes or vertices connected in pairs by lines or edges.

In optimization theory, maximum flow problems involve finding a feasible flow through a flow network that obtains the maximum possible flow rate.

In the mathematical discipline of graph theory, a matching or independent edge set in an undirected graph is a set of edges without common vertices. Finding a matching in a bipartite graph can be treated as a network flow problem.

Fractional coloring is a topic in a young branch of graph theory known as fractional graph theory. It is a generalization of ordinary graph coloring. In a traditional graph coloring, each vertex in a graph is assigned some color, and adjacent vertices — those connected by edges — must be assigned different colors. In a fractional coloring however, a set of colors is assigned to each vertex of a graph. The requirement about adjacent vertices still holds, so if two vertices are joined by an edge, they must have no colors in common.

In combinatorics, a Sperner family, or clutter, is a family F of subsets of a finite set E in which none of the sets contains another. Equivalently, a Sperner family is an antichain in the inclusion lattice over the power set of E. A Sperner family is also sometimes called an independent system or irredundant set.

Kőnigs theorem (graph theory) Theorem showing that maximum matching and minimum vertex cover are equivalent for bipartite graphs

In the mathematical area of graph theory, Kőnig's theorem, proved by Dénes Kőnig (1931), describes an equivalence between the maximum matching problem and the minimum vertex cover problem in bipartite graphs. It was discovered independently, also in 1931, by Jenő Egerváry in the more general case of weighted graphs.

Maximum cardinality matching is a fundamental problem in graph theory. We are given a graph $G$ , and the goal is to find a matching containing as many edges as possible; that is, a maximum cardinality subset of the edges such that each vertex is adjacent to at most one edge of the subset. As each edge will cover exactly two vertices, this problem is equivalent to the task of finding a matching that covers as many vertices as possible.

In graph theory, the blossom algorithm is an algorithm for constructing maximum matchings on graphs. The algorithm was developed by Jack Edmonds in 1961, and published in 1965. Given a general graph $G =$ , the algorithm finds a matching $M$ such that each vertex in $V$ is incident with at most one edge in $M$ and $| M |$ is maximized. The matching is constructed by iteratively improving an initial empty matching along augmenting paths in the graph. Unlike bipartite matching, the key new idea is that an odd-length cycle in the graph (blossom) is contracted to a single vertex, with the search continuing iteratively in the contracted graph.

In the mathematical discipline of graph theory, a rainbow matching in an edge-colored graph is a matching in which all the edges have distinct colors.

In graph theory, a matching in a hypergraph is a set of hyperedges, in which every two hyperedges are disjoint. It is an extension of the notion of matching in a graph.

In graph theory, a vertex cover in a hypergraph is a set of vertices, such that every hyperedge of the hypergraph contains at least one vertex of that set. It is an extension of the notion of vertex cover in a graph.

In the mathematical field of graph theory, Hall-type theorems for hypergraphs are several generalizations of Hall's marriage theorem from graphs to hypergraphs. Such theorems were proved by Ofra Kessler, Ron Aharoni, Penny Haxell, Roy Meshulam, and others.

Deficiency is a concept in graph theory that is used to refine various theorems related to perfect matching in graphs, such as Hall's marriage theorem. This was first studied by Øystein Ore. A related property is surplus.

In graph theory, Ryser's conjecture is a conjecture relating the maximum matching size and the minimum transversal size in hypergraphs.

In geometry, a truncated projective plane (TPP), also known as a dual affine plane, is a special kind of a hypergraph or geometric configuration that is constructed in the following way.

In graph theory, the matching polytope of a given graph is a geometric object representing the possible matchings in the graph. It is a convex polytope each of whose corners corresponds to a matching. It has great theoretical importance in the theory of matching.

References

↑ 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.
↑ 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.
↑ 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.{{cite web}}: CS1 maint: url-status (link)