Improved Combinatorial Bounds and Enumerators for the Connected Vertex Cover and Independent Feedback Vertex Set Problems
Abstract
In this thesis we shall study both the maximum number of minimal connected vertex covers and the maximum number of minimal independent feedback vertex sets in graphs. A subset S of the vertices of a graph G is a vertex cover if every edge in G is incident to some vertex in S. A vertex cover S in a graph G is a connected vertex cover if the subgraph of G induced by S is connected. A connected vertex cover S is a minimal connected vertex cover if no proper subset of S is also a connected vertex cover. A subset S of the vertices of a graph G is a feedback vertex set if the removal of S from G yields an acyclic graph. A feedback vertex set S in a graph G is an independent feedback vertex set if there are no edges in G which have both endpoints in S. An independent feedback vertex set S is a minimal independent feedback vertex set if no proper subset of S is also an independent feedback vertex set. Golovach et al. [1] showed that there are at most 1.8668^n minimal connected vertex covers in a graph on n vertices, and that these can be enumerated in time O(1.8668^n). Furthermore, it was shown by Agrawal et al. [2] that there are at most 1.7485^n minimal independent feedback vertex sets in a graph on n vertices. The authors of [2] also showed that this bound is algorithmic, that the set of all minimal independent feedback vertex sets in an n-vertex graph can be enumerated in time O*(1.7485n), where the O*-notation supresses polynomial factors. We present an upper bound 2 · 1.7076^n on the number of minimal connected vertex covers in a graph on n vertices. We also present new bounds on the maximum number of minimal independent feedback vertex sets in a graph. In particular, we show that for a graph on n vertices, there are at most 1.7229^n minimal independent feedback vertex sets, and that there exists an n-vertex graph which contains 1.5067^n minimal independent feedback vertex sets. We show that the upper bounds we achieve are algorithmic by presenting an algorithm which enumerates all minimal connected vertex covers in time O*(1.7076^n), and an algorithm which enumerates all minimal independent feedback vertex sets in time O*(1.7229^n), where n is the number of vertices in the input graph.