{'fraction_non_alphanumeric': 0.028712871287128714, 'fraction_numerical': 0.0034653465346534654, 'mean_word_length': 5.087349397590361, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Semester Thesis “Distributed Dominating Set Approximations in Various Graph Families”

In graph theory, finding small dominating sets, i.e., small subsets of the nodes whose neighborhoods cover the whole graph, is a wellknown and fundamental problem. Solving this task efficiently is also of great interest in distributed systems; for instance, this is helpful when generating a communication backbone in wireless systems. It is known that in general it is NP-hard to find dominating sets of minimum size or even a dominating set that is at most a constant factor larger than the optimum. In distributed systems, one usually concentrates on the aspect of the amount of communication that is necessary to obtain a certain result rather than the computational complexity. But also here strong negative results are known: No distributed algorithm can find a polylogarithmic approximation to a minimum dominating set (MDS) without collecting topology information up to distance Ω( √ log n/ log log n) [2]. This motivates the study of restricted graph classes, where algorithms may exploit the additional structure to obtain better results. Forests and graphs of bounded degree permit trivial constant-factor approximations in constant time, and recently two algorithms for planar graphs were proposed [1, 3]. But already in graphs of bounded growth1, constant-factor approximations require knowledge up to distance Θ(log∗ n) [4, 5].2 Your contribution to this topic will be twofold. First, you are going to give an overview of the current knowledge on distributed MDS approximation algorithms, “drawing a map” of the connections between the known bounds and their implication for other families of graphs. Starting from this, you will point at interesting regions of this map to explore, i.e., graph classes that are general enough to be of interest, yet special enough to potentially permit to obtain strong approximations quickly. Ideally, your studies will lead to new algorithms or lower bounds for these graph families.