Algorithms for subgraph isomorphism detection [closed]

Question

Subgraph isomorphism is an NP Complete problem. The most widely used algorithm is the one proposed by Ullman.

Can someone please explain the algorithm to me in layman's language? I read the above paper by him, but couldn't understand much.

What other algorithms exist for this problem?

I am working on an image processing project.

Til

Post a link to a PDF would ya? I suspect that this is homework. – Fariss

@Hamish: What kind of school/college gives solving a NP Complete problem as homework? I might join it :) – Til

Professors in graduate classes like to weed out and recruit geniuses by giving one or two crazy problems on homework sets. – Fariss

@Hamish: Thats news to me. I am still an undergraduate and definitely not a genius :) – Til

NP-complete doesn't mean a problem cannot be solved; it just means that no exact algorithm is known that scales polynomially as the input size grows large. It is still often possible to find approximate algorithms, and it is usually possible to solve the problem exactly for quite a range of small input sizes. (For example, the traveling salesperson problem can be solved for up to tens of thousands of nodes.) – Wellappointed

@Jack, you officially become a genius once you make it to grad school ;) That is because you no longer have time to drink but to release your true potential. – Fariss

I believe so far the most recent progress in the field is Turboiso: towards ultrafast and robust subgraph isomorphism search in large graph databases from SIGMOD 2013. The authors also have a survey paper on the existing algorithms in VLDB 2012. – Orissa

Answer 1

VFLib2 is a C++ library for graph isomorphism finding. It also includes an Ullman implementation: http://mivia.unisa.it/datasets/graph-database/vflib/

Gloaming

Answer 2

This blog post tries to give an overview of the algorithm. The original presentation is hard to read because it presents the algorithm as you would write it on a '70s computer.

Crawl