Editing Matching (graph theory)

{{Short description|Set of edges without common vertices}}
{{for|comparisons of two graphs|Graph matching}}

In the mathematical discipline of [[graph theory]], a '''matching''' or '''independent edge set''' in an undirected [[Graph (discrete mathematics)|graph]] is a set of [[Edge (graph theory)|edges]] without common [[vertex (graph theory)|vertices]].<ref name="NetworkX 2.8.2 documentation">{{cite web | title=is_matching | website=NetworkX 2.8.2 documentation | url=https://networkx.org/documentation/stable/reference/algorithms/generated/networkx.algorithms.matching.is_matching.html#networkx.algorithms.matching.is_matching | access-date=2022-05-31 | quote=Each node is incident to at most one edge in the matching. The edges are said to be independent.}}</ref> In other words, a subset of the edges is a matching if each vertex appears in at most one edge of that matching. Finding a matching in a [[bipartite graph]] can be treated as a [[Flow network|network flow]] problem.

{{Covering-Packing_Problem_Pairs}}

== Definitions ==

Given a [[Graph (discrete mathematics)|graph]] {{math|1=''G'' = (''V'',&thinsp;''E''),}} a '''matching''' ''M'' in ''G'' is a set of pairwise [[non-adjacent]] edges, none of which are [[loop (graph theory)|loop]]s; that is, no two edges share common vertices.

A vertex is '''matched''' (or '''saturated''') if it is an endpoint of one of the edges in the matching.  Otherwise the vertex is '''unmatched''' (or '''unsaturated''').

A '''maximal matching''' is a matching ''M'' of a graph ''G'' that is not a subset of any other matching. A matching ''M'' of a graph ''G'' is maximal if every edge in ''G'' has a non-empty intersection with at least one edge in ''M''. The following figure shows examples of maximal matchings (red) in three graphs.

:[[File:Maximal-matching.svg]]

A '''maximum matching''' (also known as maximum-cardinality matching<ref>Alan Gibbons, Algorithmic Graph Theory, Cambridge University Press, 1985, Chapter 5.</ref>) is a matching that contains the largest possible number of edges.  There may be many maximum matchings.  The '''matching number''' <math>\nu(G)</math> of a graph {{mvar|G}} is the size of a maximum matching. Every maximum matching is maximal, but not every maximal matching is a maximum matching. The following figure shows examples of maximum matchings in the same three graphs.

:[[File:Maximum-matching-labels.svg]]

A '''[[perfect matching]]''' is a matching that matches all vertices of the graph. That is, a matching is perfect if every vertex of the graph is [[incidence (geometry)|incident]] to an edge of the matching. A matching is perfect if <math>|M|=|V|/2</math>. Every perfect matching is maximum and hence maximal. In some literature, the term '''complete matching''' is used. In the above figure, only part (b) shows a perfect matching. A perfect matching is also a minimum-size [[edge cover]]. Thus, the size of a maximum matching is no larger than the size of a minimum edge cover: {{tmath|\nu(G) \le \rho(G)}}. A graph can only contain a perfect matching when the graph has an even number of vertices.

A '''near-perfect matching''' is one in which exactly one vertex is unmatched.  Clearly, a graph can only contain a near-perfect matching when the graph has an [[odd number]] of vertices, and near-perfect matchings are maximum matchings. In the above figure, part (c) shows a near-perfect matching. If every vertex is unmatched by some near-perfect matching, then the graph is called [[factor-critical graph|factor-critical]].

Given a matching ''M'', an '''alternating path''' is a path that begins with an unmatched vertex<ref>{{Cite web|url=http://diestel-graph-theory.com/basic.html|title=Preview}}</ref> and whose edges belong alternately to the matching and not to the matching. An '''augmenting path''' is an alternating path that starts from and ends on free (unmatched) vertices. [[Berge's lemma]] states that a matching ''M'' is maximum if and only if there is no augmenting path with respect to ''M''.

An '''[[induced matching]]''' is a matching that is the edge set of an [[induced subgraph]].<ref>{{citation
 | last = Cameron | first = Kathie
 | department = Special issue for First Montreal Conference on Combinatorics and Computer Science, 1987
 | doi = 10.1016/0166-218X(92)90275-F
 | issue = 1–3
 | journal = [[Discrete Applied Mathematics]]
 | mr = 1011265
 | pages = 97–102
 | title = Induced matchings
 | volume = 24
 | year = 1989| doi-access = free
 }}</ref>

== Properties ==

In any graph without isolated vertices, the sum of the matching number and the [[edge covering number]] equals the number of vertices.<ref>{{citation|last=Gallai|first=Tibor|title=Über extreme Punkt- und Kantenmengen|journal=Ann. Univ. Sci. Budapest. Eötvös Sect. Math. |volume=2|pages=133–138|year=1959}}.</ref> If there is a perfect matching, then both the matching number and the edge cover number are {{math|{{!}}''V'' {{!}} / 2}}.

If {{math|''A''}} and {{math|''B''}} are two maximal matchings, then {{math|{{!}}''A''{{!}}&nbsp;≤&nbsp;2{{!}}''B''{{!}}}} and {{math|{{!}}''B''{{!}}&nbsp;≤&nbsp;2{{!}}''A''{{!}}}}. To see this, observe that each edge in {{math|''B''&nbsp;\&nbsp;''A''}} can be adjacent to at most two edges in {{math|''A''&nbsp;\&nbsp;''B''}} because {{math|''A''}} is a matching; moreover each edge in {{math|''A''&nbsp;\&nbsp;''B''}} is adjacent to an edge in {{math|''B''&nbsp;\&nbsp;''A''}} by maximality of {{math|''B''}}, hence

:<math>|A \setminus B| \le 2|B \setminus A |.</math>

Further we deduce that

:<math>|A| = |A \cap B| + |A \setminus B| \le 2|B \cap A| + 2|B \setminus A| = 2|B|.</math>

In particular, this shows that any maximal matching is a 2-approximation of a maximum matching and also a 2-approximation of a minimum maximal matching. This inequality is tight: for example, if {{math|''G''}} is a path with 3 edges and 4 vertices, the size of a minimum maximal matching is 1 and the size of a maximum matching is 2.

A spectral characterization of the matching number of a graph is given by Hassani Monfared and Mallik as follows:  Let <math>G</math> be a [[Graph_(discrete_mathematics)|graph]] on <math>n</math> vertices, and <math>\lambda_1 > \lambda_2 > \ldots > \lambda_k>0</math> be <math>k</math> distinct nonzero [[imaginary number|purely imaginary numbers]] where <math>2k \leq n</math>. Then the [[matching number]] of <math>G</math> is <math>k</math> if and only if (a) there is a real [[skew-symmetric matrix]] <math>A</math> with graph <math>G</math> and  [[eigenvalues]] <math>\pm \lambda_1, \pm\lambda_2,\ldots,\pm\lambda_k</math> and <math>n-2k</math> zeros, and (b) all real skew-symmetric matrices with graph <math>G</math> have at most <math>2k</math> nonzero [[eigenvalues]].<ref>Keivan Hassani Monfared and Sudipta Mallik, Theorem 3.6, Spectral characterization of matchings in graphs, Linear Algebra and its Applications 496 (2016) 407–419, https://doi.org/10.1016/j.laa.2016.02.004, https://arxiv.org/abs/1602.03590 </ref> Note that the (simple) graph of a real symmetric or skew-symmetric matrix <math>A</math> of order <math>n</math> has <math>n</math> vertices and edges given by the nonozero off-diagonal entries of <math>A</math>.

== Matching polynomials ==
{{main|Matching polynomial}}
A [[generating function]] of the number of ''k''-edge matchings in a graph is called a matching polynomial.  Let ''G'' be a graph and ''m<sub>k</sub>'' be the number of ''k''-edge matchings.  One matching polynomial of ''G'' is
:<math>\sum_{k\geq0} m_k x^k.</math>
Another definition gives the matching polynomial as
:<math>\sum_{k\geq0} (-1)^k m_k x^{n-2k},</math>
where ''n'' is the number of vertices in the graph.  Each type has its uses; for more information see the article on matching polynomials.

== Algorithms and computational complexity ==
{{anchor|Bipartite matching}}
=== Maximum-cardinality matching ===
{{Main|Maximum cardinality matching}}
A fundamental problem in [[combinatorial optimization]] is finding a ''maximum matching''. This problem has various algorithms for different classes of graphs.

In an ''unweighted bipartite graph'', the optimization problem is to find a [[maximum cardinality matching]].  The problem is solved by the [[Hopcroft-Karp algorithm]] in time {{math|<var>O</var>({{radical|<var>V</var>}}<var>E</var>)}} time, and there are more efficient [[randomized algorithm]]s, [[approximation algorithm]]s, and algorithms for special classes of graphs such as bipartite [[planar graph]]s, as described in the main article.

=== Maximum-weight matching ===
{{Main|Maximum weight matching}}
In a [[weighted graph|''weighted'']] ''bipartite graph,'' the optimization problem is to find a maximum-weight matching; a dual problem is to find a minimum-weight matching. This problem is often called '''maximum weighted bipartite matching''', or the '''[[assignment problem]]'''. The [[Hungarian algorithm]] solves the assignment problem and it was one of the beginnings of combinatorial optimization algorithms. It uses a modified [[shortest path]] search in the augmenting path algorithm. If the [[Bellman–Ford algorithm]] is used for this step, the running time of the Hungarian algorithm becomes <math>O(V^2 E)</math>, or the edge cost can be shifted with a potential to achieve <math>O(V^2 \log{V} + V E)</math> running time with the [[Dijkstra algorithm]] and [[Fibonacci heap]].<ref name="Fredman87">{{citation|last1=Fredman|first1=Michael L.|title=Fibonacci heaps and their uses in improved network optimization algorithms|journal=[[Journal of the ACM]]|volume=34|issue=3|pages=596–615|year=1987|doi=10.1145/28869.28874|last2=Tarjan|first2=Robert Endre|s2cid=7904683|doi-access=free}}</ref>

In a ''non-bipartite weighted graph'', the problem of '''[[maximum weight matching]]''' can be solved in time  <math>O(V^{2}E)</math> using [[Edmonds's matching algorithm|Edmonds' blossom algorithm]].

=== Maximal matchings ===

A maximal matching can be found with a simple [[greedy algorithm]]. A maximum matching is also a maximal matching, and hence it is possible to find a ''largest'' maximal matching in polynomial time. However, no polynomial-time algorithm is known for finding a '''minimum maximal matching''', that is, a maximal matching that contains the ''smallest'' possible number of edges.

A maximal matching with ''k'' edges is an [[edge dominating set]] with ''k'' edges. Conversely, if we are given a minimum edge dominating set with ''k'' edges, we can construct a maximal matching with ''k'' edges in polynomial time. Therefore, the problem of finding a minimum maximal matching is essentially equal to the problem of finding a minimum edge dominating set.<ref>{{citation
 | first1=Mihalis | last1=Yannakakis
 | first2=Fanica | last2=Gavril
 | title=Edge dominating sets in graphs
 | journal=SIAM Journal on Applied Mathematics
 | year=1980
 | volume=38
 | pages=364–372
 | doi=10.1137/0138030
 | issue=3
| url=http://cgi.di.uoa.gr/~vassilis/co/dominating-sets.pdf
 }}.</ref> Both of these two optimization problems are known to be [[NP-hard]]; the decision versions of these problems are classical examples of [[NP-complete]] problems.<ref>{{citation
 | last1=Garey | first1=Michael R. | author-link1=Michael R. Garey
 | last2=Johnson | first2=David S. | author-link2=David S. Johnson
 | year = 1979
 | title = Computers and Intractability: A Guide to the Theory of NP-Completeness
 | publisher = W.H. Freeman
 | isbn=0-7167-1045-5
| title-link=Computers and Intractability: A Guide to the Theory of NP-Completeness }}. Edge dominating set (decision version) is discussed under the dominating set problem, which is the problem GT2 in Appendix&nbsp;A1.1. Minimum maximal matching (decision version) is the problem GT10 in Appendix&nbsp;A1.1.</ref> Both problems can be [[approximation algorithm|approximated]] within factor 2 in polynomial time: simply find an arbitrary maximal matching ''M''.<ref>{{citation
 | last1=Ausiello | first1=Giorgio
 | last2=Crescenzi | first2=Pierluigi
 | last3=Gambosi | first3=Giorgio
 | last4=Kann | first4=Viggo
 | last5=Marchetti-Spaccamela | first5=Alberto
 | last6=Protasi | first6=Marco
 | title=Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties
 | publisher=Springer
 | year=2003
}}. Minimum edge dominating set (optimisation version) is the problem GT3 in Appendix B (page 370). Minimum maximal matching (optimisation version) is the problem GT10 in Appendix B (page 374). See also [https://www.csc.kth.se/~viggo/wwwcompendium/node13.html Minimum Edge Dominating Set] and [https://www.csc.kth.se/~viggo/wwwcompendium/node21.html Minimum Maximal Matching] in the [https://www.csc.kth.se/~viggo/wwwcompendium/ web compendium].</ref>

=== Counting problems ===
{{main|Hosoya index}}
The number of matchings in a graph is known as the [[Hosoya index]] of the graph. It is [[Sharp-P-complete|#P-complete]] to compute this quantity, even for bipartite graphs.<ref>[[Leslie Valiant]], ''The Complexity of Enumeration and Reliability Problems'',  SIAM J. Comput., 8(3), 410–421</ref> It is also #P-complete to count [[Perfect matching|perfect matchings]], even in [[bipartite graph]]s, because computing the [[Permanent (mathematics)|permanent]] of an arbitrary 0–1 matrix (another #P-complete problem) is the same as computing the number of perfect matchings in the bipartite graph having the given matrix as its [[biadjacency matrix]]. However, there exists a fully polynomial time randomized approximation scheme for counting the number of bipartite matchings.<ref>{{cite journal
| last1        = Bezáková
| first1       = Ivona
| last2        = Štefankovič
| first2       = Daniel
| last3        = Vazirani
| first3       = Vijay V.
| author-link3  = Vijay Vazirani
| last4        = Vigoda
| first4       = Eric
| year         = 2008
| title        = Accelerating Simulated Annealing for the Permanent and Combinatorial Counting Problems
| journal      = [[SIAM Journal on Computing]]
| volume       = 37
| issue        = 5
| pages        = 1429–1454
| doi          = 10.1137/050644033
| citeseerx= 10.1.1.80.687
| s2cid = 755231
}}</ref> A remarkable theorem of [[Pieter Kasteleyn|Kasteleyn]] states that the number of perfect matchings in a [[planar graph]] can be computed exactly in polynomial time via the [[FKT algorithm]].

The number of perfect matchings in a [[complete graph]] ''K''<sub>''n''</sub> (with ''n'' even) is given by the [[double factorial]] (''n''&nbsp;&minus;&nbsp;1)!!.<ref>{{citation|title=A combinatorial survey of identities for the double factorial|first=David|last=Callan|arxiv=0906.1317|year=2009|bibcode=2009arXiv0906.1317C}}.</ref> The numbers of matchings in complete graphs, without constraining the matchings to be perfect, are given by the [[Telephone number (mathematics)|telephone number]]s.<ref>{{citation
 | last1 = Tichy | first1 = Robert F.
 | last2 = Wagner | first2 = Stephan
 | doi = 10.1089/cmb.2005.12.1004
 | pmid = 16201918
 | issue = 7
 | journal = [[Journal of Computational Biology]]
 | pages = 1004–1013
 | title = Extremal problems for topological indices in combinatorial chemistry
 | url = http://www.math.tugraz.at/fosp/pdfs/tugraz_main_0052.pdf
 | volume = 12
 | year = 2005}}.</ref>

The number of perfect matchings in a graph is also known as the [[hafnian]] of its [[adjacency matrix]].

=== Finding all maximally matchable edges ===
{{Main|Maximally matchable edge}}
One of the basic problems in matching theory is to find in a given graph all edges that may be extended to a maximum matching in the graph (such edges are called [[maximally matchable edge]]s, or '''allowed''' edges). Algorithms for this problem include:

* For general graphs, a deterministic algorithm in time <math>O(VE)</math> and a randomized algorithm in time <math>\tilde{O}(V^{2.376}) </math>.<ref>{{citation
| last1 = Rabin | first1 = Michael O.
| last2 = Vazirani | first2 = Vijay V.
| title = Maximum matchings in general graphs through randomization
| journal = [[Journal of Algorithms]]
| volume = 10
| year = 1989
| issue = 4
| pages = 557–567
|  doi = 10.1016/0196-6774(89)90005-9| citeseerx = 10.1.1.228.1996
}}</ref><ref>
{{citation
| last1 = Cheriyan | first1 = Joseph
| title = Randomized <math>\widetilde O(M(|V|))</math> algorithms for problems in matching theory
| journal = [[SIAM Journal on Computing]]
| volume = 26
| year = 1997
| number = 6
| pages = 1635–1655
| doi = 10.1137/S0097539793256223
}}</ref>
* For bipartite graphs, if a single maximum matching is found, a deterministic algorithm runs in time <math>O(V+E)</math>.<ref>{{citation
| last1 = Tassa | first1= Tamir
| title = Finding all maximally-matchable edges in a bipartite graph
| journal = [[Theoretical Computer Science]]
| volume = 423
| year = 2012
| pages = 50–58
| doi = 10.1016/j.tcs.2011.12.071
| doi-access = free
}}</ref>

=== Online bipartite matching ===
The problem of developing an [[online algorithm]] for matching was first considered by [[Richard M. Karp]], [[Umesh Vazirani]], and [[Vijay Vazirani]] in 1990.<ref>{{cite conference|last1=Karp|first1=Richard M.|author1-link=Richard M. Karp|last2=Vazirani|first2=Umesh V.|author2-link=Umesh Vazirani|last3=Vazirani|first3=Vijay V.|author3-link=Vijay Vazirani|contribution=An optimal algorithm for on-line bipartite matching|contribution-url=https://people.eecs.berkeley.edu/~vazirani/pubs/online.pdf|doi=10.1145/100216.100262|pages=352–358|title=Proceedings of the 22nd Annual ACM Symposium on Theory of Computing (STOC 1990)|year=1990|isbn=0-89791-361-2 }}</ref> 

In the online setting, nodes on one side of the bipartite graph arrive one at a time and must either be immediately matched to the other side of the graph or discarded. This is a natural generalization of the [[secretary problem]] and has applications to online ad auctions. The best online algorithm, for the unweighted maximization case with a random arrival model, attains a [[Competitive analysis (online algorithm)|competitive ratio]] of {{math|0.696}}.<ref>{{cite conference|last1=Mahdian|first1=Mohammad|last2=Yan|first2=Qiqi|doi=10.1145/1993636.1993716|title=Proceedings of the Forty-Third Annual ACM Symposium on Theory of Computing|pages=597–606|contribution=Online bipartite matching with random arrivals: an approach based on strongly factor-revealing LPs|year=2011|doi-access=free}}</ref>

== Characterizations ==

[[Kőnig's theorem (graph theory)|Kőnig's theorem]] states that, in bipartite graphs, the maximum matching is equal in size to the minimum [[vertex cover]]. Via this result, the minimum vertex cover, [[maximum independent set]], and [[maximum vertex biclique]] problems may be solved in [[polynomial time]] for bipartite graphs.

[[Hall's marriage theorem]] provides a characterization of bipartite graphs which have a perfect matching and the [[Tutte theorem]] provides a characterization for arbitrary graphs.

== Applications ==

=== Matching in general graphs ===
* A '''Kekulé structure''' of an [[Aromaticity|aromatic compound]] consists of a perfect matching of its [[skeletal formula|carbon skeleton]], showing the locations of [[double bond]]s in the [[chemical structure]]. These structures are named after [[Friedrich August Kekulé von Stradonitz]], who showed that [[benzene]] (in graph theoretical terms, a 6-vertex cycle) can be given such a structure.<ref>See, e.g., {{citation|title=On some solved and unsolved problems of chemical graph theory|last1=Trinajstić|first1=Nenad|author-link=Nenad Trinajstić|last2=Klein|first2=Douglas J.|last3=Randić|first3=Milan |author-link3=Milan Randić|journal=International Journal of Quantum Chemistry|year=1986|volume=30|issue=S20|pages=699–742|doi=10.1002/qua.560300762}}.</ref>
* The [[Hosoya index]] is the number of non-empty matchings plus one; it is used in [[computational chemistry]] and [[mathematical chemistry]] investigations for organic compounds.
* The [[Chinese postman problem]] involves finding a minimum-weight perfect matching as a subproblem.

=== Matching in bipartite graphs ===
* [http://community.topcoder.com/stat?c=problem_statement&pm=2852&rd=5075 Graduation problem] is about choosing minimum set of classes from given requirements for graduation.
* [[Transportation theory (mathematics)|Hitchcock transport problem]] involves bipartite matching as sub-problem.
* [[Subgraph isomorphism problem|Subtree isomorphism]] problem involves bipartite matching as sub-problem.

== See also ==
* [[Matching in hypergraphs]] - a generalization of matching in graphs.
* [[Fractional matching]].
* [[Dulmage–Mendelsohn decomposition]], a partition of the vertices of a bipartite graph into subsets such that each edge belongs to a perfect matching if and only if its endpoints belong to the same subset
* [[Edge coloring]], a partition of the edges of a graph into matchings
* [[Matching preclusion]], the minimum number of edges to delete to prevent a perfect matching from existing
* [[Rainbow matching]], a matching in an edge-colored bipartite graph with no repeated colors
* [[Skew-symmetric graph]], a type of graph that can be used to model alternating path searches for matchings
* [[Stable matching]], a matching in which no two elements prefer each other to their matched partners
* [[Independent vertex set]], a set of vertices (rather than edges) no two of which are adjacent to each other
* [[Stable marriage problem]] (also known as stable matching problem)

== References ==
{{Reflist}}

== Further reading ==
#{{Cite Lovasz Plummer|ref=none}}
#{{Citation|ref=none
 | author = [[Thomas H. Cormen]], [[Charles E. Leiserson]], [[Ronald L. Rivest]] and [[Clifford Stein]]
 | title = Introduction to Algorithms
 | publisher = MIT Press and McGraw–Hill
 | year = 2001
 | isbn = 0-262-53196-8
 | edition = second
 | at = Chapter 26, pp. 643&ndash;700
| title-link = Introduction to Algorithms
 }}
#{{cite tech report|ref=none
 | author = [[András Frank]]
 | url = http://www.cs.elte.hu/egres/tr/egres-04-14.pdf
 | title = On Kuhn's Hungarian Method – A tribute from Hungary
 | institution = Egerváry Research Group
 | year = 2004
}}
#{{Citation|ref=none
 | author = [[Michael L. Fredman]] and [[Robert E. Tarjan]]
 | title = Fibonacci heaps and their uses in improved network optimization algorithms
 | journal = [[Journal of the ACM]]
 | volume = 34
 | year = 1987
 | pages = 595&ndash;615
 | doi = 10.1145/28869.28874
 | issue = 3
 | s2cid = 7904683
 | postscript = .
| doi-access = free
 }}
#{{Citation|ref=none
 |author1=S. J. Cyvin   |author2=Ivan Gutman
  |name-list-style=amp | title = Kekule Structures in Benzenoid Hydrocarbons
 | publisher = Springer-Verlag
 | year = 1988
}}
#{{Citation|ref=none
 | author = [[Marek Karpinski]] and Wojciech Rytter
 | title = Fast Parallel Algorithms for Graph Matching Problems
 | publisher = Oxford University Press
 | year = 1998
 | isbn = 978-0-19-850162-6
 | url-access = registration
 | url = https://archive.org/details/fastparallelalgo0000karp
 }}

== External links ==
* [http://lemon.cs.elte.hu/ A graph library with Hopcroft–Karp and Push–Relabel-based maximum cardinality matching implementation ]

{{Authority control}}

[[Category:Matching (graph theory)| ]]
[[Category:Combinatorial optimization]]
[[Category:Polynomial-time problems]]
[[Category:Computational problems in graph theory]]