Masters Thesis Defense: Jesse Joshua Racicot-Askins

Candidate: Jesse Joshua Racicot-Askins
Thesis Title: Domination: Offline, Online, Any Time
Date & Time: April 29th, 2021 @ 1:00 – 3:00 pm

Online (Zoom)
Examining Committee:

Dr. Jaroslav Opatrny - Chair
Drs. Harutyunyan & Pankratov- Supervisors

Dr. Nadia Hardy - Examiner
Dr. Jaroslav Opatrny - Examiner

Abstract:

Given a graph G = (V,E), a subset D ⊆ V is called a dominating set if each vertex υ ∈ V either belongs to D or is adjacent to some vertex in D. The typical objective is to find a dominating set of minimum size. Depending on the context, the problem may be viewed from an algorithmic perspective or a purely mathematical one. The following thesis explores the topic of domination from these two different perspectives, where the former is split further into two settings. In particular, we study the topic as a computational problem within an offline setting where an algorithm is given an input graph in its entirety and alternatively, in an online setting where an algorithm is forced to make irrevocable decisions with limited information about an input graph. We also approach the topic as a purely mathematical problem as we study the domination number of a well-known family of graphs known as the Knödel graphs.

Prior to this thesis, research on the dominating set problem in an online setting was sparse. We consider an online setting where a vertex is revealed to an algorithm and the choice to add this vertex or not is a finality. In this setting, an adversary must reveal the entire neighborhood of a vertex to an algorithm while keeping the revealed portion of the graph connected at all times. We present algorithms that achieve 2-competitiveness on trees, 2.5-competitiveness on cactus graphs, (t - 1) on K1,t-free graphs, and Θ (√Δ ) for maximum degree Δ graphs. Moreover, we show that all of those competitive ratios are tight. Then, we study several more general classes of graphs, such as threshold, bipartite planar, and series-parallel graphs, and show that they do not admit competitive algorithms (that is, when competitive ratio is independent of the input size). Our results are compared with earlier results in a different input model, where a vertex is revealed alongside its restricted neighborhood: those neighbors that are among already revealed vertices. Thus, conceptually, our results quantify the value of knowing the entire neighborhood at the time a vertex is revealed as compared to the restricted neighborhood.

The family of graphs known as the Knödel graphs are studied extensively with an emphasis on determining closed form expressions for certain graph parameters. Our main contribution is the novel use of techniques from elementary number theory to establish an upper bound on the domination number of the Knödel graph on n vertices. In particular, we show that whenever we find a prime p dividing n with p ≤ [log n] such that 2 is a primitive root modulo p then there is a dominating set of size np. Moreover, if we suppose that 2 is a primitive root modulo pk, where pk divides n and φ( pk) < [log n] then we can construct a dominating set of size 2n/pk.