License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CPM.2018.17
URN: urn:nbn:de:0030-drops-86939
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/8693/
Go to the corresponding LIPIcs Volume Portal

Fertin, Guillaume ; Fradin, Julien ; Komusiewicz, Christian

On the Maximum Colorful Arborescence Problem and Color Hierarchy Graph Structure

pdf-format:
LIPIcs-CPM-2018-17.pdf (0.6 MB)

Abstract

Let G=(V,A) be a vertex-colored arc-weighted 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 maximum-weight 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 fixed-parameter 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:1--17:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-074-3},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{105},
  editor =	{Gonzalo Navarro and David Sankoff and Binhai Zhu},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2018/8693},
  URN =		{urn:nbn:de:0030-drops-86939},
  doi =		{10.4230/LIPIcs.CPM.2018.17},
  annote =	{Keywords: Subgraph problem, computational complexity, algorithms, fixed-parameter tractability, kernelization}
}

Keywords: Subgraph problem, computational complexity, algorithms, fixed-parameter tractability, kernelization
Collection: Annual Symposium on Combinatorial Pattern Matching (CPM 2018)
Issue Date: 2018
Date of publication: 18.05.2018

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI