In *Proc. of Theory and Applications of Models of Computation (TAMC 2017)*, volume 10185, of *Lect Notes Comput Sci*, pages 216–230, 2017.

doi abstract bibtex

doi abstract bibtex

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 [2] 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 needs to be amended, since the input graph G actually possesses two extra properties, which are so far unexploited. This leads us to introduce in this paper a more precise model that we call Maximum Colorful Arborescence (MCA), and extensively study it in terms of algorithmic complexity. In particular, we show that exploiting the implied color hierarchy of the input graph can lead to polynomial algorithms. We also develop Fixed-Parameter Tractable (FPT) algorithms for the problem, notably using the "dual parameter" $\ell$, defined as the number of vertices of G which are not kept in the solution.

@InProceedings{fertin17algorithmic, author = {Guillaume Fertin and Julien Fradin and G\'{e}raldine Jean}, title = {Algorithmic Aspects of the Maximum Colorful Arborescence Problem}, booktitle = {Proc. of Theory and Applications of Models of Computation (TAMC 2017)}, year = {2017}, volume = {10185}, series = lncs, pages = {216--230}, 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 [2] 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 needs to be amended, since the input graph G actually possesses two extra properties, which are so far unexploited. This leads us to introduce in this paper a more precise model that we call Maximum Colorful Arborescence (MCA), and extensively study it in terms of algorithmic complexity. In particular, we show that exploiting the implied color hierarchy of the input graph can lead to polynomial algorithms. We also develop Fixed-Parameter Tractable (FPT) algorithms for the problem, notably using the "dual parameter" $\ell$, defined as the number of vertices of G which are not kept in the solution.}, doi = {10.1007/978-3-319-55911-7_16}, owner = {Sebastian}, timestamp = {2017.12.15}, }

Downloads: 0