Maximum bipartite graph (1,n) "matching"

4
votes

I have a bipartite graph. I am looking for a maximum (1,n) "matching", which means that each vertex from partitation A has n associated vertices from partition B.

The following figure shows a maximum (1,3) matching in a graph. Edges selected for the matching are red and unselected edges are black.

See figure http://www.freeimagehosting.net/uploads/9a8df2d97c.gif

This differs from the standard bipartite matching problem where each vertex is associate with only one other vertex, which could be called (1,1) matching with this notation.

If the matching cardinality (n) is not enforced but is an upper bound (vertices from A can have 0 < x <= n associated vertices from B), then the maximum matching can be found easily by transforming the graph to a flow network and finding the max flow. However, this does not guarantee that the maximum number of vertices from A will have n associated pairs from B.

1
algorithmgraphmatching
not really :) actually, I'm developing a P2P protocol based on BitTorrent and I need the matching algorithm to associate peers with pieces... – Imre Kelényi
So, you want to maximize the number of peers with EXACTLY n connections? – Olexiy
I guess there must be some other constraint to be maximized (coverage of pieces maybe?) or else the algorithm would be trivial. At least if the picture is correct and you can habe multiple edges to a vertice in B (which isn't the case normally when performing a maximum matching) – HerdplattenToni
HerdplattenToni: the previous picture was incorrect, thanks for pointing it out. You can have only one edge to vertices in B just as with standard (1,1) matchings. – Imre Kelényi

1 Answers

3
votes

This is NP-hard, reduction from maximum independent set problem. For any graph G you can construct (in polynomial time) an instance of your problem such that:

  • Vertices in A represent vertices of G
  • Each vertex of A is connected to exactly n vertices from B
  • Any two vertices of A have a common neighbour in B if and only if they are connected in G. For this to be always possible, pick n=Δ(G).

Now the maximum 'matching' in the instance maps back to maximum independent set in G.