9
$\begingroup$

While studying data structures i was told my instructor that even i am given 3 hour/30 days/3 years to find out whether two graphs are isomorphic or not, it is very very complex and even after spending this much amount of time i will not able to figure out clearly whether the given two graphs are isomorphic or not. It is NP-complete problem.

So i got the curiosity that why i am studying it then. What could be the possible applications of such isomorphic graphs which can be solved ?

$\endgroup$
9
  • 7
    $\begingroup$ Graph isomorphism is not known to be NP-complete. Wikipedia says "[i]ts practical applications include primarily cheminformatics, mathematical chemistry (identification of chemical compounds), and electronic design automation (verification of equivalence of various representations of the design of an electronic circuit)." $\endgroup$ – Qiaochu Yuan Mar 15 '12 at 7:23
  • $\begingroup$ @QiaochuYuan : well, i was told by my instructor today that it is class NP problem. That's why i posted my confusion here... $\endgroup$ – Ankur Trapasiya Mar 15 '12 at 7:26
  • 9
    $\begingroup$ "NP" does not mean "NP-complete," although I guess this is an understandable mistake; graph isomorphism is one of the few problems in NP not known to either be in P or be NP-complete along with factoring. $\endgroup$ – Qiaochu Yuan Mar 15 '12 at 7:28
  • $\begingroup$ @QiaochuYuan : ok. I am aware of neither NP or NP complex problem. I just heard that so that i posted right here. I am editing the post for it. $\endgroup$ – Ankur Trapasiya Mar 15 '12 at 7:31
  • 1
    $\begingroup$ The term is "NP-complete", not "NP complex". $\endgroup$ – joriki Mar 15 '12 at 8:06
10
$\begingroup$

Bluntly put, the applications are endless...

Before I start the list, I think it will be appropriate to explain something. First of all, all the entities in the world (real and abstract) are connected by some relations. A big part of them is kind of regular or close to regular (e.g. the ordering of natural numbers), and people can and do exploit this very often. However, there is huge, gigantic, infinitely larger (or even more colossal, but I lack words...) class of relations that are weird, curious, peculiar, or even ridiculous. We do not know how to bridle them, so we analyze very tiny, finite parts of them using graphs. Every time when we show an isomorphism between such graphs, a new star starts to shine on the firmament of human thinking power.

Ok, to be more concrete (this list wasn't sorted by any criterion):

  • Cryptography, e.g. zero knowledge proofs.
  • In automata theory: multiple uses, mainly to show that some two languages are equal.
  • In parallel processing, to reason about behaviour of complex systems.
  • In verification of many things: computer programs, logic proofs, or even electronic circuits.
  • In compilers, e.g. to perform various optimizations.
  • In any search engine that can use formulas more sophisticated than words, e.g. in chemistry, biology, but I guess also music and other arts fall into that category as well.
  • Security, i.e. fingerprints scanners, facial scanners, retina scanners and so on.
  • I do not know for sure, but it is highly probable, that any system that performs clustering would benefit from fast graph-isomorphism algorithm, e.g.
    • linking two facebook's accounts of the same person,
    • recognizing web users based on their behavior,
    • recognizing plagiarism in students solutions,
    • :-) I have no idea if there is a Numb3rs episode that uses graph isomorphism problem, but there should be one.
  • Civil engineering, city planning, building interior planning (this may fall into "search" category as well, e.g. recognizing geographic locations with desired properties).
  • Analysis of social structures (special cases may include schools, military, parties, events, etc.), big part of it is search again.
  • Analysis of business relations.
  • I have no idea about medicine (not biology), but there has to be something there, this domain is too wide. Edit: Quick search revealed two (quite obvious...) applications:
    • travel medicine,
    • searching in database or medical images.

Please note, that most of those points are meta-examples, they do not specify particular use, i.e. there are multiple uses in each of those.

$\endgroup$
5
  • 1
    $\begingroup$ If graph isomorphism is an NP-Complete problem which is very hard to solve and takes plenty of time then how the real world applications implement it? $\endgroup$ – Ankur Trapasiya Mar 17 '12 at 8:11
  • 1
    $\begingroup$ @ankur.trapasiya Contrary to popular believes, algorithms with exponential running time can be very fast (for real-world problem instances), e.g. recent SAT algorithm $O(1.308^n)$ by Hertli. There are approximating algorithms, e.g. recent $13/9$ for TSP by Mucha, or even exact polynomial time algorithms for special cases: many for planar graphs, or graphs with bounded treewidth, etc., compare this great paper. Finally, heuristics, heuristics, heuristics--after all this is what we humans do ;-) $\endgroup$ – dtldarek Mar 17 '12 at 9:46
  • 1
    $\begingroup$ I would like know above graph isomorphism applications in detail. Can you provide me the sources. $\endgroup$ – Kumar Mar 21 '14 at 5:06
  • 1
    $\begingroup$ @Gold Quick search revealed multiple matches: 1, 2, 3, 4 5, 6, 7. $\endgroup$ – dtldarek Mar 21 '14 at 9:51
  • $\begingroup$ @Gold As for the list from the post, it does not have any source, you hear things, see things, read things, there are discussions at seminars on what people do or plan to do, etc. Many times there's no source at all, and even if there is, I forgot (it's not directly relevant to my research). As for the 7 examples above, I didn't read these papers, so I am unable to comment on their quality. $\endgroup$ – dtldarek Mar 21 '14 at 9:55
5
$\begingroup$

For subgraph isomorphism, there are too many applications; like finding defect in texture. Texture mades of regular images, and if some pieces of given texture has another shape, it can be defect (like hole).

You can divide texture in different pieces and apply graph isomorphism on pieces (Instead of using NP-Complete problem like subgraph isomorphism). Also graph isomorphism is solvable in planar graphs (by knowing that planar graphs tree-width is at most 3 times of its diameter), and texture is planar graph, so this can be a real application in real world.

Also another sample is implicitly related problems, too many problems can be reduced to graph isomorphism (and vise versa). May be this is theoretical result, but in fact, you can find at least one usage of each problem in real world, and this usage can be extended to graph isomorphism.

And finally, I personally like pure science, another real world usage of graph isomorphism is enjoyment of people like me.

$\endgroup$
5
$\begingroup$

A good example is the perturbative expansion of Feynman's path integral by summing over Feynman diagrams. This is an infinite series, each stage of which is parameterized by a finite sum over isomorphism classes of certain kinds of graphs. Writing down all isomorphism classes of graphs with certain data requires being able to tell if two graphs are isomorphic.

$\endgroup$
4
  • $\begingroup$ Sorry to say but I am not having that much knowledge to understand your answer. $\endgroup$ – Ankur Trapasiya Mar 16 '12 at 6:49
  • $\begingroup$ @ankur.trapasiya: that's okay, I only have a very primitive understanding of the path integral myself. :) $\endgroup$ – Cheerful Parsnip Mar 16 '12 at 13:51
  • $\begingroup$ If graph isomorphism is an NP-Complete problem which is very hard to solve and takes plenty of time then how the real world applications implement it? $\endgroup$ – Ankur Trapasiya Mar 17 '12 at 8:11
  • $\begingroup$ @ankur.trapasiya: only the first few terms can be computed. $\endgroup$ – Cheerful Parsnip Mar 17 '12 at 13:03
1
$\begingroup$

If your question is actually: "what are possible applications of the isomorphism problem", then check this: http://en.wikipedia.org/wiki/Graph_isomorphism_problem#Applications

Another very interesting application of the isomorphism problem is the development of algorithms for fingerprint matching http://euler.mat.ufrgs.br/~trevisan/workgraph/regina.pdf

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.