It does make sense when we talk about perfect matching in bipartite graphs because there are two sets of points, for example, one set may be jobs and other set may contain different machines. But when we talk about minimum cost perfect matching in general graphs, it is not making any sense for me, what are the nodes and edge cost representing, If you can give some real-life example depicting minimum cost perfect matching in general graphs. It will be very helpful to me.

Also, I need a precise definition of the minimum cost perfect matching problem. Thank You.


1 Answer 1


The minimum cost perfect matching problem is formally defined as an optimization problem where:

  • The set of instances is the set of all edge-weighted undirected graphs $G=(V, E, w)$, where $w : E \to \mathbb{R}$.
  • Given an instance $G=(V, E, w)$, the set of feasible solutions are the perfect matchings $M$ of $G$, i.e., all the sets $M \subseteq E$ such that, $\forall u \in V \; |M \cap \{ (u, v) \in E : v \in V \}| = 1$.
  • Given an instance $G=(V, E, w)$ and a feasible solution $M$ for $G$, the is a function called measure defined as $m(G, M) = \sum_{e \in M} w(e)$.
  • The measure is to be minimized.

As for the problem making sense... the problem is abstract in nature and it can be perfectly well-defined without any need for vertices, edges, weights or the matching itself to represent anything.

Of course it is fairly easy to come up with (mock) scenarios in which you might want to compute a minimum cost perfect matching of a suitable graph that is modelling some real-world entities, e.g., the one that follows.

You are organizing a trip for a (large) group of $n=4k$, $k \in \mathbb{N}^+$, participants that will travel together on a bus with $n$ seats. Bus seats are arranged in rows of $4$, with $2$ adjacent seats on each side and a corridor in the middle. Not all of the participants enjoy their company equally (indeed, some of them categorically refuse to be close by) and you know, for each pair of people that can sit together, how much they'd happy (or unhappy) to be sat next to each other (say, in a scale from $-1$ to $1$). Being a thoughtful organizer, you want to arrange seats in order to maximize the social welfare of the participants, i.e., the sum of the happiness of all pairs of neighbors in the arrangement you choose.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.