On paths, trails and closed trails in edge-colored graphs
Gourvès, Laurent; Lyra, Adria; Martinhon, Carlos A.; Monnot, Jérôme (2012), On paths, trails and closed trails in edge-colored graphs, Discrete Mathematics and Theoretical Computer Science, 14, 2, p. 57-74
TypeArticle accepté pour publication ou publié
External document linkhttps://hal.inria.fr/hal-00990589
Journal nameDiscrete Mathematics and Theoretical Computer Science
Discrete Mathematics and Theoretical Computer Science (DMTCS)
MetadataShow full item record
Abstract (EN)In this paper we deal from an algorithmic perspective with different questions regarding properly edge-colored (or PEC) paths, trails and closed trails. Given a c-edge-colored graph Gc, we show how to polynomially determine, if any, a PEC closed trail subgraph whose number of visits at each vertex is specified before hand. As a consequence, we solve a number of interesting related problems. For instance, given subset S of vertices in Gc, we show how to maximize in polynomial time the number of S-restricted vertex (resp., edge) disjoint pec paths (resp., trails) in Gc with endpoints in S. Further, if Gc contains no pec closed trails, we show that the problem of finding a pec s-t trail visiting a given subset of vertices can be solved in polynomial time and prove that it becomes NP-complete if we are restricted to graphs with no pec cycles. We also deal with graphs Gc containing no (almost) pec cycles or closed trails through s or t. We prove that finding 2 pec s-t paths (resp., trails) with length at most L > 0 is NP-complete in the strong sense even for graphs with maximum degree equal to 3 and present an approximation algorithm for computing k vertex (resp., edge) disjoint pec s-t paths (resp., trails) so that the maximum path (resp., trail) length is no more than k times the pec path (resp., trail) length in an optimal solution. Further, we prove that finding 2 vertex disjoint s-t paths with exactly one pec s-t path is NPcomplete. This result is interesting since as proved in , the determination of two or more vertex disjoint pec s-t paths can be done in polynomial time. Finally, if Gc is an arbitrary c-edge-colored graph with maximum vertex degree equal to four, we prove that finding two monochromatic vertex disjoint s-t paths with different colors is NP-complete. We also propose some related problems.
Subjects / KeywordsEdge-colored graphs; properly edge-colored closed trails and cycles; properly edge-colored paths and trails; monochromatic paths
Showing items related by title and author.
Luerbio, Faria; Gourvès, Laurent; Martinhon, Carlos A.; Monnot, Jérôme (2015) Article accepté pour publication ou publié