CODEWITHSUNDEEP
algorithmgraph-algorithm
user2032084
user2032084

Reputation:

How can I find Maximum Common Subgraph of two graphs?

Hi i need a help in finding a graph algorithm

im working on the following equation related to distance functions 

d (g1, g2)   = 1-       │mcs(g1,g2) │  /
             │g1│+│g2│-│mcs (g1, g2) │

Where

My Question: How can I calculate MCS?
I searched the internet but most of the algorithms are complicated anyone know from where i can get a simple algorithm to program this equation in matlab.

Upvotes: 6

Views: 11359

Answers (4)

izilotti
izilotti

Reputation: 4927

The backtracking search algorithm proposed by James J. McGregor may be utilized to identify the MCS between two graphs.

Upvotes: 3

beaker
beaker

Reputation: 16801

The main problem is finding a correspondence between nodes in the original graphs (essentially a renumbering of the vertices). For instance, if we have node p in graph g1 and node q in graph g2 where p and q are equivalent, we'd like to map them to a node s in the common subgraph, c.

The reason that the Clique Problem is so difficult is that, without any way of checking whether two nodes in different graphs actually refer to the same node, we have to try all possible combinations of pairs of nodes and check if each pair is consistent and represents the "best" correspondence.

Since the nodes in these graphs represent geographic locations, we should be able to come up with a reasonable distance metric that tells us how likely it is that a node in one graph is the same as any node in the other graph. Since the GPS coordinates of the two nodes are probably not identical, we need to make some assumptions based on the problem.

  • If we have a map of the region in which the data points occur, represented as a graph m, we can renumber or rename the nodes in g1 and g2 to correspond to their closest equivalent in in m.
  • Distance (either between the original graphs and m or between points in g1 and g2) can either be the Euclidean distance or the Manhattan distance, depending on what makes more sense for your graphs.
  • You'll have to be careful in deciding how far apart two nodes can be and still be considered equivalent. Too small and you won't get any matches; too large and your entire graph could be condensed into one node.
  • Two or more nodes in an original graph could possible all map to the same node in c. If the location data is updated frequently in relation to the distance between nodes, for instance.
  • Conversely, an edge between a pair of successive nodes in an original graph could also map to a path containing multiple edges if the update frequency is low in relation to the distances. So you'll have to figure out whether it makes sense to introduce these intermediate nodes into the common graph or treat the whole path as a single edge.

Once you've got the renumbering of the nodes you can use the method that Jens suggests to find the intersection of the renumbered graphs. This is all very general since I don't have a lot of details about your specific problem, but hopefully it's enough to get you started.

Upvotes: 0

Grigor Gevorgyan
Grigor Gevorgyan

Reputation: 6853

You can't even check if one graph is a subgraph of the other one, it's the subgraph isomorphism problem known to be NP-complete. Hereby you can't find the maximal subgraph because you can't check the isomorphism property (in polynomial time).

Upvotes: 0

amit
amit

Reputation: 178451

The problem is NP-Complete1.

The reduction from the Clique Problem2. Given an instance of Clique Problem - a graph G=(V,E), create a complete clique G'=(V,E') such that E' = {(u,v) | u != v, for each u,v in V).

The solution to the maximal clique problem is the same solution for the maximal subgraph problem for G and G'. Since clique problem is NP-Hard, so does this problem.

Thus, there is no known polynomial solution to this problem.

If you are looking for an exact algorithm, you could try exhaustive search approach and/or a branch & bound approach to solve it. Sorry for the bad news, but at least you know not to look for something that (probably) doesn't exist (unless P=NP, of course)

EDIT: exponential brute force solution to the problem:
You can just check all possible subsets, and check if it is a feasible solution.
Pseudo Code:

findMCS(vertices,G1,G2,currentSubset):
  if vertices is empty: //base clause, no more candidates to check
      if isCommonSubgraph(G1,G2,currentSubset):
         return clone(currentSubset)
      else:
         return {}
  v <- vertices.pop() //take a look at the first element
  cand1 <- findMCS(vertices,G1,G2,currentSubset) //find MCS if it is NOT in the subset
  currentSubset.append(v)
  if isCommonSubgrah(G1,G2,currentSubset): //find MCS if it is in the subset
     cand2 <- findMCS(vertices,G1,G2,currentSubset)
  currentSubset.remvoe(v) //clean up environment before getting back from recursive call
  return (|cand1| > |cand2| ? cand1 : cand2) //return the maximal subset from all candidates

Complexity of the above is O(2^n) (checking all possible subsets), and invoke it with: findMCS(G1.vertices, G1, G2, []) (where [] is an empty list).

Note:

  • isCommonSubgrah(G1,G2,currentSubset) is an easy to calculate method that just answers true if and only if currentSubset is a common subgraph of G1 and G2.
  • |cand1| and |cand2| is the sizes of these lists.

(1)Assuming that Maximum sub graph is a subset U in V such that for each u1,u2 in U (u1,u2) is in E1 if and only if (u1,u2) is in E2 (intuitively, a maximal subset of the vertices that share the exact same edges in the two graphs)

(2) Clique Problem: Given an instance of G=(V,E) find maximal subset U in V such that for each u1,u2 in U : u1 = u2 or (u1,u2) is in E.

Upvotes: 6

Related Questions