Re: László Babai's Mathematical Result on Graph Isomorphism

Hi Henry,

While existing algorithms for the graph isomorphism problem cannot be affected, 
tools that use such an algorithm in the context of RDF graphs may replace this 
algorithm by Babai's new one and, thus, may achieve better performance for the 
tasks for which they have to solve the graph isomorphism problem.

However, we should not expect improvements when it comes to /querying/ RDF 
data because query evaluation is more closely related to the subgraph 
isomorphism problem, which is a generalization of the graph isomorphism 
problem and known to be NP-complete. (BTW, there is a recent paper in which 
the authors adapt the state-of-the-art subgraph isomorphism algorithm to find 
homomorphisms and do RDF pattern matching [1]).

Best,
Olaf

[1] Kim et al.: "Taming Subgraph Isomorphism for RDF Query Processing". In 
PVLDB 8(11), 2015.


On Saturday 07 November 2015 09:29:18 henry.story@bblfish.net wrote:
> Hi,
> 
>   I was pointed to a blog entitled "A Big Result On Graph Isomorphism -
> Jumping GI down from the nearly-exponential neighborhood to the
> nearly-polynomial one"
> > László Babai is one of the world experts on complexity theory, especially
> > related to groups and graphs. He also recently won the 2015 ACM Knuth
> > Prize, for which we congratulate him. Today we wish to discuss a new
> > result that he has announced that will place graph isomorphism almost in
> > polynomial time. More exactly László shows that Graph Isomorphism is in
> > Quasipolynomial Time
> https://rjlipton.wordpress.com/2015/11/04/a-big-result-on-graph-isomorphism/
> 
> Does this affect in any way the algorithms on graphs isomorphisms for RDF
> graphs?
> 
> Henry

Received on Saturday, 7 November 2015 23:32:46 UTC