Subgraph isomorphism problem

From Free net encyclopedia

In complexity theory, Subgraph-Isomorphism is a decision problem that is known to be NP-complete. The formal description of the decision problem is as follows.

Subgraph-Isomorphism(G₁, G₂)
Input: Two graphs G₁ and G₂.
Question: Is G₁ isomorphic to a subgraph of G₂?

Sometimes the name subgraph matching is also used for the same problem. This name puts emphasis on finding such a subgraph as opposed to the bare decision problem.

Subgraph isomorphism is a generalization of the potentially easier graph isomorphism problem; if this problem is NP-complete, the polynomial hierarchy collapses, so it is suspected not to be.

See also

• Maximum common subgraph isomorphism problem

References

• Jeffrey D. Ullman: "An Algorithm for Subgraph Isomorphism". Journal of the ACM, 23(1):31–42, 1976.
• Template:Cite book A1.4: GT48, pg.202.vi:Bài toán đồ thị con đẳng cấu