# How to navigate a robot through obstacles?

We consider the following motion-planning problem: Given a set of obstacles in the plane, can we navigate a robot between two designated points without crossing 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 problem is known to be NP-hard, even when each obstacle is either a square or a straight-line segment. It 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 \in V(G)$, and $k \in \mathbb{N}$, is there an $s$-$t$ path in $G$ that uses at most $k$ colors? If each obstacle is connected, the resulting graph from this formulation satisfies the property that each color induces a connected subgraph.

In this work, we study the complexity and design algorithms for this motion-planning problem. We first show that the problem is W[SAT]-hard parameterized by $k$, and is W[1]-complete on graphs of pathwidth 4 parameterized by both $k$ and the length of the path. We then focus on the case where each color is connected. We first show that this problem is \NP-hard, even when restricted to 2-outerplanar graphs of pathwidth 3. We then exploit the planarity of the graph and the connectivity of the colors to prove the following graph-theoretic structural result. For any vertex $v$ in the graph, there exists a set of paths whose cardinality is upper bounded by some function of $k$, that ``represents'' the valid $s$-$t$ paths containing subsets of colors from $v$. We then employ this structural result to design an FPT algorithm for the problem parameterized by both $k$ and the treewidth of the graph.