## Abstract

Given a set of obstacles and two points in the plane, is there a path between the two points that does not cross more than k different obstacles? Equivalently, can we remove k obstacles so that there is an obstacle-free path between the two designated points? This is a fundamental NP-hard problem that has undergone a tremendous amount of research work. The problem can be formulated and generalized into the following graph problem: Given a planar graph G whose vertices are colored by color sets, two designated vertices s, t ∈ V(G), and k ∈ N, is there an s-t path in G that uses at most k colors? If each obstacle is connected, then the resulting graph satisfies the color-connectivity property, namely that each color induces a connected subgraph.

We study the complexity and design algorithms for the above graph problem with an eye on its geometric applications. We prove a set of hardness results, including a result showing that the color-connectivity property is crucial for any hope for fixed-parameter tractable (FPT) algorithms. We also show that our hardness results translate to the geometric instances of the problem.

We then focus on graphs satisfying the color-connectivity property. We design an FPT algorithm for this problem parameterized by both k and the treewidth of the graph and extend this result further to obtain an FPT algorithm for the parameterization by both k and the length of the path. The latter result implies and explains previous FPT results for various obstacle shapes.

We study the complexity and design algorithms for the above graph problem with an eye on its geometric applications. We prove a set of hardness results, including a result showing that the color-connectivity property is crucial for any hope for fixed-parameter tractable (FPT) algorithms. We also show that our hardness results translate to the geometric instances of the problem.

We then focus on graphs satisfying the color-connectivity property. We design an FPT algorithm for this problem parameterized by both k and the treewidth of the graph and extend this result further to obtain an FPT algorithm for the parameterization by both k and the length of the path. The latter result implies and explains previous FPT results for various obstacle shapes.

Original language | English |
---|---|

Article number | 47 |

Pages (from-to) | 1-48 |

Number of pages | 48 |

Journal | ACM Transactions on Algorithms (TALG) |

Volume | 16 |

Issue number | 4 |

DOIs | |

Publication status | Published - Jun 2020 |