A Colored Path Problem and Its Applications

Eduard Eiben, Iyad Kanj

Research output: Contribution to journalArticlepeer-review

209 Downloads (Pure)

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.
Original languageEnglish
Article number47
Pages (from-to)1-48
Number of pages48
JournalACM Transactions on Algorithms (TALG)
Volume16
Issue number4
DOIs
Publication statusPublished - Jun 2020

Cite this