## Improved Combinatorial Bounds and Enumerators for the Connected Vertex Cover and Independent Feedback Vertex Set Problems

##### Type

Master thesis###### Not peer reviewed

##### View/Open

##### Date

2018-06-20##### Author

##### Metadata

Show full item record##### 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.

##### Publisher

The University of Bergen##### Subject

independent feedback vertex setenumeration algorithmscombinatorial boundsconnected vertex cover##### Collections

Copyright the Author. All rights reserved