Thumbnail - No thumbnail

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

Type
Communication / Conférence
External document link
https://arxiv.org/abs/1609.04951v1
Date
2016
Conference title
10th International Conference on Combinatorial Optimization and Applications ( COCOA 2016)
Conference date
2016-12
Conference city
Hong Kong
Conference country
China
Book title
Combinatorial Optimization and Applications: 10th International Conference, COCOA 2016
Book author
Chan, T-H. Hubert; Li, Minming; Wang, Lusheng
Publisher
Springer International Publishing
Published in
Cham
ISBN
978-3-319-48748-9
Number of pages
793
Pages
113-127
Publication identifier
Metadata
Show full item record
Author(s)
Dondi, Riccardo
Dipartimento di Scienze dei Linguaggi, della Comunicazione e degli Studi Culturali
Sikora, Florian cc
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 / Keywords
FPT; graph theory; computational complexity