Matching

Matching is a concept in mathematics and computer science defined as a set of pairings between elements subject to a non-overlap constraint. In graph theory, a matching is a collection of edges with no shared endpoints. If every vertex in the graph is incident to exactly one edge of the collection, the matching is called perfect; if no larger matching exists, it is called a maximum matching.

In a bipartite graph, the problem of finding the largest possible matching is known as maximum bipartite matching. Efficient algorithms exist, including the Hopcroft–Karp algorithm, which runs in O(E sqrt(V)). For general graphs, Edmonds' blossom algorithm finds a maximum matching; there are also algorithms for minimum-weight or minimum-cost matchings, where edges carry costs and the goal is to minimize total cost.

Applications of graph matching span assignment, scheduling, and network design. In practice, matching models help pair resources to tasks, connect agents to opportunities, and identify correspondences between datasets in pattern recognition and computer vision.

Statistical matching refers to methods for creating comparable groups in observational studies by pairing treated and control units with similar covariates to reduce confounding. Techniques include exact matching, caliper or near-exact matching, propensity score matching, Mahalanobis distance matching, and kernel matching. Diagnostics such as standardized mean differences assess balance after matching.

In economics and social science, matching markets describe systems where participants are paired based on preferences, such as job markets or dating markets. The stable matching problem, solved by the Gale–Shapley algorithm, guarantees stable pairings under certain assumptions but is conceptually distinct from graph-theoretic matching.