11institutetext: Department of Computer Science and Software Engineering,
Concordia University, Montreal, QC, H3G1M8, Canada

# Online Domination: The Value of Getting to Know All your Neighbors

Hovhannes Harutyunyan  Denis Pankratov  Jesse Racicot

###### Abstract

We study the dominating set problem in an online setting. An algorithm is
required to guarantee competitiveness against an adversary that reveals the
input graph one node at a time. When a node is revealed, the algorithm learns
about the entire neighborhood of the node (including those nodes that have not
yet been revealed). Furthermore, the adversary is required to keep the
revealed portion of the graph connected at all times. We present an algorithm
that achieves 2-competitiveness on trees and prove that this competitive ratio
cannot be improved by any other algorithm. We also present algorithms that
achieve 2.5-competitiveness on cactus graphs, $(t-1)$-competitiveness on
$K_{1,t}$-free graphs, and $\Theta(\sqrt{\Delta})$ for maximum degree $\Delta$
graphs. 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).
Previously, the dominating set problem was considered in a slightly 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. For instance,
it was known in the restricted neighborhood model that 3-competitiveness is
optimal for trees, whereas knowing the neighbors allows us to improve it to
2-competitiveness.

###### Keywords:

Dominating set Online algorithms Competitive ratio Trees Cactus graphs
Bipartite planar graphs Series-parallel graphs Closed neighborhood.

##  1 Introduction

Given an undirected simple graph $G=(V,E)$, a subset of vertices $D\subseteq
V$ is called _dominating_ if every vertex of $V$ is either in $D$ or is
adjacent to some vertex in $D$. In the well-known $\mathcal{NP}$-hard
dominating set problem, the goal is to find a dominating set of minimum
cardinality. We study this problem in the online setting, where a graph is
revealed one node at a time. When a node is revealed its entire neighborhood
is revealed as well. An algorithm is required to make an irrevocable decision
on whether to include the newly revealed vertex into the dominating set the
algorithm is constructing or not. This decision must be made before the next
vertex is revealed. Performance of an online algorithm is measured against an
optimal offline algorithm, i.e., an algorithm that knows the entire input in
advance and has infinite computational resources. This measure is captured by
the notion of competitive ratio and analysis, which is made precise below. For
now, it suffices to note that competitive ratio is analogous to approximation
ratio in the offline setting.

The dominating set problem has important practical and theoretical
applications, such as establishing surveillance service ([1]), routing and
transmission services in (wireless) networks ([5]), as well as broadcasting
([6, 7]). While the dominating set problem and its variants (connected
dominating set, independent dominating set, weighted dominating set, etc.)
have been extensively studied in the offline setting [1, 8, 9, 13, 14, 15],
this problem has received little attention in the online algorithms community.
The current paper attempts to fill in this gap, while making a quantitative
comparison with another online model for dominating set.

Online dominating set problem has been studied in the vertex arrival model by
Boyar et al. [3]. In that model, when a vertex is revealed only restricted
neighborhood of that vertex is revealed as well, namely, those neighbors that
appear among previously revealed vertices. Moreover, in the model considered
by Boyar et al. decisions are only partially irrevocable, i.e., when a vertex
arrives an algorithm may add this vertex together with _any of its neighbors
from the restricted neighborhood_ to the dominating set. Thus, the decision to
include a vertex is irrevocable, while the decision not to include a vertex is
only partially irrevocable – an algorithm has a chance to reconsider when any
yet unrevealed neighbors arrive. The catch is that the algorithm does not know
the input size and has to maintain a dominating set at all times. In the model
considered in this paper, all decisions (to include or exclude a vertex from a
dominating set) are irrevocable. On one hand, this makes our model stronger
for the adversary. On another hand, our model is weaker for the adversary than
the model of Boyar et al. in the aspect of the adversary being forced to
reveal all neighbors of a newly revealed vertex at once. Thus, our results
when compared to those of the vertex arrival model can be viewed as
quantifying the value of getting to know all neighbors of a vertex at the time
of its revelation.

Perhaps somewhat surprisingly, we discover in several results that the benefit
of knowing all neighbors outweighs the drawbacks of fully irrevocable
decisions. Our results are summarized below, but in particular we show that in
our model $\Delta$-bounded degree graphs admit $O(\sqrt{\Delta})$ online
algorithms, while Boyar et al. show that $\Omega(\Delta)$ is necessary in
their model. Similarly, we demonstrate and analyze a $2$-competitive algorithm
for trees, while Kobayashi [11] shows a lower bound of $3$ in the vertex
arrival model. Our degree upper bound implies that $O(\sqrt{n})$ competitive
ratio is tight for general graphs, whereas Boyar et al. showed the lower bound
of $\Omega(n)$ in the vertex arrival model. This paints a picture that knowing
all the neighbors improves not only precise constants, when graph classes
allow for small competitive ratio algorithms, but also give asymptotic
improvements for more “challenging” graph classes for algorithms.

Prior to summarizing our results, we give a brief overview of competitive
analysis framework. For more details, an interested reader should consult
excellent books [2, 12] and references therein. Let $ALG$ be an algorithm for
the online dominating set problem. Let $ALG(G,\sigma)$ denote the set of
vertices that are selected by $ALG$ on the input graph $G$ with its vertices
revealed according to the order $\sigma$. We sometimes abuse the notation and
omit $G$ or $\sigma$ (or both) when they are clear from the context. Abusing
notation even more, we sometimes write $ALG(G,\sigma)$ to mean
$|ALG(G,\sigma)|$. Similar conventions apply to an offline optimal solution
denoted by $OPT$. We say that $ALG$ has _strict competitive ratio_ $c$ if
$ALG\leq c\cdot OPT$ on all inputs. We say that $ALG$ has _asymptotic
competitive ratio_ $c$ (or, alternatively, that $ALG$ is $c$-competitive) if
$\limsup_{OPT\rightarrow\infty}\frac{ALG}{OPT}\leq c$. The _competitive ratio_
of $ALG$ is the infimum over all $c$ such that $ALG$ is $c$-competitive. When
we simply write “competitive ratio” we typically mean “asymptotic competitive
ratio” unless stated otherwise.

We shall consider performance of algorithms with respect to restricted inputs,
specified by various graph classes, such as trees, cactus graphs, series-
parallel, etc. The above definitions of competitive ratios can be modified by
restricting them to inputs coming from certain graph classes. We denote the
competitive ratio of an algorithm $ALG$ with respect to the restricted graph
class CLASS by $\rho(ALG,$CLASS$)$.

The following is a summary of our contributions with the section numbers where
the results appear.

  * •

tight competitive ratio $2$ on trees (Section 3.1);

  * •

tight competitive ratio $\frac{5}{2}$ on cactus graphs (Section 3.2);

  * •

tight competitive ratio $\Theta(\sqrt{\Delta})$ on maximum degree $\Delta$
graphs (Section 3.3);

  * •

tight competitive ratio $t-1$ on $K_{1,t}$-free graphs (Section 3.4);

  * •

tight competitive ratio $\Theta(\sqrt{n})$ for threshold graphs (Section 4.1),
planar bipartite graphs (Section 4.2), and series-parallel graphs (Section
4.3).

We note that all our upper bounds are in terms of strict competitive ratios,
and all our lower bounds, with the exception of $K_{1,t}$-free graphs, are in
terms of asymptotic competitive ratios.111With the small caveat that the
performance ratio for threshold graphs is measured as a function of input size
for reasons provided later.

##  2 Preliminaries

In this section we describe definitions and establish notations that will be
used frequently in the rest of the paper. Let $G=(V,E)$ be a connected
undirected graph on $n=|V|\geq 1$ vertices. For a subset of vertices
$S\subseteq V$ we define the _closed neighborhood_ of $S$, denoted by $N[S]$,
to be $S\cup\\{v\in V\mid\exists u\in S,\\{u,v\\}\in E\\}$. We use $\langle
S\rangle$ to denote the subgraph of $G$ induced on $S$.

The vertices $V$ are revealed online in order $(v_{1},...,v_{n})$. Since we
consider the online input model where vertices are revealed alongside their
neighbors, we distinguish between two notions: those vertices that are
revealed by a certain time and those that are visible. More precisely, we have
the following:

###### Definition 1

  * •

$v_{i}$ is _revealed by time_ $j$ if $i\leq j$.

  * •

$v_{j}$ is _visible at time_ $i$ if it is either revealed by time $i$ or it is
adjacent to some vertex revealed by time $i$.

  * •

$R_{i}$ denotes the set of all vertices revealed by time $i$.

  * •

$V_{i}$ denote the vertices visible at time $i$ (i.e. $V_{i}=N[R_{i}]$).

The adversary chooses the graph $G$ as well as the revelation order of
vertices; however, the adversary is restricted to those revelation orders that
guarantee that $\langle R_{i}\rangle$ is connected for all $i$. Thus, we
observe that the process of revelation of a graph by the adversary is a
natural generalization of the breadth-first search (BFS) and depth-first
search (DFS) explorations of the graph. Thus, we can define the _revelation
tree_ analogous to BFS and DFS trees. We need the following observation first:

###### Observation 1

If $v_{j}\in V_{i}\setminus V_{i-1}$ with $i\geq 2$ then $v_{i}$ is the unique
neighbour of $v_{j}$ in $\langle V_{i}\rangle$.

In the preceding observation, we say that $v_{j}$ is a _child_ of $v_{i}$ and
that $v_{i}$ is the _parent_ of $v_{j}$. The edge $\\{v_{i},v_{j}\\}$ is
called a _tree edge_. The subgraph induced on the tree edges is the revelation
tree. Any edge $\\{u,v\\}$ where $u$ is not the parent of $v$ nor $v$ the
parent of $u$ is called a _cross edge_.

After the vertex $v_{i}$ is revealed together with its closed neighborhood
$N[v_{i}]$, an online algorithm $ALG$ must make a decision
$d_{i}\in\\{0,1\\}$, which indicates whether the algorithm takes this vertex
to be in the dominating set or not.

###### Definition 2

Given an online algorithm $ALG$ we define:

  * •

$S_{i}$ denote the set of revealed vertices selected by $ALG$ after decision
$d_{i}$ (i.e. $S_{i}=\\{v_{k}\mid d_{k}=1,1\leq k\leq i\\}$) where
$S_{0}=\emptyset$.

  * •

$D_{i}=N[S_{i}]$ is the set of vertices that are dominated after decision $i$.

  * •

$U_{i}=V_{i}\setminus D_{i-1}$ is the set of visible vertices undominated
immediately before decision $d_{i}$. $U_{0}=\emptyset$.

A series of figures are provided below which illustrate the preceding
definitions. For these figures, and all others in this paper, the convention
is that vertices that are shaded in gray are those selected by $ALG$, vertices
with thicker boundaries belong to $OPT$, an edge that is dashed is a cross
edge, and all the solid edges are tree edges.

Figure 1: A series of prefixes of the graph below. Figure 2: Top picture
depicts the prefix of a graph with $5$ revealed vertices and $10$ visible
vertices. Bottom picture depicts its revelation tree. The thickened edges are
the edges in the induced subgraph on the revealed vertices, which is acyclic
here but is only guaranteed to be connected in general.

