The problem is testing whether a graph G contains a Hamiltonian path or not with the one use of hamiltonian cycle Hcycle(V,E) function which gives output true of false whether the G contains Hamiltonian cycle.
I must write a program with polynomial time complexity, which has to decide whether the unoriented graph G contains at least one Hamiltonian path with the use of one Hamiltonian Cycle function which has to give output to this problem.
Also I need to write a program with the opposite problem. (use of Hpath function to find out whether the graph contains Hemiltonian Cycle).
I can't find a solution to this problem. I can use both Hcycle and Hpath only once.
We assume that the function Hcycle and Hpath run in linear time complexity.
Path by Hcycle(V,E): Call Hcycle() on a graph created by adding one vertex that is connected to all other vertices. If new graph has a cycle than removing new node from that cycle we get path on original graph.
Cycle by Hpath(V,E): Call Hpath() on a graph created by adding one vertex and connecting it to same neighbours as one existing vertex. That means these 2 vertices will have same naighbours. If new graph has a path than at least one path end is on these two vertices. If other vertex is not end, than it is on path third position and by reordering path we can set both vertices to be path end points. Merging these two vertices (since they have same neighbours) we get a cycle in original graph.
Path by Hcycle(V,E): If graph has cycle than it has path also. If graph doesn't have cycle than for each unconnected pair of vertices (v1, v2) add edge between them and check is there a cycle with Hcycle(V,E+(v1,v2)). If there is a cycle than there is a path between v1 and v2 in original graph. Hcycle is called max |V|^2 times.
Cycle by Hpath(V,E): Idea is to force a path to has end vertices we know about. That can be done by constructing graph where two vertices have degree one. Let N(v) be neighbours of v. For an edge (v1,v2) and n1 from N(v1)-v2 and n2 from N(v2)-v1 construct a graph by removing all edges from v1 except to n1, and removing all edges from v2 except to n2. If that graph has a path, than it's ends are on v1 and v2, and our original graph has a circle. Hpath is called max |E|*|V|^2 times.