Given a graph G, find the largest bipartite subgraph of G that contains a Hamiltonian path.

where a bipartite graph has its vertices split into two sets with edges only between sets, and a Hamiltonian path visits every vertex exactly once without vising an vertex twice or more.