Finding Disjoint Paths on Edge-Colored Graphs: A Multivariate Complexity Analysis
Dondi, Riccardo; Sikora, Florian (2016), Finding Disjoint Paths on Edge-Colored Graphs: A Multivariate Complexity Analysis, in Chan, T-H. Hubert; Li, Minming; Wang, Lusheng, Combinatorial Optimization and Applications: 10th International Conference, COCOA 2016, Springer International Publishing : Cham, p. 113-127. 10.1007/978-3-319-48749-6_9
TypeCommunication / Conférence
External document linkhttps://arxiv.org/abs/1609.04951v1
Conference title10th International Conference on Combinatorial Optimization and Applications ( COCOA 2016)
Conference cityHong Kong
Book titleCombinatorial Optimization and Applications: 10th International Conference, COCOA 2016
Book authorChan, T-H. Hubert; Li, Minming; Wang, Lusheng
Number of pages793
MetadataShow full item record
Dipartimento di Scienze dei Linguaggi, della Comunicazione e degli Studi Culturali
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Abstract (EN)The problem of finding the maximum number of vertex-disjoint uni-color paths in an edge-colored graph (MaxCDP) has been recently introduced in literature, motivated by applications in social network analysis. In this paper we investigate how the complexity of the problem depends on graph parameters (distance from disjoint paths and size of vertex cover), and that is not FPT-approximable. Moreover, we introduce a new variant of the problem, called MaxCDDP, whose goal is to find the maximum number of vertex-disjoint and color-disjoint uni-color paths. We extend some of the results of MaxCDP to this new variant, and we prove that unlike MaxCDP, MaxCDDP is already hard on graphs at distance two from disjoint paths.
Subjects / KeywordsFPT; graph theory; computational complexity
Showing items related by title and author.
Hamiltonian problems in edge-colored complete graphs and Eulerian cycles in edge-colored graphs: some complexity results Benkouar, A.; Manoussakis, Yannis; Paschos, Vangelis; Saad, Rachid (1996) Article accepté pour publication ou publié