Online Dominating Set ∗
Joan Boyar 1

Stephan J. Eidenbenz 2
Michal Kotrbčı́k 1

arXiv:1604.05172v1 [] 18 Apr 2016

1

Lene M. Favrholdt 1

Kim S. Larsen 1

University of Southern Denmark, Odense, Denmark

{joan,lenem,kotrbcik,kslarsen}@imada.sdu.dk
2

Los Alamos National Laboratory, Los Alamos, NM, USA
eidenben@lanl.gov

Abstract
This paper is devoted to the online dominating set problem and its variants on trees, bipartite, bounded-degree, planar, and general graphs, distinguishing between connected and
not necessarily connected graphs. We believe this paper represents the first systematic study
of the effect of two limitations of online algorithms: making irrevocable decisions while not
knowing the future, and being incremental, i.e., having to maintain solutions to all prefixes
of the input. This is quantified through competitive analyses of online algorithms against two
optimal algorithms, both knowing the entire input, but only one having to be incremental. We
also consider the competitive ratio of the weaker of the two optimal algorithms against the
other. In most cases, we obtain tight bounds on the competitive ratios. Our results show that
requiring the graphs to be presented in a connected fashion allows the online algorithms to
obtain provably better solutions. Furthermore, we get detailed information regarding the significance of the necessary requirement that online algorithms be incremental. In some cases,
having to be incremental fully accounts for the online algorithm’s disadvantage.

1

Introduction

We consider online versions of a number of NP-complete graph problems, dominating set (DS),
and variants hereof. Given an undirected graph G = (V, E) with vertex set V and edge set E, a
set D ⊆ V is a dominating set for G if for all vertices u ∈ V , either u ∈ D (containment) or there
exists an edge {u, v} ∈ E, where v ∈ D (dominance). The objective is to find a dominating set of
minimum cardinality.
In the variant connected dominating set (CDS), we add the requirement that D be connected (if G
is not connected, D should be connected for each connected component of G). In the variant total
dominating set (TDS), every vertex must be dominated by another, corresponding to the definition
above with the “containment” option removed. We also consider independent dominating set
∗

The first, third, fourth, and fifth authors were supported in part by the Danish Council for Independent Research
and the Villum Foundation.

1

(IDS), where we add the requirement that D be independent, i.e., if {u, v} ∈ E, then {u, v} 6⊆
D. In both this introduction and the preliminaries section, when we refer to dominating set, the
statements are relevant to all the variants unless explicitly specified otherwise.
The study of dominating set and its variants dates back at least to seminal books by König [18],
Berge [3], and Ore [20]. The concept of domination readily lends itself to modelling many conceivable practical problems. Indeed, at the onset of the field, Berge [3] mentions a possible application of keeping all points in a network under surveillance by a set of radar stations, and Liu [19]
notes that the vertices in a dominating set can be thought of as transmitting stations that can transmit messages to all stations in the network. Several monographs are devoted to domination [13],
total domination [14], and connected domination [11], and we refer the reader to these for further
details.
We consider online [5] versions of these problems. More specifically, we consider the vertexarrival model where the vertices of the graph arrive one at a time and with each vertex, the edges
connecting it to previous vertices are also given. The online algorithm must maintain a dominating
set, i.e., after each vertex has arrived, D must be a dominating set for the subgraph given so far.
In particular, this means that the first vertex must always be included in the solution, except for
the case of total dominating set. Since the graph consisting of a single vertex does not have a total
dominating set at all, we allow an online algorithm for TDS to not include isolated vertices in the
solution, unlike the other variants of DS. If the online algorithm decides to include a vertex in the
set D, this decision is irrevocable. Note, however, that not just a new vertex but also vertices given
previously may be added to D at any time. An online algorithm must make this decision without
any knowledge about possible future vertices.
Defining the nature of the irrevocable decisions is a modelling issue, and one could alternatively
have made the decision that also the act of not including the new vertex in D should be irrevocable,
i.e., not allowing algorithms to include already given vertices in D at a later time. The main reason
for our choice of model is that it is much better suited for applications such as routing in wireless
networks for which domination is intensively studied; see for instance [9] and the citations thereof.
Indeed, when domination models a (costly) establishment of some service, there is no reason why
not establishing a service at a given time should have any inherent costs or consequences, such as
preventing one from doing so later. Furthermore, the stricter variant of irrevocability results in a
problem for which it becomes next to impossible for an online algorithm to obtain a non-trivial
result in comparison with an optimal offline algorithm. Consider, for example, an instance where
the adversary starts by giving a vertex followed by a number of neighbors of that vertex. If the
algorithm ever rejects one of these neighbors, the remaining part of the sequence will consist of
neighbors of the rejected vertex and the neighbors must all be selected. This shows that, using
this model of irrevocability, online algorithms for DS or TDS would have to select at least n − 1
vertices, while the optimal offline algorithm selects at most two. For CDS it is even worse, since
rejecting any vertex could result in a nonconnected dominating set. A similar observation is made
in [17] for this model; their focus is on a different model, where the vertices are known in advance,
and all edges incident to a particular vertex are presented when that vertex arrives.
An online algorithm can be seen as having two characteristics: it maintains a feasible solution
at any time, and it has no knowledge about future requests. We also define a larger class of
algorithms: An incremental algorithm is an algorithm that maintains a feasible solution at any
time. It may or may not know the whole input from the beginning.
We analyze the quality of online algorithms for the dominating set problems using competitive
analysis [21, 15]. Thus, we consider the size of the dominating set an online algorithm computes
up against the result obtained by an optimal offline algorithm, O PT.
2

