The problem of finding the maximum number of vertexdisjoint 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 unicolor 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.
(2016). Finding disjoint paths on edge-colored graphs: A multivariate complexity analysis . Retrieved from http://hdl.handle.net/10446/78438
Finding disjoint paths on edge-colored graphs: A multivariate complexity analysis
Dondi, Riccardo;
2016-01-01
Abstract
The problem of finding the maximum number of vertexdisjoint 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 unicolor 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.File | Dimensione del file | Formato | |
---|---|---|---|
Cocoa2016Draft.pdf
accesso aperto
Versione:
postprint - versione referata/accettata senza referaggio
Licenza:
Licenza default Aisberg
Dimensione del file
260.81 kB
Formato
Adobe PDF
|
260.81 kB | Adobe PDF | Visualizza/Apri |
chp_10.1007_978-3-319-48749-6_9(1).pdf
Solo gestori di archivio
Versione:
publisher's version - versione editoriale
Licenza:
Licenza default Aisberg
Dimensione del file
248.6 kB
Formato
Adobe PDF
|
248.6 kB | Adobe PDF | Visualizza/Apri |
Pubblicazioni consigliate
Aisberg ©2008 Servizi bibliotecari, Università degli studi di Bergamo | Terms of use/Condizioni di utilizzo