Talk:Subgraph isomorphism problem

	Mathematics portal This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.MathematicsWikipedia:WikiProject MathematicsTemplate:WikiProject Mathematicsmathematics articles
Mid	This article has been rated as Mid-priority on the project's priority scale.

Computer science Mid‑importance

This article is within the scope of WikiProject Computer science, a collaborative effort to improve the coverage of Computer science related articles on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.Computer scienceWikipedia:WikiProject Computer scienceTemplate:WikiProject Computer scienceComputer science articles

Mid

This article has been rated as Mid-importance on the project's importance scale.

Things you can help WikiProject Computer science with:

Here are some tasks awaiting attention:

Article requests :
- Requested articles/Applied arts and sciences/Computer science, computing, and Internet
Cleanup :
- Computer science articles needing attention
- Computer science articles needing expert attention
Copyedit :
- Computing
Expand :
- Computer science
Infobox :
- Computer science articles without infoboxes
Maintain :
- Timeline of computing 2020–present
Photo :
- Find pictures for the biographies of computer scientists (see List of computer scientists)
- Computing articles needing images
Stubs :
- Computer science stubs
Unreferenced :
- WikiProject Computer science/Unreferenced BLPs
Project-related :
- Tag all relevant articles in Category:Computer science and sub-categories with {{WikiProject Computer science}}

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)[reply]

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

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)[reply]

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)[reply]

formal problem description

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

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)[reply]

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

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)[reply]

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)[reply]

This article lacks almost all practical implementations

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

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)[reply]