Abstract (EN)

We deal with different algorithmic questions regarding properly arc-colored s–ts–t trails, paths and circuits in arc-colored digraphs. Given an arc-colored digraph DcDc with c≥2c≥2 colors, we show that the problem of determining the maximum number of arc disjoint properly arc-colored s–ts–t trails can be solved in polynomial time. Surprisingly, we prove that the determination of a properly arc-colored s–ts–t path is NP-complete even for planar digraphs containing no properly arc-colored circuits and c=Ω(n)c=Ω(n), where nn denotes the number of vertices in DcDc. If the digraph is an arc-colored tournament, we show that deciding whether it contains a properly arc-colored circuit passing through a given vertex xx (resp., properly arc-colored Hamiltonian s–ts–t path) is NP-complete for c≥2c≥2. As a consequence, we solve a weak version of an open problem posed in Gutin et al. (1998) [23], whose objective is to determine whether a 22-arc-colored tournament contains a properly arc-colored circuit.