An approximation algorithm for the longest path problem in solid grid graphs

Abstract

The longest path problem is a well-known NP-hard problem which can be used to model and solve some optimization problems. There are only a few classes of graphs for which this problem can be solved polynomially. In addition, the results show that the problem is hard to approximate within any reasonable factor for general graphs. We introduce a polynomial-time -approximation algorithm for the longest path problem in solid grid graphs. Our algorithm can also approximate the longest path between any two given boundary vertices of a solid grid graph within the same approximation factor.

Keywords:

• longest path
• Hamiltonian path
• approximation algorithm
• solid grid graph

AMS Subject Classification:

• 68R10
• 05C85

Disclosure statement

No potential conflict of interest was reported by the authors.