Constructing minimum changeover cost arborescenses in bounded treewidth graphs

Abstract

Given an edge-colored graph, an internal vertex of a path experiences a reload cost if it lies between two consecutive edges of different colors. The value of the reload cost depends only on the colors of the traversed edges. The reload cost concept has important applications in dynamic networks, such as transportation networks and dynamic spectrum access networks. In the minimum changeover cost arborescence (MINCCA) problem, we seek a spanning tree of an edge-colored graph, in which the sum of reload costs of all internal vertices, starting from a given root, is minimized. In general, MINCCA is known to be hard to approximate within factor n(1-is an element of), for any is an element of > 0, on a graph of n vertices. We first show that MINCCA can be optimally solved in polynomial-time on cactus graphs. Our main result is an optimal polynomial-time algorithm for graphs of bounded treewidth, thus establishing the solvability of our problem on a fundamental subclass of graphs. Our results imply that MINCCA is fixed parameter tractable when parameterized by treewidth and the maximum degree of the input graph. (C) 2016 Elsevier B.V. All rights reserved.