CODEWITHSUNDEEP
algorithmgraph-theorybipartite
GaoYu
GaoYu

Reputation: 31

An extension of bipartite graph maximum matching

Assume that there are two graphs like this:

enter image description here

We aim to find the matching correspondences between the two graph.And now we use a method to calculate the similarity of two nodes between the two graphs. w(A,1) means the similarity of the node A from the left graph between the node 1 from the right graph. Then we can have table like this:

enter image description here

Our target is to calculate the maximum weight matching of all this nodes. And we can use the algorithm Kuhn－Munkras to solve this problem.

But now the question is that is if we add the similarity between edges from the two graphs,how can we calulate the maximum weight matching. It means that the table become this:

enter image description here

AA means the node A, and AB means the edge from A to B. The constraints are that if the final result is that node A matches node 1,the edge AB must matches 12 or 13.So can we use a algorithm like Kuhn－Munkras to solve this problem? If not , how can we find the the maximum weight matching in polynomial time?

Upvotes: 3

Views: 319

Answers (1)

Peter de Rivaz
Peter de Rivaz

Reputation: 33509

Suppose we want to know if two graphs are isomorphic, e.g. the two in your example.

In the first graph we have edges AC and CB, while in the second graph we have edges 13 and 32.

We can set the weight matrix such that there is a high reward for mapping any edge in the first to an edge in the second.

i.e. AC->13 and AC->32 and CB->13 and CB->32 will all have weight 1, while all other matchings have weight zero.

There is an isomorphism between the graphs if and only if there is a maximum weight matching with weight equal to the number of edges.

Therefore your problem is at least as hard as graph isomorphism so it is unlikely that the Kuhn algorithm can be efficiently extended to this case.

Upvotes: 1

Related Questions