Exact and approximate algorithms for the longest induced path problem
Ruslán G. Marzo, Celso Carneiro Ribeiro · RAIRO - Operations Research · 2021
The longest induced path problem consists in finding a maximum subset of vertices of a graph such that it induces a simple path. We propose a new exact enumerative algorithm that solves problems with up to 138 vertices and 493 edges and a heuristic for larger problems. Detailed computational experiments compare the results obtained by the new algorithms with other approaches in the literature and investigate the characteristics of the optimal solutions.