# Re: maximum common subgraph

*From*: GCRhoads <GCRhoads@xxxxxxxxxxxxxxx>*Date*: Mon, 01 Oct 2007 22:19:00 -0700

On Sep 30, 4:02 pm, sor...@xxxxxxxxx wrote:

Dear all,

I quote fromhttp://en.wikipedia.org/wiki/Maximum_common_subgraph_isomorphism_problem

* Input: Two graphs G1 and G2.

* Question: What is the largest subgraph of G1 isomorphic to a

subgraph of G2?

First, I'd like some clarifications. Do they mean _induced_ subgraph?

(http://en.wikipedia.org/wiki/Subgraph#Subgraphs) I suppose they mean

induced. Otherwise we could choose the subgraph G1' that contains min(|

G1|, |G2|) vertices and no edges and it would be the common subgraph

with the largest number of vertices.

Both subgraphs (the subgraph of G1 and the subgraph of G2) have to be

induced, or only the subgraph of G1?

You've misquoted the problem listed on the referenced page!

The page says,

"Question: What is the largest *induced* subgraph of G1 isomorphic to

a subgraph of G2."

subgraph of G2 does not have to be.From this I assume they mean the subgraph of G1 is induced but the

Second, they suggest the following algorithm:

One possible solution for this problem is to build a product graph, in

which the largest clique represents a solution for the MCS problem.

Please have a look at the talk pagehttp://en.wikipedia.org/wiki/Talk:Maximum_common_subgraph_isomorphism...

I've tried to apply their algorithm on the example in the figure, but

the algorithm does not produce the desired result. What did I

misunderstand?

The graph you drew is *NOT* the modular product graph, it is not even

close. E.g. you have A2 and B1 as the neighbors of A1 when in fact

the neighbors of A1 are B2, C3, C4, D3, and D4. The given definition

is misstated in a way that doesn't make sense. It should read, "Any

two vertices (u, v) and (u', v') ..." with the rest being the same.

Also, vertices u and u' must be distinct vertices in G1, and v and v'

are distinct in G2. If they are not distinct, then there is no edge

in the modular product graph. Does that clear up your confusion?

[It is easy to see that A1, B2, C3, and D4 do form a clique in the

modular product graph but it is not so easy to see that it is a

maximum clique.]

.

- Prev by Date:
**Re: Subset sum problem: probabilistic fast testing algorithm...** - Next by Date:
**Re: Exploiting limitations of Turing machines in Turing tests?** - Previous by thread:
**Re: Subset sum problem: probabilistic fast testing algorithm...** - Next by thread:
**Algorithm: Min cost in a 2D array** - Index(es):