3
$\begingroup$

It is known, that maximal matchings (i.e. matchings with the maximal number of edges) and optimal matchings (i.e. matchings for which the sum of edge weights is optimal) can be calculated in polynomial time.

I would like to know whether the same is true for optimal matchings with a given fixed number of edges.

The problem can be illustrated as follows: a tennis club has the task to find e.g. the 10 best pairs of players that will take part in a tournament of doubles (i.e. two players on each side). The situation can be modeled as a graph where the vertices correspond to players and the edge weights correspond to the playing strength of the pair of players. The task is then to find 10 non-adjacent edges with maximal weight sum.

Improve this question
$\endgroup$

2 Answers 2

Reset to default
3
$\begingroup$

With a little trick you can use the algorithm for finding an optimal matching to solve this.

Let the graph $G$ have $n$ vertices and you want to find the optimal matching with size $k$. Lets suppose that there is a matching of size $k$.

The first remark is that if you add the same constant to all edge weights then the set of optimal matchings of size $k$ will not change. So lets add a constant $C$ big enough to the weights so that every matching of $k$ size will have a bigger weight than any matching of lesser size.

Now you add $n-2k$ new vertices to the graph and connect each of these new vertices with all the old ones. The weight of these new edges should be big enough so that every optimal matching in this new graph $G'$ must use exactly $n-2k$ of these new edges (the maximum possible).

You search for an optimal matching in $G'$. It will have $n-2k$ of the new edges and so at most $k$ from the original edges of $G$. So it will find us an optimal matching in $G$ of size at most $k$. But because of our first step and because there is a matching of size $k$ in $G$ thus it will contain exactly $k$ original edges.

Improve this answer
$\endgroup$
1
  • $\begingroup$ @David: your answer really solves the problem in an elegant way; I had checked some literature, but couldn't anything like that. A minor remark: the weights of the newly added edges should all be the same so that the original matching isn't altered, but that's fairly obvious. $\endgroup$
    – Manfred Weis
    Commented Feb 23, 2013 at 10:03
3
$\begingroup$

Yes, at least for bipartite graphs. Namely, the Hungarian algorithm builds a maximum weight matching incrementally, and at stage $j$ it has a maximum weight matching with $j$ edges. Cf. e.g. my old notes, or Sect. 3.5 of A.Schrijver's lecture notes.

IIRC, it is the case for the general graphs too, but you should check this in a monograph on the topic, e.g. Sect. 26 of A.Schrijver's 3-volume work.

Improve this answer
$\endgroup$
1
  • $\begingroup$ The more general question would be under which conditions integrality is preserved when adding a size restriction to an LP, but the answer is of good help for me; thank you Dima. $\endgroup$
    – Manfred Weis
    Commented Feb 11, 2013 at 4:56

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .