Talk:Subgraph isomorphism problem

Citations are inconsistent

Why does this page use a mixture of harvard and citation note [1] styles? 129.67.86.189 (talk) 12:42, 26 April 2010 (UTC)

That's pretty standard. See graph coloring or Hilbert space. --Robin (talk) 13:04, 26 April 2010 (UTC)

Pseudocode anyone? Also, another algorithm?

I'm surprised such a ubiquitously mentioned problem doesn't already have an algorithm outlined in pseudocode, or mention of an algorithm besides Ullmann's. Does another useful algorithm not even exist? Anyhow, I'm gonna tackle implementing this soon, and would love to post some pseudocode (or even a naive Java implementation) once I've completed it. If anyone knows of another algorithm for subgraph isomorphism, please don't hesitate to mention it (especially if it's simpler, and therefore more pseudocode-able, than Ullmann's.) --Frizzil (talk) 02:15, 17 October 2012 (UTC)

I just realized there's pseudocode in the paper describing Ullmann's, although it's illegible to the point Adobe Reader produces garbage when you attempt to copy/paste it. I'll try to decipher it by late tomorrow night. --Frizzil (talk) 02:18, 17 October 2012 (UTC)

formal problem description

can anyone add a formal description of the problem? --141.53.216.143 (talk) 10:40, 4 March 2013 (UTC)

The original description is perfectly formal. Why do you think it isn’t, and why do you think your description is more formal (rather than just more symbol-laden)?—Emil J. 17:51, 4 March 2013 (UTC)

Agree with EmilJ. I think the definition in text is perfectly formal. --Robin (talk) 19:48, 4 March 2013 (UTC)

The characterization of isomorphic in the formal statement of the problem is wrong I believe. The left-to-right implication should be a bi-implication. As it stands, the left-to-right implication is always true (take G_0 to be a graph with no edges). The right-to-left implication is what is important. So I suppose the implication could be reversed. I would not recommend it however. In the definition of the problem I feel it is best to give the most straightforward characterization, rather than one that relies on a (admittedly easy to see, for some at least) consequence of this specific problem - that any subgraph of G is an eligible candidate.

Question: is the formal problem description as written not the induced subgraph isomorphism problem? It seems that according to this definition, there can not be an edge in G0 if it is absent in H. — Preceding unsigned comment added by 2a02:a44f:2c3b:0:8506:397c:617a:83c3 (talk • contribs)

I thought you might be right, but on second thought the definition looks ok to me. It defines G0 as a subgraph of G (not an induced subgraph) and then checks that the resulting subgraph is isomorphic to H (bijection of vertices with edges present in one iff present in the other). —David Eppstein (talk) 19:02, 10 November 2024 (UTC)

Now I see indeed. I think I mistook G0 as an induced subgraph somehow. Thanks! 2A02:A44F:2C3B:0:403E:F802:EF1C:4AF (talk) 15:24, 14 November 2024 (UTC)

This article lacks almost all practical implementations

including survey papers thereof. 86.127.138.234 (talk) 06:14, 18 February 2015 (UTC)

Incomplete proof that subgraph isomorphism is NP-complete

This may be a nitpick, but the proof only shows that subgraph isomorphism is NP-hard. To demonstrate NP-completeness, it has to also be shown to be in NP. While this is straightforward to do, by first checking that the function f is a bijection, and its domain is of size n, it should be mentioned.--Houseofwealth (talk) 19:40, 11 March 2020 (UTC)