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

dc.contributor.author | Wingsternes, Thomas | |

dc.date.accessioned | 2018-08-16T16:04:20Z | |

dc.date.available | 2018-08-16T16:04:20Z | |

dc.date.issued | 2018-06-20 | |

dc.date.submitted | 2018-06-19T22:00:06Z | |

dc.identifier.uri | https://hdl.handle.net/1956/18135 | |

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 |

dc.language.iso | eng | eng |

dc.publisher | The University of Bergen | en_US |

dc.subject | independent feedback vertex set | eng |

dc.subject | enumeration algorithms | eng |

dc.subject | combinatorial bounds | eng |

dc.subject | connected vertex cover | eng |

dc.title | Improved Combinatorial Bounds and Enumerators for the Connected Vertex Cover and Independent Feedback Vertex Set Problems | en_US |

dc.type | Master thesis | |

dc.date.updated | 2018-06-19T22:00:06Z | |

dc.rights.holder | Copyright the Author. All rights reserved | en_US |

dc.description.degree | Masteroppgave i informatikk | en_US |

dc.description.localcode | INF399 | |

dc.subject.nus | 754199 | eng |

fs.subjectcode | INF399 | |

fs.unitcode | 12-12-0 |