Portal de Periódicos da CAPES

Artigo Acesso aberto Produção Nacional Revisado por pares

BIBTEX RIS

Complexity of trails, paths and circuits in arc-colored digraphs

2012; Elsevier BV; Volume: 161; Issue: 6 Linguagem: Inglês

10.1016/j.dam.2012.10.025

1872-6771

Laurent Gourvès, Adria Lyra, Carlos A. Martinhon, Jérôme Monnot,

Computational Geometry and Mesh Generation

We deal with different algorithmic questions regarding properly arc-colored s–t trails, paths and circuits in arc-colored digraphs. Given an arc-colored digraph Dc with c≥2 colors, we show that the problem of determining the maximum number of arc disjoint properly arc-colored s–t trails can be solved in polynomial time. Surprisingly, we prove that the determination of a properly arc-colored s–t path is NP-complete even for planar digraphs containing no properly arc-colored circuits and c=Ω(n), where n denotes the number of vertices in Dc. 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 x (resp., properly arc-colored Hamiltonian s–t path) is NP-complete for c≥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 2-arc-colored tournament contains a properly arc-colored circuit.