## On paths, trails and closed trails in edge-colored graphs

dc.contributor.author | Gourvès, Laurent | |

dc.contributor.author | Lyra, Adria | |

dc.contributor.author | Martinhon, Carlos A. | |

dc.contributor.author | Monnot, Jérôme | |

dc.date.accessioned | 2013-09-12T09:51:44Z | |

dc.date.available | 2013-09-12T09:51:44Z | |

dc.date.issued | 2012 | |

dc.identifier.uri | https://basepub.dauphine.fr/handle/123456789/11639 | |

dc.language.iso | en | en |

dc.subject | Edge-colored graphs | en |

dc.subject | properly edge-colored closed trails and cycles | en |

dc.subject | properly edge-colored paths and trails | en |

dc.subject | monochromatic paths | en |

dc.subject.ddc | 003 | en |

dc.title | On paths, trails and closed trails in edge-colored graphs | en |

dc.type | Article accepté pour publication ou publié | |

dc.description.abstracten | 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 [1], 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. | en |

dc.relation.isversionofjnlname | Discrete Mathematics and Theoretical Computer Science | |

dc.relation.isversionofjnlvol | 14 | en |

dc.relation.isversionofjnlissue | 2 | en |

dc.relation.isversionofjnldate | 2012 | |

dc.relation.isversionofjnlpages | 57-74 | en |

dc.identifier.urlsite | https://hal.inria.fr/hal-00990589 | |

dc.relation.isversionofjnlpublisher | Discrete Mathematics and Theoretical Computer Science (DMTCS) | en |

dc.subject.ddclabel | Recherche opérationnelle | en |

dc.relation.forthcoming | non | en |

dc.relation.forthcomingprint | non | en |

## Files in this item

Files | Size | Format | View |
---|---|---|---|

There are no files associated with this item. |