1 Search Results for "Fradin, Julien"

Document
DOI: 10.4230/LIPIcs.CPM.2018.17
On the Maximum Colorful Arborescence Problem and Color Hierarchy Graph Structure

Authors: Guillaume Fertin, Julien Fradin, and Christian Komusiewicz

Published in: LIPIcs, Volume 105, 29th Annual Symposium on Combinatorial Pattern Matching (CPM 2018)

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|.
Cite as

Guillaume Fertin, Julien Fradin, and Christian Komusiewicz. On the Maximum Colorful Arborescence Problem and Color Hierarchy Graph Structure. In 29th Annual Symposium on Combinatorial Pattern Matching (CPM 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 105, pp. 17:1-17:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{fertin_et_al:LIPIcs.CPM.2018.17,
  author =	{Fertin, Guillaume and Fradin, Julien and Komusiewicz, Christian},
  title =	{{On the Maximum Colorful Arborescence Problem and Color Hierarchy Graph Structure}},
  booktitle =	{29th 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 =	{Navarro, Gonzalo and Sankoff, David and Zhu, Binhai},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2018.17},
  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}
}
  • Refine by Author
  • 1 Fertin, Guillaume
  • 1 Fradin, Julien
  • 1 Komusiewicz, Christian

  • Refine by Classification
  • 1 Theory of computation → Dynamic programming
  • 1 Theory of computation → Fixed parameter tractability

  • Refine by Keyword
  • 1 Subgraph problem
  • 1 algorithms
  • 1 computational complexity
  • 1 fixed-parameter tractability
  • 1 kernelization

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2018

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact