Linear-Time Algorithm for the Paired-Domination Problem in Convex Bipartite Graphs

Abstract

A bipartite graph G=(U,W,E) with vertex set V=U∪W is convex if there exists an ordering of the vertices of W such that for each u∈U, the neighbors of u are consecutive in W. A compact representation of a convex bipartite graph for specifying such an ordering can be computed in O(|V|+|E|) time. The paired-domination problem on bipartite graphs has been shown to be NP-complete. The complexity of the paired-domination problem on convex bipartite graphs has remained unknown. In this paper, we present an O(|V|) time algorithm to solve the paired-domination problem on convex bipartite graphs given a compact representation. As a byproduct, we show that our algorithm can be directly applied to solve the total domination problem on convex bipartite graphs in the same time bound.

1 Introduction

All graphs considered in this paper are finite and undirected, without loops or multiple edges. For any two sets X and Y, let X−Y denote the set of elements of X that are not in Y. Let G=(V,E) be a graph with vertex set V and edge set E. Throughout this paper, let n and m denote the numbers of vertices and edges of graph G, respectively. Let v be a vertex of V and let D be a subset of V. The open neighborhood N(v) of the vertex v consists of the set of vertices adjacent to v, that is, N(v)={w∈V| (v,w)∈E}, and the closed neighborhood of v is N[v]=N(v)∪{v}. The open neighborhood N(D) is defined to be ∪ _v∈D N(v), and the closed neighborhood of D is N[D]=N(D)∪D. The set D dominates vertex v if either v∈D or N(v)∩D≠∅. If D dominates all vertices in a subset S of V, then we say that D dominates S. The set D is called a dominating set of G if and only if D dominates V, that is, every vertex in V−D is adjacent to a vertex in D. The domination number γ(G) equals the minimum cardinality of a dominating set of G. A dominating set D is called total if N(v)∩D≠∅ for all v∈D, that is, the subgraph of G induced by D contains no isolated vertex. The minimum cardinality of a total dominating set of G is called the total domination number γ _t (G). A minimum dominating set of G is a dominating set with cardinality γ(G). A minimum total dominating set of G is a total dominating set with cardinality γ _t (G). The domination problem is to find a minimum dominating set of G. The total domination problem is defined analogously. These two problems are known to be NP-complete for general graphs.

Variations of the domination problem seek to find a minimum dominating set with some additional properties, e.g., to be independent or to induce a acyclic graph. These problems arise in a number of distributed network applications, where the problem is to locate the smallest number of centers in networks such that every vertex is nearby at least one center. Domination and its variations in graphs have been thoroughly studied, and the literature on this subject has been surveyed and detailed in two books [21, 22]. In this paper, we will study a variant of the domination problem, namely the paired-domination problem.

A set S⊆V is a paired-dominating set of G if S dominates V and the subgraph G[S] induced by S contains a perfect matching. That is, a paired-dominating set S with matching M is a dominating set S={v ₁,v ₂,…,v _2k−1, v _2k } with independent edge set M={e ₁,e ₂,…,e _k } where each edge e _i is incident to two vertices of S, that is, M is a perfect matching in G[S]. Two vertices joined by an edge of M are said to be paired. A vertex v is called a paired-vertex of a matching if there is an edge in it incident to v. Every graph without isolated vertices has a paired-dominating set, since the paired-vertices of any maximal matching form such a set [20]. The paired-domination number γ _p (G) of a graph G equals the minimum cardinality of a paired-dominating set of G. A minimum paired-dominating set of G is a paired-dominating set with cardinality γ _p (G). The paired-domination problem is to find a minimum paired-dominating set of G. For example, for the three-dimensional hypercube graph Q ₃ shown in Fig. 1, S={v ₁,v ₅,v ₄,v ₈} is a paired-dominating set of Q ₃ since S is a dominating set and the subgraph induced by S contains a perfect matching M={(v ₁,v ₅),(v ₄,v ₈)} where v ₁ and v ₅ (v ₄ and v ₈) form a pair, and γ _p (Q ₃)=4.

Fig. 1

The three-dimensional hypercube graph Q ₃

Paired-domination was introduced by Haynes and Slater [20] with the following application in mind. If, in a graph G, we consider each vertex as the possible location for a guard capable of protecting every vertex adjacent to it, then “domination” requires every vertex to be protected. In paired-domination, each guard is assigned another adjacent guard, and they are designed to provide a backup for each other. The problem of determining the paired-domination number γ _p (G) of an arbitrary graph G has been known to be NP-complete [20]. The paired-domination problem is still NP-complete in some special classes of graphs such as bipartite graphs, chordal graphs, and split graphs [12]. However, the problem admits polynomial-time algorithms when the input is restricted to some special classes of graphs, including trees [33], circular-arc graphs [13], permutation graphs [14, 27], strongly chordal graphs [11], block graphs and interval graphs [12].

Let G=(U,W,E) represent an undirected, bipartite graph with vertex set U∪W, where U and W is a partition of the vertices and E is the edge set in which each edge (u,w) is such that u∈U and w∈W. The bipartite graph G is called convex if the vertices in W can be ordered in a way that for each u∈U, the neighbors of u are consecutive in W. This ordering can be obtained in a preprocessing step by an O(n+m) time algorithm [4]. A compact representation for specifying such an ordering can be computed in O(n+m) time [34, 36]. Convex bipartite graphs form a subclass of bipartite graphs and are a superclass of bipartite permutation graphs and biconvex graphs [7]. They were introduced by Glover [19], motivated by some industrial applications. Since then several problems have been studied in this kind of graphs. In the following, we give a brief survey on convex bipartite graphs. Asdre and Nikolopoulos proved that the harmonious coloring problem, the pair-complete coloring problem, and the k-path partition problem on convex bipartite graphs are NP-complete [2]. However, several problems on them have been shown to be polynomial time solvable. The problem of finding a maximum independent set in convex bipartite graphs given a compact representation can be solved in O(n) time [29, 34]. The Hamiltonian cycle problem on them is O(n ²) time solvable [30]. Liang and Chang solved the feedback vertex set problem on weighted convex bipartite graphs in O(n ² m) time [28]. Yang showed that the link-orientation problem on weighted convex bipartite graphs can be solved in polynomial time [37]. Yu et al. solved the k-chain subgraph cover problem on convex bipartite graphs in O(m ²) time [39]. Brandstädt et al. improved the result in [39] to obtain an O(n ²) time algorithm for the k-chain subgraph cover problem [8]. Katriel considered the problem of finding a U-perfect matching of maximum weight in a weighted convex bipartite graph, and solved it in O(m+nlogn) time [25]. Brodal et al. considered the problem of maintaining a maximum matching in a convex bipartite graph under a set of update operations which includes insertion and deletions of vertices and edges [6]. They developed a data structure to implement a set of update operations in O(log² n) amortized time per operation. Park et al. designed a boolean circuit to find a maximum matching of a convex bipartite graph [32]. Recently, Nussbaum et al. computed a maximum edge biclique of a convex bipartite graph in O(nlog³ nloglogn) time [31]. The maximum matching problem is the most frequently studied problem in the literature for convex bipartite graphs. Matchings in convex bipartite graphs correspond to the problem of scheduling unit length tasks on a single disjunctive resource, given a release time and a deadline for every task [25]. Glover first considered the maximum matching problem in 1967 and provided an O(m) time algorithm for determining the maximum matching of a convex bipartite graph [19]. This algorithm progresses iteratively through each vertex of W in nondecreasing order and, of all the unmatched vertices of U incident to the vertex consideration, matches it the one which is selected by a greedy strategy. Subsequently, Gallo used a special data structure based on a binary heap to design an O(nlogn) time algorithm for finding a maximum matching [18]. Now, finding a maximum matching of a convex bipartite graph can be done in O(n) time [36]. For parallel algorithms on convex bipartite graphs, we refer readers to [5, 9, 17].

