Re: maximum common subgraph

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."

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


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.]


.

Relevant Pages