The Maximum Colorful Arborescence problem: How (computationally) hard can it be?

Abstract Given a vertex-colored arc-weighted directed acyclic graph G, the Maximum Colorful Subtree problem (or MCS ) aims at finding an arborescence of maximum weight in G, in which no color appears more than once. The problem was originally introduced in [1] in the context of de novo identification of metabolites by tandem mass spectrometry. However, a thorough analysis of the initial motivation shows that the formal definition of MCS should be amended, since the input graph G actually possesses extra properties, which have been unexploited so far. This leads us to describe in this paper a more precise model that we call Maximum Colorful Arborescence ( MCA ), which we extensively study in terms of algorithmic complexity. In particular, we show that exploiting the implied Color Hierarchy Graph of the input graph G can lead to exact polynomial algorithms and approximation algorithms. We also develop Fixed-Parameter Tractable ( FPT ) algorithms for the problem parameterized by the “dual parameter” l C , defined as the minimum number of vertices of G which are not kept in the solution.