| dc.description.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. | en_US |
