Induced Path

Input

Graph $G = (V, E)$, positive integer $K \leq |V|$.

Question

Is there a subset $V' \subseteq V$ with $|V'| \geq K$ such that the subgraph induced by $V'$ is a simple path on $|V'|$ vertices?

Classes

• NP-complete

Comments

Note that this is not a hereditary property, so the result is not implied by either of the previous two results. Remains NP-complete if $G$ is bipartite. The same result holds for the variant in which simple path is replaced by simple cycle. The problems of finding the longest simple path or longest simple cycle (not necessarily induced) are also NP-complete.

Proofs

NP-complete

Transformation from 3-Satisfiability.

Reducible from

• 3-Satisfiability