Maximum bipartite graph (1,n) "matching"

views:

509

answers:

+3 Q:

Maximum bipartite graph (1,n) "matching"

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

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.

+3 A:

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.

Rafał Dowgird 2009-10-06 19:40:43

Your last bullet cannot always be satisfied. For example G has a vertex v with N+1 neighbors. None of those N+1 neighbors are connected to each other. By pigeon hole principle for v to have a common neighbor with N+1 items, using only N outgoing edges. Two common neighbors must share one of the outgoing edges, which would have connected them in G, which isn't true.If you add the restriction that G has maximum degree N then your proof works. I think maximal independent set is not NP-hard if max degree is 1 or 2, so your proof only works for N>=3.

theycallhimtom 2009-10-07 16:39:54

But you are free to choose N when constructing the problem instance. Just choose N=|V(G)|.

Rafał Dowgird 2009-10-07 16:41:52

My first thought was similar to theycallhimtom's, but given the additional constraint on N, the proof seems solid. You need to choose N so that N >= D(G) where D(G) is the maximum degree of G.One little typo/mistake is that the reduction is from the "maximum independent set problem" not the "maximal" since the latter is a different problem and is much easier. Thank you so much for the answer, it helped a lot. (I'll rate it up as soon as I have enough reputation to do so.)

Imre Kelényi 2009-10-08 09:58:09

Thanks for the correction. Edited/fixed.

Rafał Dowgird 2009-10-08 16:27:36

ansaurus

tags:

views:

answers:

Maximum bipartite graph (1,n) "matching"

related questions