Fertin, Guillaume ;
Fradin, Julien ;
Komusiewicz, Christian
On the Maximum Colorful Arborescence Problem and Color Hierarchy Graph Structure
Abstract
Let G=(V,A) be a vertexcolored arcweighted directed acyclic graph (DAG) rooted in some vertex r. The color hierarchy graph H(G) of G is defined as follows: the vertex set of H(G) is the color set C of G, and H(G) has an arc from c to c' if G has an arc from a vertex of color c to a vertex of color c'. We study the Maximum Colorful Arborescence (MCA) problem, which takes as input a DAG G such that H(G) is also a DAG, and aims at finding in G a maximumweight arborescence rooted in r in which no color appears more than once. The MCA problem models the de novo inference of unknown metabolites by mass spectrometry experiments. Although the problem has been introduced ten years ago (under a different name), it was only recently pointed out that a crucial additional property in the problem definition was missing: by essence, H(G) must be a DAG. In this paper, we further investigate MCA under this new light and provide new algorithmic results for this problem, with a focus on fixedparameter tractability (FPT) issues for different structural parameters of H(G). In particular, we develop an O^*(3^{{x_H}})time algorithm for solving MCA, where {x_{H}} is the number of vertices of indegree at least two in H(G), thereby improving the O^*(3^{C})time algorithm of Böcker et al. [Proc. ECCB '08]. We also prove that MCA is W[2]hard with respect to the treewidth t_H of the underlying undirected graph of H(G), and further show that it is FPT with respect to t_H + l_{C}, where l_{C} := V  C.
BibTeX  Entry
@InProceedings{fertin_et_al:LIPIcs:2018:8693,
author = {Guillaume Fertin and Julien Fradin and Christian Komusiewicz},
title = {{On the Maximum Colorful Arborescence Problem and Color Hierarchy Graph Structure}},
booktitle = {Annual Symposium on Combinatorial Pattern Matching (CPM 2018)},
pages = {17:117:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770743},
ISSN = {18688969},
year = {2018},
volume = {105},
editor = {Gonzalo Navarro and David Sankoff and Binhai Zhu},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2018/8693},
URN = {urn:nbn:de:0030drops86939},
doi = {10.4230/LIPIcs.CPM.2018.17},
annote = {Keywords: Subgraph problem, computational complexity, algorithms, fixedparameter tractability, kernelization}
}
18.05.2018
Keywords: 

Subgraph problem, computational complexity, algorithms, fixedparameter tractability, kernelization 
Seminar: 

Annual Symposium on Combinatorial Pattern Matching (CPM 2018)

Issue date: 

2018 
Date of publication: 

18.05.2018 