As something a little unusual in competitive analysis, we are working with two different optimal
algorithms. This is with the aim of investigating whether it is predominantly the requirement to
maintain feasible solutions or the lack of knowledge of the future which makes the problem hard.
Thus, we define O PT INC to be an optimal incremental algorithm and O PT OFF to be an optimal offline
algorithm, i.e., it is given the entire input, and then produces a dominating set for the whole graph.
The reason for this distinction is that in order to properly measure the impact of the knowledge of
the future, it is necessary that it is the sole difference between the algorithm and O PT. Therefore,
O PT has to solve the same problem and hence the restriction on O PT INC . While such an attention
to comparing algorithms to an appropriate O PT already exists in the literature, to the best of our
knowledge the focus also on the comparison of different optimum algorithms is a novel aspect of
our work. Previous results requiring the optimal offline algorithm to solve the same problem as
the online algorithm include (1) [6] which considers fair algorithms that have to accept a request
whenever possible, and thus require O PT to be fair as well, (2) [7] which studies k-bounded-space
algorithms for bin packing that have at any time at most k open bins and requires O PT to also
adhere to this restriction, and (3) [4] which analyzes the performance of online algorithms for a
variant of bin packing against a restricted offline optimum algorithm that knows the future, but has
to process the requests in the same order as the algorithm under consideration.
Given an input sequence I and an algorithm A LG, we let A LG(I) denote the size of the dominating
set computed by A LG on I, and we define A LG to be c-competitive if there exists a constant α
such that for all input sequences I, A LG(I) ≤ c O PT(I) + α, where O PT may be O PT INC or
O PT OFF , depending on the context. The (asymptotic) competitive ratio of A LG is the infimum over
all such c and we denote this CRINC (A LG) and CROFF (A LG), respectively. In some results, we use
the strict competitive ratio, i.e., the inequality above holds without an additive constant. For these
results, when the strict result is linear in n, we write the asymptotic competitive ratio in Table 2
without any additive constant.
We consider the four dominating set problem variants on various graph types, including trees,
bipartite, bounded-degree (letting ∆ denote the maximum degree), and to some extent planar
graphs. In all cases, we also consider the online variant where the adversary is restricted to giving
the vertices in such a manner that the graph given at any point in time is connected. In this case,
the graph is called always-connected. One motivation is that graphs in applications such as routing
in networks are most often connected. The connectivity assumption allows us to obtain provably
better bounds on the performance of online algorithms, at least compared to O PT OFF , and these
bounds are of course more meaningful for the relevant applications.
The results for online algorithms are summarized in Tables 1 and 2. The results for O PT INC against
O PT OFF are identical to the results of Table 2, except that for DS on trees, CROFF (O PT INC ) = 2 and
for DS on always-connected planar graphs, CROFF (O PT INC ) = dn/2e. The results are discussed
in the conclusion.
Graph class

DS

Trees

[n/4, n/2]

IDS

1

n/4

Always-connected bipartite
Always-connected bounded degree

TDS
1

2

Bipartite
Bounded degree

CDS

[∆
2 ; ∆ + 1]

[∆
2 ; ∆]
[∆
2 ; ∆ − 1]

[∆
2 ; ∆]

Table 1: Bounds on the competitive ratio of any online algorithm with respect to O PT INC .
3

Graph class
Trees

DS

CDS

TDS

[2; 3]

1

2

n

Bipartite

n/2

IDS
n

n/2

Always-connected bipartite
Bounded degree

[∆; ∆ + 1]

∆+1

Always-connected bounded degree

[∆
2 ; ∆ + 1]

[∆ − 2; ∆ − 1]

Planar

n

[∆ − 1; ∆]
n/2

∆
[∆ − 1; ∆]
n

Always-connected planar
Table 2: Bounds on the competitive ratio of any online algorithm with respect to O PT OFF .

2

Preliminaries

Since we are studying online problems, the order in which vertices are given is important. We
assume throughout the paper that the indices of the vertices of G, v1 , . . . , vn , indicate the order
in which they are given to the online algorithm, and we use A LG(G) to denote the size of the
dominating set computed by A LG using this ordering. When no confusion can occur, we implicitly
assume that the dominating set being constructed by an online algorithm A LG is denoted by D.
We use the phrase select a vertex to mean that the vertex in question is added to the dominating
set in question. We use Gi to denote the subgraph of G induced by {v1 , . . . , vi }. We let Di denote
the dominating set constructed by A LG after processing the first i vertices of the input. When
no confusion can occur, we sometimes implicitly identify a dominating set D and the subgraph
it induces. For example, we may say that D has k components or is connected, meaning that the
subgraph of G induced by D has k components or is connected, respectively.
Online algorithms must compute a solution for all prefixes of the input seen by the algorithm.
Given the irrevocable decisions, this can of course affect the possible final sizes of a dominating
set. When we want to emphasize that a bound is derived under this restriction, we use the word
incremental to indicate this, i.e., if we discuss the size of an incremental dominating set D of G,
this means that D1 ⊆ D2 ⊆ · · · ⊆ Dn = D and that Di is a dominating set of Gi for each i. Note
in particular that any incremental algorithm, including O PT INC , for DS, CDS, or IDS must select
the first vertex.
Throughout the text, we use standard graph-theoretic notation. In particular, the path on n vertices
is denoted Pn . A star with n vertices is the complete bipartite graph K1,n−1 . A leaf is a vertex of
degree 1, and an internal vertex is a vertex of degree at least 2. We use c(G) to denote the number
of components of a graph G. The size of a minimum dominating set of a graph G is denoted
by γ(G). We use indices to indicate variants, using γC (G), γT (G), and γI (G) for connected, total,
and independent dominating set, respectively. This is an alternative notation for the size computed
by O PT OFF . We also use these indices on O PT INC to indicate which variant is under consideration.
We use ∆ to denote the maximum degree of the graph under consideration. Similarly, we always
let n denote the number of vertices in the graph.
In many of the proofs of lower bounds on the competitive ratio, when the path, Pn , is considered,
either as the entire input or as a subgraph of the input, we assume that it is given in the standard
order, the order where the first vertex given is a leaf, and each subsequent vertex is a neighbor of
4

the vertex given in the previous step. When the path is a subgraph of the input graph, we often
extend this standard order of the path to an adversarial order of the input graph – a fixed ordering
of the vertices that yields an input attaining the bound.
In some online settings, we are interested in connected graphs, where the vertices are given in
an order such that the subgraph induced at any point in time is connected. In this case, we use
the term always-connected, indicating that we are considering a connected graph G, and all the
partial graphs Gi are connected. We implicitly assume that trees are always-connected and we
drop the adjective. Since all the classes we consider are hereditary (that is, any induced subgraph
also belongs to the class), no further restriction of partial inputs Gi is necessary. In particular,
these conventions imply that for trees, the vertex arriving at any step (except the first) is connected
to exactly one of the vertices given previously, and since we consider unrooted trees, we can think
of that vertex as the parent of the new vertex.

3

The Cost of Being Online

