Multi-Path Algorithms for minimum-colour path problems with applications to approximating barrier resilience

Let G   be a graph with zero or more colours assigned to its vertices, and let vsvs and vtvt be two vertices of G. The minimum-colour path problem   is to determine the minimum over all vs–vtvs–vt paths of the number of colours used, where a colour is considered used if it is assigned to any vertex in the path. Although this problem is NP-hard with strong hardness of approximation results, many problems can be formulated as instances of the minimum-colour path problem with additional constraints which may be exploited to allow polynomial-time solutions or close approximations. We introduce a family of approximation algorithms, referred to as the Multi-Path Algorithms, for minimum-colour path problems, and go on to show examples of constraints which would allow polynomial-time solutions or constant factor approximations.In particular, we describe applications to variants of the barrier resilience problem: given a pair of points s and t   and an arrangement AA of n   regions in the plane, the problem is to determine the minimum over all s–ts–t paths of the number of regions intersected. We show how to reduce the barrier resilience problem to the minimum-colour path problem, and go on to show that the Multi-Path Algorithms guarantee a 1.5 approximation when regions are unit disks and s,ts,t are separated by at least 23.