Consider undirected unweighted graph. My problem is to find the longest simple path between two given vertices or its approximation.
I was thinking of solution like this - Find the shortest simple path using Dijkstra's algorithm. For every 2 vertices, which are neighbors on that path, simulate that edge between them is missing and try to find another path between them using Dijkstra's algorithm. Then apply it again on newly created path until we are not able to increase size of the path.
I think that this would work but it has very high time complexity.
Can anyone help me with better algorithm or does anyone know any approximation to this problem ?