Subgraph isomorphism problem
- Subgraph isomorphism problem
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(G1, G2) Input: Two graphs G1 and G2. Question: Is G1 isomorphic to a subgraph of G2?
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.
The proof of subgraph isomorphism being NP-complete is simple and based on reduction of the clique problem. If subgraph isomorphism were polynomial, you could use it to solve the clique problem in polynomial time. Let "n" be the number of edges in G: you can then run the subgraph isomorphism "n"-2 times (with G1 being a clique of size 3 to "n", and G2 being G) to find the largest clique in "G".
Subgraph isomorphism is a generalization of the potentially easier graph isomorphism problem; if the graph isomorphism problem is NP-complete, the polynomial hierarchy collapses, so it is suspected not to be.
Application areas
In the area of cheminformatics often the term substructure search is used. Typically a query structure is defined as SMARTS, a SMILES extension.
Also of main importance to graph grammars.
ee also
*Induced subgraph isomorphism problem
*Maximum common subgraph isomorphism problem
References
* J. R. Ullmann: "An Algorithm for Subgraph Isomorphism". Journal of the ACM, 23(1):31–42, 1976.
* A1.4: GT48, pg.202.
Wikimedia Foundation.
2010.
Look at other dictionaries:
Induced subgraph isomorphism problem — In complexity theory and graph theory, induced subgraph isomorphism is an NP complete decision problem that involves finding a given graph as an induced subgraph of a larger graph.Formally, the problem takes as input two graphs G 1=( V 1, E 1)… … Wikipedia
Maximum common subgraph isomorphism problem — In complexity theory, maximum common subgraph isomorphism (MCS) is an optimization problem that is known to be NP hard. The formal description of the problem is as follows: Maximum common subgraph isomorphism(G1, G2) Input: Two graphs G1 and G2.… … Wikipedia
Graph isomorphism — In graph theory, an isomorphism of graphs G and H is a bijection between the vertex sets of G and H such that any two vertices u and v of G are adjacent in G if and only if ƒ(u) and ƒ(v) are adjacent in H. This kind of bijection is commonly… … Wikipedia
Clique problem — The brute force algorithm finds a 4 clique in this 7 vertex graph (the complement of the 7 vertex path graph) by systematically checking all C(7,4)=35 4 vertex subgraphs for completeness. In computer science, the clique problem refers to any of… … Wikipedia
Zarankiewicz problem — In the mathematical field of extremal graph theory, the Zarankiewicz problem asks how many edges can be added to a bipartite graph while avoiding a specific bipartite subgraph. Initially, the Polish mathematician K. Zarankiewicz proposed the… … Wikipedia
NP-complete — Euler diagram for P, NP, NP complete, and NP hard set of problems In computational complexity theory, the complexity class NP complete (abbreviated NP C or NPC) is a class of decision problems. A decision problem L is NP complete if it is in the… … Wikipedia
Graph theory — In mathematics and computer science, graph theory is the study of graphs : mathematical structures used to model pairwise relations between objects from a certain collection. A graph in this context refers to a collection of vertices or nodes and … Wikipedia
List of mathematics articles (I) — NOTOC Ia IA automorphism ICER Icosagon Icosahedral 120 cell Icosahedral prism Icosahedral symmetry Icosahedron Icosian Calculus Icosian game Icosidodecadodecahedron Icosidodecahedron Icositetrachoric honeycomb Icositruncated dodecadodecahedron… … Wikipedia
Color-coding — For other uses, see Color code. In computer science and graph theory, the method of color coding[1][2] efficiently finds k vertex simple paths, k vertex cycles, and other small subgraphs within a given graph using probabilistic algorithms, which… … Wikipedia
Graph rewriting — In graph theory, graph rewriting is a system of rewriting for graphs, i.e. a set of graph rewrite rules of the form p: L ightarrow R, with L being called pattern graph (or left hand side) and R being called replacement graph (or right hand side… … Wikipedia
