  The notion of forbidden-transition graphs allows for a robust generalization
of walks in graphs. In a forbidden-transition graph, every pair of edges
incident to a common vertex is permitted or forbidden; a walk is compatible if
all pairs of consecutive edges on the walk are permitted. Forbidden-transition
graphs and related models have found applications in a variety of fields, such
as routing in optical telecommunication networks, road networks, and
bio-informatics.
  We initiate the study of fundamental connectivity problems from the point of
view of parameterized complexity, including an in-depth study of tractability
with regards to various graph-width parameters. Among several results, we prove
that finding a simple compatible path between given endpoints in a
forbidden-transition graph is W[1]-hard when parameterized by the
vertex-deletion distance to a linear forest (so it is also hard when
parameterized by pathwidth or treewidth). On the other hand, we show an
algebraic trick that yields tractability when parameterized by treewidth of
finding a properly colored Hamiltonian cycle in an edge-colored graph; properly
colored walks in edge-colored graphs is one of the most studied special cases
of compatible walks in forbidden-transition graphs.
