Maximum bipartite graph (1, n) "match"

Question

I have a bipartite graph. I am looking for the maximum (1, n) "match", which means that each vertex from partitation A has n connected vertices from section B.

The following figure shows the maximum (1.3) match on the graph. The edges selected for matching are red, and unselected edges are black.

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

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

If the matched cardinality (n) is not applied, but is the upper boundary (vertices from A can have 0 <x <= n connected vertices from B), then the maximum match can be easily found by transforming the graph to the flow network and detecting the maximum flow. However, this does not guarantee that the maximum number of vertices from A will have n associated pairs from B.

Answer 1

This is NP-hard, short for maximum independent typing task. For any graph G you can build (in polynomial time) an instance of your problem so that:

• Vertices in represent vertices from G
• Each vertex from A is associated with exactly n vertices from B
• Any two vertices from A have a common neighbor in B if and only if they are connected in G For this, one can always choose n = Δ (G).

Now the maximum match in the instance returns to the maximum independent set in G