Induced path

In the mathematical area of graph theory, an induced path in an undirected graph G is a path that is an induced subgraph of G. That is, it is a sequence of vertices in G such that each two adjacent vertices in the sequence are connected by an edge in G, and each two nonadjacent vertices in the sequence are not connected by any edge in G. An induced path is sometimes called a snake, and the problem of finding long induced paths in hypercube graphs is known as the snake-in-the-box problem.

[2] The induced path number of a graph G is the smallest number of induced paths into which the vertices of the graph may be partitioned,[3] and the closely related path cover number of G is the smallest number of induced paths that together include all vertices of G.[4] The girth of a graph is the length of its shortest cycle, but this cycle must be an induced cycle as any chord could be used to produce a shorter cycle; for similar reasons the odd girth of a graph is also the length of its shortest odd induced cycle.

The problem of finding the longest induced path or cycle in a hypercube, first posed by Kautz (1958), is known as the snake-in-the-box problem, and it has been studied extensively due to its applications in coding theory and engineering.

[7] As a consequence, determining the induced path number of a graph is NP-hard.

The complexity of approximating the longest induced path or cycle problems can be related to that of finding large independent sets in graphs, by the following reduction.