Parameterized Complexity of the MINCCA Problem on Graphs of Bounded Decomposability - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Conference Papers Year : 2016

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.
Fichier principal
Vignette du fichier
MINCCA-FPT.pdf (2.26 Mo) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

Dates and versions

lirmm-01481360 , version 1 (02-03-2017)

Identifiers

Cite

Didem Gözüpek, Sibel Özkan, Christophe Paul, Ignasi Sau, Mordeshai Shalom. Parameterized Complexity of the MINCCA Problem on Graphs of Bounded Decomposability. WG 2016 - 42nd International on Workshop on Graph-Theoretic Concepts in Computer Science, Jun 2016, Istanbul, Turkey. pp.195-206, ⟨10.1007/978-3-662-53536-3_17⟩. ⟨lirmm-01481360⟩
142 View
209 Download

Altmetric

Share

Gmail Facebook X LinkedIn More