
Finding disjoint paths on edge-colored graphs: more tractability results
Dondi, Riccardo; Sikora, Florian (2018), Finding disjoint paths on edge-colored graphs: more tractability results, Journal of Combinatorial Optimization, 36, 4, p. 1315-1332. 10.1007/s10878-017-0238-6
View/ Open
Type
Article accepté pour publication ou publiéDate
2018Journal name
Journal of Combinatorial OptimizationVolume
36Number
4Publisher
Springer
Pages
1315-1332
Publication identifier
Metadata
Show full item recordAuthor(s)
Dondi, RiccardoSikora, Florian

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-disjointuni-color paths in anedge-colored graph (called MaxCDP) has been recently introduced in literature, motivatedby applications in social network analysis. In this paper we investigate how the complexity ofthe problem depends on graph parameters (namely the number of vertices to remove to makethe graph a collection of disjoint paths and the size of the vertex cover of the graph), which makes sense since graphs in social networks are not random and have structure. The problemwas known to be hard to approximate in polynomial time and not fixed-parameter tractable (FPT) for the natural parameter. Here, we show that it is still hard to approximate, evenin FPT-time. Finally, we introduce a new variant of the problem, called MaxCDDP, whosegoal 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, MaxCDDPis already hard on graphs at distance two from disjoint paths.Subjects / Keywords
Parameterized complexity; Approximation; Social networks; Edge-colored graphsRelated items
Showing items related by title and author.
-
Dondi, Riccardo; Sikora, Florian (2016) Communication / Conférence
-
Benkouar, A.; Manoussakis, Yannis; Paschos, Vangelis; Saad, Rachid (1996) Article accepté pour publication ou publié
-
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é
-
Sikora, Florian; Dondi, Riccardo (2021) Communication / Conférence