Since an online algorithm makes irrevocable decisions and it must produce a
feasible solution, there may be situations where an algorithm is forced to
select a vertex $v_{j}$ to be in the dominating set. This happens because
$v_{j}$ is the “last chance” to dominate some other vertex $v_{i}$. In this
case, we say that $v_{j}$ saves $v_{i}$ or that $v_{j}$ is the savior of
$v_{i}$. Note that it is possible for a vertex $v_{j}$ to save itself. The
following definition makes the notion of “saving” precise.

###### Definition 3

A vertex $v_{j},j\geq 1$ _saves_ a vertex $v_{i}$ if $j=\max\\{k\mid v_{k}\in
N[v_{i}]\\}$ and $N[v_{i}]\setminus\\{v_{j}\\}$ contains no vertices from
$S_{j-1}$. Let $s(v_{j})$ denote the set of vertices that $v_{j}$ saves.

Observe that if a vertex is saved then it must be that every one of its
neighbours (itself included) had a chance to dominate the said vertex.

###### Observation 2

If $v_{i}$ is saved then $v_{i}\in N[v_{j}]\cap U_{j}$ for any $v_{j}\in
N[v_{i}]$.

All our upper bounds are established by either a GREEDY algorithm or a
$k$-DOMINATE algorithm for some fixed integer value of parameter $k$:

  * •

The algorithm GREEDY selects a newly revealed vertex if and only if the vertex
is not currently dominated. Using the notation introduced above, GREEDY
selects $v_{i},i\geq 1$ if and only if $v_{i}\in U_{i}$.

  * •

The algorithm $k$-DOMINATE (for some fixed integer parameter $k$) selects a
newly revealed vertex if and only if either (1) the vertex has at least $k$
undominated neighbors, or (2) the vertex saves at least one other vertex.
Using the notation introduced above, $v_{i},i\geq 1$ is selected if and only
if either (1) $|N(v_{i})\cap U_{i}|\geq k$, or (2) $|s(v_{i})|\geq 1$.

Both GREEDY and $k$-DOMINATE give rise to rather efficient offline algorithms
so that any of the positive results given in this paper may be realized as
efficient offline approximation algorithms.

##  3 Competitive Graph Classes

###  3.1 Trees

In this section we establish the tight bound of $2$ on the best competitive
ratio when the input graph is restricted to be a tree. The upper bound is
achieved by the $2$-DOMINATE algorithm and is proved in Theorem 3.2 below. The
lower bound on all online algorithms is established in Theorem 3.1. We begin
this section with the lower bound.

###### Theorem 3.1

$\rho(ALG,TREE)\geq 2$ for any algorithm $ALG$.

###### Proof

Consider an arbitrary small $\epsilon>0$. We will give an adversarial input
that guarantees that $ALG\geq(2-\epsilon)OPT$. Let
$k=\lceil\frac{3}{\epsilon}\rceil\geq 4$. At the start, the adversary reveals
$v_{1}$ with $k$ children $\\{c_{1},\ldots,c_{k}\\}$. Then we start the
process described in the next paragraph at $c_{1}$. The process can terminate
in two ways: (i) $ALG$ stops selecting vertices to be in the dominating set,
or (ii) $ALG$ selects $k$ vertices revealed after $c_{1}$ (inclusive). If the
process terminates because of (i), then the adversary restarts the process at
child $c_{2}$ of $v_{1}$. The process again terminates either with (i) or (ii)
with respect to $c_{2}$. If it is due to (i), then the adversary restarts the
process at $c_{3}$, and so on. If the process terminates with (ii) with
respect to $c_{i}$ then we reveal $c_{j}$ for $j>i$ as leaves of $v_{1}$.

Next, we describe the process with respect to $c_{i}$. The adversary reveals
$c_{i}$ with $2$ children and if $ALG$ selects $c_{i}$ then exactly one child
of $c_{i}$ is revealed with two additional children. If $ALG$ selects the
child then one of its children is revealed with two additional children, and
so on. Let $j_{i}$ be the number of these vertices that are selected by $ALG$.
This process terminates only if $ALG$ stops selecting these vertices with two
children ($j_{i}<k$) or when $ALG$ selects $k$ of them ($j_{i}=k$). At this
point the subtree grown at $c_{i}$ has some revealed vertices as well as
visible, but not yet revealed vertices. To finish revealing the entire
subtree, the adversary proceeds as follows.

If $j_{i}<k$ then the two children on the $(j_{i}+1)$’st vertex are revealed
to be leaves. Moreover, each of the $j_{i}$ selected vertices have exactly one
visible child that is not yet revealed. Reveal those $j_{i}$ children, called
_support vertices_ , with an additional leaf child (i.e. the child is revealed
to be a leaf after its parent is revealed). Including the $2$ children of the
$(j_{i}+1)$’st vertex $ALG$ must select at least $j_{i}+2$ additional vertices
to dominate these leaves for a total of $j_{i}+(j_{i}+2)=2(j_{i}+1)$ selected
vertices in this subtree. In this case, $OPT$ can select the support vertices
together with the $(j_{i}+1)$’st vertex for a total $j_{i}+1$ vertices to
dominate the entire subtree.

If $j_{i}=k$ the procedure to finish revealing the entire subtree at $c_{i}$
is similar: the $k$’th vertex children are both revealed to be leaves and each
of the other $k-1$ selected vertices has the other child become a support
vertex, i.e., revealed with an additional leaf child. The performance is
similar here but $ALG$ is not forced to select the two children of the $k$’th
vertex so $ALG$ selects at least $k+(k-1)=2k-1$. In this case, $OPT$ needs
only select the $k$’th vertex together with the support vertices for a total
of $k$ vertices to dominate the subtree.

To finish the analysis, we consider the following two cases:

Case 1 : for all $i$ we have $j_{i}<k$. Then $ALG\geq 2(j_{i}+1)$ on each
subtree whereas $OPT\leq j_{i}+1$ on each subtree. Summing over all subtrees
and remarking that $OPT$ might select $v_{1}$ we obtain that

$ALG/OPT\geq\left(\sum 2(j_{i}+1)\right)/\left(1+\sum(j_{i}+1)\right)\geq
2-2/k\geq 2-\epsilon.$

Case 2 : there exists $\ell$ such that $j_{\ell}=k$. Then $OPT$ selects
$j_{i}+1$ vertices for $i<\ell$, $k$ vertices for $i=\ell$, $0$ vertices for
$i>\ell$ per subtree, plus $v_{1}$. Whereas $ALG$ selects at least
$2(j_{i}+1)$ for $i<\ell$, $2k-1$ for $i=\ell$, and $0$ for $i>\ell$. By a
similar calculation to Case 1, we obtain that $ALG/OPT\geq 2-3/k\geq
2-\epsilon$.

Figure 3: An example of the process described in Theorem 3.1 where $ALG$
selects $j_{i}=3$ vertices on the subtree rooted at $c_{i}$. The top depicts
the subtree immediately after revealing $c_{i,3}$ whereas the bottom shows the
entirely revealed subtree.

Now that we have established an asymptotic lower bound of $2$ for any
algorithm we show that $2$-DOMINATE is $2$-competitive.

###### Theorem 3.2

$\rho($2-DOMINATE, TREE$)=2$.

High level overview of the proof. Consider an arbitrary input $T=(V,E)$ on
$n\geq 3$ vertices and let $OPT$ denote a minimum dominating set of $T$ which
contains no vertices of degree $1$ (i.e. any such vertex can be exchanged for
its only neighbor). Recall that $S$ is the set of vertices selected by
$2$-DOMINATE. Initially, we assign charge $1$ to each vertex $v$ in $S$ and
charge $0$ to each vertex $v$ not in $S$. Thus, $|S|=\sum\limits_{v\in
S}ch(v)$ where $ch(v)$ denotes the charge of $v$. With a charging scheme
described shortly, we spread the charge from the vertices in $S$ to the
vertices of $V$. Let $ch^{*}(v)$ denote the new charge associated with vertex
$v$. We extend the functions $ch$ and $ch^{*}$ to subsets of vertices
linearly, e.g., for $W\subseteq V$ we have $ch(W)=\sum_{v\in W}ch(v)$. We
shall demonstrate that the procedure of spreading the charge satisfies two
properties:

  1. 1.

conservation property: $\sum_{v}ch(v)=\sum_{v}ch^{*}(v)$ meaning that the
total charge is preserved; and

  2. 2.

$OPT$-concentration property: for each $v\in OPT$ we have $ch^{*}(N[v])\leq
2$.

With these two properties it follows that $2$-DOMINATE
$\leq\sum_{v}ch(v)=\sum_{v}ch^{*}(v)\leq\sum_{v\in OPT}ch^{*}(N[v])\leq 2OPT$,
so $2$-DOMINATE is strictly $2$-competitive.

Before we proceed with this plan, we make a couple of useful observations:

###### Lemma 1

If input is a tree, there are no cross edges incident on any vertex $v_{i}$.
In particular, any vertex $v_{i}$ has at most one neighbour before it is
revealed.

###### Corollary 1

If $deg(v_{i})\geq 3$ then $v_{i}\in S$.

Now, we are ready to present formal details of the above plan. We spread the
charges according to the following rule:

Consider any $v_{i}\in S$ with $X_{i}=N[v_{i}]\cap U_{i}$. Remarking that
$X_{i}\neq\emptyset$ we then give each vertex in $X_{i}$ an equal charge of
$\frac{1}{|X_{i}|}$. That is, a vertex selected by $2$-DOMINATE spreads its
charge evenly to all the newly dominated vertices in its closed neighbourhood.
We say that each vertex in $X_{i}$ is charged by $v_{i}$.

###### Observation 3

Every vertex is charged by exactly one vertex.

The preceding observation immediately implies that any vertex has charge at
most $1$. This observation is tight in the sense that, on certain inputs,
there are vertices with charge equal to $1$. A vertex with charge $1$ is a
rather special case though. In particular, if $v_{i}$ has charge $1$ then it
must be saved by some vertex $v_{j}$ where $X_{j}=\\{v_{i}\\}$ (this does not
exclude the possibility that $v_{i}=v_{j}$). If $v_{i}$ does not meet this
condition then it must have charge at most $\frac{1}{2}$.

###### Lemma 2

If $v_{i}$ and $v_{j}$ both have charge equal to $1$ then they share no common
neighbours.

###### Proof

Suppose for the sake of deriving a contradiction that $v_{i^{\prime}}$ were a
common neighbour of $v_{i}$ and $v_{j}$. Since $v_{i}$ is saved, by
Observation 2 it must be that $v_{i}\in N(v_{i}^{\prime})\cap U_{i^{\prime}}$.
Similarly, we have that $v_{j}\in N(v_{i}^{\prime})\cap U_{i^{\prime}}$. That
is, $|N(v_{i}^{\prime})\cap U_{i^{\prime}}|\geq 2$ and thus $v_{i}^{\prime}\in
S$. Moreover, $X_{i^{\prime}}=N[v_{i^{\prime}}]\cap U_{i^{\prime}}$ contains
$v_{i}$ and $v_{j}$. In particular, we have that $|X_{i^{\prime}}|\geq 2$ with
$v_{i},v_{j}\in X_{i^{\prime}}$ and therefore $v_{i}$ and $v_{j}$ receive
charge no larger than $\frac{1}{2}$, a contradiction.

###### Lemma 3

