The Maximum Colorful Arborescence problem: how (computationally) hard can it be? (English) Zbl 1477.68224
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 and F. Rasche, “Towards de novo identification of metabolites by analyzing tandem mass spectra”, Bioinform. 24, No. 16, 49–55 (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 should be amended, since the input graph \(G\) actually possesses extra properties, which have been unexploited so far. This leads us to describe in this paper a more precise model that we call Maximum Colorful Arborescence (MCA), which we extensively study in terms of algorithmic complexity. In particular, we show that exploiting the implied Color Hierarchy Graph of the input graph \(G\) can lead to exact polynomial algorithms and approximation algorithms. We also develop Fixed-Parameter Tractable \((\mathsf{FPT})\) algorithms for the problem parameterized by the “dual parameter” \(\ell_{\mathcal{C}}\), defined as the minimum number of vertices of \(G\) which are not kept in the solution.
MSC:
| 68R10 | Graph theory (including graph drawing) in computer science |
| 68Q17 | Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) |
| 68Q27 | Parameterized complexity, tractability and kernelization |
| 68W05 | Nonnumerical algorithms |
| 68W25 | Approximation algorithms |
Keywords:
complexity; FPT algorithms; approximation algorithms; maximum colorful arborescence; tandem mass spectrometryReferences:
| [1] | Böcker, S.; Rasche, F., Towards de novo identification of metabolites by analyzing tandem mass spectra, 7th European Conference on Computational Biology (ECCB’08). 7th European Conference on Computational Biology (ECCB’08), Bioinformatics, 24, 16, i49-i55 (2008) |
| [2] | Fernie, A. R.; Trethewey, R. N.; Krotzky, A. J.; Willmitzer, L., Metabolite profiling: from diagnostics to systems biology, Nat. Rev. Mol. Cell Biol., 5, 9, 763 (2004) |
| [3] | Last, R. L.; Jones, A. D.; Shachar-Hill, Y., Innovations: towards the plant metabolome and beyond, Nat. Rev. Mol. Cell Biol., 8, 2, 167 (2007) |
| [4] | Neumann, S.; Böcker, S., Computational mass spectrometry for metabolomics: identification of metabolites and small molecules, Anal. Bioanal. Chem., 398, 7-8, 2779-2788 (2010) |
| [5] | Li, J. W.-H.; Vederas, J. C., Drug discovery and natural products: end of an era or an endless frontier?, Science, 325, 5937, 161-165 (2009) |
| [6] | Schmidt, B. M.; Ribnicky, D. M.; Lipsky, P. E.; Raskin, I., Revisiting the ancient concept of botanical therapeutics, Nat. Chem. Biol., 3, 7, 360 (2007) |
| [7] | Oberacher, H.; Pavlic, M.; Libiseller, K.; Schubert, B.; Sulyok, M.; Schuhmacher, R.; Csaszar, E.; Köfeler, H. C., On the inter-instrument and inter-laboratory transferability of a tandem mass spectral reference library: 1. Results of an Austrian multicenter study, J. Mass Spectrom., 44, 4, 485-493 (2009) |
| [8] | Tautenhahn, R.; Cho, K.; Uritboonthai, W.; Zhu, Z.; Patti, G. J.; Siuzdak, G., An accelerated workflow for untargeted metabolomics using the METLIN database, Nat. Biotechnol., 30, 9, 826 (2012) |
| [9] | Wishart, D. S.; Knox, C.; Guo, A. C.; Eisner, R.; Young, N.; Gautam, B.; Hau, D. D.; Psychogios, N.; Dong, E.; Bouatra, S.; Mandal, R.; Sinelnikov, I.; Xia, J.; Jia, L.; Cruz, J. A.; Lim, E.; Sobsey, C. A.; Shrivastava, S.; Huang, P.; Liu, P.; Fang, L.; Peng, J.; Fradette, R.; Cheng, D.; Tzur, D.; Clements, M.; Lewis, A.; De Souza, A.; Zuniga, A.; Dawe, M.; Xiong, Y.; Clive, D.; Greiner, R.; Nazyrova, A.; Shaykhutdinov, R.; Li, L.; Vogel, H. J.; Forsythe, I., HMDB: a knowledgebase for the human metabolome, Nucleic Acids Res., 37, D603-D610 (2009) |
| [10] | Rasche, F.; Svatos, A.; Maddula, R. K.; Böttcher, C.; Böcker, S., Computing fragmentation trees from tandem mass spectrometry data, Anal. Chem., 83, 4, 1243-1251 (2011) |
| [11] | Rasche, F.; Scheubert, K.; Hufsky, F.; Zichner, T.; Kai, M.; Svatos, A.; Böcker, S., Identifying the unknowns by aligning fragmentation trees, Anal. Chem., 84, 7, 3417-3426 (2012) |
| [12] | Hufsky, F.; Dührkop, K.; Rasche, F.; Chimani, M.; Böcker, S., Fast alignment of fragmentation trees, Bioinformatics, 28, 12, 265-273 (2012) |
| [13] | Dührkop, K.; Hufsky, F.; Böcker, S., Molecular formula identification using isotope pattern analysis and calculation of fragmentation trees, Mass Spectrom., 3, Special Issue 2, S0037 (2014) |
| [14] | Böcker, S.; Dührkop, K., Fragmentation trees reloaded, J. Cheminformatics, 8, 1, 5:1-5:26 (2016) |
| [15] | Niedermeier, R., Invitation to Fixed-Parameter Algorithms (2006), Oxford University Press · Zbl 1095.68038 |
| [16] | Fertin, G.; Fradin, J.; Jean, G., Algorithmic aspects of the maximum colorful arborescence problem, (Gopal, T. V.; Jäger, G.; Steila, S., Theory and Applications of Models of Computation - 14th Annual Conference, TAMC 2017, Proceedings. Theory and Applications of Models of Computation - 14th Annual Conference, TAMC 2017, Proceedings, Lecture Notes in Computer Science, vol. 10185 (2017)), 216-230 · Zbl 1485.68181 |
| [17] | Rauf, I.; Rasche, F.; Nicolas, F.; Böcker, S., Finding maximum colorful subtrees in practice, J. Comput. Biol., 20, 4, 311-321 (2013) |
| [18] | Dondi, R.; Fertin, G.; Vialette, S., Complexity issues in vertex-colored graph pattern matching, J. Discret. Algorithms, 9, 1, 82-99 (2011) · Zbl 1222.05053 |
| [19] | 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) |
| [20] | Fertin, G.; Fradin, J.; Komusiewicz, C., On the maximum colorful arborescence problem and color hierarchy graph structure, (Navarro, G.; Sankoff, D.; Zhu, B., 29th Annual Symposium on Combinatorial Pattern Matching, CPM 2018. 29th Annual Symposium on Combinatorial Pattern Matching, CPM 2018, LIPIcs, vol. 105 (2018), Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik), 17:1-17:15 · Zbl 1506.68072 |
| [21] | 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) |
| [22] | Ausiello, G.; Crescenzi, P.; Gambosi, G.; Kann, V.; Marchetti-Spaccamela, A.; Protasi, M., Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties (1999), Springer-Verlag · Zbl 0937.68002 |
| [23] | Rizzi, R.; Sikora, F., Some results on more flexible versions of graph motif, Theory Comput. Syst., 56, 4, 612-629 (2015) · Zbl 1316.05048 |
| [24] | Zuckerman, D., Linear degree extractors and the inapproximability of Max Clique and Chromatic Number, Theory Comput., 3, 1, 103-128 (2007) · Zbl 1213.68322 |
| [25] | Fradin, J., Complex graphs in biology: problems, algorithms and evaluation (2018), University of Nantes: University of Nantes France, Ph.D. thesis |
| [26] | White, W. T.J.; Beyer, S.; Dührkop, K.; Chimani, M.; Böcker, S., Speedy colorful subtrees, (Xu, D.; Du, D.; Du, D., Computing and Combinatorics - 21st International Conference, COCOON, Proceedings. Computing and Combinatorics - 21st International Conference, COCOON, Proceedings, Lecture Notes in Computer Science, vol. 9198 (2015), Springer), 310-322 · Zbl 1467.92078 |
| [27] | Chu, Y.-J.; Liu, T.-H., On shortest arborescence of a directed graph, Sci. Sin., 14, 10, 1396-1400 (1965) · Zbl 0178.27401 |
| [28] | Edmonds, J., Optimum branchings, J. Res. Natl. Bur. Stand. B, 71, 4, 233-240 (1967) · Zbl 0155.51204 |
| [29] | Cygan, M.; Fomin, F. V.; Kowalik, L.; Lokshtanov, D.; Marx, D.; Pilipczuk, M.; Pilipczuk, M.; Saurabh, S., Parameterized Algorithms (2015), Springer · Zbl 1334.90001 |
| [30] | Impagliazzo, R.; Paturi, R.; Zane, F., Which problems have strongly exponential complexity?, J. Comput. Syst. Sci., 63, 4, 512-530 (2001) · Zbl 1006.68052 |
| [31] | Fertin, G.; Komusiewicz, C., Graph Motif problems parameterized by dual, (Grossi, R.; Lewenstein, M., 27th Annual Symposium on Combinatorial Pattern Matching, CPM 2016. 27th Annual Symposium on Combinatorial Pattern Matching, CPM 2016, LIPIcs, vol. 54 (2016), Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik), 7:1-7:12 · Zbl 1382.68106 |
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