The paired-domination problem on bipartite graphs has been shown to be NP-complete [12]. The complexity of the paired-domination problem in convex bipartite graphs is still unknown. In this paper, we present the first O(n) time algorithm to solve the paired-domination problem on convex bipartite graphs given a compact representation. Further, we show that our algorithm can be applied to solve the total domination problem on convex bipartite graphs in the same time bound. The paired-domination problem in convex bipartite graphs has the following application. Consider a system represented by a convex bipartite graph. The problem of placing monitoring devices in the system such that every site in it (including the monitoring devices themselves) is adjacent to a monitor and every monitor is paired with a backup monitor, can be modelled by paired-domination in convex bipartite graphs.

Previous related works are summarized below. Damaschke et al. solved the domination problem for convex bipartite graphs in O(n ³) time [16]. To the best of our knowledge, the best algorithms for the domination and independent domination problems on convex bipartite graphs run in O(n ²) time [3]. Yen solved the bottleneck independent domination problem on convex bipartite graphs in O(m) time [38]. Srinivasan et al. solved the edge domination problem on bipartite permutation graphs in O(n ²+mn ^1.5) time [35]. To the best of our knowledge, the complexity status of the edge domination problem on convex bipartite graphs is still unknown. Recently, Korpelainen proved that the efficient edge domination problem on convex bipartite graphs is polynomial solvable [26].

The rest of this paper is organized as follows. In Sect. 2, we review some properties of convex bipartite graphs and define some basic notations used in this paper. Section 3 introduces a clustering procedure used in our algorithm. In Sect. 4, we present an O(n) time algorithm for solving the paired-domination problem given a compact representation of a convex bipartite graph. Section 5 shows that our algorithm can be directly applied to solve the total domination problem on convex bipartite graphs given a compact representation in O(n) time. Finally, some concluding remarks and future work are given in Sect. 6.

2 Preliminaries

Let G=(U,W,E) be a bipartite graph, where U and W define the bipartition of the vertices, and E is the edge set in the form (u,w) such that u∈U and w∈W. The graph G is called convex if the vertices in W can be ordered in such a way that for each u∈U, the neighbors of u are consecutive in W. For convenience, we consider that U={1,2,…,|U|} and W={1,2,…,|W|}, and that the vertices in W are given according to the ordering mentioned above. This ordering can be obtained in a preprocessing step by an O(n+m) time algorithm [4]. We say that a vertex w′∈W is smaller (larger) than a vertex w″∈W if the integer representing w′ is smaller (larger) than the integer representing w″. That is, we will represent vertices of W by integers from 1 to |W|. A convex bipartite graph has a compact representation by a set of |U| triples of the form (i,begin(i),end(i)), where i is a vertex in U, begin(i) and end(i) are the smallest and largest vertices, respectively, in the interval of vertices (i.e., a sequence of consecutively numbered vertices) of W connected to i. For example, Fig. 2(a) shows a convex bipartite graph and Fig. 2(b) depicts its compact representation.

Fig. 2

(a) A convex bipartite graph and a paired-dominating set on it (filled circles together with bold edges), and (b) a compact representation of (a)

Theorem 1

[4, 34, 36]

Given a convex bipartite graph, its compact representation can be computed in O(n+m) time.

Throughout the remainder of the paper, we assume that the input of the algorithm is a compact representation of a convex bipartite graph. A paired-dominating set of a convex bipartite graph G=(U,W,E) contains a perfect matching M such that for (u,w)∈M, u∈U and w∈W. For instance, Fig. 2(a) shows a paired-dominating set of a convex bipartite graph, where filled circles indicate the vertices in the paired-dominating set and bold edges form the perfect matching.

Hereafter, let G=(U,W,E) be a convex bipartite graph with a compact representation. We denote by [i,j] the set of consecutive integers {i,i+1,…,j}. The vertices of U (resp. W) are represented by integers in [1,|U|] (resp. [1,|W|]). Thus, U=[1,|U|] and W=[1,|W|]. We call [i,j] an (integer) interval starting from i and ending at j. Further, we call i and j the left endpoint and right endpoint of interval I=[i,j], denoted by l(I) and r(I), respectively. For p<i⩽ℓ⩽j, we say that ℓ dominates interval [i,j], interval [i,j] covers ℓ, and interval [i,j] is to the right of p. Note that p and ℓ may be the integers representing vertices. Two intervals are called disjoint if the intersection of them is empty. In addition, we also let U denote an array representing G in a compact representation. Each element of the array U[1..|U|] has the fields begin and end. The triple (i,begin(i),end(i)) of the compact representation of G is represented here by (i,U[i].begin,U[i].end). We may assume that the input convex bipartite graph has no isolated vertices since isolated vertices can be easily determined. By the definition of convex bipartite graphs, the neighbors of a vertex u in U can be represented as an interval I _u =[u.begin,u.end], called the neighbor interval of u. Then, the neighbors of vertices of U can be represented by a set I(U) of intervals. We call I(U) the interval representation of neighbors of vertices in U. For example, Fig. 3(b) shows the interval representation I(U) for the convex bipartite graph shown in Fig. 2(a).

Fig. 3

(a) Sorted clusters of U, and (b) interval representation I(U) of neighbors of vertices in U for the convex bipartite graph shown in Fig. 2(a)

3 The Clustering Process

We first observe one property of a convex bipartite graph G=(U,W,E). For two vertices x,y in U, either x.begin=y.begin or not. If x.begin=y.begin, then the smallest neighbors of x and y are the same vertex in W. Thus, we define clusters of U as follows.

Definition 1

Two vertices x and y of U are said to be in the same cluster if x.begin=y.begin, i.e., their smallest neighbors are the same vertex of W.

To obtain an O(n) time algorithm, we will sort the clusters of U in increasing manner according to their smallest neighbors. We then define the sorted clusters of U as follows.

Definition 2

The sequential clusters C ₁,C ₂,…,C _k of U are called sorted clusters if a.begin<b.begin for a∈C _i , b∈C _j , and i<j. Cluster C _i is said to be smaller than cluster C _i+1 for 1⩽i⩽k−1. Moreover, for two vertices u _i and u _j in two distinct clusters, we say that u _i <u _j if u _i .begin<u _j .begin.

