FPT-algorithms for minimum-bends tours

Estivill-Castro, V. (Vladimir); Heednacram, Apichat; Suraweera, Francis

doi:http://dx.doi.org/10.1142/S0218195911003615

FPT-algorithms for minimum-bends tours

Citation

Estivill-Castro V, Heednacram A, Suraweera F. FPT-algorithms for minimum-bends tours. Int J Comput Geom Appl. 2011 Apr;21(2):189-213. DOI: 10.1142/S0218195911003615

Abstract

This paper discusses the κ-BENDS TRAVELING SALESMAN PROBLEM. In this NP-complete problem, the inputs are n points in the plane and a positive integer κ, and we are asked whether we can travel in straight lines through these n points with at most κ bends. There are a number of applications where minimizing the number of bends in the tour is desirable because bends are considered very costly. We prove that this problem is fixed-parameter tractable (FPT). The proof is based on the kernelization approach. We also consider the RECTILINEAR κ-BENDS TRAVELING SALESMAN PROBLEM, which requires that the line-segments be axis-parallel.1 Note that a rectilinear tour with κ bends is a cover with κ-line segments, and therefore a cover by lines. We introduce two types of constraints derived from the distinction between line-segments and lines. We derive FPT-algorithms with different techniques and improved time complexity for these cases.