A note on the parameterized complexity of unordered maximum tree orientation. (English) Zbl 1243.05063
Summary: In the unordered maximum tree orientation problem, a set \(P\) of paths in a tree and a parameter \(k\) is given, and we want to orient the edges in the tree such that all but at most \(k\) paths in \(P\) become directed paths. This is a more difficult variant of a well-studied problem in computational biology where the directions of paths in \(P\) are already given. We show that the parameterized complexity of the unordered version is between edge bipartization and vertex bipartization, and we give a characterization of orientable path sets in trees by forbidden substructures, which are cycles of a certain kind.
References:
| [1] | Böcker, S.; Hüffner, F.; Truss, A.; Wahlström, M., A faster fixed-parameter approach to drawing binary tanglegrams, (Chen, J.; Fomin, F. V., IWPEC 2009. IWPEC 2009, LNCS, vol. 5917 (2009), Springer: Springer Heidelberg), 38-49 · Zbl 1273.68157 |
| [2] | Chen, J.; Kanj, I. A.; Xia, G., Improved upper bounds for vertex cover, Theory. Comput. Sci., 411, 3736-3756 (2010) · Zbl 1205.05217 |
| [3] | Dorn, B.; Hüffner, F.; Krüger, D.; Niedermeier, R.; Uhlmann, J., Exploiting bounded signal flow for graph orientation based on cause-effect pairs, Algor. Mol. Biol., 6, 21 (2011) · Zbl 1325.05165 |
| [4] | Downey, R. G.; Fellows, M. R., Parameterized Complexity (1999), Springer: Springer New York · Zbl 0914.68076 |
| [5] | Elberfeld, M.; Segev, D.; Davidson, C. R.; Silverbush, D.; Sharan, R., Approximation algorithms for orienting mixed graphs, (Giancarlo, R.; Manzini, G., CPM 2011. CPM 2011, LNCS, vol. 6661 (2011), Springer: Springer Heidelberg), 416-428 · Zbl 1339.68315 |
| [6] | Guo, J.; Gramm, J.; Hüffner, F.; Niedermeier, R.; Wernicke, S., Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization, J. Comput. System. Sci., 72, 1386-1396 (2006) · Zbl 1119.68134 |
| [7] | Lokshtanov, D.; Saurabh, S.; Sikdar, S., Simpler parameterized algorithm for OCT, (Fiala, J.; Kratochvíl, J.; Miller, M., IWOCA 2009. IWOCA 2009, LNCS, vol. 5874 (2009), Springer: Springer Heidelberg), 380-384 · Zbl 1267.05268 |
| [8] | Medvedovsky, A.; Bafna, V.; Zwick, U.; Sharan, R., An algorithm for orienting graphs based on cause-effect pairs and its applications to orienting protein networks, (Crandall, K. A.; Lagergren, J., WABI 2008. WABI 2008, LNCS, vol. 5251 (2008), Springer: Springer Heidelberg), 222-232 |
| [9] | Niedermeier, R., (Invitation to Fixed-Parameter Algorithms. Invitation to Fixed-Parameter Algorithms, Oxford Lecture Series in Math. and its Appl. (2006), Oxford Univ. Press) · Zbl 1095.68038 |
| [10] | Raman, V.; Saurabh, S.; Sikdar, S., Efficient exact algorithms through enumerating maximal independent sets and other techniques, Theory Comput. Syst., 41, 563-587 (2007) · Zbl 1148.68054 |
| [11] | Reed, B.; Smith, K.; Vetta, A., Finding odd cycle transversals, Oper. Res. Lett., 32, 299-301 (2004) · Zbl 1052.05061 |
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.
