Faster enumeration of minimal connected dominating sets in split graphs

Abstract

Graphs are mathematical objects that can be used to model many real world problems. An example is a roadmap, where the nodes in the graph represent cities and the edges of the graph represent roads. An interesting and important task is to find certain objects or node subsets with a specified property in a graph. It is exactly this type of question this thesis will study, and the objects that we are looking for are minimal connected dominating sets. In many applications the best known way to find a minimum object of a certain type can be to list all the minimal objects and then pick the smallest one among these minimal objects. Thus, knowing the number of such objects and being able to list them in reasonable time might help us get faster algorithms for hard problems. In 2015, Golovach, Heggernes and Kratsch gave an O(1.3803^n)-time algorithm for enumerating the mcds in split graphs. This algorithm gives the best known upper bound on the number of mcds in split graphs. Golovach et al also give the best known lower bound example on the number of mcds in split graphs, which has 1.3195^n mcds, so there is an albeit small gap between the lower and the upper bound. In this thesis we implement and test the mentioned enumeration algorithm, and with these tests we find a new lower bound example with 1.3195^n mcds. On the theoretical side, we improve the running time of the enumeration algorithm to O(1.3674^n), thereby proving that the maximum number of mcds in split graphs is at most 1.3674^n. Consequently, we narrow the gap between the known upper and lower bound on the maximum number of mcds in split graphs.