For example, Fig. 3(a) shows the sorted clusters for the convex bipartite graph shown in Fig. 2(a).

In the following, we will partition U into k disjoint sorted clusters C ₁,C ₂,…,C _k . We call it the clustering process. It is easy to see that the clustering process runs in O(nlogn) time if it is implemented by a general purpose sorting algorithm. Since it is too time-consuming, we do not use a general purpose sorting algorithm to implement the clustering process. Given an array U[1..|U|] representing G in a compact representation, each element of U forms a triple (i,U[i].begin,U[i].end) and U[i].begin is an integer in the range from 1 to |W|. Thus, we can use the Counting Sort algorithm in [15] to implement the clustering process in O(|U|+|W|) time.

For readers’ convenience, we introduce how to apply Counting Sort algorithm to compute the sorted clusters as follows. We require three other arrays: The clustered array U ^c holds the sorted clusters, where each element of U ^c consists of a triple (u,u.begin,u.end) for u∈U, and two auxiliary arrays, namely beginCounts[1..ω] and startingLoc[1..ω], provide temporary working storage, where ω is the largest integer in ⋃_1⩽i⩽|U| U[i].begin and is bounded by |W|. The clustering procedure is sketched as follows. It first determines the number of elements in each begin field of the array U and stores them in the auxiliary array beginCounts. For each integer ℓ, 1⩽ℓ⩽ω, the item beginCounts[ℓ] stores the number of elements whose U[i].begin equals ℓ. Then, it uses the information in array beginCounts to determine the starting location of each cluster in U ^c and stores them in array startingLoc. Initially, the item startingLoc[ℓ] stores the starting location of cluster C _i in the clustered array U ^c, where the begin field of each element in C _i equals ℓ, i.e., U[j].begin=ℓ for j∈C _i . Let ℓ′ be the largest integer in [1,ℓ−1] such that beginCounts[ℓ′]≠0. Then, the starting location, startingLoc[ℓ], is beginCounts[ℓ′]+startingLoc[ℓ′]. By using these two auxiliary arrays, the procedure can move the elements in the original array U one by one into their correct location in the clustered array U ^c. During the moving process, the contents of array startingLoc will be modified. Suppose that it is about to move element i of U with triple (i,U[i].begin,U[i].end). It first finds the location startingLoc[U[i].begin] of triple (i,U[i].begin,U[i].end) from auxiliary array startingLoc. Then, it moves this triple to the startingLoc[U[i].begin]th location of U ^c. Finally, it lets startingLoc[U[i].begin]= startingLoc[U[i].begin]+1. After completing the above moving process, it outputs U ^c as the clustered array for storing the sorting clusters.

For example, given the compact representation U of a convex bipartite graph shown in Fig. 2(b), Fig. 4(a) shows the initial auxiliary arrays, beginCounts and startingLoc, Fig. 4(b) reveals the contents of the final auxiliary arrays after moving all elements of U into U ^c, and Fig. 4(c) shows the clustered array U ^c. Figure 4(c) also depicts the sorted clusters of the graph. Since every element of U is processed once and the length ω of each auxiliary array is at most |W|, the above clustering process runs in O(|U|+|W|) time. Thus, we have the following lemma.

Fig. 4

(a) The initial auxiliary arrays, beginCounts and startingLoc, (b) the final auxiliary arrays after moving every element of U into U ^c, and (c) the clustered array U ^c, where the input compact representation U is shown in Fig. 2

Lemma 1

The sorted clusters of a convex bipartite graph G=(U,W,E) can be computed in O(|U|+|W|) time.

From now on, it is assumed that the clustering process has been done, i.e., sorted clusters of U and clustered array U ^c are given. The number of clusters gives us an upper bound of γ _p (G) as follows.

Lemma 2

Let G=(U,W,E) be a convex bipartite graph without isolated vertices, and let U be partitioned into k sorted clusters C ₁,C ₂,⋯,C _k . Then, 2k⩾γ _p (G).

Proof

Let u _i be a vertex in C _i , 1⩽i⩽k, such that u′.end⩽u _i .end for all u′∈C _i , and let w _i ∈W such that w _i =u _i .begin. By pairing u _i with w _i for 1⩽i⩽k, we obtain a paired-dominating set of size 2k. Thus, 2k⩾γ _p (G). □

