Subgraph isomorphism problem
From Wikipedia, the free 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 graphss G₁ and G₂.
Question: Is G₁ isomorphic to a subgraph of G₂?

The original article can be found at: http://en.wikipedia.org/wiki/Subgraph_isomorphism_problem.
All text is available under the terms of the GNU Free Documentation License.