Re: [igraph] Inexact graph matching

[Tamás Nepusz]

Hello Khris, 

This seems to be a very complicated graph matching problem and I'm very 
confident that you cannot find the exact solution in polynomial time -- if you 
could, you could also solve the graph isomorphism problem in polynomial time by 
finding the best match between the two graphs and checking whether the distance 
between the two matched matrices is zero or not. If the graph is small, you can 
try a branch-and-bound strategy -- basically an exhaustive search where you 
keep track of the best match found so far (and its "cost") and skip the 
branches of the search tree where you can infer that the cost of any leaf in 
that branch is higher than the best match found so far. (You can do this 
because the cost function is monotonously increasing as you match more and more 
nodes along a branch of a search tree). This will be exponential, but with some 
clever heuristics it may be tractable. The heuristic part comes into play at 
two places:

1. You have to decide in which order you are going to consider the nodes of one 
graph to be matched to the other as you build up the complete matching.
2. You have to decide in which order you try to assign the unmatched nodes of 
G2 to the currently considered node in G1.

-- 
T.


On Tuesday, 3 July 2012 at 16:12, Khris wrote:

> Hi,
> 
> I have specific Graph matching problem and I am not sure what's the best way 
> to deal with it. The following is the def:-
> 
> We have 2 weighted undirected graphs. In one graph I know the distance of 
> every vertex from every other vertex whereas in another graph I know only 
> which vertices are close to a given vertex. So I know the neighboring 
> vertices given a vertex. So the distance matrix of other Graph is 
> incompletely known. So the question is what's the best way to find the 
> correct alignment between the 2 graphs. Are there any functions in iGraph 
> library which implements those Algorithms?
> 
> Ex:- G1 is know the complete distance matrix. For G2, if there are four 
> vertices let's say (v1, v2, v3 v4) the I know edge weight (v1,v2) and (v1,v3) 
> but have no information of edge weight(v1,v4). Similarly I know about (v2,v3) 
> but no information about edge weights (v2,v4) or (v3,v4). So G2 is 
> incompletely known.
> 
> Appreciate any useful feedback and pointers.
> 
> Rest fine
> Khris.
> 
> 
> 
> _______________________________________________
> igraph-help mailing list
> address@hidden (mailto:address@hidden)
> https://lists.nongnu.org/mailman/listinfo/igraph-help