Trails in arc-colored digraphs avoiding forbidden transitions

Let H be a digraph possibly with loops.Let D be a digraph without loops.An H-coloring of D is a function c : A(D) → V (H).We say that D is an H-colored digraph whenever we are taking a fixed H-coloring of D. A trail W = (v0, e0, v1, e1, v2, . . ., vn-1, en-1, vn) in D is an H-trail if and only if (c(ei), c(ei+1)) is an arc in H for every i ∈ {0, . . ., n-2}.Whenever the vertices of an H-trail are pairwise different, we say that it is an H-path.In this paper, we study the problem of finding s -t H-trail in H-colored digraphs.First, we prove that finding an H-trail starting with the arc e and ending at arc f can be done in polynomial time.As a consequence, we give a polynomial time algorithm to find the shortest H-trail from a vertex s to a vertex t (if it exists).Moreover, we obtain a Menger-type theorem for H-trails.As a consequence, we show that the problem of maximizing the number of arc disjoint s -t H-trails in D can be solved in polynomial time.Although finding an H-path between two given vertices is an NP-problem, it becomes a polynomial time problem in the case when H is a reflexive and transitive digraph.