# Parameterized complexity of the MINCCA problem on graphs of bounded decomposability

arXiv: https://arxiv.org/abs/1605.00532 · HTML: https://mlsanity.com/paper/1605.00532/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 2 May 2016.

## Built on by (most cited first, 1 of 1)

- [The Complexity of Optimizing Atomic Congestion](https://mlsanity.com/paper/2312.10219/) (2023)

## Abstract (arXiv)

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"oz"upek 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"oz"upek 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"oz"upek 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.