The graph crawling problem is NP-complete, in the sense of the NP core: it is definable in existential second-order logic, and every problem of NP reduces to it by an ordered first-order reduction. This is Proposition 4 of Gauquier, Manolescu and Senellart (EDBT 2026) at unit page costs, hardness coming from Set Cover by the paper's reduction.

Five problems on set systems: a universe carrying two unary marks that separate the ground elements from the sets of a family, a binary incidence relation between them, and a third unary mark whose cardinality is the threshold $k$, in unary representation. SetCover asks for at most $k$ sets covering every element, HittingSet for at most $k$ elements meeting every set, SetPacking for at least $k$ pairwise disjoint sets, ExactCover for a subfamily covering every element exactly once, and SetSplitting for a two-coloring of the elements leaving no set monochromatic. Nothing forces an element of the universe to be an element or a set, and disjointness in a packing is required of the ground elements only; both conventions are what let a first-order interpretation build a set system inside a tagged power of its input.

All five are in NP by existential second-order definitions except Hitting Set, which reduces to Set Cover by reading incidence backwards, the same interpretation reducing Set Cover to Hitting Set. Hardness comes by first-order reductions: Set Cover from Vertex Cover, Set Packing from Independent Set, Exact Cover from 1-in-SAT, Set Splitting from NAE-SAT.