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~*(3.2361~k) without large hidden factors. For TREE COVER, we show exactly the same complexity, improving vastly 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.