Complexity of trails, paths and circuits in arc-colored digraphs
Gourvès, Laurent; Lyra, Adria; Martinhon, Carlos A.; Monnot, Jérôme (2013), Complexity of trails, paths and circuits in arc-colored digraphs, Discrete Applied Mathematics, 161, 6, p. 819-828. 10.1016/j.dam.2012.10.025
Type
Article accepté pour publication ou publiéDate
2013Journal name
Discrete Applied MathematicsVolume
161Number
6Publisher
Elsevier
Pages
819-828
Publication identifier
Metadata
Show full item recordAuthor(s)
Gourvès, LaurentLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Lyra, Adria
Universidade Federal Rural do Rio de Janeiro [UFRRJ]
Martinhon, Carlos A.
Monnot, Jérôme

Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
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.Subjects / Keywords
Properly arc-colored paths/trails and circuits; Arc-colored digraphs; Hamiltonian directed path; Arc-colored tournaments; Polynomial algorithms; NP-completenessRelated items
Showing items related by title and author.
-
Gourvès, Laurent; Lyra, Adria; Martinhon, Carlos A.; Monnot, Jérôme (2010) Communication / Conférence
-
Gourvès, Laurent; Lyra, Adria; Martinhon, Carlos A.; Monnot, Jérôme (2012) Article accepté pour publication ou publié
-
Gourvès, Laurent; Martinhon, Carlos A.; Monnot, Jérôme; Adria, Lyra; Protti, Fabio (2009) Article accepté pour publication ou publié
-
Gourvès, Laurent; Lyra, Adria; Martinhon, Carlos A.; Monnot, Jérôme (2010) Article accepté pour publication ou publié
-
Gourvès, Laurent; Lyra, Adria; Martinhon, Carlos A.; Monnot, Jérôme (2009) Communication / Conférence