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. == Problem statement == Formally, the problem takes as input two graphs G1=(V1, E1) and G2=(V2, E2), where the number of vertices in V1 can be assumed to be less than or equal to the number of vertices in V2.

This neuron ends here.