Parameterized complexity of the MINCCA problem on graphs of bounded decomposability

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 () 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. (2016) that the problem when parameterized by the treewidth and the maximum degree of the input graph is in . In this article we present the following hardness results for :