In this section we focus on the comparison of algorithms bound to the same irrevocable decisions. We do so by comparing any online algorithm with O PT INC and O PT OFF , investigating the
role played by the (absence of) knowledge of the future. We start by using the size of a given
dominating set to bound the sizes of some connected or incremental equivalents.
Theorem 1. Let G be always-connected, let S be a dominating set of G, and let R be an incremental dominating set of G. Then the following hold:
1. There is a connected dominating set S 0 of G such that |S 0 | ≤ |S| + 2(c(S) − 1).
2. There is an incremental connected dominating set R0 of G such that |R0 | ≤ |R| + c(R) − 1.
3. If G is a tree, there is an incremental dominating set R00 of G such that |R00 | ≤ |S| + c(S).
Moreover, all three bounds are tight for infinitely many graphs.
Proof. Let S be any dominating set of G. We argue that by selecting additionally at most 2(c(S)−
1) vertices, we can connect all the components in S. We do this inductively. If there are two
components separated by a path of at most two unselected vertices, we select all the vertices on
this path and continue inductively. Otherwise, assume to the contrary that all pairs of components
require the selection of at least three vertices to become connected. We choose a shortest such
path of length k consisting of vertices u1 , . . . , uk , where ui is dominated by a component Ci for
all i. If C1 6= C2 , we can connect them by selecting u1 and u2 , which would be a contradiction.
If C1 = C2 , then we have found a shorter path between C1 and Ck ; also a contradiction. We
conclude that |S 0 | ≤ |S| + 2(c(S) − 1), which proves 1.
To see that the bound is tight, consider a path Pn in the standard order, where n ≡ 0 (mod 3).
Clearly, the size of a minimum dominating set S of Pn is n/3 and c(S) = n/3. On the other hand,
the size of any minimum connected dominating set of Pn is n − 2 and n − 2 = |S| + 2(c(S) − 1).
To prove 2., we label the components of R in the order in which their first vertices arrive. Thus,
let C1 , . . . , Ck be the components of R, and, for 1 ≤ i ≤ k, let vji be the first vertex of Ci that
arrives. Assume that vji arrives before vji+1 for each i = 1, . . . , k − 1. We prove that for each
component Ci of R, there is a path of length 2 joining vji with Ch in Gji for some h < i, i.e.,
a path with only one vertex not belonging to either component. Let P = vl1 , . . . , vlm , vji be a
5

shortest path in Gji connecting vji and some component Ch , h < i, and assume for the sake of
contradiction that m ≥ 3. In Gji , the vertex vl3 is not adjacent to a vertex in any component Ch0 ,
where h0 < i, since in that case a shorter path would exist. However, since vertices cannot be
unselected as the online algorithm proceeds, it follows that in Gl3 , vl3 is not dominated by any
vertex, which is a contradiction. Thus, selecting just one additional vertex at the arrival of vij
connects Ci to an earlier component, and the result follows inductively. To see that the bound is
tight, observe that the optimal incremental connected dominating set of Pn has n − 1 vertices,
while for even n, there is an incremental dominating set of size n/2 with n/2 components.
To obtain 3., consider an algorithm A LG processing vertices greedily, while always selecting all
vertices from S. That is, v1 and all vertices of S are always selected, and when a vertex v not in S
arrives, it is selected if and only if it is not dominated by already selected vertices, in which case
it is called a bad vertex. Clearly, A LG produces an incremental dominating set, R00 , of G.
To prove the upper bound on |R00 |, we gradually mark components of S. For a bad vertex vi , let
v be a vertex from S dominating vi , and let C be the component of S containing v. Mark C. To
prove the claim it suffices to show that each component of S can be marked at most once, since
each bad vertex leads to some component of S being marked.
Assume for the sake of contradiction that some component, C, of S is marked twice. This happens
because a vertex v of C is adjacent to a bad vertex b, and a vertex v 0 (not necessarily different from
v) of C is adjacent to some later bad vertex b0 . Since G is always-connected and b0 was bad, b and
b0 are connected by a path not including v 0 . Furthermore, v and v 0 are connected by a path in C.
Thus, the edges {b, v} and {b0 , v 0 } imply the existence of a cycle in G, contradicting the fact that
it is a tree.
To see that the bound is tight, let v1 , . . . , vm , m ≡ 2 (mod 6), be a path in the standard order. Let
G be obtained from Pm by attaching m pendant vertices (new vertices of degree 1) to each of the
vertices v2 , v5 , v8 , . . . , vm , where the pendant vertices arrive in arbitrary order, though respecting
that G should be always-connected. Each minimum incremental dominating set of G contains
each of the vertices v2 , v5 , v8 , . . . , vm , the vertex v1 , and one of the vertices v3i and v3i+1 for
each i, and thus it has size 2(m + 1)/3. On the other hand, the vertices v2 , v5 , v8 , . . . , vm form a
dominating set S of G with c(S) = (m + 1)/3.
Theorem 1 is best possible in the sense that none of the assumptions can be omitted. Indeed,
Proposition 21 implies that it is not even possible to bound the size of an incremental (connected)
dominating set in terms of the size of a (connected) dominating set, much less to bound the size of
an incremental connected dominating set in terms of the size of a dominating set. Therefore, 1. and
2. in Theorem 1 cannot be combined even on bipartite planar graphs. The situation is different for
trees: Corollary 10 1. essentially leverages the fact that any connected dominating set D on a tree
can be produced by an incremental algorithm without increasing the size of D.
Proposition 2. For any graph G, there is a unique incremental independent dominating set.
Proof. We fix G and proceed inductively. The first vertex has to be selected due to the online
requirement. When the next vertex, vi+1 , is given, if it is dominated by a vertex in Di , it cannot be
selected, since then Di+1 would not be independent. If vi+1 is not dominated by a vertex in Di ,
then vi+1 or one of its neighbors must be selected. However, none of vi+1 ’s neighbors can be
selected, since if they were not selected already, then they are dominated, and selecting one of
them would violate the independence criteria. Thus, vi+1 must be selected. In either case, Di+1 is
uniquely defined.
6

