Cheap and Secure Web Hosting Provider : See Now

[Solved]: Finding common edges of two graphs

, , No Comments
Problem Detail: 

Is there any algorithm that finds the common edges and vertices between two graphs? Its not a common subgraph problem though, the edges which are common between the two graphs may not be connected to each other, may be far apart. How to find all the common edges in the graph? Like finding the common subgraphs between two graphs such that none of the subgraphs are connected to each other. Like these two graphs, the black and the blue part are the uncommon part...
the green and yellow and red nodes are common, the black and blue are uncommon

Asked By : Rishika

Answered By : D.W.

This appears to be the maximum subgraph isomorphism problem: given graphs $G,H$, you want to find the largest pairs of subgraphs $G',H'$ that are isomorphic (where $G'$ is a subgraph of $G$ and $H'$ is a subgraph of $H'$ and $G'$ is isomorphic to $H'$). Then the edges of $G',H'$ are common to both $G$ and $H$. Apparently, this problem has been applied in chemistry, which might be of interest to you given the diagram you showed.

In the comments you asked about the case $G$ and $H$ both have two common subgraphs which are not connected to each other. The maximum subgraph isomorphism solution will automatically find those. Nothing requires $G'$ or $H'$ to be connected. Thus, in your case, the optimal solution will have $G'$ consist of two disconnected components, and $H'$ consisting of the same two components. So, this problem already does what you want.

This problem is NP-hard for general graphs, so the general expectation is that there's not likely to be any efficient algorithm that can handle large, general graphs. However, you have two aspects that offer room for hope. First, it appears that your graphs are relatively small, so there might algorithms that are acceptable for graphs that are about the size of the examples in your diagram: even exponential-time algorithms might be practical. Second, and more importantly, it looks like you aren't dealing with arbitrary graphs. As Tom van der Zanden accurately explains:

The graphs shown in the example are both trees and they appear to be models of molecules. While of course molecules (like benzene) can have cycles, depending on what molecules the OP is interested in the problem may not be NP-hard.

So, I suggest you search the research literature to see if there's been work done on the maximum subgraph isomorphism problem for trees. There might be algorithms that have been described in the algorithms literature that you could use.

Best Answer from StackOverflow

Question Source :

3.2K people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback