Search

The input of the Maximum Colored Cut problem consists of a graph G = (V , E) with an edge-coloring c : E → { 1 , 2 , 3 , ... , p } and a positive integer k , and the question is whether G has a nontrivial edge cut using at least k colors. The Colorful Cut problem has the same input but asks for a nontrivial edge cut using all p colors. Unlike what happens for the classical Maximum Cut problem, we prove that both problems are NP -complete even on complete, planar, or bounded treewidth graphs. Furthermore, we prove that Colorful Cut is NP -complete even when each color class induces a clique of size at most three, but is trivially solvable when each color induces an edge. On the positive side, we prove that Maximum Colored Cut is fixed-parameter tractable when parameterized by either k or p , by constructing a cubic kernel in both cases. [ABSTRACT FROM AUTHOR]

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. (2016) that the MinCCA problem when parameterized by the treewidth and the maximum degree of the input graph is in FPT . In this article we present the following hardness results for MinCCA : • the problem is W [1]-hard when parameterized by the vertex cover number of the input graph, even on graphs of degeneracy at most 3. In particular, it is W [1]-hard parameterized by the treewidth of the input graph, which answers the main open problem in the work of Gözüpek et al. (2016); • it is W [1]-hard on multigraphs parameterized by the tree-cutwidth of the input multigraph; and • 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. [ABSTRACT FROM AUTHOR]