Subgraph isomorphism problem
Encyclopedia
In theoretical computer science
, the subgraph isomorphism problem is a computational task in which two graphs G and H are given as input, and one must determine whether G contains a subgraph that is isomorphic
to H.
Subgraph isomorphism is a generalization of both the maximum clique problem
and the problem of testing whether a graph contains a Hamiltonian cycle, and is therefore NP-complete
. However certain other cases of subgraph isomorphism may be solved in polynomial time.
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 input to the decision problem is a pair of graphs G and H. The answer to the problem is positive if H is isomorphic to a subgraph of G, and negative otherwise.
The proof of subgraph isomorphism being NP-complete is simple and based on reduction of the clique problem
, an NP-complete decision problem in which the input is a single graph G and a number k, and the question is whether G contains a complete subgraph
with k vertices. To translate this to a subgraph isomorphism problem, simply let H be the complete graph Kk; then the answer to the subgraph isomorphism problem for G and H is equal to the answer to the clique problem for G and k. Since the clique problem is NP-complete, this polynomial-time many-one reduction shows that subgraph isomorphism is also NP-complete.
An alternative reduction from the Hamiltonian cycle problem translates a graph G which is to be tested for Hamiltonicity into the pair of graphs G and H, where H is a cycle having the same number of vertices as G. Because the Hamiltonian cycle problem is NP-complete even for planar graphs, this shows that subgraph isomorphism remains NP-complete even in the planar case.
Subgraph isomorphism is a generalization of the graph isomorphism problem
, which asks whether G is isomorphic to H: the answer to the graph isomorphism problem is true if and only if G and H both have the same number of vertices and the subgraph isomorphism problem for G and H is true. However the complexity-theoretic status of graph isomorphism remains an open question.
In the context of the Aanderaa–Karp–Rosenberg conjecture on the query complexity of monotone graph properties, showed that any subgraph isomorphism problem has query complexity Ω(n3/2); that is, solving the subgraph isomorphism requires an algorithm to check the presence or absence in the input of Ω(n3/2) different edges in the graph.
and H is fixed, the running time of subgraph isomorphism can be reduced to linear time.
to find similarities between chemical compounds from their structural formula; often in this area the term substructure search is used. Typically a query structure
is defined as SMARTS
, a SMILES extension.
The closely related problem of counting the number of isomorphic copies of a graph H in a larger graph G has been applied to pattern discovery in databases, the bioinformatics
of protein-protein interaction networks, and in exponential random graph methods for mathematically modeling social network
s.
describe an application of subgraph isomorphism in the computer-aided design
of electronic circuits. Subgraph matching is also a substep in graph rewriting
(the most runtime-intensive), and thus offered by graph rewrite tools.
Theoretical computer science
Theoretical computer science is a division or subset of general computer science and mathematics which focuses on more abstract or mathematical aspects of computing....
, the subgraph isomorphism problem is a computational task in which two graphs G and H are given as input, and one must determine whether G contains a subgraph that is isomorphic
Graph isomorphism
In graph theory, an isomorphism of graphs G and H is a bijection between the vertex sets of G and H f \colon V \to V \,\!such that any two vertices u and v of G are adjacent in G if and only if ƒ and ƒ are adjacent in H...
to H.
Subgraph isomorphism is a generalization of both the maximum clique problem
Clique problem
In computer science, the clique problem refers to any of the problems related to finding particular complete subgraphs in a graph, i.e., sets of elements where each pair of elements is connected....
and the problem of testing whether a graph contains a Hamiltonian cycle, and is therefore NP-complete
NP-complete
In computational complexity theory, the complexity class NP-complete is a class of decision problems. A decision problem L is NP-complete if it is in the set of NP problems so that any given solution to the decision problem can be verified in polynomial time, and also in the set of NP-hard...
. However certain other cases of subgraph isomorphism may be solved in polynomial time.
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.
Decision problem and computational complexity
To prove subgraph isomorphism NP-complete, it must be formulated as a decision problemDecision problem
In computability theory and computational complexity theory, a decision problem is a question in some formal system with a yes-or-no answer, depending on the values of some input parameters. For example, the problem "given two numbers x and y, does x evenly divide y?" is a decision problem...
. The input to the decision problem is a pair of graphs G and H. The answer to the problem is positive if H is isomorphic to a subgraph of G, and negative otherwise.
The proof of subgraph isomorphism being NP-complete is simple and based on reduction of the clique problem
Clique problem
In computer science, the clique problem refers to any of the problems related to finding particular complete subgraphs in a graph, i.e., sets of elements where each pair of elements is connected....
, an NP-complete decision problem in which the input is a single graph G and a number k, and the question is whether G contains a complete subgraph
Complete graph
In the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge.-Properties:...
with k vertices. To translate this to a subgraph isomorphism problem, simply let H be the complete graph Kk; then the answer to the subgraph isomorphism problem for G and H is equal to the answer to the clique problem for G and k. Since the clique problem is NP-complete, this polynomial-time many-one reduction shows that subgraph isomorphism is also NP-complete.
An alternative reduction from the Hamiltonian cycle problem translates a graph G which is to be tested for Hamiltonicity into the pair of graphs G and H, where H is a cycle having the same number of vertices as G. Because the Hamiltonian cycle problem is NP-complete even for planar graphs, this shows that subgraph isomorphism remains NP-complete even in the planar case.
Subgraph isomorphism is a generalization of the graph isomorphism problem
Graph isomorphism problem
The graph isomorphism problem is the computational problem of determining whether two finite graphs are isomorphic.Besides its practical importance, the graph isomorphism problem is a curiosity in computational complexity theory as it is one of a very small number of problems belonging to NP...
, which asks whether G is isomorphic to H: the answer to the graph isomorphism problem is true if and only if G and H both have the same number of vertices and the subgraph isomorphism problem for G and H is true. However the complexity-theoretic status of graph isomorphism remains an open question.
In the context of the Aanderaa–Karp–Rosenberg conjecture on the query complexity of monotone graph properties, showed that any subgraph isomorphism problem has query complexity Ω(n3/2); that is, solving the subgraph isomorphism requires an algorithm to check the presence or absence in the input of Ω(n3/2) different edges in the graph.
Algorithms
describes a recursive backtracking procedure for solving the subgraph isomorphism problem. Although its running time is, in general, exponential, it takes polynomial time for any fixed choice of H (with a polynomial that depends on the choice of H). When G is a planar graphPlanar graph
In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints...
and H is fixed, the running time of subgraph isomorphism can be reduced to linear time.
Applications
As subgraph isomorphism has been applied in the area of cheminformaticsCheminformatics
Cheminformatics is the use of computer and informational techniques, applied to a range of problems in the field of chemistry. These in silico techniques are used in pharmaceutical companies in the process of drug discovery...
to find similarities between chemical compounds from their structural formula; often in this area the term substructure search is used. Typically a query structure
Query language
Query languages are computer languages used to make queries into databases and information systems.Broadly, query languages can be classified according to whether they are database query languages or information retrieval query languages...
is defined as SMARTS
Smiles arbitrary target specification
SMiles ARbitrary Target Specification is a language for specifying substructural patterns in molecules. The SMARTS line notation is expressive and allows extremely precise and transparent substructural specification and atom typing....
, a SMILES extension.
The closely related problem of counting the number of isomorphic copies of a graph H in a larger graph G has been applied to pattern discovery in databases, the bioinformatics
Bioinformatics
Bioinformatics is the application of computer science and information technology to the field of biology and medicine. Bioinformatics deals with algorithms, databases and information systems, web technologies, artificial intelligence and soft computing, information and computation theory, software...
of protein-protein interaction networks, and in exponential random graph methods for mathematically modeling social network
Social network
A social network is a social structure made up of individuals called "nodes", which are tied by one or more specific types of interdependency, such as friendship, kinship, common interest, financial exchange, dislike, sexual relationships, or relationships of beliefs, knowledge or prestige.Social...
s.
describe an application of subgraph isomorphism in the computer-aided design
Computer-aided design
Computer-aided design , also known as computer-aided design and drafting , is the use of computer technology for the process of design and design-documentation. Computer Aided Drafting describes the process of drafting with a computer...
of electronic circuits. Subgraph matching is also a substep in graph rewriting
Graph rewriting
Graph transformation, or Graph rewriting, concerns the technique of creating a new graph out of an original graph using some automatic machine. It has numerous applications, ranging from software verification to layout algorithms....
(the most runtime-intensive), and thus offered by graph rewrite tools.
See also
- Induced subgraph isomorphism problemInduced subgraph isomorphism problemIn 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....
- Maximum common subgraph isomorphism problemMaximum common subgraph isomorphism problemIn complexity theory, maximum common subgraph-isomorphism is an optimization problem that is known to be NP-hard. The formal description of the problem is as follows:Maximum common subgraph-isomorphism...