If $v_{i}$ and $v_{j}$ both have charge equal to $1$ then they are not
adjacent.

###### Proof

It is easy to see that $v_{1}$ cannot have charge $1$ on any input with at
least $2$ vertices. Therefore we safely assume that $1<i<j$ such that both
$v_{i}$ and $v_{j}$ have a parent. We assume for the sake of deriving a
contradiction that $v_{i}$ and $v_{j}$ are adjacent.

Now, since both $v_{i}$ and $v_{j}$ have charge $1$ it follows that they are
both saved vertices. First we show that both $v_{i},v_{j}\notin S$. Notice
that any saved vertex $v_{k}$ has the property that $|N[v_{k}]\cap S|=1$.
Therefore, if we assume by way of contradiction that $v_{i}\in S$ we obtain
that $N[v_{i}]\cap S=N[v_{j}]\cap S=\\{v_{i}\\}$ and therefore $v_{i}$ saves
itself and $v_{j}$. This yields that $X_{i}=N[v_{i}]\cap U_{i}$ contains
$v_{i}$ and $v_{j}$. In particular, we have that $|X_{i}|\geq 2$ with
$v_{i},v_{j}\in X_{i}$ and therefore $v_{i}$ and $v_{j}$ receive charge no
larger than $\frac{1}{2}$, a contradiction. An identical argument will yield
that $v_{j}\notin S$.

Therefore it must be that $v_{i}$ is saved by some vertex $v_{i^{\prime}}$
with $i^{\prime}\notin\\{i,j\\}$. Moreover, we must have $i<j<i^{\prime}$
since $i<j$ by assumption and $i^{\prime}=\max\\{k\mid v_{k}\in N[v_{i}]\\}$.
This implies that both $v_{j},v_{i^{\prime}}$ are children of $v_{i}$ by
Observation 1 yielding that $|N(v_{i})\cap U_{i}|\geq 2$ but $v_{i}$ cannot be
in $S$.

From the two preceding lemmas we have the immediate corollary.

###### Corollary 2

For any vertex $v_{i}$, at most one vertex in $N[v_{i}]$ has charge $1$.

Now, we finish the proof of $2$-competitiveness of $2$-DOMINATE on trees.

######  Proof (Proof of Theorem 3.2)

The lower bound follows from Theorem 3.1. Let $v_{i}\in OPT$ be an arbitrary
vertex in $OPT$. We consider two cases (1) $deg(v_{i})=2$ or (2)
$deg(v_{i})\geq 3$.

Case 1 : Suppose that $deg(v_{i})=2$ and hence $|N[v_{i}]|=3$. By Corollary 2
it follows that at most one vertex in $N[v_{i}]$ has charge $1$. If no
vertices in $N[v_{i}]$ have charge $1$ then $ch(x)\leq\frac{1}{2}$ for each
$x\in N[v_{i}]$ and we obtain that $\sum\limits_{x\in N[v_{i}]}ch(x)\leq
3\big{(}\frac{1}{2}\big{)}<2$. If there is exactly one vertex $x^{\prime}\in
N[v_{i}]$ with charge $1$ we therefore obtain that $\sum\limits_{x\in
N[v_{i}]}ch(x)=\sum\limits_{x\in
N[v_{i}]\setminus\\{x^{\prime}\\}}ch(x)+ch(x^{\prime})\leq\frac{2}{2}+1=2$.

Case 2 : Suppose that $deg(v_{i})\geq 3$. By Corollary 1 it follows that
$v_{i}\in S$ with at least $2$ children. Let $C_{i}=V_{i}\setminus V_{i-1}$
denote the children of $v_{i}$ and remark that $C_{i}\subseteq X_{i}$. That
is, each child of $v_{i}$ is charged by $v_{i}$ and only $v_{i}$. Therefore
the children of $v_{i}$ can receive at most the full initial charge on $v_{i}$
and thus attribute a charge of at most $1$.

Now we claim that any vertex in $N[v_{i}]\setminus C_{i}$ has a charge of at
most $\frac{1}{2}$. Indeed, suppose a vertex $v_{i^{\prime}}\in
N[v_{i}]\setminus C_{i}$ has charge $1$ then it must be saved by $v_{i}$ since
$|N[v_{i^{\prime}}]\cap S|=1$ for any saved vertex $v_{i^{\prime}}$. That is,
there is exactly one vertex in its closed neighbourhood that is selected and
since $v_{i}$ is selected it must be $v_{i}$. Thus, we must have that
$v_{i^{\prime}}\in X_{i}$ but since $C_{i}\subseteq X_{i}$ we know that
$|X_{i}|\geq 2$ and thus $v_{i^{\prime}}$ receives a charge of no more than
$\frac{1}{2}<1$, contradicting our assumption that $v_{i^{\prime}}$ has charge
$1$.

Thus, by remarking that $|N[v_{i}]\setminus C_{i}|\leq 2$ we obtain that
$\sum\limits_{x\in N[v_{i}]}ch(x)=\sum\limits_{v_{j}\in
C_{i}}ch(v_{j})+\sum\limits_{v_{i^{\prime}}\in N[v_{i}]\setminus
C_{i}}ch(v_{i^{\prime}})\leq 1+2\big{(}\frac{1}{2}\big{)}=2$ as desired.

###  3.2 Cactus Graphs

A graph $G$ is said to be a cactus graph if it is connected and every edge
lies on at most one cycle. [hedetniemi1986linear] provide an exact offline
algorithm that runs in linear time for finding a minimum dominating set of a
cactus graph. Of course, an efficient offline algorithm does not guarantee
that an online algorithm can perform well but fortunately, cactus graphs are a
class of graphs for which an online algorithm can achieve constant competitive
ratio. In this section, we show that $2$-DOMINATE is $\frac{5}{2}$-competitive
when inputs are restricted to cactus graphs, and that this is as well as any
algorithm can perform.

Before presenting a lower bound of $\frac{5}{2}$ on all online algorithms we
describe a gadget that is used in the proof. The gadget itself is a cactus
graph on $3\leq n\leq 4$ vertices with the property that $OPT$ selects exactly
$1$ vertex and any algorithm $ALG$ selects at least $2$ vertices. Consider
revealing a root vertex $r$ with $2$ children $c$ and $c^{\prime}$. If $ALG$
does not select $r$ then both $c,c^{\prime}$ are revealed as only adjacent to
$r$ and $ALG$ must select both whereas $OPT$ selects only $r$. If $ALG$ does
select $r$ then $c$ is revealed as adjacent to $c^{\prime}$, and $c^{\prime}$
is revealed with an additional child $x$. The vertex $x$ is adjacent only to
$c^{\prime}$ and thus $ALG$ must select at least one of $c^{\prime},x$ whereas
$OPT$ selects only $c^{\prime}$ (both cases are depicted in figure 4). Given
any input cactus graph with a visible vertex $r$ not yet revealed this gadget
can be constructed with $r$ as the root. Within the proof of the lower bound
we call this a $2$-gadget.

Figure 4: The cactus $2$-gadget : The leftmost figure depicts the case where
$ALG$ does not select the root $r$ and rightmost depicts the case where $ALG$
selects $r$.

###### Theorem 3.3

$\rho(ALG,CACTUS)\geq\frac{5}{2}$ for any algorithm $ALG$.

###### Proof

We prove this lower bound on the asymptotic competitive ratio. We construct a
sequence of graphs, one for each $k$, such that the competitive ratio
approaches $5/2$ as $k$ goes to infinity. We start by revealing the first
vertex $v_{1}$ with $k$ children. Then we run an adversarial process starting
with each child of $v_{1}$ in order. The process consists of several rounds,
each round increases the output of $OPT$ and $ALG$. The process might
terminate for one of two reasons: either (i) we guarantee strict competitive
ratio at least $5/2$ on the subcactus rooted at the child, or (ii) we ran the
process for sufficiently long time, i.e., $k$ rounds. Each round increases
$OPT$ by a multiple of $2$ while increasing $ALG$ by a multiple of $5$.
However, due to initial set up of the process $ALG$ might be off by additive
$1$ from the intended multiple of $5$. When the process terminates according
to (i), it means that $ALG$ made a mistake and this “off by 1” is corrected to
give a strict competitive ratio. When the process terminates according to
(ii), it means that the process ran for sufficient duration that the “off by
1” has been amortized and the ratio approaches $5/2$ asymptotically. After the
first child of $v_{1}$ that terminates according to (ii) (if it exists), the
rest of the children of $v_{1}$ are revealed as leaves. The formal analysis is
analogous to that done in Theorem 3.1 and is omitted. We present the process
which constitutes the crux of the argument.

Using each child of $v_{1}$, we construct a subcactus for which
$\frac{ALG}{OPT}$ approaches $\frac{5}{2}$. Let $c$ be a child of $v_{1}$ and
reveal $c$ with $3$ children. If $ALG$ does not select $c$ then each child of
$c$ is revealed with no additional neighbours and $ALG$ must select all $3$
children whereas $OPT$ selects $c$. Suppose then that $ALG$ selects $c$ and
let $c_{1,1},c_{1,2},c_{1,3}$ be the three children of $c$. Reveal $c_{1,1}$
as adjacent to $c_{1,2}$ along with $2$ additional children. If $ALG$ does not
select $c_{1,1}$ then the children of $c_{1,1}$ are revealed as leaves,
forcing $ALG$ to select them and $c_{1,3}$ is revealed as the root of a
$2$-gadget ($c_{1,2}$ is revealed with no additional neighbours). Thus,
$\frac{ALG}{OPT}\geq\frac{5}{2}$ in this case (see Figure 5). If instead $ALG$
selects $c_{1,1}$ then $c_{1,2}$ and $c_{1,3}$ are revealed as the roots of
two distinct $2$-gadgets and since $c$ is dominated by $v_{1}$ (we assume that
$v_{1}\in OPT$) we have that $\frac{ALG}{OPT}\geq\frac{5}{2}$ on this
subcactus (excluding $c_{1,1}$) thus far and we continue the trap with
$c_{1,1}$ as the root.

At this point, $c_{1,1}$ is selected by $ALG$ we let $c_{2,1},c_{2,2}$ be the
$2$ children of $c_{1,1}$ and we reveal $c_{2,1}$ as adjacent to $c_{2,2}$
with $2$ children $c_{3,1},c_{3,2}$. If $ALG$ does not select $c_{2,1}$ then
$c_{3,1},c_{3,2}$ are revealed as leaves and $ALG$ selects
$c_{1,1},c_{3,1},c_{3,2}$ and $OPT$ can select $c_{2,1}$ for a performance of
$3$ along with the running performance of $\frac{5}{2}$ (see Figure 7). If
$ALG$ does select $c_{2,1}$ then $c_{3,1}$ is revealed as adjacent to
$c_{3,2}$ with two children $c_{4,1},c_{4,2}$. If $ALG$ does not select
$c_{3,1}$ then $c_{4,1},c_{4,2}$ are revealed as leaves and $c_{2,2}$ is
revealed with an additional leaf neighbour $l_{2,2}$ so that $ALG$ must select
at least one of $c_{2,2},l_{2,2}$. Thus, $ALG$ here selects
$c_{1,1},c_{2,1},c_{4,1},c_{4,2}$ and at least one of $c_{2,2},l_{2,2}$
whereas $OPT$ can select $c_{3,1}$ and $c_{2,2}$ for a performance of
$\frac{5}{2}$ (see Figure 8). If instead $ALG$ selects $c_{3,1}$ (thus far
$c_{1,1},c_{2,1}$ and $c_{3,1}$ are all selected) then $c_{2,2}$ is revealed
with an additional leaf neighbour $l_{2,2}$ so that $ALG$ must select at least
one of $c_{2,2},l_{2,2}$, and $c_{3,2}$ is revealed as the root of a
$2$-gadget so that $\frac{ALG}{OPT}\geq\frac{5}{2}$ on the subcactus thus far
(excluding $c_{3,1}$) and we repeat the trap with $c_{3,1}$ as the selected
root (see Figure 9).

