Abstract
We present a new method of solving graph problems related to Vertex Cover by enumerating and expanding appropriate sets of nodes. As an application, we obtain dramatically improved runtime bounds for two variants of the Vertex Cover problem. In the case of Connected Vertex Cover, we take the upper bound from O *(6k) to O *(2.7606k) without large hidden factors. For Tree Cover, we show a complexity of O *(3.2361k), improving over the previous bound of O *((2k)k). In the process, faster algorithms for solving subclasses of the Steiner tree problem on graphs are investigated.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Balasubramanian, R., Fellows, M.R., Raman, V.: An improved fixed parameter algorithm for vertex cover. Inf. Process. Lett. 65(3), 163–168 (1998)
Chandran, L.S., Grandoni, F.: Refined memorization for vertex cover. Inf. Process. Lett. 93, 125–131 (2005)
Chen, J., Kanj, I.A., Jia, W.: Vertex cover: further observations and further improvements. J. Algorithms 41, 280–301 (2001)
Chen, J., Kanj, I.A., Xia, G.: Simplicity is beauty: improved upper bounds for vertex cover. Technical Report TR05-008, School of CTI, DePaul University (2005)
Downey, R.G., Fellows, M.R.: Parameterized Complexity. Springer, New York (1999)
Dreyfus, S.E., Wagner, R.A.: The Steiner problem in graphs. Networks 1, 195–207 (1972)
Fernau, H.: On parameterized enumeration. In: Proceedings of the 8th Annual International Computing and Combinatorics Conference (COCOON). Lecture Notes in Computer Science, vol. 2387, pp. 564–573. Springer, New York (2002)
Fernau, H., Manlove, D.F.: Vertex and edge covers with clustering properties: complexity and algorithms. Technical Report TR-2006-210, Dept. of Computing Science, University of Glasgow (April 2006)
Guo, J., Niedermeier, R., Wernicke, S.: Parameterized complexity of generalized vertex cover problems. In: Proceedings of the 9th Workshop on Algorithms and Data Structures (WADS), Waterloo, Canada. Lecture Notes in Computer Science, vol. 3608, pp. 36–48. Springer, New York (2005)
Mölle, D., Richter, S., Rossmanith, P.: Enumerate and expand: new runtime bounds for vertex cover variants. In: Proceedings of the 12th Annual International Computing and Combinatorics Conference (COCOON). Lecture Notes in Computer Science, vol. 4112. Springer, New York (2006)
Mölle, D., Richter, S., Rossmanith, P.: A faster algorithm for the Steiner tree problem. In: Proceedings of the 23rd Symposium on Theoretical Aspects of Computer Science (STACS). Lecture Notes in Computer Science, vol. 3884, pp. 561–570. Springer, New York (2006)
Niedermeier, R., Rossmanith, P.: Upper bounds for vertex cover further improved. In: Proceedings of the 16th Symposium on Theoretical Aspects of Computer Science (STACS). Lecture Notes in Computer Science, vol. 1563, pp. 561–570. Springer, New York (1999)
Niedermeier, R., Rossmanith, P.: On efficient fixed parameter algorithms for weighted vertex cover. J. Algorithms 47, 63–77 (2003)
Author information
Authors and Affiliations
Corresponding author
Additional information
Supported by the DFG under grant RO 927/6-1 (TAPI).
Rights and permissions
About this article
Cite this article
Mölle, D., Richter, S. & Rossmanith, P. Enumerate and Expand: Improved Algorithms for Connected Vertex Cover and Tree Cover. Theory Comput Syst 43, 234–253 (2008). https://doi.org/10.1007/s00224-007-9089-3
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00224-007-9089-3