Return to Question

While searching The information System on Graph Classes and their Inclusions, I stumbled on several graph classes for which the Hamiltonian Cycle problem is $NP$-complete while the complexity of Hamiltonian Path problems is NOT known. Some of those classes are 2-connected cubic planar graphs, circle graphs and triangular grid graphs.

Also, I found in the graph classes database a weird case of solid grid graphs where Hamiltonian cycle problem is in $P$ while Hamiltonian path problem is of unknown complexity.

Is there a graph class, listed in the above database of graph classes, where Hamiltonian Cycle and Hamiltonian Path problems have different complexity? Is there an explanation for this phenomena?

I am looking for a graph class, listed in the above database of graph classes, where one of the two problems is known to be polynomial-time solvable while the other is known to be $NP$-complete when inputs are restricted to this class of graphs.

I posted essentially a similar question on CS theory Stackexchange with no satisfactory answer.

While searching The information System on Graph Classes and their Inclusions, I stumbled on several graph classes for which the Hamiltonian Cycle problem is $NP$-complete while the complexity of Hamiltonian Path problems is NOT known. Some of those classes are 2-connected cubic planar graphs, circle graphs and triangular grid graphs.

Also, I found in the graph classes database a weird case of solid grid graphs where Hamiltonian cycle problem is in $P$ while Hamiltonian path problem is of unknown complexity.

Is there a graph class, listed in the above database of graph classes, where Hamiltonian Cycle and Hamiltonian Path problems have different complexity? Is there an explanation for this phenomena?

I am looking for a graph class, listed in the above database of graph classes, where one of the two problems is known to be polynomial-time solvable while the other is known to be $NP$-complete when inputs are restricted to this class of graphs.

I posted essentially a similar question on CS theory Stackexchange with no satisfactory answer.

While searching The information System on Graph Classes and their Inclusions, I stumbled on several graph classes for which the Hamiltonian Cycle problem is $NP$-complete while the complexity of Hamiltonian Path problems is NOT known. Some of those classes are 2-connected cubic planar graphs, circle graphs and triangular grid graphs.

Also, I found in the graph classes database a weird case of solid grid graphs where Hamiltonian cycle problem is in $P$ while Hamiltonian path problem is of unknown complexity.

Is there a graph class where Hamiltonian Cycle and Hamiltonian Path problems have different complexity? Is there an explanation for this phenomena?

I am looking for a graph class where one of the two problems is polynomial-time solvable while the other is $NP$-complete when inputs are restricted to this class of graphs.

I posted essentially a similar question on CS theory Stackexchange with no satisfactory answer.

While searching The information System on Graph Classes and their Inclusions, I stumbled on several graph classes for which the Hamiltonian Cycle problem is $NP$-complete while the complexity of Hamiltonian Path problems is NOT known. Some of those classes are 2-connected cubic planar graphs, circle graphs and triangular grid graphs.

Also, I found in the graph classes database a weird case of solid grid graphs where Hamiltonian cycle problem is in $P$ while Hamiltonian path problem is of unknown complexity.

Is there a graph class, listed in the above database of graph classes, where Hamiltonian Cycle and Hamiltonian Path problems have different complexity? Is there an explanation for this phenomena?

I am looking for a graph class, listed in the above database of graph classes, where one of the two problems is known to be polynomial-time solvable while the other is known to be $NP$-complete when inputs are restricted to this class of graphs.

I posted essentially a similar question on CS theory Stackexchange with no satisfactory answer.

While searching The information System on Graph Classes and their Inclusions, I stumbled on several graph classes for which the Hamiltonian Cycle problem is NP-complete while the complexity of Hamiltonian Path problems is NOT known. Some of those classes are 2-connected cubic planar graphs, circle graphs and triangular grid graphs.

Also, I found in the graph classes database a weird case of solid grid graphs where Hamiltonian cycle problem is in $P$ while Hamiltonian path problem is of unknown complexity.

Is there a graph class where Hamiltonian Cycle and Hamiltonian Path problems have different complexity? Is there an explanation for this phenomena?

I am looking for a graph class where one of the two problem is polynomial-time solvable while the other is $NP$-complete when inputs are restricted to this class of graphs.

I posted essentially a similar question on CS theory stackexchange with no satisfactory answer.

While searching The information System on Graph Classes and their Inclusions, I stumbled on several graph classes for which the Hamiltonian Cycle problem is $NP$-complete while the complexity of Hamiltonian Path problems is NOT known. Some of those classes are 2-connected cubic planar graphs, circle graphs and triangular grid graphs.

Also, I found in the graph classes database a weird case of solid grid graphs where Hamiltonian cycle problem is in $P$ while Hamiltonian path problem is of unknown complexity.

Is there a graph class where Hamiltonian Cycle and Hamiltonian Path problems have different complexity? Is there an explanation for this phenomena?

I am looking for a graph class where one of the two problems is polynomial-time solvable while the other is $NP$-complete when inputs are restricted to this class of graphs.

I posted essentially a similar question on CS theory Stackexchange with no satisfactory answer.