Enumerate and Expand: Improved Algorithms for Connected Vertex Cover and Tree Cover

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 ^*(6 ^k ) to O ^*(2.7606 ^k ) without large hidden factors. For Tree Cover, we show a complexity of O ^*(3.2361 ^k ), 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. Supported by the DFG under grant RO 927/6-1 (TAPI).