  Given a set of obstacles and two points, is there a path between the two
points that does not cross more than $k$ different obstacles? This is a
fundamental problem that has undergone a tremendous amount of work. It is known
to be NP-hard, even when the obstacles are very simple geometric shapes (e.g.,
unit-length line segments). The problem can be 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 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 that without the
color-connectivity property, the problem is W[SAT]-hard parameterized by $k$. A
corollary of this result is that, unless W[2] $=$ FPT, the problem cannot be
approximated in FPT time to within a factor that is a function of $k$. By
describing a generic plane embedding of the graph instances, we show that our
hardness results translate to the geometric instances of the problem.
  We then focus on graphs satisfying the color-connectivity property. By
exploiting the planarity of the graph and the connectivity of the colors, we
develop topological results to "represent" the valid $s$-$t$ paths containing
subsets of colors from any vertex $v$. We employ these results to design an FPT
algorithm for the problem parameterized by both $k$ and the treewidth of the
graph, and extend this result to obtain an FPT algorithm for the
parameterization by both $k$ and the length of the path. The latter result
directly implies previous FPT results for various obstacle shapes, such as unit
disks and fat regions.