Figure 5: The case described in Theorem 3.3 where $ALG$ does not select
$c_{1,1}$.  Figure 6: The case described in Theorem 3.3 where $ALG$ does
select $c_{1,1}$. The enclosed region contributes a performance of
$\frac{5}{2}$. A trap is continued in this case with the root $c_{1,1}$.
Figure 7: The case described in Theorem 3.3 where $ALG$ does not select
$c_{2,1}$. Figure 8: The case described in Theorem 3.3 where $ALG$ does not
select $c_{3,1}$. The enclosed regions each contribute a performance of
$\frac{5}{2}$. Figure 9: The case described in Theorem 3.3 where $ALG$ does
select $c_{3,1}$. The enclosed regions each contribute a performance of
$\frac{5}{2}$. The trap used on a selected root $c_{1,1}$ is repeated on the
root $c_{3,1}$.

###### Theorem 3.4

$\rho($2-DOMINATE, CACTUS$)=\frac{5}{2}$.

The proof can be viewed as an adaptation of our proof for trees to cactus
graphs. We use a charging argument similar to the one given in the section on
trees. Initially, a charge of $1$ is given for each $v\in S$, the charge on
each vertex is then spread to certain neighbours, and we then show that
$\sum\limits_{x\in N[v_{i}]}ch(x)\leq\frac{5}{2}$ for each $v_{i}\in OPT$. We
spread the charge according to the same rule given in the preceding section
and recall that Observation 3 (each vertex receives a new charge from one
other vertex) still holds. In the analysis of how the charge gets reallocated,
the structure of the underlying graph is of paramount importance. We begin
with an analogue to Lemma 1.

###### Lemma 4

In cactus graphs, there is at most one cross edge incident on any $v_{i}$. In
particular, $v_{i}$ has at most $2$ neighbours before it is revealed.

###### Proof

Suppose that $v_{i}\neq v_{1}$ since the statement is clearly true for
$v_{i}=v_{1}$. Suppose for the sake of deriving a contradiction that, at time
$i-1$, $v_{i}$ has three neighbours $v_{h},v_{i_{1}},v_{i_{2}}$ where $v_{h}$
is the parent of $v_{i}$ and $\\{v_{i},v_{i_{1}}\\},\\{v_{i},v_{i_{2}}\\}$ are
cross edges. Notice that $v_{i_{1}},v_{i_{2}}$ are both visible at time $i-1$
as otherwise would imply that $\\{v_{i},v_{i_{1}}\\}$ were a tree edge. Thus,
at time $i-1$, $v_{i_{1}}$ is visible and there is only one tree edge incident
on $v_{i}$. In particular, this implies that there is a path consisting
entirely of tree edges from $v_{i_{1}}$ to $v_{h}$ where said path does not
contain the edge $\\{v_{h},v_{i}\\}$ since it does not pass through $v_{i}$
nor does it contain the edges $\\{v_{i},v_{i_{1}}\\},\\{v_{i},v_{i_{2}}\\}$
since they are cross edges. Thus, by adding edges
$\\{v_{h},v_{i}\\},\\{v_{i},v_{i_{1}}\\}$ to this path we obtain a cycle (in
the completely revealed input graph) that contains the edge
$\\{v_{h},v_{i}\\}$ but does not contain the edge $\\{v_{i},v_{i_{2}}\\}$. A
similar argument yields that there is a path consisting of tree edges from
$v_{i_{1}}$ to $v_{h}$ that does not contain the edges
$\\{v_{h},v_{i}\\},\\{v_{i},v_{i_{1}}\\},\\{v_{i},v_{i_{2}}\\}$ and hence by
adding edges $\\{v_{h},v_{i}\\},\\{v_{i},v_{i_{1}}\\}$ we obtain a cycle which
contains the edge $\\{v_{h},v_{i}\\}$ but does not contain the edge
$\\{v_{i},v_{i_{1}}\\}$. That is, two distinct cycles that share the common
edge $\\{v_{h},v_{i}\\}$, a contradiction.

Since $v_{i}$ has at most $2$ neighbours before it is revealed then it has at
least $deg(v_{i})-2$ children. The following is analogous to Corollary 1 for
trees.

###### Corollary 3

If $deg(v_{i})\geq 4$ then $v_{i}\in S$.

###### Lemma 5

  1. 1.

If $v_{i}$ and $v_{j}$ both have charge equal to $1$ then they share no common
neighbours.

  2. 2.

If $v_{i}$ and $v_{j}$ both have charge equal to $1$ then they are not
adjacent.

  3. 3.

For any vertex $v_{i}$, at most one vertex in $N[v_{i}]$ has charge $1$.

###### Proof

  1. 1.

Follows identically to the proof of Lemma 2.

  2. 2.

First, note that $v_{1}$ cannot have charge $1$ on any input with at least $2$
vertices. Therefore we safely assume that $1<i<j$ such that both $v_{i}$ and
$v_{j}$ have a parent. We assume for the sake of deriving a contradiction that
$v_{i}$ and $v_{j}$ are adjacent.

Now, since both $v_{i}$ and $v_{j}$ have charge $1$ it follows that they are
both saved vertices. We first argue that both $v_{i},v_{j}\notin S$. Notice
that any saved vertex $v_{k}$ has the property that $|N[v_{k}]\cap S|=1$.
Therefore, if we assume by way of contradiction that $v_{i}\in S$ we obtain
that $N[v_{i}]\cap S=N[v_{j}]\cap S=\\{v_{i}\\}$ and therefore $v_{i}$ saves
itself and $v_{j}$. This yields that $X_{i}=N[v_{i}]\cap U_{i}$ contains
$v_{i}$ and $v_{j}$. In particular, we have that $|X_{i}|\geq 2$ with
$v_{i},v_{j}\in X_{i}$ and therefore $v_{i}$ and $v_{j}$ receive charge no
larger than $\frac{1}{2}$, a contradiction. An identical argument will yield
that $v_{j}\notin S$.

Thus, we assume that $v_{i}$ is saved by a neighbour $v_{i^{\prime}}$ and
$v_{j}$ is saved by a neighbour $v_{j^{\prime}}$ where
$i^{\prime},j^{\prime}\notin\\{i,j\\}$. Moreover, $i^{\prime}\neq j^{\prime}$
since $v_{i}$ and $v_{j}$ can share no common neighbours by part 1. Thus, we
have that $i,j,i^{\prime},j^{\prime}$ are all distinct with $i<j<i^{\prime}$
and $i<j<j^{\prime}$ since $i^{\prime}=\max\\{k\mid v_{k}\in N[v_{i}]\\}$ and
$j^{\prime}=\max\\{k\mid v_{k}\in N[v_{j}]\\}$. As mentioned above $v_{i}$
must have a parent $v_{h}$ where $h<i<j<i^{\prime}$. Therefore,
$deg(v_{i})\geq 3$ and since $v_{i}\notin S$ it follows by Corollary 3 that
$deg(v_{i})=3$.

We are now in the situation where $v_{i},v_{j}\notin S$ and $v_{i}$ is
incident on exactly $3$ edges $\\{v_{h},v_{i}\\}$, $\\{v_{i},v_{j}\\}$,
$\\{v_{i},v_{i^{\prime}}\\}$ where exactly one of the edges
$\\{v_{i},v_{j}\\},\\{v_{i},v_{i^{\prime}}\\}$ is a tree edge (and the other a
cross edge). We finish the proof by examining the two cases where (1) :
$\\{v_{i},v_{i^{\prime}}\\}$ is a tree edge or (2) : $\\{v_{i},v_{j}\\}$ is a
tree edge.

Case 1 : Suppose $\\{v_{i},v_{i^{\prime}}\\}$ is a tree edge so that
$v_{i^{\prime}}$ is a child of $v_{i}$. Therefore, $v_{i^{\prime}}\in
C_{i}\subseteq N(v_{i})\cap U_{i}$, that is, $v_{i^{\prime}}$ is an
undominated neighbour of $v_{i}$ when $v_{i}$ is revealed. Since $v_{j}$ is
saved then by Observation 2 it follows that $v_{j}\in N(v_{i})\cap U_{i}$,
that is, $v_{j}$ is also an undominated neighbour of $v_{i}$ when $v_{i}$ is
revealed. That is, both $v_{i^{\prime}},v_{j}\in N(v_{i})\cap U_{i}$ implying
that $|N(v_{i})\cap U_{i}|\geq 2$ but $v_{i}\notin S$, a contradiction.

Case 2 : Suppose $\\{v_{i},v_{j}\\}$ is a tree edge so that $v_{j}$ is a child
of $v_{i}$. First notice that $\\{v_{i},v_{j}\\}$ is the only tree edge
incident on $v_{j}$. Indeed, if there were a tree edge $\\{v_{j},v_{l}\\}$
then $v_{l}$ would be the child of $v_{j}$. Since $v_{i}$ is saved we have
$v_{i}\in N(v_{j})\cap U_{j}$ by Observation 2 implying that $|N(v_{j})\cap
U_{j}|\geq 2$ but $v_{j}\notin S$. Thus, we are in the situation depicted in
Figure 10 where $\\{v_{i},v_{j}\\}$ is the only tree edge incident on $v_{j}$
and by assumption $\\{v_{h},v_{i}\\},\\{v_{i},v_{j}\\}$ are the only two tree
edges incident on $v_{i}$. Therefore we have a path from $v_{i^{\prime}}$ to
$v_{h}$ consisting of tree edges where said path does not contain the edges
$\\{v_{h},v_{i}\\},\\{v_{i},v_{i^{\prime}}\\},\\{v_{i},v_{j}\\},\\{v_{j},v_{j^{\prime}}\\}$.
Thus, by adding edges $\\{v_{h},v_{i}\\},\\{v_{i},v_{i}^{\prime}\\}$ to this
path we obtain a cycle (in the completely revealed input) that contains the
edge $\\{v_{h},v_{i}\\}$ but does not contain the edge
$\\{v_{j},v_{j^{\prime}}\\}$. Similarly, there is a path from $v_{j^{\prime}}$
to $v_{h}$ consisting of tree edges where said path does not contain the edges
$\\{v_{h},v_{i}\\},\\{v_{i},v_{i^{\prime}}\\},\\{v_{i},v_{j}\\},\\{v_{j},v_{j^{\prime}}\\}$
and by adding edges
$\\{v_{h},v_{i}\\},\\{v_{i},v_{j}\\},\\{v_{j},v_{j^{\prime}}\\}$ we obtain a
cycle (in the completely revealed input) that contains the edge
$\\{v_{h},v_{i}\\}$ but does not contain the edge
$\\{v_{i},v_{i^{\prime}}\\}$. That is, two distinct cycles that share the
common edge $\\{v_{h},v_{i}\\}$, a contradiction.

  3. 3.