Let C _i be a cluster of U. Define min(C _i ) and max(C _i ) to be two vertices in C _i such that min(C _i ).end ⩽u′.end⩽max(C _i ).end for all u′∈C _i . Further, $I_{\min(C_{i})}=[\min(C_{i}).\mathit{begin}, \min(C_{i}).\mathit{end}]$ and $I_{\max(C_{i})}=[\max(C_{i}).\mathit{begin}, \max(C_{i}).\mathit{end}]$. We can see that for u′∈C _i , $I_{\min(C_{i})}\subseteq I_{u'}\subseteq I_{\max(C_{i})}$. In addition, every vertex of C _i is adjacent to all vertices of $I_{\min(C_{i})}$ in W. The vertex of $I_{\min(C_{i})}$ in W is called a common neighbor of vertices of C _i . For example, let C ₁ be a cluster of U shown in Fig. 3. Then, min(C ₁)=1, $I_{\min(C_{1})}=[1,3], \max(C_{1})=3$, and $I_{\max(C_{1})}=[1,4]$. Let C ₁,C ₂,…,C _k be the disjoint clusters of U. We define $I_{\min}(U)=\{I_{\min(C_{i})} | 1\leqslant i\leqslant k\}$ and $I_{\max}(U)=\{I_{\max(C_{i})} | 1\leqslant i\leqslant k\}$. For example, Fig. 5 shows I _min(U) and I _max(U) for the convex bipartite graph shown in Fig. 3. By visiting every vertex of a cluster C _i once, $I_{\min(C_{i})}$ and $I_{\max(C_{i})}$ can be easily found. In addition, by visiting every element of clustered array U ^c once, we can easily construct the representing sorted arrays A _min and A _max of I _min(U) and I _max(U), respectively, in O(|U|) time. For instance, Fig. 6 shows the representing sorted arrays of I _min(U) and I _max(U) shown in Fig. 5. Thus, we have the following lemma.

Fig. 5

(a) I _min(U), and (b) I _max(U) for the convex bipartite graph shown in Fig. 3

Fig. 6

(a) The representing sorted array A _min of I _min(U), and (b) the representing sorted array A _max of I _max(U), where they are constructed from Fig. 4(c), and I _min(U) and I _max(U) are shown in Fig. 5

Lemma 3

Let G=(U,W,E) be a convex bipartite graph without isolated vertices, and let U be partitioned into k sorted clusters C ₁,C ₂,…,C _k . Then, I _min(U) and I _max(U) together with their representing sorted arrays can be constructed in O(|U|) time.

4 The Paired-Domination Problem in Convex Bipartite Graphs

In this section, we will present an O(n) time algorithm to solve the paired-domination problem on a convex bipartite graph G=(U,W,E) given a compact representation. Let $\hat{W}$ and $\hat{U}$ be subsets of W and U, respectively. Recall that the set $\hat{W}$ (resp. $\hat{U}$) dominates U (resp. W) if every vertex of U (resp. W) is adjacent to at least one vertex of $\hat{W}$ (resp. $\hat{U}$). Let C ₁,C ₂,…,C _k be the disjoint sorted clusters of U. By Lemma 2, 2k⩾γ _p (G). In the following, we will obtain a lower bound of γ _p (G). Our basic idea is described as follows. We first find a minimum cardinality subset $\tilde{W}$ of W and a minimum cardinality subset $\tilde{U}$ of U such that U and W are dominated by $\tilde{W}$ and $\tilde{U}$, respectively. By the definition of a convex bipartite graph, it is not hard to verify the following lemma.

Lemma 4

Let $\tilde{W}$ and $\tilde{U}$ be the minimum cardinality subsets of W and U, respectively, such that $\tilde{W}$ dominates U and $\tilde{U}$ dominates W. Then, $\gamma_{p}(G)\geqslant 2\times\max\{|\tilde{W}|,|\tilde{U}|\}$.

After computing such two sets $\tilde{W}$ and $\tilde{U}$, we construct a paired-dominating set of G with cardinality not less than $2\cdot\max\{|\tilde{W}|,|\tilde{U}|\}$. By Lemma 4, the constructed paired-dominating set is a minimum paired-dominating set of G if its size equals $2\cdot\max\{|\tilde{W}|,|\tilde{U}|\}$. We then show that the constructed paired-dominating set is a minimum paired-dominating set of G if its size is larger than $2\cdot\max\{|\tilde{W}|,|\tilde{U}|\}$. In the following, we show how to construct two such sets $\tilde{W}$ and $\tilde{U}$.

We first construct a minimum cardinality subset $\tilde{W}$ of W such that $\tilde{W}$ dominates U. Observe that every vertex not in I _min(U) is not in $\tilde{W}$. We give the following lemma to verify this observation.

Lemma 5

Let $\tilde{W}$ be a minimum cardinality subset of W such that $\tilde{W}$ dominates U. Then, $\tilde{W}\subseteq I_{\min}(U)$.

Proof

Assume by contradiction that $\tilde{W}-I_{\min}(U)\neq \emptyset$. Let $w\in \tilde{W}-I_{\min}(U)$ such that w is adjacent to one vertex of cluster C _i in U. Then, $w\in I_{\max(C_{i})}-I_{\min(C_{i})}$, i.e., min(C _i ).end<w⩽max(C _i ).end. Consider that $I_{\min(C_{i})}\cap \tilde{W}=\emptyset$. Then, min(C _i )∈U is not adjacent to any vertex of $\tilde{W}$, and, hence, $\tilde{W}$ does not dominate U, a contradiction. On the other hand, consider that $I_{\min(C_{i})}\cap \tilde{W}\neq\emptyset$. Then, every vertex of C _i is adjacent to one vertex of $I_{\min(C_{i})}\cap \tilde{W}$. Thus, $\tilde{W}-\{w\}$ also dominates U. It contradicts that $\tilde{W}$ is a minimum cardinality subset of W dominating U. In any case, a contradiction occurs. Thus, $\tilde{W}-I_{\min}(U)=\emptyset$, i.e., $\tilde{W}\subseteq I_{\min}(U)$. □

By the above lemma, we can only consider the vertices in $I_{\min(C_{i})}$, 1⩽i⩽k, for computing $\tilde{W}$. Then, we are given by I _min(U). Note that the vertices of W and U are represented by integers. In the following, we will use integers and vertices interchangeably. Then, the problem of finding a minimum cardinality subset of W dominating U is equivalent to seek a minimum set of integers such that they together dominate intervals of I _min(U). We introduce Procedure GD-W to compute such a set $\tilde{W}$ of integers of W. This procedure is inspired by the greedy algorithms on interval graphs [1, 10, 23], but the basic approach is different from theirs. Given a set I _min(U) of intervals, Procedure GD-W uses a greedy principle to obtain a subset $\tilde{W}$ of W as follows. Initially, let $\tilde{W}=\emptyset$, I _min=I _min(U), and let s(I _min) denote the interval in I _min with the smallest right endpoint. Let w be the right endpoint of s(I _min) and let I ^w be the set of intervals dominated by w in I _min. Let $\tilde{W}=\tilde{W}\cup\{w\}$ and let I _min=I _min−I ^w. Repeat the above process until I _min=∅. Then it outputs $\tilde{W}$. For example, given a set I _min(U) of intervals shown in Fig. 5(a), Procedure GD-W outputs $\tilde{W}=\{3,8\}$.

Before we show how to verify the optimality of Procedure GD-W, let us observe the behavior of Procedure GD-W and the integers obtained by it from I _min. It is easy to see that every interval in I _min−{s(I _min)} is either dominated by w which is the right endpoint of s(I _min), or to the right of w. We see that Procedure GD-W maintains the following invariant while growing set $\tilde{W}=\{w_{1},w_{2},\ldots,w_{p}\}$ with w ₁<w ₂<⋯<w _p to be computed:

Every interval x∈I _min dominated by none of $\tilde{W}$ is to the right of w _p , and the intervals with right endpoints w _i , 1⩽i⩽p, are disjoint.

Initially, $\tilde{W}=\{w_{1}\}$, w ₁ is the right endpoint of interval s(I _min(U)), and the invariant holds trivially. Assume now $\tilde{W}=\{w_{1},w_{2},\ldots,w_{h}\}$, where w ₁<w ₂<⋯<w _h and h⩾1, and the invariant holds. In this time, every interval of I _min is dominated by none of $\tilde{W}$. Let w be the right endpoint of s(I _min) and let I ^w be the set of intervals dominated by w in I _min. By the variant, s(I _min) is to the right of w _h . In addition, every interval x∈I _min−I ^w dominated by none of $\tilde{W}\cup\{w\}$ is to the right of w. By induction then, the invariant maintained by Procedure GD-W holds true.

Since every interval needs to be dominated by at least one integer, the following proposition can be easily verified by the pigeonhole principle.

Proposition 1

Let I be a set of disjoint intervals, and let D be a set of integers such that every interval of I is dominated by at least one integer of D. Then, |D|⩾|I|.

Let $\tilde{W}$ be the output by Procedure GD-W. By the invariant maintained by Procedure GD-W, every interval of I _min(U) is dominated by at least one integer of $\tilde{W}$, and intervals with right endpoints in $\tilde{W}$ are disjoint. By Proposition 1, the minimum number of integers that dominate intervals of I _min(U) is at least $|\tilde{W}|$. Thus, $\tilde{W}$ is a minimum cardinality subset of W such that $\tilde{W}$ dominates U.

We have proved the correctness of Procedure GD-W. Now, we show how to implement it in O(|U|+|W|) time. By Lemma 3, the representing sorted array A _min of I _min(U) can be constructed in O(|U|) time. We will use an array L together with linked pointers to store the endpoints of intervals of I _min(U), where |L|=|W| and the index of L corresponds to the integer (vertex) of W. In addition, we need a stack S to perform operations of this procedure. Initially, let L and S be empty. We first visits the elements of A _min one by one. Suppose that it is about to process element A _min[i] with a triple (u,u.begin,u.end), where u∈U. Then, we insert the left endpoint l(I _u ) of the neighbor interval I _u of u into L[u.begin], insert the right endpoint r(I _u ) of I _u into L[u.end], and link l(I _u ) to r(I _u ). If L[u.begin] (resp. L[u.end]) is not empty, then we append l(I _u ) (resp. r(I _u )) to the tail of L[u.begin] (resp. L[u.end]). After completing the above process, we construct an array L with linked points to maintain the sorted endpoints of intervals of I _min(U). For example, Fig. 7(a) shows the linked array L for I _min(U) shown in Fig. 5(a). It is easy to see that the above process runs in O(|U|) time. We then progress iteratively through each element of the constructed linked array L in nondecreasing order. When a left endpoint l(I _i ) is visited, it is pushed into stack S. When a right endpoint r(I _i ) is visited, s(I _min) is found, where L[w] stores r(I _i ) which is the right endpoint of s(I _min). In this time, let $\tilde{W}=\tilde{W}\cup\{w\}$. And, it repeats popping l(I _i ) from stack S and removing its linked right endpoint r(I _i ) from L until S is empty, and it removes r(I _j ) from L for all l(I _j ) stored in L[w]. For instance, Fig. 7(b) depicts the remnants of linked array L for Fig. 7(a) after finding the first vertex 3 of $\tilde{W}$. After processing each element of L once, $\tilde{W}$ is computed. Since |L|=|W| and the number of endpoints of intervals of I _min(U) is 2|U|, the above implementation of Procedure GD-W can be done in O(|U|+|W|) time. Thus, we have the following lemma.

Fig. 7

(a) The linked array L maintaining sorted endpoints of I _min(U) shown in Fig. 5(a), and (b) the remnants of linked array L after computing the first vertex 3 of $\tilde{W}$

Lemma 6

Procedure GD-W computes a minimum cardinality subset $\tilde{W}$ of W that dominates U, and it runs in O(|U|+|W|) time.

By similar strategy in computing $\tilde{W}$, we can find a minimum cardinality subset $\tilde{U}$ of U such that $\tilde{U}$ dominates W. Notice that the vertices of U and W are always represented by integers, and that an interval covers an integer p if p is in the interval. Observe that if there exists a vertex j in $\tilde{U}$ such that its neighbor interval $I_{j}\not\in I_{\max}(U)$, then j can be replaced by one vertex i such that I _i ∈I _max(U) and I _j ⊆I _i . Thus, we can only consider the vertices whose neighbor intervals are in I _max(C _i ), 1⩽i⩽k. Then, we are given by I _max(U). The problem of finding a minimum cardinality subset of U dominating W is then equivalent to compute a minimum set of intervals in I _max(U) such that they together cover all integers of W. Before showing how to compute such a set of intervals in I _max(U), we observe one property below. Let $\hat{W}$ be a subset of W such that every interval of I _max(U) covers at most one integer of $\hat{W}$. Since every integer needs to be covered by at least one interval, the number of intervals covering all integers of $\hat{W}$ is at least $|\hat{W}|$. For example, given a set I _max(U) of intervals shown in Fig. 5(b), let $\hat{W}=\{1,5,9\}$. Then, no interval of I _max(U) covers more than one integer of $\hat{W}$. By the pigeonhole principle, the minimum number of intervals covering all integers of $\hat{W}$ is at least three. Thus we have the following proposition.

Proposition 2

Let $\hat{W}$ be a subset of W such that no two integers of $\hat{W}$ are covered by one interval of I _max(U). Then, the minimum number of intervals of I _max(U) covering all integers of W is at least $|\hat{W}|$.

By the above proposition, we can find a subset $\tilde{U}$ of U and a subset $\hat{W}$ of W such that $\tilde{U}$ dominates W, no interval of I _max(U) covers more than one integer of $\hat{W}$, and $|\tilde{U}|=|\hat{W}|$. Then, $\tilde{U}$ is the required set. We now introduce Procedure GD-U to construct such a minimum cardinality subset $\tilde{U}$ of U that dominates W. Given a set I _max(U) of intervals, Procedure GD-U uses a greedy principle to obtain a subset $\tilde{U}$ of U as follows. Initially, let $\tilde{U}=\emptyset$, $\hat{W}=\emptyset$, and let I _max=I _max(U). Let w be the smallest integer of intervals in I _max, let I ^w be the set of intervals in I _max covering w, and let s(I _max) denote the interval in I ^w with the largest right endpoint z. Let u be a vertex of U such that its neighbor interval I _u is the interval with right endpoint z. Let $\tilde{U}=\tilde{U}\cup\{u\}$ and let $\hat{W}=\hat{W}\cup\{w\}$. Remove from I _max all integers which are not larger than z. Repeat the above process until I _max=∅. Then it outputs $\tilde{U}$. For example, given a set I _max(U) of intervals shown in Fig. 5(b), Procedure GD-U outputs $\tilde{U}=\{3,6,8\}$. Note that $\hat{W}=\{1,5,9\}$ is used to verify the optimality of Procedure GD-U.

We can see that Procedure GD-U maintains the following invariant while growing sets $\tilde{U}=\{u_{1},u_{2},\ldots,u_{p}\}$ and $\hat{W}=\{w_{1},w_{2},\ldots,w_{p}\}$ with u ₁<u ₂<⋯<u _p and w ₁<w ₂<⋯<w _p to be computed:

Every integer of W covered by none of neighbor intervals of $\tilde{U}$ is larger than z _p , where z _p is the right endpoint of neighbor interval of u _p , and no interval of I _max covers more than one integer of $\hat{W}$.

The above invariant can be easily verified from the greedy principle of Procedure GD-U by induction. Let $\tilde{U}$ be the output by Procedure GD-U. By the invariant maintained by Procedure GD-U, $\tilde{U}$ dominates W and no interval of I _max covers more than one integer of $\hat{W}$. Note that $|\tilde{U}|=|\hat{W}|$. By Proposition 2, the minimum number of intervals of I _max(U) covering all integers of W is at least $|\hat{W}|$. This proves the optimality of Procedure GD-U. By similar arguments in analyzing the complexity of Procedure GD-W, it is not hard to verify that Procedure GD-U can be implemented in O(|U|+|W|) time. Thus, we have the following lemma.

Lemma 7

Procedure GD-U computes a minimum cardinality subset $\tilde{U}$ of U that dominates W, and it runs in O(|U|+|W|) time.

Based upon Lemmas 1, 3, 4, 6, and 7, our algorithm for the paired-domination problem is given by a compact representation of a convex bipartite graph G=(U,V,E) and is sketched as follows.

Stage 1 :

Partition U into k disjoint sorted clusters C ₁,C ₂,…,C _k ;

Stage 2 :

Compute the interval representation I(U) of U, and construct I _min(U) and I _max(U) from I(U);

Stage 3 :

Call Procedure GD-W given I _min(U) to compute a minimum cardinality subset $\tilde{W}$ of W such that $\tilde{W}$ dominates U, and call Procedure GD-U given I _max(U) to compute a minimum cardinality subset $\tilde{U}$ of U such that $\tilde{U}$ dominates W;

Stage 4 :

Construct a minimum paired-dominating set D _mpd of G with size not less than $2\cdot\max\{|\tilde{W}|,|\tilde{U}|\}$, and output D _mpd.

In Stage 4, we need to construct a minimum paired-dominating set D _mpd of G with cardinality not less than $2\cdot\max\{|\tilde{W}|,|\tilde{U}|\}$. This construction is shown as follows. Let $\tilde{U} = \{u_{1}, u_{2}, \cdots, u_{|\tilde{U}|}\}$ such that u _i <u _i+1 for $1\leqslant i\leqslant |\tilde{U}|-1$. Note that u _i <u _i+1 indicates that u _i .begin<u _i+1.begin, i.e., the cluster containing u _i is smaller than the cluster containing u _i+1 in the sorted clusters. For convenience, we denote by C _i the cluster containing u _i for $1\leqslant i\leqslant |\tilde{U}|$. Let $\tilde{W} = \{w_{1}, w_{2}, \ldots, w_{|\tilde{W}|}\}$ such that w _i <w _i+1 for $1\leqslant i\leqslant |\tilde{W}|-1$. We first consider that $|\tilde{U}|=\max\{|\tilde{W}|,|\tilde{U}|\}$. Initially, let D _mpd=∅. We then traverse the vertices of $\tilde{U}$ in a nondecreasing order, i.e., u _i is visited before u _i+1 for $1\leqslant i\leqslant |\tilde{U}|-1$. Suppose that it is about to process u _i . Let w _h be the smallest unpaired vertex of $\tilde{W}\cap N(u_{i})$, i.e., w _h ⩽w _j for $w_{j}\in {(\tilde{W}\cap N(u_{i}))-D_{\mathrm{mpd}}}$. If such a vertex w _h does not exist, then let w _h =u _i .end. By the construction of Procedure GD-U, w _h does exist. By pairing u _i with w _h , we obtain a new set D _mpd=D _mpd∪{u _i ,w _h }. After processing each vertex of $\tilde{U}$, let $\hat{W}=\tilde{W}-D_{\mathrm{mpd}}$. If $\hat{W}=\emptyset$, then D _mpd is a paired-dominating set of G with cardinality $2\cdot\max\{|\tilde{W}|,|\tilde{U}|\}$, and, hence, D _mpd is a minimum paired-dominating set of G by Lemma 4. Suppose that $\hat{W}\neq\emptyset$. Let $\hat{w}$ be the smallest vertex of $\hat{W}$ and let $\hat{u}$ be the vertex in cluster $\hat{C}$ such that $\hat{u}.\mathit{end}=\hat{w}$. Then, D _mpd does not dominate $\hat{C}$ and hence it is not a dominating set of G. In this time, we pair $\hat{u}$ with $\hat{w}$, i.e., let $D_{\mathrm{mpd}}=D_{\mathrm{mpd}}\cup \{\hat{u}, \hat{w}\}$, and let $\hat{W}=\hat{W}-\{\hat{w}\}$. Repeat the above process until $\hat{W}=\emptyset$. Then, D _mpd is the constructed paired-dominating set of G.

The optimality of the above process under that $\hat{W}\neq\emptyset$ is shown as follows. Let D _mpd be the constructed set before processing the vertices of $\hat{W}$, i.e., $|D_{\mathrm{mpd}}|=2\cdot|\tilde{U}|$, and let $\hat{W}=\tilde{W}-D_{\mathrm{mpd}}\neq\emptyset$. We will prove the optimality of the above process by induction on $|\hat{W}|$. Let $\hat{W}=\{\hat{w}_{1}, \hat{w}_{2}, \ldots, \hat{w}_{|\hat{W}|}\}$ such that $\hat{w}_{j}<\hat{w}_{j+1}$ for $1\leqslant j\leqslant |\hat{W}|-1$, and let $\hat{u}_{i}$ be the vertex in cluster $\hat{C}_{i}$ such that $\hat{u}_{i}.end=\hat{w}_{i}$ for $1\leqslant i\leqslant |\hat{W}|$. Let $\hat{U}_{i}$ be the set of clusters that are less than cluster $\hat{C}_{i}$, and let $\hat{W}_{i}=N(\hat{U}_{i})$. Let $G_{i}=(\hat{U}_{i},\hat{W}_{i},E_{i})$ be a subgraph of G induced by $\hat{U}_{i}\cup \hat{W}_{i}$, and let $\hat{G}_{i}=(\hat{U}_{i}\cup \hat{C}_{i},\hat{W}_{i},\hat{E}_{i})$ be a subgraph of G induced by $\hat{U}_{i}\cup \hat{C}_{i}\cup \hat{W}_{i}$, where $1\leqslant i \leqslant |\hat{W}|$. Then, G _i and $\hat{G}_{i}$ are convex bipartite graphs, $\hat{u}_{i}\not\in G_{i}$, $\hat{u}_{i}\in \hat{G}_{i}$, $\hat{w}_{i}\in G_{i}$, and $\hat{w}_{i}\in \hat{G}_{i}$. Let D _mpd|G′=D _mpd∩G′, where G′ is either G _i or $\hat{G}_{i}$. Then, $D_{\mathrm{mpd}|G_{i}}=D_{\mathrm{mpd}|\hat{G}_{i}}$. Let $D_{\mathrm{p}}=\{\hat{u}_{1},\hat{w}_{1}, \ldots,\hat{u}_{i-1},\hat{w}_{i-1}\}$ if i>1; otherwise, let D _p=∅. We will prove the following invariant:

$D_{{\mathrm{mpd}}|G_{i}}\cup D_{\mathrm{p}}$ is a minimum paired-dominating set of G _i , there exists no minimum paired-dominating set of G _i such that it contains $\hat{w}_{i}$, and $D_{{\mathrm{mpd}}|G_{i}}\cup D_{\mathrm{p}}\cup\{\hat{u}_{i},\hat{w}_{i}\}$ is a minimum paired-dominating set of $\hat{G}_{i}$.

Initially, consider the smallest vertex $\hat{w}_{1}$ of $\hat{W}$. Let $\tilde{U}_{1}$ and $\tilde{W}_{1}$ be the outputs of Procedure GD-U and Procedure GD-W given G ₁, respectively. By the construction of D _mpd, $|\tilde{U}_{1}|=|\tilde{W}_{1}|\geqslant 1$ and $\hat{w}_{1}$ is dominated by $\tilde{U}_{1}$. Then, $D_{\mathrm{mpd}|G_{1}}=\tilde{U}_{1}\cup\tilde{W}_{1}$ is a minimum paired-dominating set of G ₁ by Lemma 4. If there exists a set of paired vertices of G ₁ with size $|\tilde{U}_{1}|+|\tilde{W}_{1}|$ such that it contains $\hat{w}_{1}$, then it does not dominate at least one cluster of $\hat{U}_{1}$ since the clusters of $\hat{U}_{1}$ must be dominated by a subset of $\hat{W}_{1}$ whose cardinality is at least $|\tilde{W}_{1}|$, and, hence, it is not a dominating set. Thus, there exists no minimum paired-dominating set of G ₁ such that it contains $\hat{w}_{1}$. On the other hand, let $\tilde{U}_{1}^{\prime}$ and $\tilde{W}_{1}^{\prime}$ be the outputs of Procedure GD-U and Procedure GD-W given $\hat{G}_{1}$, respectively. Then, $\tilde{U}_{1}^{\prime}=\tilde{U}_{1}$ and $\tilde{W}_{1}^{\prime}=\tilde{W}_{1}\cup\{\hat{w}_{1}\}$. Since $|\tilde{U}_{1}|=|\tilde{W}_{1}|$, $|\tilde{W}_{1}^{\prime}|=|\tilde{U}_{1}|+1$. By Lemma 4, $\gamma_{p}(\hat{G}_{1})\geqslant 2\cdot\max\{|\tilde{W}_{1}^{\prime}|,|\tilde{U}_{1}^{\prime}|\}=$ $2\cdot|\tilde{W}_{1}^{\prime}|=2\cdot(|\tilde{U}_{1}^{\prime}|+1)$. Thus, $D_{{\mathrm{mpd}}|G_{1}}\cup\{\hat{u}_{1},\hat{w}_{1}\}$ is a minimum paired-dominating set of $\hat{G}_{1}$. Assume now the invariant holds true when i=h⩾1. Let $D_{\mathrm{p}}= \{\hat{u}_{1},\hat{w}_{1},\ldots, \hat{u}_{h-1},\hat{w}_{h-1}, \hat{u}_{h},\hat{w}_{h}\}$. Consider that G _h+1 and $\hat{G}_{h+1}$. Let $\tilde{U}_{h+1}$ and $\tilde{W}_{h+1}$ be the outputs of Procedure GD-U and Procedure GD-W given G _h+1, respectively. By the construction of D _mpd, $|\tilde{U}_{h+1}-\hat{G}_{h}|=|\tilde{W}_{h+1}-\hat{G}_{h}|\geqslant 1$ and $\hat{w}_{h+1}$ is dominated by $\tilde{U}_{h+1}$ since $\tilde{U}$ dominates $\tilde{w}_{h+1}$ but $\tilde{U}-\tilde{U}_{h+1}$ does not dominate $\tilde{w}_{h+1}$. By the induction hypothesis, $D_{\mathrm{mpd}|G_{h}} \cup D_{\mathrm{p}}$ is a minimum paired-dominating set of $\hat{G}_{h}$. Thus, $D_{\mathrm{mpd}|G_{h+1}}\cup D_{\mathrm{p}}$ is a minimum paired-dominating set of G _h+1. If there exists a set of paired vertices of G _h+1 with size $|D_{\mathrm{mpd}|G_{h+1}}\cup D_{\mathrm{p}}|$ such that it contains $\hat{w}_{h+1}$, then it does not dominate at least one cluster of $\hat{U}_{h+1}$ which is less than cluster $\hat{C}_{h+1}$, and, hence it is not a dominating set. Thus, there exists no minimum paired-dominating set of G _h+1 such that it contains $\hat{w}_{h+1}$. Since $D_{\mathrm{mpd}|G_{h+1}}\cup D_{\mathrm{p}}$ is a minimum paired-dominating set of G _h+1, there exists no minimum paired-dominating set of G _h+1 such that it contains $\hat{w}_{h+1}$, and $D_{\mathrm{mpd}|G_{h+1}}\cup D_{\mathrm{p}}$ is not a dominating set of $\hat{G}_{h+1}$, we get that $D_{\mathrm{mpd}|G_{h+1}}\cup D_{\mathrm{p}}\cup\{\hat{u}_{h+1},\hat{w}_{h+1}\}$ is a minimum paired-dominating set of $\hat{G}_{h+1}$. Thus, the invariant holds true when i=h+1. By induction then, the invariant holds true. This proves the optimality of our construction.

Next, we consider that $|\tilde{W}|=\max\{|\tilde{W}|,|\tilde{U}|\}$. By the similar construction for the case of $|\tilde{U}|=\max\{|\tilde{W}|,|\tilde{U}|\}$, we can construct a minimum paired-dominating set of G as follows. Initially, let D _mpd=∅. We first traverse the vertices of $\tilde{W}$ in an increasing manner, i.e., w _i is visited before w _i+1 for $1\leqslant i\leqslant |\tilde{W}|-1$. Suppose that it is about to process w _i . Let u _h be the smallest vertex of N(w _i ) such that it is in $\tilde{U}$ but is not in D _mpd. If such a vertex u _h does not exist, then let u _h be the vertex of cluster C _h such that w _i =u _h .end and $C_{h}\cap \tilde{U}=\emptyset$. By the construction of Procedure GD-W, u _h does exist. By pairing w _i with u _h , we obtain a new set D _mpd=D _mpd∪{w _i ,u _h }. After processing each vertex of $\tilde{W}$, let $\hat{U}=\tilde{U}-D_{\mathrm{mpd}}$. If $\hat{U}=\emptyset$, then D _mpd is a paired-dominating set of G with cardinality $2\cdot|\tilde{W}|$, and, hence, D _mpd is a minimum paired-dominating set of G by Lemma 4. Suppose that $\hat{U}\neq\emptyset$. Let $\hat{u}$ be the smallest vertex of $\hat{U}$ and let $\hat{w}$ be the vertex in W such that $\hat{w}=\hat{u}.\mathit{end}$. Then, D _mpd does not dominate $\hat{w}$ and hence it is not a dominating set of G. In this time, we pair $\hat{w}$ with $\hat{u}$, i.e., let $D_{\mathrm{mpd}}=D_{\mathrm{mpd}}\cup \{\hat{w},\hat{u}\}$, and let $\hat{U}=\hat{U}-\{\hat{u}\}$. Repeat the above process until $\hat{U}=\emptyset$. Then, D _mpd is the constructed paired-dominating set of G. The optimality of the above process can be verified by similar arguments in proving the case of $|\tilde{U}|=\max\{|\tilde{W}|,|\tilde{U}|\}$.

For instance, given I _min(U) and I _max(U) shown in Fig. 5, Procedure GD-W outputs $\tilde{W} = \{3,8\}$ and Procedure GD-U outputs $\tilde{U} =\{3,6,8\}$. Then, $|\tilde{U}|=\max\{|\tilde{W}|,|\tilde{U}|\}=3$. By the above construction, we obtain a set of pairs (3,3),(6,8),(8,12), where pair (u,w) satisfies that u∈U and w∈W, bold lines in Fig. 5 depicts such three pairs, and a minimum paired-dominating set D _mpd of size 6. Let k be the number of disjoint clusters of U. By Lemmas 2 and 4, $2k\geqslant \gamma_{p}(G)\geqslant 2\cdot\max\{|\tilde{W}|,|\tilde{U}|\}$. Then, $|U|\geqslant k\geqslant\max\{|\tilde{W}|,|\tilde{U}|\}$. Thus, the above process for constructing a minimum paired-dominating set of G runs in O(|U|) time, and, hence, Stage 4 can be done in O(|U|) time.

By Lemma 1, Stage 1 can be done in O(|U|+|W|) time. By Lemma 3, Stage 2 runs in O(|U|) time. By Lemmas 6 and 7, Stage 3 can be done in O(|U|+|W|) time. Thus, the algorithm runs in O(|U|+|W|) time and we conclude the following theorem.

Theorem 2

The paired-domination problem on an n-vertex convex bipartite graph given a compact representation can be solved in O(n) time.

5 The Total Domination Problem in Convex Bipartite Graphs

In this section, we will extend our algorithm to solve the total domination problem on convex bipartite graphs. Let G=(U,W,E) be a convex bipartite graph. Let $\tilde{U}$ and $\tilde{W}$ be the outputs of Procedure GD-U and Procedure GD-W given I _max(U) and I _min(U) of G, respectively, and let $D_{\mathrm{mtd}}=\tilde{U}\cup\tilde{W}$. We will show that D _mtd is a minimum total dominating set of G, i.e., $\gamma_{t}(G)=|\tilde{U}|+|\tilde{W}|$. Note that $\tilde{U}$ and $\tilde{W}$ are minimum cardinality subsets of U and W, respectively, such that $\tilde{U}$ dominates W and $\tilde{W}$ dominates U, and that C ₁,C ₂,…,C _k are sorted clusters of U.

We first partition U into three disjoint subsets U _min, U _max, and $\overline{U}$ such that U _min=⋃_1⩽i⩽k min(C _i ), U _max=⋃_1⩽i⩽k max(C _i ), and $\overline{U}=U-(U_{\min}\cup U_{\max})$. Then, N(min(C _i ))⊆N(u)⊆N(max(C _i )) for u∈C _i . We first claim that there exists a minimum total dominating set $\mathcal{D}_{\mathrm{td}}$ of G such that $(\mathcal{D}_{\mathrm{td}}\cap U)\subseteq U_{\max}$. We will prove the above claim as follows. Assume that $\mathcal{D}_{\min}$ is a minimum total dominating set of G. Let $\mathcal{D}_{U_{\min}}=\mathcal{D}_{\min}\cap U_{\min}$, $\mathcal{D}_{U_{\max}}=\mathcal{D}_{\min}\cap U_{\max}$, $\mathcal{D}_{\overline{U}}=\mathcal{D}_{\min}\cap \overline{U}$, and let $\mathcal{D}_{W}=D_{\min}\cap W$. Consider that $\mathcal{D}_{U_{\min}}\neq\emptyset$. Let $u_{\min}\in D_{U_{\min}}$ and u _max∈U _max such that u _min and u _max are in the same cluster. Then, N(u _min)⊆N(u _max). Since $\mathcal{D}_{\min}$ is a total dominating set of G, u _min is adjacent to at least one vertex of $\mathcal{D}_{W}$. Thus, $\mathcal{D}_{W}$ dominates u _min. If $u_{\max}\in \mathcal{D}_{\min}$, then $\mathcal{D}_{\min}-\{u_{\min}\}$ is still a total dominating set of G since N(u _min)⊆N(u _max) and $\mathcal{D}_{W}$ dominates u _min, and, hence, it contradicts that $\mathcal{D}_{\min}$ is a minimum total dominating set of G. Thus, $u_{\max}\not\in \mathcal{D}_{\min}$. Let $\mathcal{D}_{\mathrm{td}}=\mathcal{D}_{\min}-\{u_{\min}\}\cup\{u_{\max}\}$. Then, $\mathcal{D}_{\mathrm{td}}$ is a total dominating set of G with size $|\mathcal{D}_{\min}|$. Thus, there exists a minimum total dominating set $\mathcal{D}_{\mathrm{td}}$ of G such that $\mathcal{D}_{\mathrm{td}}\cap U_{\min}=\emptyset$. By the same arguments, we can show that there exists a minimum total dominating set $\mathcal{D}_{\mathrm{td}}$ of G such that $\mathcal{D}_{\mathrm{td}}\cap \overline{U}=\emptyset$. It follows from the above arguments that the claim holds true.

By the above claim, there exists a minimum total dominating set $\mathcal{D}_{\mathrm{td}}$ of G such that $(\mathcal{D}_{\mathrm{td}}\cap U)\subseteq U_{\max}$. Then, $|\mathcal{D}_{\mathrm{td}}|=|\mathcal{D}_{\mathrm{td}}\cap W|+|\mathcal{D}_{\mathrm{td}}\cap U_{\max}|$. Since $\mathcal{D}_{\mathrm{td}}$ is a total dominating set of G, every vertex of $\mathcal{D}_{\mathrm{td}}\cap W$ (resp. $\mathcal{D}_{\mathrm{td}}\cap U_{\max}$) is adjacent to at least one vertex of $\mathcal{D}_{\mathrm{td}}\cap U_{\max}$ (resp. $\mathcal{D}_{\mathrm{td}}\cap W$). Thus, $\mathcal{D}_{\mathrm{td}}\cap U_{\max}$ dominates W and $\mathcal{D}_{\mathrm{td}}\cap W$ dominates U. By the constructions of $\tilde{U}$ and $\tilde{W}$, $|\mathcal{D}_{\mathrm{td}}\cap U_{\max}|\geqslant |\tilde{U}|$ and $|\mathcal{D}_{\mathrm{td}}\cap W|\geqslant |\tilde{W}|$. Thus, $|\mathcal{D}_{\mathrm{td}}| \geqslant |\tilde{U}|+|\tilde{W}|=|D_{\mathrm{mtd}}|$. That is, $D_{\mathrm{mtd}}=\tilde{U}\cup\tilde{W}$ is a minimum total dominating set of G. Therefore, we conclude the following theorem.

Theorem 3

The total domination problem on an n-vertex convex bipartite graph given a compact representation can be solved in O(n) time.

6 Concluding Remarks

The paired-domination problem on bipartite graphs has been shown to be NP-complete. The complexity of the paired-domination problem on convex bipartite graphs was unknown prior to our work. In this paper, we give an innovative approach to solve the paired-domination problem on convex bipartite graphs given a compact representation in O(n) time. We also show that the proposed approach can be directly applied to solve the total domination problem on convex bipartite graphs in the same time bound. To the best of our knowledge, the best algorithms for the domination and independent domination problems on convex bipartite graphs run in O(n ²) time. It is interesting to see if the proposed procedures can be used to solve the domination and independent domination problems on convex bipartite graphs given a compact representation in O(n) time. We would like to post it as an open problem to interested readers.