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. Complexity theory is part of the theory of computation dealing with the resources required during computation to solve a given problem. ... In logic, a decision problem is determining whether or not there exists a decision procedure or algorithm for a class S of questions requiring a Boolean value (i. ... In complexity theory, the NP-complete problems are the most difficult problems in NP, in the sense that they are the ones most likely not to be in P. The reason is that if you could find a way to solve an NP-complete problem quickly, then you could use...
Subgraph-Isomorphism(G1, G2) Input: Two graphs G1 and G2. Question: Is G1isomorphic to a subgraph of G2? In mathematics, an isomorphism (in Greek isos = equal and morphe = shape) is a kind of interesting mapping between objects. ...
Sometimes also name subgraph matching is used for the same problem. This name puts emphasis on finding such a subgraph and is not a bare decision problem.
Besides its importance for solving a variety of practical problems, the graph isomorphismproblem is a curiosity in complexity theory for defying the typical classifications that apply to other interesting practical problems.
The complement of the graph isomorphismproblem, sometimes called the graph nonisomorphism problem, is in co-NP, and was one of the first problems shown to be solvable by interactive proof systems, as well as one of the first problems for which a zero-knowledge proof was exhibited.
The class GI Because the graph isomorphismproblem is neither complete for any known classical class nor efficiently solvable, researchers sought to gain insight into the problem by defining a new class GI, the set of problems with a polynomial-time Turing reduction to the graph isomorphismproblem.
The formal description of the decision problem is as follows.
Subgraphisomorphism is a generalization of the potentially easier graph isomorphismproblem; if this problem is NP-complete, the polynomial hierarchy collapses, so it is suspected not to be.
Feeds |
Contact