Follows immediately from the previous parts.

Figure 10: Case $2$ of the second part of Lemma 5. Figure 11: Resolution of
the preceding case in Figure 10. Two cycles sharing the common edge
$\\{v_{h},v_{i}\\}$.

Now, we are ready to prove the upper bound for Theorem 3.4.

######  Proof (Proof of Theorem 3.4)

The lower bound follows from Theorem 3.3. Let $v_{i}\in OPT$ be an arbitrary
vertex in $OPT$. We consider two cases (1) $deg(v_{i})\leq 3$ or (2)
$deg(v_{i})\geq 4$.

Case 1 : Suppose that $deg(v_{i})\leq 3$ and hence $|N[v_{i}]|\leq 4$. By
Lemma 5 part 3 it follows that at most one vertex in $N[v_{i}]$ has charge
$1$. If no vertices in $N[v_{i}]$ have charge $1$ then $ch(x)\leq\frac{1}{2}$
for each $x\in N[v_{i}]$ and we obtain that $\sum\limits_{x\in
N[v_{i}]}ch(x)\leq 4\big{(}\frac{1}{2}\big{)}=2<\frac{5}{2}$. If there is
exactly one vertex $x^{\prime}\in N[v_{i}]$ with charge $1$ we therefore
obtain that $\sum\limits_{x\in N[v_{i}]}ch(x)=\sum\limits_{x\in
N[v_{i}]\setminus\\{x^{\prime}\\}}ch(x)+ch(x^{\prime})\leq\frac{3}{2}+1=\frac{5}{2}$.

Case 2 : Suppose that $deg(v_{i})\geq 4$. By Corollary 3 it follows that
$v_{i}\in S$ with at least $2$ children. Let $C_{i}=V_{i}\setminus V_{i-1}$
denote the children of $v_{i}$ and remark that $C_{i}\subseteq X_{i}$. That
is, each child of $v_{i}$ is charged by $v_{i}$ and only $v_{i}$. Therefore
the children of $v_{i}$ can receive at most the full initial charge on $v_{i}$
and thus attribute a charge of at most $1$.

Now we claim that any vertex in $N[v_{i}]\setminus C_{i}$ has a charge of at
most $\frac{1}{2}$. Indeed, suppose a vertex $v_{i^{\prime}}\in
N[v_{i}]\setminus C_{i}$ has charge $1$ then it must be saved by $v_{i}$ since
$|N[v_{i^{\prime}}]\cap S|=1$ for any saved vertex $v_{i^{\prime}}$. That is,
there is exactly one vertex in its closed neighbourhood that is selected and
since $v_{i}$ is selected it must be $v_{i}$. Thus, we must have that
$v_{i^{\prime}}\in X_{i}$ but since $C_{i}\subseteq X_{i}$ we know that
$|X_{i}|\geq 2$ and thus $v_{i^{\prime}}$ receives a charge of no more than
$\frac{1}{2}<1$, contradicting our assumption that $v_{i^{\prime}}$ has charge
$1$. Thus, by remarking that $|N[v_{i}]\setminus C_{i}|\leq 3$ we obtain that
$\sum\limits_{x\in N[v_{i}]}ch(x)=\sum\limits_{v_{j}\in
C_{i}}ch(v_{j})+\sum\limits_{v_{i^{\prime}}\in N[v_{i}]\setminus
C_{i}}ch(v_{i^{\prime}})\leq 1+3\big{(}\frac{1}{2}\big{)}=\frac{5}{2}$ as
desired.

###  3.3 Graphs of Bounded Degree

We study the problem when the inputs are restricted to graphs of bounded
degree. That is, a positive integer $\Delta\geq 2$ is provided to the
algorithm beforehand and the adversary is restricted to presenting graphs
where every vertex has degree no larger than $\Delta$. The problem of bounded
degree graphs was explored in [3] although within the vertex arrival model
described earlier. The authors show that a greedy strategy obtains a
competitive ratio no larger than $\Delta$ and, when inputs are further
restricted to be “always-connected” (i.e. each prefix of the input is
connected) they provide a lower bound of $\Delta-2$ for any algorithm.

By definition, any input belonging to our setting is “always-connected” yet
the lower bound of $\Delta-2$ does not apply. In particular, we show that
$\big{\lceil}\sqrt{\Delta}\big{\rceil}$-DOMINATE is
$3\sqrt{\Delta}$-competitive along with a lower bound of
$\Omega(\sqrt{\Delta})$ for any online algorithm, essentially closing the
problem in our setting. As previously mentioned, the authors in [10] consider
a setting similar to ours where their adversary is not required to reveal
visible vertices and they assume that an algorithm has additional knowledge of
input size $n$. In this setting they provide an algorithm that achieves
competitive ratio of $\Theta(\sqrt{n})$ for arbitrary graphs. For the upper
bound below we follow a proof nearly identical to theirs modulo some minor
details and definitions.

###### Definition 4

A vertex $v_{i}\in S$ is said to be heavy if $|N(v_{i})\cap
U_{i}|\geq\big{\lceil}\sqrt{\Delta}\big{\rceil}$ and light otherwise. We let
$H$ and $L$ denote the set of heavy and light vertices in $S$ so that
$|S|=|H|+|L|$.

To establish that $\big{\lceil}\sqrt{\Delta}\big{\rceil}$-DOMINATE is
$3\sqrt{\Delta}$-competitive we use a charging argument, but it is quite
different from the arguments in Sections 3.1 and 3.2. Initially, let $ch(v)=1$
for each $v\in S$ so that $|S|=\sum\limits_{v\in S}ch(v)$. Then spread the
charge from $S$ strictly to vertices in $OPT$ so that $\sum\limits_{v\in
S}ch(v)=\sum\limits_{v\in OPT}ch^{*}(v)$ where $ch^{*}(v)$ is the new charge
on a vertex in $OPT$. We then show that $ch^{*}(v)\leq 2\sqrt{\Delta}$ for all
$v\in OPT$ and thus $|S|=\sum\limits_{v\in S}ch(v)=\sum\limits_{v\in
OPT}ch^{*}(v)\leq|OPT|2\sqrt{\Delta}$ and the result then follows. We spread
the charge from $S$ to $OPT$ according to the following rules:

  1. 1.

If $v_{i}\in S\cap OPT$ then $v_{i}$ keeps its full initial charge.

  2. 2.

If $v_{i}\in H\setminus OPT$ then its spread its initial charge evenly over
all vertices in $OPT$. That is, each $v\in OPT$ obtains an additional charge
of $\frac{1}{|OPT|}$ from $v_{i}$.

  3. 3.

For each $v_{i}\in L\setminus OPT$, let $s(v_{i})$ denote the set of vertices
saved by $v_{i}$. Given a vertex $v_{i^{\prime}}\in s(v_{i})$ let
$opt(v_{i^{\prime}})=v_{i^{\prime}}$ if $v_{i^{\prime}}\in OPT$ and
$opt(v_{i^{\prime}})=\min\\{k\mid v_{k}\in N(v_{i^{\prime}})\cap OPT\\}$
otherwise. For each $v_{i^{\prime}}\in s(v_{i})$, $v_{i}$ spreads
$\frac{1}{|s(v_{i})|}$ to $opt(v_{i^{\prime}})$.

###### Lemma 6

If $v_{i}\in OPT$ then it receives charge from at most
$\lceil\sqrt{\Delta}\rceil$ light vertices.

###### Proof

We consider two cases; (1) $v_{i}\in S$ or (2) $v_{i}\notin S$.

Case 1 :  Suppose that $v_{i}\in S$, we show that $v_{i}$ then it receives no
charge from a distinct light vertex (therefore it receives charge from at most
one light vertex, itself). Since $v_{i}\in S$ this implies that it is not
saved by any $v_{j},j\neq i$. Thus, if $v_{i}$ were to receive charge from a
light vertex it must be that $v_{i}=opt(v_{i^{\prime}})$ for some
$v_{i^{\prime}}$ that is saved by some $v_{k}\in L$ different from $v_{i}$.
More precisely, $v_{i}$ must be adjacent to some $v_{i^{\prime}}$ that is
saved by some $v_{k}$ with $k\neq i$. Yet, if $v_{i^{\prime}}\in N(v_{i})$ is
saved then $N[v_{i^{\prime}}]\cap S=\\{v_{i}\\}$ so this cannot be the case.

