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 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. G1 is isomorphic to an induced subgraph of G2 if there is an injective function f which maps the vertices of G1 to vertices of G2 such that for all pairs of vertices x, y in V1, edge (x, y) is in E1 if and only if the edge (f(x), f(y)) is in E2. The answer to the decision problem is yes if this function f exists, and no otherwise.
This is different from the subgraph isomorphism problem in that the absence of an edge in G1 implies that the corresponding edge in G2 must also be absent. In subgraph isomorphism, these "extra" edges in G2 may be present.
The complexity of induced subgraph isomorphism separates outerplanar graphs from their generalization series-parallel graphs: it may be solved in polynomial time for 2-connected outerplanar graphs, but is NP-complete for 2-connected series-parallel graphs.
The special case of finding a long path as an induced subgraph of a hypercube has been particularly well-studied, and is called the snake-in-the-box problem. The maximum independent set problem is also an induced subgraph isomorphism problem in which one seeks to find a large independent set as an induced subgraph of a larger graph, and the maximum clique problem is an induced subgraph isomorphism problem in which one seeks to find a large clique graph as an induced subgraph of a larger graph.
Famous quotes containing the words induced and/or problem:
“The classicist, and the naturalist who has much in common with him, refuse to see in the highest works of art anything but the exercise of judgement, sensibility, and skill. The romanticist cannot be satisfied with such a normal standard; for him art is essentially irrational—an experience beyond normality, sometimes destructive of normality, and at the very least evocative of that state of wonder which is the state of mind induced by the immediately inexplicable.”
—Sir Herbert Read (1893–1968)
“The problem is simply this: no one can feel like CEO of his or her life in the presence of the people who toilet trained her and spanked him when he was naughty. We may have become Masters of the Universe, accustomed to giving life and taking it away, casually ordering people into battle or out of their jobs . . . and yet we may still dirty our diapers at the sound of our mommy’s whimper or our daddy’s growl.”
—Frank Pittman (20th century)