Parameterized Complexity of the MINCCA Problem on Graphs of Bounded Decomposability

Abstract : In an edge-colored graph, the cost incurred at a vertex on a path when two incident edges with different colors are traversed is called reload or changeover cost. The "Minimum Changeover Cost Arborescence" (MINCCA) problem consists in finding an arborescence with a given root vertex such that the total changeover cost of the internal vertices is minimized. It has been recently proved by Gözüpek et al. [TCS 2016] that the problem is FPT when parameterized by the treewidth and the maximum degree of the input graph. In this article we present the following results for the MINCCA problem: - the problem is W[1]-hard parameterized by the treedepth of the input graph, even on graphs of average degree at most 8. In particular, it is W[1]-hard parameterized by the treewidth of the input graph, which answers the main open problem of Gözüpek et al. [TCS 2016];
- it is W[1]-hard on multigraphs parameterized by the tree-cutwidth of the input multigraph;
- it is FPT parameterized by the star tree-cutwidth of the input graph, which is a slightly restricted version of tree-cutwidth. This result strictly generalizes the FPT result given in Gözüpek et al. [TCS 2016];
- it remains NP-hard on planar graphs even when restricted to instances with at most 6 colors and 0/1 symmetric costs, or when restricted to instances with at most 8 colors, maximum degree bounded by 4, and 0/1 symmetric costs.
Type de document :
Communication dans un congrès
Graph Theoretical Concepts in Computer Science - WG, 2016, Istanbul, Turkey. International Workshop on Graph-Theoretic Concepts in Computer Science, LNCS (9941), pp.195-206, 2016, WG 2016. 〈10.1007/978-3-662-53536-3_17〉
Liste complète des métadonnées

Littérature citée [20 références]  Voir  Masquer  Télécharger

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01481360
Contributeur : Christophe Paul <>
Soumis le : jeudi 2 mars 2017 - 14:57:34
Dernière modification le : jeudi 24 mai 2018 - 15:59:22
Document(s) archivé(s) le : mercredi 31 mai 2017 - 16:44:43

Fichier

MINCCA-FPT.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Didem Gözüpek, Sibel Özkan, Christophe Paul, Ignasi Sau, Mordeshai Shalom. Parameterized Complexity of the MINCCA Problem on Graphs of Bounded Decomposability. Graph Theoretical Concepts in Computer Science - WG, 2016, Istanbul, Turkey. International Workshop on Graph-Theoretic Concepts in Computer Science, LNCS (9941), pp.195-206, 2016, WG 2016. 〈10.1007/978-3-662-53536-3_17〉. 〈lirmm-01481360〉

Partager

Métriques

Consultations de la notice

61

Téléchargements de fichiers

152