Case 2 :  Assume that $v_{i}\notin S$ and first remark that $v_{i}$ is saved
by at most one vertex so that it receives at most one charge from a light
vertex in this way. If $v_{i}$ receives charge from any other light vertex
$v_{k}\in L$, it must be that $v_{i}$ is adjacent to some vertex
$v_{i^{\prime}}$ that is saved by $v_{k}$. By Observation 2 it must be that
$v_{i^{\prime}}\in N(v_{i})\cap U_{i}$, that is, is undominated when $v_{i}$
is revealed. All this to say, that any light vertex that charges $v_{i}$
determines at least one neighbor of $v_{i}$ that is undominated at time $i$.
Since $v_{i}\notin S$ we have $|N(v_{i}\cap
U_{i}|\leq\lceil\sqrt{\Delta}\rceil-1$ and thus accounting for possibly one
light vertex that charges $v_{i}$ there are at most
$\lceil\sqrt{\Delta}\rceil$ light vertices that charge $v_{i}$.

###### Lemma 7

$\frac{|H|}{|OPT|}\leq\sqrt{\Delta}+\frac{1}{\sqrt{\Delta}}$.

###### Proof

Since every vertex in $H$ is selected because it dominated at least
$\lceil\sqrt{\Delta}\rceil$ undominated vertices it follows that
$|H|\leq\big{\lfloor}\frac{n}{\lceil\sqrt{\Delta}\rceil}\big{\rfloor}$.
Moreover, by a standard result, first proved by Berge [1], a lower bound on
$OPT$ is $|OPT|\geq\big{\lceil}\frac{n}{\Delta+1}\big{\rceil}$. Ultimately
this yields that

$\frac{|H|}{|OPT|}\leq\frac{\big{\lfloor}\frac{n}{\lceil\sqrt{\Delta}\rceil}\big{\rfloor}}{\big{\lceil}\frac{n}{\Delta+1}\big{\rceil}}\leq\frac{\frac{n}{\lceil\sqrt{\Delta}\rceil}}{\frac{n}{\Delta+1}}\leq\frac{\frac{n}{\sqrt{\Delta}}}{\frac{n}{\Delta+1}}=\frac{\Delta+1}{\sqrt{\Delta}}=\sqrt{\Delta}+\frac{1}{\sqrt{\Delta}}.$

###### Theorem 3.5

$\rho(\big{\lceil}\sqrt{\Delta}\big{\rceil}$-DOMINATE$,\Delta$-BOUNDED$)\leq
3\sqrt{\Delta}$.

###### Proof

Consider an arbitrary vertex $v_{i}\in OPT$. In light of Lemma 6 we see that
it receives charge from at most $\lceil\sqrt{\Delta}\rceil$ light vertices,
where each charge is no larger than $1$. Moreover, by Lemma 7 the charge
received by the heavy vertices is at most
$\sqrt{\Delta}+\frac{1}{\sqrt{\Delta}}$ and $v_{i}$ possibly receives charge
from itself (it may be a heavy or light vertex). In particular we obtain that

$ch(v_{i})\leq\frac{|H|}{|OPT|}+\big{\lceil}\sqrt{\Delta}\big{\rceil}+1\leq\big{(}\sqrt{\Delta}+\frac{1}{\sqrt{\Delta}}\big{)}+\big{\lceil}\sqrt{\Delta}\big{\rceil}+1\leq
3\sqrt{\Delta}.$

We now prove a lower bound $\Omega(\sqrt{\Delta})$ for any online algorithm.
We should note that the adversarial input is bounded in size by a function of
$\Delta$. Although we have omitted the details, it is straightforward to
extend the input so that the lower bound is in fact an asymptotic one.

###### Theorem 3.6

$\rho(ALG,\Delta$-BOUNDED$)=\Omega(\sqrt{\Delta}).$

###### Proof

For simplicity we assume that $\Delta$ is a perfect square. Reveal $v_{1}$
with $\Delta$ children and reveal each child of $v_{1}$ with an additional
$\sqrt{\Delta}$ children. Of the $\Delta$ children of $v_{1}$, suppose that
$ALG$ selects exactly $j$ where $0\leq j\leq\Delta$. For the $\Delta-j$
vertices not selected, their $\sqrt{\Delta}$ neighbours are revealed to have
degree $1$ and $ALG$ is forced to select each of these
$(\Delta-j)(\sqrt{\Delta})$ vertices of degree $1$.

Let $S_{j}$ denote the set of the $j$ selected vertices in $N(v_{1})$ and
$X=\bigcup_{v_{i}\in S_{j}}N(v_{i})$. Since each vertex in $S_{j}$ has
$\sqrt{\Delta}$ children, it follows that $|X|=j\sqrt{\Delta}$. Partition the
vertices of $X$ into
$\lceil\frac{j\sqrt{\Delta}}{\Delta}\rceil=\lceil\frac{j}{\sqrt{\Delta}}\rceil$
parts of size $\Delta$ (with at most one part having size $<\Delta$). Letting
the parts be $X_{1},X_{2},...,X_{\lceil\frac{j}{\sqrt{\Delta}}\rceil}$ we
reveal each vertex in a given part to a common vertex $y_{i}$ (see figure 12
for an example). $ALG$ must select at least one vertex for each part to
dominate $y_{i}$ and therefore at least an additional
$\lceil\frac{j}{\sqrt{\Delta}}\rceil$ vertices are selected.

In total, $ALG$ selects at least
$j+(\Delta-j)(\sqrt{\Delta})+\frac{j}{\sqrt{\Delta}}$ whereas $OPT$ simply
selects $v_{1}$, the $\Delta-j$ vertices in $N(v_{1})\setminus S_{j}$ and the
$\frac{j}{\sqrt{\Delta}}$ vertices with labels $y_{i}$. Ultimately we have

$\displaystyle\frac{ALG}{OPT}$
$\displaystyle\geq\frac{j+(\Delta-j)(\sqrt{\Delta})+\frac{j}{\sqrt{\Delta}}}{1+(\Delta-j)+\frac{j}{\sqrt{\Delta}}}=\frac{j+j\sqrt{\Delta}+(\Delta-j)\Delta}{j+\sqrt{\Delta}+(\Delta-j)\sqrt{\Delta}}$
$\displaystyle=\frac{\sqrt{\Delta}(j/\sqrt{\Delta}+j+(\Delta-j)\sqrt{\Delta})}{2(j/2+\sqrt{\Delta}/2+(\Delta-j)\sqrt{\Delta}/2)}\geq\frac{\sqrt{\Delta}}{2},$

where the last inequality follows from the fact that
$j/2+\sqrt{\Delta}/2+(\Delta-j)\sqrt{\Delta}/2\leq
j/\sqrt{\Delta}+j+(\Delta-j)\sqrt{\Delta}$, since $\sqrt{\Delta}/2\leq
j/\sqrt{\Delta}+j/2+(\Delta-j)\sqrt{\Delta}/2$, which can be seen since when
$j<\Delta$ then the last term on the right hand side already is at least as
large as the left hand side and when $j=\Delta$ then the middle term on the
right hand side is at least the left hand side.

Figure 12: An instance described in the proof of Theorem 3.6 with $\Delta=4$.
The top depicts the graph after the children of $v_{1}$ have been revealed.
Assuming that $ALG$ selects $\\{c_{1},c_{3},c_{4}\\}$ above, the bottom
depicts the completely revealed graph.

###  3.4 Graphs with Bounded Claws

Let $t\geq 3$, a graph $G$ is said to be $K_{1,t}$-free if it contains no
induced subgraph isomorphic to $K_{1,t}$. When $t=3$, this is the well-studied
class of claw-free graphs. In this section we study $K_{1,t}$-free graphs,
which we also refer to as graphs with bounded “claws”.

From the preceding sections one might notice that the existence of an induced
subgraph $K_{1,t}$ poses challenges for an algorithm. This section suggests
that this intuition holds more than just a grain of truth. We show that, when
inputs are restricted to $K_{1,t}$-free graphs, the competitive ratio of every
algorithm is bounded below by $t-1$ and there is an algorithm that achieves
competitive ratio $t-1$. The upper bounds that we have demonstrated so far
were all based on the $k$-DOMINATE algorithm for a suitable choice of
parameter $k$. Interestingly, our upper bound on $K_{1,t}$-free graphs is
based on a conceptually simpler GREEDY algorithm. The analysis is no longer
based on a charging scheme, but follows from combinatorial properties of
graphs with bounded claws.

###### Theorem 3.7

$\rho(ALG,K_{1,t}$-FREE$)\geq t-1.$

###### Proof

Reveal $v_{1}$ with $t-1$ children. If $ALG$ does not select $v_{1}$ then the
input terminates as a star on $t$ vertices (i.e. the $t-1$ neighbours of
$v_{1}$ are revealed with no additional neighbours). Any feasible algorithm
must select the $t-1$ neighbours of $v_{1}$ whereas $OPT$ selects $v_{1}$ and
the statement then follows. Suppose that $ALG$ selects $v_{1}$ and let
$c_{i},1\leq i\leq t-1$ be the children of $v_{1}$. Reveal $c_{1}$ as adjacent
to each child of $v_{1}$ and with an additional $t-2$ children. If $ALG$ does
not select $c_{1}$ then the children of $c_{1}$ are revealed as leaves whereas
the rest of the input is revealed to be a clique. That is, $N[v_{1}]$ is a
clique and only $c_{1}$ has children. $ALG$ selected $v_{1}$ and is forced to
select the $t-2$ children of $c_{1}$ whereas $OPT$ selects only $c_{1}$ as a
single dominating vertex. It is not hard to see that this input is
$K_{1,t}$-free and the result then follows (see Figure 13 for an example).

Suppose that $ALG$ selects $c_{1}$, the input then continues in the following
way; For each $2\leq j\leq t-2$, (as long as $ALG$ is accepting $c_{j}$) we
reveal $c_{j}$ as adjacent to every visible vertex and with an additional
$t-3$ children. That is, $c_{j}$ is adjacent to each child $c_{i},i\neq j$ of
$v_{1}$ and the grandchildren of $v_{1}$ (i.e. the children of all the $c_{i}$
with $1\leq i\leq j$) so that $c_{j}$ is a single dominating vertex of this
prefix.

Case 1 : If there is some $2\leq j\leq t-2$ such that $ALG$ does not select
$c_{j}$ then the $t-3$ children of $c_{j}$ are revealed as leaves, $N[v_{i}]$
is revealed as a clique, and the $(t-2)+\sum\limits_{i=2}^{j}(t-3)=j(t-3)+1$
grandchildren of $v_{1}$ are revealed to form a clique. At this point, $ALG$
has selected $\\{v_{1},c_{1},...,c_{j-1}\\}$ and is now forced to select the
$t-3$ children of $c_{j}$ for an output of at least $j+(t-3)\geq 2+(t-3)=t-1$
whereas $OPT$ selects only $c_{j}$ so that $\frac{ALG}{OPT}\geq\frac{t-1}{1}$.

We now argue that this input is $K_{1,t}$-free. Notice that for all $v$ in
this input we have $N(v)\subseteq N(c_{j})$ so that if there is a an induced
$K_{1,t}$ with central vertex $v$ then there is a claw with central vertex
$c_{j}$. Therefore it is sufficient to show that is no claw with central
vertex $c_{j}$ to finish the claim. Suppose for contradiction’s sake that
there were an induced $K_{1,t}$ where $c_{j}$ is the central vertex and the
$t$ neighbors of $c_{j}$ are all pairwise non-adjacent. Let $G$ denote the
grandchildren of $v_{1}$ and remark that any neighbor of $c_{j}$ is either a
child of $c_{j}$, a grandchild of $v_{1}$, or a vertex from
$N[v_{1}]\setminus\\{c_{j}\\}$. Since there are $t$ vertices and $c_{j}$ only
has $t-3$ children by the pigeonhole principle we must have at least two
vertices $u,v$ that both are grandchildren of $v_{1}$ or both belong
$N[v_{1}]\setminus\\{c_{j}\\}$. Yet, both the set of grandchildren of $v_{1}$
and $N[v_{1}]\setminus\\{c_{j}\\}$ are cliques. Therefore we have that $u$ and
$v$ are adjacent, contradicting our assumption.

Case 2 : If $ALG$ selects each $c_{i},1\leq i\leq t-2$ then the $(t-2)(t-3)+1$
grandchildren of $v_{1}$ are then revealed to form a clique ($N[v_{1}]$ has
already been revealed as a clique). $ALG$ has already selected
$\\{v_{1},c_{1},...,c_{t-2}\\}$ and therefore has an output of at least $t-1$
whereas $OPT$ selects only $c_{t-2}$. An argument similar to the one above
will yield that this input is $K_{1,t}$-free and the result then follows.

Figure 13: An instance described in Theorem 3.7 with $t=5$ where ALG does not
select $c_{1}$. The top depicts the graph at the moment $c_{1}$ was revealed
and the bottom depicts the completely revealed graph. Figure 14: An instance
described in Theorem 3.7 with $t=5$ where ALG does not select $c_{2}$. The top
depicts the graph at the moment $c_{1}$ was revealed and the bottom depicts
the completely revealed graph. Figure 15: An instance described in Theorem 3.7
with $t=5$ where ALG does not select $c_{3}$. The top depicts the graph at the
moment $c_{3}$ was revealed and the bottom depicts the completely revealed
graph.

When inputs are restricted to $K_{1,t}$-free graphs, we show that the online
algorithm GREEDY is $(t-1)$-competitive. The crucial observation to make here
is that the output of GREEDY is an independent set. We provide a result below
that is a straightforward generalization of one given in [4]. The simplicity
of the result suggests that it may have appeared in earlier work.

###### Lemma 8

Let $t\geq 3$, $G=(V,E)$ be a $K_{1,t}$-free graph and $I$ be any independent
set in $G$. Then $|D|\geq\frac{|I|}{t-1}$ for any dominating set $D$ in $G$.

###### Proof

Suppose for the sake of deriving a contradiction that there is some dominating
set $D$ in $G$ with $|D|<\frac{|I|}{t-1}$. Remarking that the vertices of $D$
dominate the vertices of $I$ as $D$ is a dominating set we notice that there
is some vertex $v\in D$ that dominates at least $t$ vertices of $I$ (i.e. if
every vertex of $D$ dominated at most $t-1$ vertices then $D$ would dominate
at most $(t-1)|D|<|I|$ vertices). Moreover, since $v$ is adjacent to at least
one of the $t\geq 3$ vertices of $I$ it dominates, it cannot belong to $I$ as
$I$ is independent. Therefore, the vertices of $I$ dominated by $v\notin I$
are adjacent to $v$. In particular, at least $t$ vertices of $I$, all pairwise
non-adjacent, are neighbors of $v$ and this induces $K_{1,t}$ in $G$.

The preceding lemma shows that for any independent set $I$ in a $K_{1,t}$-free
graph $G$, $|I|\leq(t-1)\gamma(G)$. Given that GREEDY outputs an independent
set we obtain the following result which is of interest to us.

###### Theorem 3.8

$\rho($GREEDY, $K_{1,t}$-FREE$)=t-1$.

###### Proof

The upper bound is a consequence of Proposition 8 and the remarks that follow.
The lower bound follows from Theorem 3.7.

##  4 Noncompetitive Graph Classes

Recall that the setting defined in [10] is nearly identical to ours except
that an algorithm knows the input size $n$ beforehand and the induced subgraph
on the revealed vertices is not necessarily connected. Within this setting the
authors establish a lower bound of $\Omega(\sqrt{n})$ for arbitrary graphs.
Their proof can be augmented to show a lower bound of $\Omega(\sqrt{n})$ in
our model, which is tight by our upper bound of $O(\sqrt{\Delta})$ on degree
at most $\Delta$ graphs (applied to $\Delta=n-1$). Instead, we strengthen such
a result in several ways by showing that the lower bound of $\Omega(\sqrt{n})$
applies to several restricted classes such as threshold graphs222With the
caveat that, for threshold graphs, we instead consider the performance ratio
as a function of input size., planar bipartite graphs, and series-parallel
graphs.

###  4.1 Threshold Graphs

The graph join operation applied to two graphs $G_{1}$ and $G_{2}$ takes the
disjoint union of the two graphs and adds all possible edges between the two
graphs to the result (in addition to retaining the edges of $G_{1}$ and
$G_{2}$). The class of threshold graphs can be described recursively as
follows:

  1. 1.

$K_{1}$ (i.e. a single isolated vertex) is a threshold graph.

  2. 2.

If $G$ is a threshold graph then the disjoint union $G\cup K_{1}$ is a
threshold graph.

  3. 3.

If $G$ is a threshold graph then the graph join $G\oplus K_{1}$ is a threshold
graph.

It is not hard to see that any connected threshold graph has a dominating set
of size $1$. Since our setting only allows for connected graphs we instead
measure $ALG$ as a function of input size $n$ since $OPT\leq 1$ on every
input. In particular, we show that for any algorithm there is an infinite
family of threshold graphs for which this algorithm selects $\Omega(\sqrt{n})$
vertices (where the input has $n$ vertices). Although $OPT$ does not tend
towards infinity, we consider this to be an asymptotic lower bound, but with
input size $n$ tending to infinity. In a sense, this is a stronger lower bound
since the algorithm is guaranteed an input graph with a single dominating
vertex, yet it still selects more than $\Omega(\sqrt{n})$ vertices in the
input.

###### Observation 4

The star on $n\geq 1$ vertices, that is, $K_{1,n-1}$, is a threshold graph.

Now we describe a slightly more complicated graph belonging to the class of
threshold graphs. Let $k\geq 2$ and $j_{1},...,j_{k}$ be non-negative
integers. Let $n=k+1+\sum\limits_{i=1}^{k}j_{i}$ and consider the following
graph $G$ on $n$ vertices; $V(G)=\\{u\\}\cup C_{k}\cup I$, where
$C_{k}=\\{v_{1},...,v_{k}\\}$ and $I=I_{j_{1}}\cup I_{j_{2}}\cup...\cup
I_{j_{k}}$, with each $I_{j_{i}}$ having exactly $j_{i}$ vertices (each
$I_{j_{i}}$ is possibly empty). The set $\\{u\\}\cup C_{k}$ is a clique on
$k+1$ vertices, and for each $i$, $I_{j_{i}}$ is an independent set where each
$v\in I_{j_{i}}$ is adjacent only to vertices $v_{i},...,v_{k}$.

###### Lemma 9

The graph described above is a threshold graph.

###### Proof

We describe a construction using the recursive definition given above.
Initially, start with the single isolated vertex $u$. For each $1\leq i\leq
k$, take the resulting graph from the previous step, disjoint union said graph
with an independent set $I_{j_{i}}$ (i.e. repeatedly perform $j_{i}$ disjoint
unions of with a single vertex) and then join the vertex $v_{i}$. That is, let
$G_{0}=(\\{u\\},\emptyset)$ and for $1\leq i\leq k$, $G_{i}=(G_{i-1}\cup
I_{j_{i}})\oplus v_{i}$.

We are now ready to prove a strong lower bound for any online algorithm.
Although we do not mention this explicitly in the proof, the adversarial
inputs given are either $K_{1,k-1}$ for some $k\geq 3$ or one that can be
obtained by appropriately applying the recursive construction in Lemma 9.

###### Theorem 4.1

For infinitely many values of $n$ there is a threshold graph $G_{n}$ such that

$ALG(G_{n})=\Omega(\sqrt{n}).$

###### Proof

Let $k\geq 3$ be an integer and reveal $v_{1}$ with $k-1$ children. If $ALG$
does not select $v_{1}$ then the input terminates as a star on $k$ vertices
(i.e. the $k-1$ neighbours of $v_{1}$ are revealed with no additional
neighbours). $ALG$ is forced to select the $k-1$ neighbours of $v_{1}$ ($OPT$
selects only $v_{1}$). In this case, the statement follows since
$ALG=k-1\geq\sqrt{k}=\sqrt{n}$.

Suppose that $ALG$ selects $v_{1}$ and let $c_{i},1\leq i\leq k-1$ be the
children of $v_{1}$. Reveal $c_{1}$ as adjacent to each child of $v_{1}$ and
with an additional $k$ children. If $ALG$ does not select $c_{1}$ then the
children of $c_{1}$ are revealed as leaves whereas the rest of the input is
revealed to be a clique. That is, $N[v_{1}]$ is a clique and only $c_{1}$ has
children. In this case, $ALG$ must select the $k$ children of $v_{2}$ yielding
an output of $k+1$ (see Figure 16 for an example). Therefore, in this case the
statement follows since $ALG\geq k+1=\frac{n}{2}+1\geq\sqrt{n}$.

Suppose that $ALG$ selects $c_{1}$, the input then continues in the following
way; For each $2\leq j\leq k-1$, (as long as $ALG$ is accepting $c_{j}$) we
reveal $c_{j}$ as adjacent to every visible vertex and with an additional $k$
children. That is, $c_{j}$ is adjacent to each child $c_{i},i\neq j$ of
$v_{1}$ and the grandchildren of $v_{1}$ (i.e. the children of all the $c_{i}$
with $1\leq i\leq j$) so that $c_{j}$ is a single dominating vertex of this
prefix.

Case 1 : If there is some $2\leq j\leq k-1$ such that $ALG$ does not select
$c_{j}$ then the $k$ children of $c_{j}$ are revealed as leaves and $N[v_{1}]$
is revealed as a clique (see Figure 17 for an example). The input has
$n=1+(k-1)+\sum\limits_{i=2}^{j}ik=k+(j-1)k=jk$ vertices. At this point, $ALG$
has selected $\\{v_{1},c_{1},...,c_{j-1}\\}$ and is now forced to select the
$k$ children of $c_{j}$ ($OPT$ selects only $c_{j}$) for an output of at least
$j+k\geq 2+k\geq\sqrt{n}$ since $j<k$ and $n=jk$.

Case 2 : If $ALG$ selects each $c_{i},1\leq i\leq k-1$ then the input is
terminated with $n=1+(k-1)+\sum\limits_{i=2}^{j}ik=k+(k-1)k=k^{2}$ vertices
after revealing $c_{k-1}$. $ALG$ has already selected
$\\{v_{1},c_{1},...,c_{k-1}\\}$ and therefore $ALG\geq k=\sqrt{n}$.

Figure 16: An instance described in Theorem 4.1 with $k=5$ where $ALG$ does
not select $v_{2}$. The top depicts the graph at the moment $v_{2}$ was
revealed and the bottom depicts the completely revealed graph. Figure 17: An
instance described in Theorem 4.1 with $k=5$ where $ALG$ does not select
$v_{3}$. The top depicts the graph at the moment $v_{3}$ was revealed and the
bottom depicts the completely revealed graph.

###  4.2 Planar Bipartite Graphs

Below is a lower bound of $\Omega(\sqrt{n})$ for planar bipartite graphs. We
should mention that is strikingly similar to the lower bound on general graphs
given in [10]. We provide a simple augmentation of their lower bound so that
it not only consists of inputs that are revealed according to our model but
inputs that are also planar bipartite graphs.

###### Theorem 4.2

$\rho(ALG,$PLANAR BIPARTITE$)=\Omega(\sqrt{n}).$

###### Proof

Let $k\geq 2$ and consider a path on $k$ vertices with the vertices ordered
$v_{i},1\leq i\leq k$. Each vertex along the path is adjacent to $k$ neighbors
appearing as leaves. Every odd labeled vertex is adjacent to a common vertex
$o$ and every even labeled vertex is adjacent to a common vertex $e$ where
both $e,o$ do not lie on the path (and have not yet been revealed). The
ordering of the path is the order in which these vertices were revealed to
$ALG$ (see Figure 18). Of the $k$ vertices along the path we suppose that
$ALG$ selects $k-i$ where $0\leq i\leq k$. For each of the $k-(k-i)=i$
vertices not selected by $ALG$, the $k$ leaves adjacent are revealed to remain
leaves and $ALG$ must select them. For each of the $k-i$ vertices selected by
$ALG$, the leaves adjacent to said vertices are revealed as adjacent to $e$ if
their neighbour had an odd label and $o$ if their neighbour had an even label.
Thus, $ALG$ selects at least $(k-i)+(i)k=k+i(k-1)$ vertices whereas $OPT$ need
only select $o,e$ and the $i$ vertices not selected by $ALG$.

Thus, we have that $\frac{ALG}{OPT}\geq\frac{k+i(k-1)}{i+2}$. Noting that
$k-1\geq\frac{k}{2}$ since $k\geq 2$ we obtain that

$i(k-1)\geq i(k/2)\iff k+i(k-1)\geq
i(k/2)+k=\frac{k}{2}(i+2)\iff\frac{k+i(k-1)}{i+2}\geq\frac{k}{2}.$

Since the input consists of $n=k^{2}+k+2$ vertices the result would then
follow. To finish we provide a justification that the input is planar and
bipartite. To see that it is bipartite let one part $X$ consist of the
vertices along the path with odd labels and the neighbors of the vertices with
even labels (this includes $e$). The other part $Y$ consists of the vertices
along the path with even labels and the neighbors of the vertices with odd
labels (this includes $o$). To see that it is planar, consider a drawing with
the vertices along the path drawn in a line from left to right, $e$ placed
above this path and $o$ placed below. For any odd labeled vertex $v_{i}$, the
$k$ neighbors of $v_{i}$ that do not lie on the path (and are different from
$o$) are placed immediately above $v_{i}$ but below $e$ (i.e. $v_{i}$ along
with said neighbors are depicted as a star on $k+1$ vertices with $v_{i}$ as
the center). Similarly, for any even labeled vertex $v_{i}$, the $k$ neighbors
of $v_{i}$ that do not lie on the path and are different from $e$ are placed
immediately below $v_{i}$ and above $o$.

Figure 18: An instance described in Theorem 4.2 with $k=4$. The top depicts
the prefix where only vertices along the path have been revealed. Assuming the
vertices on the path that $ALG$ selects are $v_{2}$ and $v_{4}$, the bottom
depicts the completely revealed graph.

We remark that in Theorem 4.2 there are cases when $OPT\leq\alpha$ for some
constant $\alpha\geq 2$. For example, when $ALG$ selects all $k$ vertices
along the path $OPT$ selects only $\\{e,o\\}$. In this case, we extend the
input by revealing $o$ with an additional neighbor $u_{1}$, and repeat a
similar trap with $u_{1}$ as the first vertex along the path.

###  4.3 Series-Parallel Graphs

In light of our $2$-competitive algorithm for trees, it is natural to suppose
that some class of graphs generalizing trees might admit competitive
algorithms, that is, algorithms with bounded competitive ratio. One such
generalization is graphs of bounded treewidth. Trees have treewidth $1$, so
the next step is to consider graphs of treewidth $2$. Unfortunately, in this
section we show that by increasing treewidth parameter from $1$ to $2$, the
online dominating set problem becomes extremely hard for online algorithms.
More specifically, we show that series-parallel graphs do not admit online
algorithms with competitive ratio better than $\Omega(\sqrt{n})$. We remark
that series-parallel graphs have treewidth at most $2$.

We begin by recalling the definition of a series-parallel graph. It is defined
with the help of the notion of a two-terminal graph $(G,s,t)$, which is a
graph $G$ with two distinguished vertices $s$, called a source, and $t$,
called a sink. For a pair of two-terminal graphs $(G_{1},s_{1},t_{1})$ and
$(G_{2},s_{2},t_{2})$, there are two composition operations:

  * •

_Parallel composition_ : take a disjoint union of $G_{1}$ with $G_{2}$ and
merge $s_{1}$ with $s_{2}$ to get the new source, as well as $t_{1}$ with
$t_{2}$ to get the new sink.

  * •

_Series composition_ : take a disjoint union of $G_{1}$ with $G_{2}$ and merge
$t_{1}$ with $s_{2}$, which now becomes an inner vertex of the resulting two-
terminal graph; $s_{1}$ becomes the new source and $t_{2}$ becomes the new
sink.

A two-terminal series-parallel graph is a two-terminal graph that can be
obtained by starting with several copies of the $K_{2}$ graph and applying a
sequence of parallel and series compositions. Lastly, a graph is called
series-parallel if it is a two-terminal series-parallel graph for some choice
of source and sink vertices. Observe that intermediate graphs resulting in the
construction of a series-parallel graph may have multiple parallel edges, so
they are multigraphs. This is permitted, as long as the resulting overall
graph is a simple undirected graph at the end.

Now, we are ready to prove the main result of this section.

###### Theorem 4.3

$\rho(ALG,$SERIES-PARALLEL$)=\Omega(\sqrt{n}).$

###### Proof

Let $k\geq 2$ be an integer. The adversary reveals $s$ with $k$ neighbors
$c_{1},\ldots,c_{k}$. Then $c_{1},\ldots,c_{k}$ are revealed in this order
with $k$ new neighbors each. Let neighbors of $c_{i}$ be
$d_{i1},\ldots,d_{ik}$. Let $S\subseteq\\{c_{1},\ldots,c_{k}\\}$ be those
vertices selected by $ALG$. For those $i\notin S$ we reveal their new
neighbors in order $d_{i1},\ldots,d_{ik}$. Each such $d_{ij}$ is revealed with
a single new neighbor $f_{ij}$. For $i\in S$ we reveal their new neighbors in
order $d_{i1},\ldots,d_{ik}$. Each such $d_{ij}$ is revealed with a new
neighbor $t$ that is common to all these vertices. Then $f_{ij}$ are revealed
in arbitrary order with $t$ as a new neighbor. Lastly $t$ is revealed without
any new neighbors.

Let $p=|S|$. Observe that in addition to these $p$ vertices $ALG$ must select
at least one vertex from each of $\\{d_{ij},f_{ij}\\}$ pairs for those
$i\notin S$; otherwise, vertex $d_{ij}$ would be undominated. Thus, $ALG\geq
p+k(k-p)$. Also, observe that $\\{s,t\\}\cup\\{c_{i}\mid i\notin S\\}$ is a
dominating set, so $OPT\leq k-p+2$. The bound on the competitive ratio is

$\frac{ALG}{OPT}\geq\frac{p+k(k-p)}{k-p+2}=k-\frac{2k-p}{k-p+2}\geq\frac{k}{2},$

where the last inequality is obtained as follows. For $k\geq 2$ we have
$k^{2}-kp\geq 2k-2p$, which implies $k^{2}-kp+2k\geq 4k-2p$. This in turn
implies that $k(k-p+2)\geq 2(2k-p)$, hence $(2k-p)/(k-p+2)\leq k/2$. The
quantitative part of the statement of this theorem follows from the fact that
the total number of vertices is at most $2+k+k^{2}+k(k-p)=\Theta(k^{2})$.

Lastly, we note that the adversarial graph thus constructed is, indeed,
series-parallel. For each $i\notin S$ and $j\in\\{1,\ldots,k\\}$ the path
$c_{i}\rightarrow d_{ij}\rightarrow f_{ij}\rightarrow t$ is a series-
composition of $3$ copies of $K_{2}$. These paths can be merged by a parallel
composition to obtain the subgraph induced on
$\\{c_{i},t\\}\cup\\{d_{ij},f_{ij}\mid j\in\\{1,\ldots,k\\}\\}$ for each
$i\notin S$. Each of these subgraphs is composed at $c_{i}$ with another copy
of $K_{2}$ with the new vertex playing the role of $s$. Similar argument holds
to show that the subgraph induced on $\\{s,c_{i},t\\}\cup\\{d_{ij}\mid
j\in\\{1,\ldots,k\\}\\}$ for $i\in S$ is a two-terminal series-parallel graph.
Lastly, all these subgraphs are merged by a sequence of parallel compositions
at $s$ and $t$.

Figure 19: An instance described in Theorem 4.3 with $k=3$. The top depicts a
prefix where $ALG$ selects $S=\\{c_{1},c_{3}\\}$ whereas the bottom depicts
the completely revealed graph.

##  5 Conclusions

In this paper we studied the minimum dominating set problem in an online
setting where a vertex is revealed alongside all its neighbors. We also
contrasted our results with those obtained by Boyar et al. [3] and Kobayashi
[11] in a related vertex-arrival model. Dominating set is a difficult problem
both offline and online. In our setting, the best achievable competitive ratio
on general graphs is $O(\sqrt{n})$. This observation prompted us to study this
problem with respect to more restrictive graph classes. Trees provide a
natural graph class that usually allows for non-trivial competitive ratios.
Indeed, we showed that in our model trees admit $2$-competitive algorithms.
There are several ways to try to extend this result to larger graph classes.
We considered cactus graphs and showed that the optimal competitive ratio is
$2.5$ on them. Another way of generalizing trees is to consider graphs of
higher treewidth. Unfortunately, once treewidth goes up to $2$, competitive
ratio jumps to $\Omega(\sqrt{n})$ (which is trivial in our setting due to
$O(\sqrt{n})$ upper bound), as witnessed by series-parallel graphs. We also
established non-trivial upper bounds on graphs of bounded degree, as well as
graphs with bounded claws. When one moves to planar (even bipartite planar)
graphs and threshold graphs, the competitive ratio jumps to $\Omega(\sqrt{n})$
again.

The above can be viewed as a larger program of developing a deeper
understanding of the dominating set problem in an online setting. What are the
main structural obstacles in graphs that prohibit online algorithms with small
competitive ratios? Can one discover a family of graphs parameterized by some
parameter $t$, which include cactus graphs, claw-free graphs, and bounded-
degree graphs, such that the competitive ratio scales gracefully with $t$?
Lastly, as another research direction, we mention that we have only considered
the deterministic setting, so it would be of interest to extend our results to
the randomized setting, as well as the setting of online algorithms with
advice.

## References

  * [1] Berge, C.: The Theory of Graphs and Its Applications. Methuen (1962)
  * [2] Borodin, A., El-Yaniv, R.: Online Computation and Competitive Analysis. Cambridge University Press (1998)
  * [3] Boyar, J., Eidenbenz, S.J., Favrholdt, L.M., Kotrbcík, M., Larsen, K.S.: Online dominating set. Algorithmica 81(5), 1938–1964 (2019)
  * [4] Cygan, M., Philip, G., Pilipczuk, M., Pilipczuk, M., Wojtaszczyk, J.O.: Dominating set is fixed parameter tractable in claw-free graphs. Theoretical Computer Science 412(50), 6982–7000 (2011)
  * [5] Das, B., Bharghavan, V.: Routing in ad-hoc networks using minimum connected dominating sets. In: 1997 IEEE International Conference on Communications: Towards the Knowledge Millennium, ICC 1997, Montréal, Québec, Canada, June 8-12, 1997. pp. 376–380. IEEE (1997)
  * [6] Harutyunyan, H.A.: An efficient vertex addition method for broadcast networks. Internet Math. 5(3), 211–225 (2008)
  * [7] Harutyunyan, H.A., Liestman, A.L.: Upper bounds on the broadcast function using minimum dominating sets. Discret. Math. 312(20), 2992–2996 (2012)
  * [8] Haynes, T., Hedetniemi, S., Slater, P.: Fundamentals of Domination in Graphs. Marcel Dekker, New York (1998)
  * [9] Henning, M., Yeo, A.: Total Domination in Graphs. Springer-Verlag New York (2013)
  * [10] King, G., Tzeng, W.: On-line algorithms for the dominating set problem. Inf. Process. Lett. 61(1), 11–14 (1997)
  * [11] Kobayashi, K.M.: Improved bounds for online dominating sets of trees. In: Okamoto, Y., Tokuyama, T. (eds.) 28th International Symposium on Algorithms and Computation, ISAAC 2017, December 9-12, 2017, Phuket, Thailand. LIPIcs, vol. 92, pp. 52:1–52:13. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2017)
  * [12] Komm, D.: An Introduction to Online Computation - Determinism, Randomization, Advice. Texts in Theoretical Computer Science. An EATCS Series, Springer (2016)
  * [13] König, D.: Theorie der Endlichen und Unendlichen Graphen. Chelsea, New York (1950)
  * [14] Ore, O.: Theory of Graphs. American Mathematical Society (1962)
  * [15] Wang, F., Du, D., Cheng, X.: Connected dominating set. In: Encyclopedia of Algorithms, pp. 425–430 (2016)