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

closed as unclear what you're asking by Tom van der Zanden, David Richerby, vonbrand, Nicholas Mancuso, Thomas Klimpel Aug 5 '15 at 22:41

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 1
    When are two edges "common"? Are both graphs subgraphs of the same original graph? – Raphael Jul 24 '15 at 8:53
  • there are matching subgraphs within these graphs, these subgraphs are not connected to each other – girl101 Jul 24 '15 at 8:55
  • This sounds like graph isomorphism. You want to determine what connected components are isomorphic. – Tom van der Zanden Jul 24 '15 at 10:11
  • 1
    What do you mean by subgraphs of two separate graphs being "connected"? You need to give either a formal definition or at least an example. – Raphael Jul 24 '15 at 11:28
  • 2
    I still can not make sense of your text, but it seems you want to solve the Maximum common subgraph isomorphism problem? – Raphael Jul 24 '15 at 11:47
up vote 1 down vote accepted

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.

  • here the isomorphic subgraphs are just one in number, I want to find all the maximal subgraphs that are not connected to each other between two graphs – girl101 Jul 25 '15 at 7:50
  • 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. – Tom van der Zanden Jul 25 '15 at 9:54
  • @Rishika, see my edited answer -- it now addresses that point explicitly. – D.W. Jul 25 '15 at 18:18
  • @TomvanderZanden, great point! Thank you! I've added that to my answer. – D.W. Jul 25 '15 at 18:19

Not the answer you're looking for? Browse other questions tagged or ask your own question.