×

Algorithmic aspects of the maximum colorful arborescence problem. (English) Zbl 1485.68181

Gopal, T. V. (ed.) et al., Theory and applications of models of computation. 14th annual conference, TAMC 2017, Bern, Switzerland, April 20–22, 2017. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 10185, 216-230 (2017).
Summary: 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 [S. Böcker et al., “Towards de novo identification of metabolites by analyzing tandem mass spectra”, Bioinf. 24, No. 16, i49–i55 (2008; doi:10.1093/bioinformatics/btn270)] 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.
For the entire collection see [Zbl 1360.68012].

MSC:

68R10 Graph theory (including graph drawing) in computer science
05C22 Signed and weighted graphs
68Q25 Analysis of algorithms and problem complexity
68W05 Nonnumerical algorithms
92C40 Biochemistry, molecular biology
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] Ausiello, G., Crescenzi, P., Gambosi, G., Kann, V., Marchetti-Spaccamela, A., Protasi, M.: Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties. Springer-Verlag, Heidelberg (1999) · Zbl 0937.68002
[2] Böcker, S., Rasche, F.: Towards de novo identification of metabolites by analyzing tandem mass spectra. In: Proceedings of Seventh European Conference on Computational Biology and Bioinformatics, ECCB 2008, vol. 24, no. 16, pp. i49–i55 (2008)
[3] Böcker, S., Rasche, F., Steijger, T.: Annotating fragmentation patterns. In: Salzberg, S.L., Warnow, T. (eds.) WABI 2009. LNCS, vol. 5724, pp. 13–24. Springer, Heidelberg (2009). doi: 10.1007/978-3-642-04241-6_2 · Zbl 05624724
[4] Chu, Y.J., Liu, T.H.: On shortest arborescence of a directed graph. Sci. Sinica 14(10), 1396 (1965) · Zbl 0178.27401
[5] Cygan, M., Fomin, F.V., Kowalik, L., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Parameterized Algorithms. Springer, Cham (2015) · Zbl 1334.90001
[6] Dondi, R., Fertin, G., Vialette, S.: Complexity issues in vertex-colored graph pattern matching. J. Discrete Algorithms 9(1), 82–99 (2011) · Zbl 1222.05053
[7] Fertin, G., Komusiewicz, C.: Graph Motif problems parameterized by dual. In: Grossi, R., Lewenstein, M. (eds.) 27th Annual Symposium on Combinatorial Pattern Matching, CPM 2016. LIPIcs, vol. 54, pp. 7:1–7:12. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2016) · Zbl 1382.68106
[8] Impagliazzo, R., Paturi, R., Zane, F.: Which problems have strongly exponential complexity? J. Comput. Syst. Sci. 63(4), 512–530 (2001) · Zbl 1006.68052
[9] Lacroix, V., Fernandes, C.G., Sagot, M.: Motif search in graphs: application to metabolic networks. IEEE/ACM Trans. Comput. Biol. Bioinform. 3(4), 360–368 (2006) · Zbl 05335791
[10] Rauf, I., Rasche, F., Nicolas, F., Böcker, S.: Finding maximum colorful subtrees in practice. J. Comput. Biol. 20(4), 311–321 (2013)
[11] Scheubert, K., Hufsky, F., Rasche, F., Böcker, S.: Computing fragmentation trees from metabolite multiple mass spectrometry data. J. Comput. Biol. 18(11), 1383–1397 (2011)
[12] Scott, J., Ideker, T., Karp, R.M., Sharan, R.: Efficient algorithms for detecting signaling pathways in protein interaction networks. J. Comput. Biol. 13(2), 133–144 (2006) · Zbl 1119.92331
[13] White, W.T.J., Beyer, S., Dührkop, K., Chimani, M., Böcker, S.: Speedy colorful subtrees. In: Xu, D., Du, D., Du, D. (eds.) COCOON 2015. LNCS, vol. 9198, pp. 310–322. Springer, Cham (2015). doi: 10.1007/978-3-319-21398-9_25 · Zbl 1467.92078
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.