Thesis Topic Details

Topic ID:
3400
Title:
Lower bounds for extremal vertex sets in graphs
Supervisor:
Serge Gaspers
Research Area:
Algorithms, Theory, Discrete Mathematics
Associated Staff
Assessor:
Toby Walsh
Topic Details
Status:
Active
Type:
Research
Programs:
CS CE BIOM BINF SE
Group Suitable:
No
Industrial:
No
Pre-requisites:
--
Description:
A dominating set in a graph is a subset of vertices such that every vertex outside the set has a neighbor in the set. A dominating set is minimal (by inclusion) if it does not contain another dominating set as a subset. It is known that the number of minimal dominating sets in a graph on n vertices is at most 1.7697^n. On the other hand, there exist infinitely many graphs with 15^(n/6) > 1.5704^n minimal dominating sets. The family of graphs providing this lower bound is a disjoint union of n/6 octahedrons, the octahedron being a small graph on 6 vertices with 15 minimal dominating sets.

The aim of this thesis is to find lower bounds for the number of various extremal vertex sets in graphs, such as minimal dominating sets, minimal separators, minimal feedback vertex sets, etc. One plausible approach is to systematically enumerate and analyze all small graphs with the help of a computer, as building blocks for the graphs providing the lower bounds. In some cases, e.g., minimal dominating sets, it is trivial to assemble these building blocks. In other cases, e.g., minimal separators, more ingenious methods are needed for their assembly.

Bounds of this kind are motivated by the analysis of algorithmic running times. For instance, the bound on minimal dominating sets arises in the analysis of algorithms for computing the domatic number, which has applications in facility-location problems in networks.

The thesis requires very good programming skills, with a focus on code profiling and optimization, and working with succinct representations of graphs, in order to be able to analyze a maximum number of building blocks.
Comments:
--
Past Student Reports
 
No Reports Available. Contact the supervisor for more information.

Check out all available reports in the CSE Thesis Report Library.

NOTE: only current CSE students can login to view and select reports to download.