Since a correct incremental algorithm is uniquely defined by this proposition by a forced move in
every step, O PT INC must behave exactly the same. This fills the column for independent dominating set in Table 1.
We let PARENT denote the following algorithm for trees. The algorithm selects the first vertex.
When a new vertex v arrives, if v is not already dominated by a previously arrived vertex, then the
parent vertex that v is adjacent to is added to the dominating set. For connected dominating set on
trees, PARENT is 1-competitive, even against O PT OFF :
Proposition 3. For any tree T , PARENT(T ) outputs a connected dominating set of T and
(
PARENT(T ) =

γC (T ) + 1 if v1 is a leaf of T
γC (T )

otherwise.

Proof. For trees with at least two vertices, PARENT selects the internal vertices plus at most one
leaf. Clearly, the size of the minimal connected dominating set of any tree T equals the number of
its internal vertices.
To show that for total dominating set on trees, PARENT is also 1-competitive against O PT INC , we
prove the following:
Lemma 4. For any incremental total dominating set D for an always-connected graph G, all Di
are connected.
Proof. For the sake of a contradiction, suppose that for some i, the set Di induces a subgraph of G
with at least two components, and let i be the smallest index with this property. It follows that the
vertex vi constitutes a singleton component of the subgraph induced by Di . Thus, vi cannot be
dominated by any other vertex of Di , contradicting that the solution was incremental.
Corollary 5. For any tree T on n vertices,
(
INC

INC

O PTT (T ) = O PTC (T ) =

int(T ) + 1 if v1 is a leaf of T
int(T )

otherwise,

where int(T ) is the number of internal vertices of T . Consequently, when given in the standard
INC
order O PTC
(Pn ) = O PTTINC (Pn ) = n − 1 for every n ≥ 3.
Proposition 6. For any positive integer n and Pn given in the standard order, O PT INC (Pn ) =
dn/2e.
Proof. Clearly, Pn admits an incremental dominating set of size dn/2e, consisting of every second
vertex, starting with v1 . Assume to the contrary that Pn has an incremental dominating set D such
that |D| ≤ dn/2e − 1. Since c(D) ≤ |D|, Theorem 1 2. implies that there is an incremental
connected dominating set C of Pn such that |C| ≤ |D| + c(D) − 1 ≤ 2dn/2e − 3 ≤ n − 2, which
contradicts Corollary 5.
Proposition 7. For any online algorithm A LG for dominating set and for any n > 0, there is a
tree T with n vertices such that the dominating set constructed by A LG for T contains at least
n − 1 vertices.
7

Proof. We prove that the adversary can maintain the invariant that at most one vertex is not included in the solution of A LG. The algorithm has to select the first vertex, so the invariant holds
initially. When presenting a new vertex vi , the adversary checks whether all vertices given so far
are included in A LG’s solution. If this is the case, vi is connected to an arbitrary vertex, and the
invariant still holds. Otherwise, vi is connected to the unique vertex not included in Di−1 . Now vi
is not dominated, so A LG must select an additional vertex.
Proposition 8. For any always-connected bipartite graph G, the smaller partite set of G (plus,
possibly, the vertex v1 ) forms an incremental dominating set.
Proof. The smaller partite set S of any connected bipartite graph G is a dominating set of G. If the
first presented vertex v1 belongs to S, then S is an incremental dominating set of G. Otherwise,
S ∪ {v1 } is an incremental dominating set of G.
As a corollary of Proposition 7 and Proposition 8, we get the following result.
Corollary 9. For any online algorithm A LG for DS on trees, CRINC (A LG) ≥ 2.
Corollary 10. For trees, the following hold.
1. For DS, CRINC (PARENT) = 2 and CROFF (PARENT) = 3.
2. For CDS, CRINC (PARENT) = CROFF (PARENT) = 1.
3. For TDS, CRINC (PARENT) = 1 and CROFF (PARENT) = 2.
We extend the PARENT algorithm for graphs that are not trees as follows. When a vertex vi , i > 1,
arrives, which is not already dominated by one of the previously presented vertices, PARENT
selects any of the neighbors of vi in Gi .
Proposition 11. For any always-connected graph G, the set computed by PARENT on G is an
incremental connected dominating set of G.
Proof. We prove the claim by induction on n. Since PARENT always selects v1 , the statement
holds for n = 1. Consider the graph Gi , for some i > 1, and assume that Di−1 is an incremental
connected dominating set of Gi−1 . If vi is already dominated by a vertex in Di−1 , then PARENT
keeps D unchanged (that is, Di = Di−1 ) and thus Di is an incremental connected dominating
set of Gi . If vi is not dominated by Di−1 , then PARENT chooses a neighbor v of vi in Gi−1 .
Clearly, this implies that Di is an incremental dominating set of Gi . Since Di−1 is an incremental
connected dominating set of Gi−1 and the vertex v is adjacent to the only component of Di−1 , Di
is connected, which concludes the proof.
Proposition 12. For DS and CDS on always-connected bipartite graphs, CROFF (PARENT) ≤ n/2.
Proof. If γC (G) ≥ 2, then there is nothing to prove. Therefore, we assume that there is a single
vertex v adjacent to every other vertex. Since G is bipartite, there is no edge between any of the
vertices adjacent to v, so G is a star. Since Gi is connected for each i, the vertex v arrives either as
the first or the second vertex. Furthermore, if another vertex arrives after v, then v is selected by
PARENT. Once v is selected, all future vertices are already dominated by v, so no more vertices
are selected, implying that PARENT(G) ≤ 2, which concludes the proof.
Proposition 13. Let G be a graph with n vertices and maximum degree ∆. For any graph G,
γC (G) ≥ γ(G) ≥ n/(∆ + 1) and γT (G) ≥ n/∆.
8

Proof. Clearly, any vertex can dominate at most itself and its at most ∆ neighbors. For total
dominating set, a vertex can only dominate its at most ∆ neighbors.
Proposition 13 implies that any algorithm computing an incremental dominating set is no worse
than (∆ + 1)-competitive.
Corollary 14. For any algorithm A LG for DS, CROFF (A LG) ≤ ∆ + 1. Furthermore, for any
algorithm A LG for TDS, CROFF (A LG) ≤ ∆.
Proposition 15. For any algorithm A LG for CDS, CROFF (A LG) ≤ ∆ − 1.
Proof. Let D be a minimum connected dominating set of G with |D| = k. Since D is connected,
any spanning tree of the subgraph induced by D contains k −1 edges and each endpoint is adjacent
to the other endpoint in the spanning tree, so the vertices of D are altogether adjacent to at least
2k − 2 vertices in G. Thus, there are at most k∆ − (2k − 2) vertices not in D which D dominates,
giving n ≤ k∆ − k + 2 = k(∆ − 1) + 2 vertices in G. It follows that γC (G) ≥ (n − 2)/(∆ − 1)
and thus, for any incremental algorithm A LG for CDS, CROFF (A LG) ≤ ∆ − 1.
The next proposition follows from the fact that on always-connected graphs with γ(G) = 1 with
at least four vertices, PARENT selects at most n − 2 vertices.
Proposition 16. For DS and CDS on always-connected graphs, for n ≥ 4, the inequality
CROFF (PARENT) ≤ n − 2
holds for the strict competitive ratio.
Proof. We need to consider only the case of γ(G) = 1, since otherwise there is nothing to prove,
and thus there is a vertex v adjacent to every other vertex of G. Since after the arrival of any
vertex, PARENT increases the size of the dominating set by at most one, it suffices to prove that,
immediately after some vertex has been processed, there are two vertices not selected by PARENT.
First note that once v is selected, PARENT does not select any other vertex and thus we can assume
that v is not the first vertex. Suppose that v arrives after vi , i ≥ 2. The vertex vi has not yet been
selected when v arrives, and v is dominated by v1 , so there are two vertices not selected. The last
remaining case is when v arrives as the second vertex. In this case we distinguish whether v3 is
adjacent to v1 , or not. If v3 is adjacent to v1 , then v is not selected, there are two vertices not
selected (v and v3 ), and we are done. If v3 is not adjacent to v1 , then PARENT selects v when v3
arrives. No further vertex will be added to the dominating set, concluding the proof.
In the next result and in Proposition 20 in Section 4 we use layers in an always-connected graph
G defined by letting L assign layer numbers to vertices in the following manner. Let L(v1 ) = 0
and for i > 1, L(vi ) = 1 + min {L(vj ) | vj is a neighbor of vi in Gi }.
Our next aim is to show that for always-connected bipartite graphs, there is an n/4-competitive
algorithm against O PT INC . This is achieved by considering the following first parent algorithm, denoted F IRST PARENT, which generalizes PARENT. For DS and CDS, the algorithm F IRST PARENT
always selects v1 and for each vertex vi , i > 1, if vi is not dominated by one of the already selected vertices, it selects a neighbor of vi with the smallest layer number. For TDS, we add the
following to F IRST PARENT, so that the dominating set produced is total: If, when vi arrives, vi
and vj (j < i) are the only vertices of a component of size 2, then besides vj , F IRST PARENT also
selects vi .
9

Theorem 17. For DS, CDS, and TDS on always-connected bipartite graphs, we have
CRINC (F IRST PARENT) ≤ n/4
for n ≥ 4.
Proof. We consider DS and CDS first. Since F IRST PARENT is an instantiation of PARENT, Proposition 11 implies that the incremental dominating set constructed by F IRST PARENT is connected.
Therefore, the fact that for any graph G with at least three vertices O PT INC (G) ≤ O PTTINC (G) ≤
INC
O PTC
(G) + 1 implies that it is sufficient to prove that F IRST PARENT is n/4-competitive against
INC
O PT . Furthermore, we only need to consider the case O PT INC (G) < 4, since otherwise
F IRST PARENT is trivially n/4-competitive. Since G is bipartite, there are no edges between vertices of a single layer. Our first aim is to bound the number of layers.
Claim: If O PT INC (G) < 4, then G has at most 6 layers.
To establish the claim, we prove that if an always-connected graph G has 2k + 1 layers, then
O PT INC (G) > k. For the sake of contradiction, suppose that there exist graphs G that are alwaysconnected with 2k + 1 layers such that O PT INC (G) ≤ k, and among all such graphs choose one,
G, with the smallest number of vertices. Since any dominating set contains at least one vertex,
we have k ≥ 1. Let D be an incremental dominating set of G with |D| ≤ k and let l be the
largest integer such that Gl has 2k − 1 layers. Since G is the smallest counterexample, we have
O PT INC (Gl ) ≥ k. Recall that Dl is defined as D∩Gl . The fact that D is an incremental dominating
set implies that Dl is a dominating set of Gl . We claim that |Dl | = k, since otherwise Dl would be
an incremental dominating set of Gl with |Dl | < k, contradicting the fact that O PT INC (Gl ) ≥ k.
The fact that |Dl | = k is equivalent to D ⊆ V (Gl ) and, in particular, L(v) ≤ 2k − 1 for each
vertex v from D. Let w be a vertex of G such that L(w) = 2k + 1, such a vertex exists since G
has 2k + 1 layers. By the definition of layers the vertex w does not have a neighbor in any of the
first 2k − 1 layers and thus is not adjacent to any vertex of D, contradicting the fact that D is a
dominating set of G. This concludes the proof of the claim.
In the rest of the proof, we distinguish several cases according to the number of layers of G. If there
are at most two layers, then F IRST PARENT selects only the root v1 and the result easily follows.
Let li denote the size of the i-th layer and si the number of vertices selected by F IRST PARENT from
the i-th layer. For convenience, we will ignore the terms s0 and l0 , both of which are one, which
is viable since we are dealing with the asymptotic competitive ratio. Because F IRST PARENT can
add a vertex from the i-th layer to the dominating set only when a (non-dominated) vertex from
the (i + 1)-st layer arrives, we have
si ≤ li+1 .
(Ai)
Clearly,
si ≤ li .

(Bi)

The letter i in equations (A) and (B) indicates the layer for which the equation is applied. If there
are precisely three layers, then O PT INC (G) ≥ 2 and we must prove that s1 + s2 ≤ n/2. However,
s2 = 0, and s1 /2 ≤ l1 /2 by (B1) and s1 /2 ≤ l2 /2 by (A1). Adding the last two inequalities
yields s1 ≤ l1 /2 + l2 /2 = n/2, as required.
We use the same idea as for three layers also in the cases of four and five layers, albeit the counting
is slightly more complicated. First we deal separately with the case where O PT INC (G) = 2,
and, consequently, there are four layers. Note that the two vertices in the optimal solution are
necessarily in layers 0 and 2, and it follows that l2 = 1. Furthermore, (A1) implies that s1 ≤ 1
and (B2) implies that s2 ≤ 1. Since s3 = 0, F IRST PARENT always selects at most 3 vertices,
which yields the desired result. Assume now that O PT INC (G) ≥ 3 and therefore, our aim is to
10

prove that F IRST PARENT(G) ≤ 3n/4. Adding 1/4 times (A1), 3/4 times (B1), 1/2 times (A2),
and 1/2 times (B2) yields
s1 + s2 ≤ 3l1 /4 + 3l2 /4 + l3 /2.
(1)
If there are four layers, then s3 = 0 and the right-hand side of (1) satisfies 3l1 /4 + 3l2 /4 + l3 /2 ≤
3(l1 + l2 + l3 )/4 = 3n/4, which yields the desired result. If there are five layers, we add 3/4
times (A3) and 1/4 times (B3) to (1), which gives s1 + s2 + s3 ≤ 3(l1 + l2 + l3 + l4 )/4 = 3n/4,
as required. The last remaining case is that of six layers and O PT INC (G) = 3, which is dealt with
similarly to that of four layers and O PT INC (G) = 2. In particular, the vertices selected by O PT INC
necessarily lie in layers 0, 2, and 4, and thus l0 = l2 = l4 = 1. Now observing that s5 = 0 and
adding (Bi) for all even i to (Ai) for i = 1 and i = 3 yields that F IRST PARENT(G) ≤ 5, which
implies the result in the always-connected case.
For TDS, the additional vertices accepted by F IRST PARENT must by accepted by any incremental
online algorithm, so the result also holds for TDS.
Proposition 18. For DS, CDS, and TDS, we have CRINC (F IRST PARENT) ≤ n/2 for n ≥ 2.
Proof. Since for any graph, F IRST PARENT constructs an incremental dominating set, we need to
INC
consider only the cases where O PT INC (G) ≤ 1, O PTC
(G) ≤ 1, and O PTTINC (G) ≤ 1. For TDS,
either G has no edges, in which case the empty set of vertices is a feasible solution constructed
both by O PTTINC and F IRST PARENT, or G contains an edge, in which case O PTTINC (G) ≥ 2 and
INC
the bound follows. Since O PT INC (G) ≤ O PTC
(G), it is sufficient to consider the case where
INC
O PT (G) = 1. If, at any point, Gi has more than one component, then O PT INC (Gi ) ≥ 2. Thus,
if O PT INC (Gi ) = 1, G is a star and is always-connected. Thus, the center vertex must arrive as
either the first or second request, so F IRST PARENT(G) ≤ 2 ≤ n.

Figure 1: A two-layer construction; the minimum connected dominating set is depicted in red
(Proposition 19).

Proposition 19. For any online algorithm A LG for DS, CDS, or TDS on always-connected bipartite graphs, CRINC (A LG) ≥ n/4 and CRINC (A LG) ≥ ∆/2.
Proof. We prove that for any online algorithm A LG for DS, CDS, or TDS and for any integer
∆ ≥ 2, there is a bipartite graph G with maximum degree ∆ such that A LG(G) = ∆ ≥ n/2
INC
and O PT INC (G) = O PTC
(G) = O PTTINC (G) = 2. Consider the graph consisting of a root v,
∆ vertices u1 , . . . , u∆ adjacent to the root and constituting the first layer, and an additional ∆ −
1 vertices w1 , . . . , w∆−1 , which will be given in that order, constituting the second layer, with
adjacencies as follows: For i = 1, . . . , ∆ − 1, the i-th vertex wi of the second layer is adjacent to
∆−i+1 vertices of the first layer in such a way that we obtain the following strict set containment
of sets of neighbors of these vertices: N (wi ) ⊃ N (wi+1 ) for all i = 1, . . . , ∆ − 2. An example
of this construction for ∆ = 4 is depicted in Figure 1. After the entire first layer is presented to
the algorithm, the vertices of the first layer are indistinguishable to the algorithm and D∆+1 does
not necessarily contain more than one vertex. For each i = 1, . . . , ∆ − 1, the neighbors of wi are
chosen from the first layer in such a way that N (wi−1 ) ⊃ N (wi ), the degree of wi is ∆−i+1, and
11

N (wi ) contains as many vertices not contained in the dominating set constructed by A LG so far as
possible. Consider the situation when the vertex wi arrives. It is easy to see that if the set N (wi )
does not contain a vertex from the dominating set constructed so far, then A LG must select at least
one additional vertex at this time. The last observation implies that A LG selects at least ∆ − 1
vertices from the first and second layer, plus the root.
Since there is a vertex u in the first layer that is adjacent to all vertices in the second layer, {u, v}
is an incremental connected dominating set of G, which concludes the proof.

4

The Cost of Being Incremental

This section is devoted to comparing the performance of incremental algorithms and O PT OFF .
Since O PT OFF performs at least as well as O PT INC and O PT INC performs at least as well as any
online algorithm, each lower bound in Table 2 is at least the maximum of the corresponding lower
bound in Table 1 and the corresponding lower bound for CROFF (O PT INC ). Similarly, each upper
bound in Table 1 and corresponding upper bound for CROFF (O PT INC ) is at least the corresponding
upper bound in Table 2. In both cases, we mention only bounds that cannot be obtained in this
way from cases considered already.
The following result, which improves bounds of Proposition 16, generalizes the idea of Proposition 8.
Proposition 20. For DS on always-connected graphs, CROFF (O PT INC ) ≤ n/2.
Proof. For a fixed ordering of G, consider the layers L(v) assigned to vertices of G. It is easy to
see that the set of vertices in the even layers is an incremental solution for DS and similarly for the
set of vertices in odd layers plus the vertex v1 . Therefore, O PT INC can select the smaller of these
two sets, which necessarily has at most n/2 vertices.
Proposition 21. The following hold for the strict competitive ratio. For DS on bipartite planar
graphs, CROFF (O PT INC ) ≥ n − 1 and CROFF (O PT INC ) ≥ ∆. For CDS on bipartite planar graphs,
CROFF (O PT INC ) ≥ n.
Proof. We prove that for each ∆ ≥ 3, i > 0, and n = i(∆ + 1), there is a bipartite planar graph G
INC
with n vertices and maximum degree ∆ such that O PT INC (G) = n∆/(∆ + 1), O PTC
(G) = n,
and γ(G) = γC (G) = n/(∆ + 1). Let G consist of i disjoint copies of the star on ∆ + 1
vertices, with the center of each star arriving as the last vertex among the vertices of that particular
star. Clearly, γ(G) = γC (G) = n/(∆ + 1). On the other hand, any incremental dominating
set has to contain every vertex, except the last vertex of each star, since all these vertices are
pairwise nonadjacent. In addition, any incremental connected dominating set has to contain the
centers of the stars to preserve connectedness of the solution in each component. It follows that
for dominating set, O PT INC selects n∆/(∆ + 1) vertices, which proves the claim for boundeddegree graphs. For connected bipartite planar graphs, setting ∆ = n − 1 and i = 1 in the above
construction gives the result for both dominating set and connected dominating set.
Proposition 22. For IDS and for the strict competitive ratio,
CROFF (O PT INC ) ≥ ∆ and CROFF (O PT INC ) ≥ n − 1.
Proof. Let G be a star K1,∆ , ∆ ≥ 2, where v2 is the unique vertex of degree ∆. Clearly, γI (G) =
1. Since v1 is always selected by any algorithm constructing an incremental solution, the vertex
12

v2 cannot be selected. Consequently, all n − 1 = ∆ vertices of degree 1 have to be selected in the
dominating set, which proves the lower bound of the first part.
To prove the upper bound, consider any graph G and let S = {s1 , . . . , sk } be an independent
dominating set of G with size k = γI (G). Let Ri be a set of vertices being dominated by si
for each i, where Ri are pairwise disjoint. Let Ri0 be the set Ri \ {si }. For each i, the vertex si
is in D if and only if all the vertices of Ri0 are not in D. It follows that |D|/|S| is bounded by
the maximum size of Ri0 , which is ∆, concluding the proof of the upper bound. The second part
follows from the first by choosing ∆ = n − 1 for each n ≥ 3.
Proposition 23. For IDS on always-connected graphs, ∆ − 1 ≤ CROFF (O PT INC ) ≤ ∆.
Proof. The upper bound follows from Proposition 22. To prove the lower bound, consider a path
Pn in the standard order, with ∆ − 2 vertices of degree 1 attached to vi for each even i, where
the vertices of degree 1 arrive after all the vertices of the path. The even vertices vi are centers
of stars of degree ∆. Furthermore, any incremental algorithm for IDS on a path in the standard
order selects exactly the odd vertices of the path and thus also select all the vertices of degree 1.
Let k = bn/2c. It follows that O PT INC selects k∆ − (k − 1) vertices, while the optimal offline
solution has size k, which implies the result.
Theorem 1 3. implies the following bound on the performance of O PT INC on trees.
Corollary 24. For DS on trees, CROFF (O PT INC ) ≤ 2.
A fan of degree ∆ is the graph obtained from a path P∆ by addition of a vertex v that is adjacent
to all vertices of the path, as in Figure 2. The adversarial order of a fan is defined by the standard
order of the underlying path, followed by the vertex v.
Proposition 25. For always-connected planar graphs (and, thus, also on general planar graphs),
the following strict competitive ratio results hold.
• For DS, CROFF (O PT INC ) ≥ n/2.
• For CDS, CROFF (O PT INC ) ≥ n − 2.
• For TDS, CROFF (O PT INC ) ≥ n/2 − 1.
Proof. Let G be a fan of degree ∆, where n = ∆ + 1, in the adversarial order. We prove that
INC
O PT INC (G) = n/2, O PTC
(G) = O PTTINC (G) = n − 2, γ(G) = γC (G) = 1, and γT (G) = 2.
Since Gn−1 induces a path, by Proposition 6 the size of any incremental dominating set of G is at
least n/2. Similarly, Corollary 5 implies the size of any incremental connected (total) dominating
set of G is at least n − 2. Moreover, it is easy to see that there is an incremental solution of size
exactly n − 2 for all considered problems. On the other hand, vn forms a connected dominating
set of size 1, and vn with, say, v1 , form a total dominating set of size 2, which concludes the
proof.
An alternating fan with k fans of degree ∆ consists of k copies of the fan of degree ∆, where the
individual copies are joined in a path-like manner by identifying some of the vertices of degree 2,
as in Figure 2. Thus, n = k(∆ + 1) − (k − 1) and k = (n − 1)/∆. The adversarial order of an
alternating fan is defined by the concatenation of the adversarial orders of the underlying fans.
Proposition 26. For DS on always-connected graphs, CROFF (O PT INC ) ≥ (∆ − 1)/2.
13

Figure 2: A fan with ∆ = 4 (left; Proposition 25) and an alternating fan with k = 3 and ∆ = 4
(right; Proposition 26).

Proof. Let G be an alternating fan with k fans of degree ∆ for any ∆ ≥ 4 given in the adversarial
order. We prove that O PT INC (G) > (∆ − 1)n/(2∆) and γ(G) = (n − 1)/∆. (In Figure 2,
the vertices belonging to the dominating set are red.) Since, by Proposition 6, any incremental
dominating set on a path P in the standard order has at least d|V (P )|e vertices, O PT INC must select
at least d(n−k)/2e vertices of G. Inserting k = (n−1)/∆ into (n−k)/2 gives (n(∆−1)+1)/2.
into the results above proves the proposition.
A modular bridge of degree ∆ with k sections, where k is even, is the graph obtained from a path
on k(∆ − 1) vertices, with an additional k chord vertices. There is a perfect matching on the
chord vertices u1 , . . . , uk with u2i is adjacent to u2i−1 for all i = 1, . . . , k/2. Furthermore, the
i-th chord vertex is adjacent to the vertices of the i-th section; see Figure 3 for an example. The
adversarial order of a modular bridge is defined by the standard order of the path, followed by the
chord vertices in any order.

Figure 3: A modular bridge with k = 4 and ∆ = 5 (Proposition 27).

Proposition 27. For TDS on always-connected graphs, CROFF (O PT INC ) ≥ ∆ − 1.
Proof. Let G be a modular bridge of degree ∆ with k sections given in the adversarial order. Let
m = k(∆ − 1). Since Gm is a path, by Corollary 5, we have A LG(G) ≥ k(∆ − 1) − 1. Clearly,
γT (G) ≤ k.
A bridge of degree ∆ with k sections is obtained from a modular bridge of degree ∆ − 1 with k
sections by joining vertices u2i and u2i+1 by an edge for each i = 1, . . . , k/2 − 1; see Figure 4
for an example. The adversarial order of a bridge is identical with the adversarial order of the
underlying modular bridge.

Figure 4: A bridge with k = 4 and ∆ = 6 (Proposition 28).

Proposition 28. For CDS on always-connected graphs, CROFF (O PT INC ) ≥ ∆ − 2.
Proof. Let G be a bridge of degree ∆ with k sections, given in the adversarial order. Let m =
k(∆ − 2). Since Gm induces a path, we have A LG(G) ≥ A LG(Gm ) = k(∆ − 2) − 1, by
Corollary 5. The chord vertices form a connected dominating set of G and, thus, γC (G) ≤ k.
14

A rotor of degree ∆, where ∆ ≥ 2 is even, is a graph obtained from a star, K1,∆ , on ∆ + 1 vertices
by adding the edges of a perfect matching on the pendant vertices, as in Figure 5. The adversarial
order of a rotor G of degree ∆ is any fixed order such that G2i is a graph with a perfect matching
for each i = 1, . . . , ∆/2 and the central vertex of the original star is the last vertex to arrive.
Proposition 29. For CDS, CROFF (O PT INC ) ≥ ∆ + 1, and for TDS, CROFF (O PT INC ) ≥ ∆/2.
Proof. Let G be a rotor of degree ∆ given in the adversarial order. Since any algorithm producing
an incremental solution D of either CDS or TDS on a K2 must select vertices, D∆ contains all
vertices of G∆ . Furthermore, at least one additional vertex is required to make D∆ connected
INC
and thus O PTC
(G) ≥ ∆ + 1. On the other hand, the set D = V (G) is clearly an incremental
INC
connected dominating set of G and thus O PTC
(G) = ∆ + 1. For total dominating set, it is easy
to see that D∆ is an incremental total dominating set of G and thus O PTTINC (G) = ∆. The proof
is concluded by observing that the central vertex (the central vertex plus an arbitrary other vertex)
forms a connected (total) dominating set of G and thus γC (G) = 1 and γT (G) = 2.
For any n ≥ 2, the two-sided fan of size n is the graph obtained from a path on n − 2 vertices by
attaching two additional vertices, one to the even-numbered vertices of the path and the other to
the odd-numbered vertices of the path. The adversarial order of a two-sided fan is defined by the
standard order of the path, followed by the two additional vertices. See Figure 5 for an illustration
of a two-sided fan of size 10.

Figure 5: The rotor of degree 8 (left, Proposition 29) and two-sided fan of size 10 (right, Proposition 30).

Proposition 30. For any incremental algorithm A LG for CDS or TDS on always-connected bipartite graphs, CROFF (A LG) ≥ (n − 3)/2 holds for the strict competitive ratio.
Proof. Let Gn be a two-sided fan of size n, given in the adversarial order. It suffices to prove
INC
that O PTC
(Gn ) = O PTTINC (Gn ) = n − 3 and γ(Gn ) = γC (Gn ) = γT (Gn ) = 2. This is
straightforward from the facts that the first n − 2 vertices of G induce a path, that online connected
and total dominating sets coincide, and that any incremental connected dominating set on a path
of length k has size at least k − 1.

5

Conclusion and Open Problems

Online algorithms for four variants of the dominating set problem are compared using competitive analysis to O PT INC and O PT OFF , two reasonable alternatives for the optimal algorithm having
knowledge of the entire input. Several graph classes are considered, and tight results are obtained
in most cases.
The difference between O PT INC and O PT OFF is that O PT INC is required to maintain an incremental
solution (as any online algorithm), while O PT OFF is only required to produce an offline solution for
15

the final graph. The algorithms are compared to both O PT INC and O PT OFF , and O PT INC is compared
to O PT OFF , in order to investigate why all algorithms tend to perform poorly against O PT OFF . Is
this due to the requirement that online algorithms have to maintain an incremental solution at all
times, or is it because of the lack of knowledge of the future that both O PT INC and O PT OFF have?
Inspecting the results in the tables, perhaps the most striking conclusion is that the competitive
ratios of any online algorithm and O PT INC , respectively, against O PT OFF , are almost identical. This
indicates that the requirement to maintain an incremental dominating set is a severe restriction,
which can be offset by the full knowledge of the input only to a very small extent. On the other
hand, when we restrict our attention to online algorithms against O PT INC , it turns out that the
handicap of not knowing the future still presents a barrier, leading to competitive ratios of the
order of n or ∆ in most cases.
One could reconsider the nature of the irrevocable decisions, which originally stemmed from
practical applications. Which assumptions on irrevocability are relevant for practical applications,
and which irrevocability components make the problem hard from an online perspective? We
expect that these considerations will apply to many other online problems as well.
There is relatively little difference observed between three of the variants of dominating set considered: dominating set, connected dominating set, and total dominating set. In fact, the results
for total dominating set generally followed directly from those for connected dominating set as a
consequence of Lemma 4. The results for independent dominating set were significantly different
from the others. It can be viewed as the minimum maximal independent set problem since any
maximal independent set is a dominating set. This problem has been studied in the context of
investigating the performance of the greedy algorithm for the independent set problem. In fact,
the unique incremental independent dominating set is the set produced by the greedy algorithm
for independent set.
In yet another orthogonal dimension, we compare the results for various graph classes. Dominating set is a special case of set cover and is notoriously difficult in classical complexity, being
NP-hard [16], W [2]-hard [10], and not approximable within c log n for any constant c on general
graphs [12]. On the positive side, on planar graphs, the problem is FPT [1] and admits a PTAS [2],
and it is approximable within log ∆ on bounded degree graphs [8]. On the other hand, the relationship between the performance of online algorithms and structural properties of graphs is not
particularly well understood. In particular, there are problems where the absence of knowledge
of the future is irrelevant; examples of such problems in this work are CDS and TDS on trees,
and IDS on any graph class. As expected, for bounded degree graphs, the competitive ratios are
of the order of ∆, but closing the gap between ∆/2 and ∆ seems to require additional ideas. On
the other hand, for planar graphs, the problem, rather surprisingly, seems to be as difficult as the
general case when compared to O PT OFF . When online algorithms for planar graphs are compared
to O PT INC , we suspect there might be an algorithm with constant competitive ratio. At the same
time, this case is the most notable open problem directly related to our results. Drawing inspiration from classical complexity, one may want to eventually consider more specific graph classes
in the quest for understanding exactly what structural properties make the problem solvable. From
this perspective, our consideration of planar, bipartite, and bounded degree graphs is a natural first
step.

Acknowledgment The authors would like to thank anonymous referees for constructive comments on an earlier version of the paper.
16

References
[1] J. Alber, H. L. Bodlaender, H. Fernau, T. Kloks, and R. Niedermeier. Fixed parameter algorithms for dominating set and related problems on planar graphs. Algorithmica, 33(4):461–
493, 2002.
[2] B. S. Baker. Approximation algorithms for NP-complete problems on planar graphs. Journal
of the ACM, 41(1):153–180, 1994.
[3] C. Berge. Theory of Graphs and its Applications. Meuthen, London, 1962.
[4] M. Böhm, J. Sgall, and P. Veselý. Online colored bin packing. In E. Bampis and O. Svensson, editors, 12th International Workshop on Approximation and Online Algorithms (WAOA),
volume 8952 of Lecture Notes in Computer Science, pages 35–46. Springer, 2015.
[5] A. Borodin and R. El-Yaniv. Online Computation and Competitive Analysis. Cambridge
University Press, 1998.
[6] J. Boyar and K. S. Larsen. The seat reservation problem. Algorithmica, 25(4):403–417,
1999.
[7] M. Chrobak, J. Sgall, and G. J. Woeginger. Two-bounded-space bin packing revisited. In
C. Demetrescu and M. M. Halldórsson, editors, 19th Annual European Symposium (ESA),
volume 6942 of Lecture Notes in Computer Science, pages 263–274. Springer, 2011.
[8] V. Chvátal. A greedy heuristic for the set-covering problem. Mathematics of Operations
Research, 4(3):233–235, 1979.
[9] B. Das and V. Bharghavan. Routing in ad-hoc networks using minimum connected dominating sets. In IEEE International Conference on Communications (ICC), volume 1, pages
376–380, 1997.
[10] R. G. Downey and M. R. Fellows. Fixed-parameter tractability and completeness I: Basic
results. SIAM Journal on Computing, 24(4):873–921, 1995.
[11] D.-Z. Du and P.-J. Wan. Connected Dominating Set: Theory and Applications. Springer,
New York, 2013.
[12] U. Feige. A threshold of ln n for approximating set cover. Journal of the ACM, 45(4):634–
652, 1998.
[13] T. W. Haynes, S. Hedetniemi, and P. Slater. Fundamentals of Domination in Graphs. Marcel
Dekker, New York, 1998.
[14] M. Henning and A. Yao. Total Domination in Graphs. Springer, New York, 2013.
[15] A. R. Karlin, M. S. Manasse, L. Rudolph, and D. D. Sleator. Competitive snoopy caching.
Algorithmica, 3:79–119, 1988.
[16] R. M. Karp. Reducibility among combinatorial problems. In R. E. Miller and J. W. Thatcher,
editors, Complexity of Computer Computations, The IBM Research Symposia Series, pages
85–103. Plenum Press, New York, 1972.
[17] G.-H. King and W.-G. Tzeng. On-line algorithms for the dominating set problem. Inform.
Process. Lett., 61(1):11–14, 1997.
17

[18] D. König. Theorie der Endlichen und Unendlichen Graphen. Chelsea, New York, 1950.
[19] C. L. Liu. Introduction to Combinatorial Mathematics. McGraw-Hill, New York, 1968.
[20] O. Ore. Theory of Graphs, volume 38 of Colloquium Publications. American Mathematical
Society, Providence, 1962.
[21] D. D. Sleator and R. E. Tarjan. Amortized efficiency of list update and paging rules. Communications of the ACM, 28(2):202–208, 1985.

18

