Performance Guaranteed Evolutionary Algorithm for Minimum Connected Dominating Set

Except for $\emptyset$, every vertex set $C$ has $p(C)\geq 1$ and $q(C)\geq 1$. So, $f_{1}(C)\geq 2$ and equality holds if and only if $p(C)=q(C)=1$. A CDS $C$ clearly satisfies $p(C)=q(C)=1$ and thus $f_{1}(C)=2$. On the other hand, if $C$ is not a dominating set, then there is a vertex $v\in V\setminus C$ which has no neighbor in $C$. In this case, $v$ forms a connected component itself in $G\langle C\rangle$, and thus $G\langle C\rangle$ has at least two connected components. So, $q(C)=1$ holds only when $C$ is a dominating set. Furthermore, the condition $p(C)=1$ is equivalent to saying that $G[C]$ is connected. So a vertex set $C$ with $p(C)=q(C)=1$ must be a CDS. ∎

$(i)$ We prove property $(i)$ by distinguishing two cases.

In the case $q(C)>1$, $C$ is not a dominating set by the proof of Lemma 3.1. By the connectedness of $G$, there exists a vertex $v\in V\setminus C$ such that $v$ is not adjacent with $C$ and $v$ is adjacent with a vertex $u\in N(C)$ where $N(C)$ is the neighbor set of $C$. Then $p(C\cup\{u\})\leq p(C)$ and $q(C\cup\{u\})<q(C)$.

In the case $q(C)=1$, since $f_{1}(C)>2$, we have $p(C)>1$. So, $G[C]$ has at least two connected components. By $q(C)=1$, it can be seen that the closest connected components of $G[C]$ is exactly 2-hops away from each other, which implies that there is a vertex $v\in V\setminus C$ that is adjacent to at least two connected components of $G[C]$. In this case, $p(C\cup\{v\})<p(C)$ and $q(C\cup\{v\})=q(C)=1$.

In any case, $f_{1}(C\cup\{v\})<f_{1}(C)$. By the choice of $v_{C}$, and because $f_{1}$ is an integer-valued set function, we have $f_{1}(C\cup\{v_{C}\})\leq f_{1}(C\cup\{v\})\leq f_{1}(C)-1$.

$(ii)$ In order to prove $(ii)$, we show that there is a vertex in an optimal solution the addition of which satisfies the claimed inequality.

Let $C^{*}$ be a minimum CDS of $G$. Since $G[C^{*}]$ is connected, we may order vertices in $C^{*}$ as $v_{1}^{*},v_{2}^{*},\ldots,v_{m}^{*}$ such that for any $j=1,\ldots,m$, the subgraph of $G$ induced by vertex set $C_{j}^{*}=\{v_{1}^{*},v_{2}^{*},\ldots,v_{j}^{*}\}$ is connected. This can be done by finding a spanning tree of $G[C^{*}]$ and removing leaf vertices one by one, ordering the vertices in the reverse order of their removal. Due to the connectedness of $G[C_{j-1}^{*}]$, it can be seen that

Furthermore, it could be proved that function $-q$ is submodular and thus

It follows that

Rewrite $f_{1}(C)-f_{1}(C\cup C^{*})$ in the following way:

where $C_{0}^{*}=\emptyset$. Making use of inequality (1), and the fact $f(C\cup C^{*})=2$ (because $C\cup C^{*}$ is a CDS), we have

Let $v_{j_{0}}^{*}=\arg\max_{v_{j}^{*}}\{f_{1}(C)-f_{1}(C\cup\{v_{j}^{*}\})\}$. Then

By the choice of $v_{C}$, we have

and thus $f_{1}(C\cup\{v_{C}\})\leq\left(1-\frac{1}{m}\right)f_{1}(C)+\frac{2}{m}+1$. Property $(ii)$ is proved. ∎

Let $m$ be the size of a minimum CDS of $G$. Notice that although we use the optimal value $m$ in the analysis, the algorithm does not depend on $m$.

For $i=2,3,\ldots,n$, let $B_{i}$ be the bin which contains the individual in $P$ whose $f_{1}$-value equals $i$. Notice that at any time, each bin contains at most one individual, this is because for any two individuals created in the evolutionary process, if they have the same $f_{1}$-value, then only the one with the smaller $f_{2}$-value is kept in $P$. To track a “path” of desirable mutations, we only consider those bins containing good individuals, where an individual $\bf x$ is said to be “good” if it satisfies the following constraint:

Claim 1. Any good individual ${\bf x}$ with $f_{1}({\bf x})\geq 2m+2$ has $|{\bf x}|\leq m\ln\Delta$.

By the definition of good individual,

Using $(1-\frac{1}{m})^{|{\bf x}|}\leq e^{-\frac{|{\bf x}|}{m}}$, it can be derived that

Since every vertex can dominate at most $\Delta+1$ vertices, we have $n\leq(\Delta+1)m$, and thus $\frac{n-2-m}{m}\leq\Delta$. Hence $|{\bf x}|\leq m\ln\Delta$, Claim 1 is proved.

Claim 2. Suppose $\bf x$ is a good individual. Then, an individual ${\bf x}^{\prime}$ with $f_{1}({\bf x}^{\prime})\leq f_{1}({\bf x})$ and $|{\bf x}^{\prime}|\leq|{\bf x}|$ is also good.

This is because

Claim 3. Suppose $\bf x$ is a good individual, let ${\bf x}^{\prime}$ be the vector corresponding to vertex set $C_{\bf x}\cup\{v_{C_{\bf x}}\}$, where $v_{C_{{\bf x}}}=\arg\max_{v\in V\setminus C_{{\bf x}}}\{f_{1}(C_{{\bf x}})-f_{1}(C_{{\bf x}}\cup\{v\})\}$. Then

$(2.1)$ $|{\bf x}^{\prime}|=|{\bf x}|+1$,

$(2.2)$ $f_{1}({\bf x^{\prime}})\leq f_{1}({\bf x})-1$, and

$(2.3)$ ${\bf x}^{\prime}$ is also a good individual.

Property $(2.1)$ is obvious, and property $(2.2)$ is a consequence of Lemma 4.1 $(i)$. Next, we show property $(2.3)$. By Lemma 4.1 $(ii)$,

Since $\bf x$ is good and $|{\bf x}^{\prime}|=|{\bf x}|+1$, we have

Hence $\bf x^{\prime}$ is also a good individual.

An individual ${\bf x}^{\prime}$ generated by the way described in Claim 2 is desirable, for convenience, we call such ${\bf x}^{\prime}$ to be the best offspring of $\bf x$.

Next, we define an indicator $J_{i}$ for each bin $B_{i}$ such that individuals contained in bins with indicator 1 are all good.

Initially, only $J_{n}=1$ and all other $J_{i}=0$ for $i=2,3,\ldots,n-1$.

When we say that bin $B_{i}$ is going to be filled with an individual ${\bf x}^{\prime}$, it refers to the setting that the newly generated individual ${\bf x}^{\prime}$ can be put into $B_{i}$, either because $B_{i}$ is empty and $i=f_{1}({\bf x}^{\prime})$, or because ${\bf x}^{\prime}$ can replace the individual ${\bf x}$ in $B_{i}$ due to $f_{1}({\bf x}^{\prime})=f_{1}({\bf x})=i$ and $|{\bf x}^{\prime}|\leq|{\bf x}|$.

When bin $B_{i}$ is going to be filled with an individual ${\bf x}^{\prime}$, its indicator $J_{i}$ is changed from 0 to 1 if one of the following two good events occur.

$(i)$ There is an individual $\bar{\bf x}$ belonging to a bin $B_{j}$ with indicator $J_{j}=1$ such that its best offspring $\bar{\bf x}^{\prime}$ is weakly worse than ${\bf x}^{\prime}$, that is

$(ii)$ There is an individual $\bar{\bf x}$ belonging to a bin $B_{j}$ with indicator $J_{j}=1$ such that

It is possible that indicator $J_{i}$ can be changed from 1 to 0: if the individual contained in bin $B_{i}$ is removed from the population because of the creation of a better individual, then $J_{i}$ is set to be 0.

Claim 4. Any bin $B_{i}$ with $J_{i}=1$ contains a good individual.

We first show that if current $B_{i}$ contains a good individual, then as long as $B_{i}$ continues to be non-empty, the individual contained in $B_{i}$ is always good. In fact, suppose $\bf x$ is a good individual in $B_{i}$, it can be replaced by another individual ${\bf x}^{\prime}$ only when $f_{1}({\bf x^{\prime}})=f_{1}({\bf x})$ and $|{\bf x^{\prime}}|\leq|{\bf x}|$. Then by Claim 2, $\bf x^{\prime}$ is also good.

So, as long as we can show the following property:

then all individuals contained in $B_{i}$ during the span when $J_{i}=1$ will be good. Next, we use induction on the process of assigning indicator 1’s to prove (6).

Initially, only $J_{n}=1$, and $B_{n}=\{{\bf x}^{(0)}\}$. Notice that $|{\bf x^{0}}|=0$ and $f_{1}({\bf x^{0}})=n=(n-2-m)(1-\frac{1}{m})^{0}+m+2$, so ${\bf x}^{(0)}$ is a good individual.

Suppose the claim is true for all bins with indicator 1 in current population, and after some mutation, $J_{i}$ is to be changed from 0 to 1. The first case for such a change is because of the existence of ${\bf x}^{\prime},\bar{\bf x},\bar{\bf x}^{\prime}$ satisfying (4). By induction hypothesis, $\bar{\bf x}$ is good. By Claim 3, $\bar{\bf x}^{\prime}$ is also good. Then by condition (4) and Claim 2, ${\bf x}^{\prime}$ is also good. The second case for such a change is because of the existence of ${\bf x}^{\prime},\bar{\bf x}$ satisfying (5). By induction hypothesis, $\bar{\bf x}$ is good, and thus by Claim 2, ${\bf x}^{\prime}$ is good. Claim 4 is proved.

The following analysis is divided into two phases. For each phase, a potential will be used to track the progress of the algorithm.

Define a potential $I$ with respect to current population $P$ to be the integer

The initial population $P=\{{\bf x}^{(0)}\}$ has potential $I=n$.

Claim 5. Potential $I$ will never increase, and the expected time for $I$ to be decreased by at least 1 is at most $n(n-1)$.

Suppose $\bar{\bf x}$ is the individual corresponding to current potential $I$. As long as $\bar{\bf x}$ remains in $P$, the value of $I$ will not increase. By the algorithm, $\bar{\bf x}$ can be removed from $P$ only when a newly generated individual ${\bf x^{\prime}}$ satisfies $f_{1}({\bf x^{\prime}})\leq f_{1}(\bar{\bf x})$ and $|{\bf x^{\prime}}|\leq|\bar{\bf x}|$. If $f_{1}({\bf x}^{\prime})=f_{1}(\bar{\bf x})$, then $\bar{\bf x}$ is replaced by ${\bf x}^{\prime}$ and $I$ remains the same. If $f_{1}({\bf x}^{\prime})<f_{1}(\bar{\bf x})$, then by (5), the birth of ${\bf x}^{\prime}$ makes $J_{i^{\prime}}$ to change from 0 to 1, where $i^{\prime}=f_{1}({\bf x}^{\prime})<f_{1}(\bar{\bf x})=i$. In this case, the new $I^{\prime}=i^{\prime}<I$. In any case, $I$ will not increase.

Next, we consider the expected time to reduce $I$. If the mutation picks $\bar{\bf x}$ and generates its best offspring $\bar{\bf x}^{\prime}$, then $J_{i}$ can be changed from 0 to 1, where $i=f_{1}(\bar{\bf x}^{\prime})\leq f_{1}(\bar{\bf x})-1<I$ (notice that before the mutation, $J_{i}$ must be $0$ since $I$ is the smallest index for the bin with indicator 1). Notice that the probability of choosing $\bar{\bf x}$ in line 4 of Algorithm 1 is $\frac{1}{|P|}$, and the probability of obtaining its best offspring $\bar{\bf x}^{\prime}$ in line 5 of Algorithm 1 is $\frac{1}{n}$. So, the probability

where $|P|\leq n-1$ is used since $f_{1}$ has at most $n-1$ distinct values, namely $2,3,\ldots,n$, and no solutions having the same $f_{1}$-value can coexist in $P$ by line 7 of the algorithm.

Notice that the derivation of (8) is valid starting from “any” individual in the population achieving current potential, even when the above $\bar{\bf x}$ is removed from $P$ due to the entering of a better individual. So, the expected number of mutations for potential $I$ to be decreased by at least $1$ is at most $n(n-1)$. Claim 5 is proved.

By Claim 5, in expected $n(n-1)(n-2)$ iterations, $I$ could be reduced from $n$ to $2$. However, merely tracking potential $I$ could not guarantee that the final solution has small size. In fact, since $f_{1}(V)=2$, the vector ${\bf x}^{(1)}=(1,1,\ldots,1)$ satisfies (2), and thus $V$ is also a good individual, whose size is clearly too large. From the algorithmic point of view, when $f_{1}({\bf x})$ is small, the decreasing speed of $f_{1}$ implied by Lemma 4.1 $(ii)$ will slow down. So, we shall track another potential after the $f_{1}$-value becomes smaller than $2m+2$. The details are given as follows.

If $n<2m+2$, then the approximation ratio $2+\ln\Delta$ holds for the trivial solution $V$. So, we assume $n\geq 2m+2$ in the following. Since the initial value for $I$ is $n\geq 2m+2$, and the final value for $I$ is $2<2m+2$, there must be a time when $I$ jumps over $2m+2$. That is, there exists a mutation, before which potential $\widetilde{I}\geq 2m+2$, after which potential $\widetilde{I}^{\prime}\leq 2m+1$.

Define a second potential $K$ as follows.

Claim 6. Let $\widetilde{\bf x}^{\prime}$ be the individual corresponding to $\widetilde{I}^{\prime}$. Then $\widetilde{\bf x}^{\prime}$ satisfies the constraint in (9). Hence from the time when $\widetilde{\bf x}^{\prime}$ enters population $P$, potential $K$ is well-defined, and $K\leq f_{1}(\widetilde{\bf x}^{\prime})=\widetilde{I}^{\prime}\leq 2m+1$.

The core part for the proof of Claim 6 is to show that $\widetilde{\bf x}^{\prime}$ satisfies the constraint in (9). Since we are considering the time when potential $\widetilde{I}\geq 2m+2$ is jumped down to $\widetilde{I}^{\prime}=f_{1}(\widetilde{\bf x}^{\prime})\leq 2m+1$, the creation of $\widetilde{\bf x}^{\prime}$ incurs the change of $J_{\widetilde{I}^{\prime}}$ from 0 to 1. The reason for such a change is because of the existence of a bin $B_{j}$ with $J_{j}=1$ and the individual $\bar{\bf x}$ in $B_{j}$ satisfying constraint (4) or constraint (5) (with ${\bf x}^{\prime}$ replaced by $\widetilde{\bf x}^{\prime}$), that is,

or

Since $J_{j}=1$, by Claim 4, $\bar{\bf x}$ is good. Since $\widetilde{I}$ is the smallest index of bins with indicator 1 before the mutation, we have $j\geq\widetilde{I}\geq 2m+2$. So $\bar{\bf x}$ is a good individual with $f_{1}(\bar{\bf x})=j\geq 2m+2$. Then by Claim 1,

Since $\bar{\bf x}^{\prime}$ is the best offspring of $\bar{\bf x}$, we have

So, in the first case, namely (10), we have

The second case (11) is easier by using (12). Claim 6 is proved.

Claim 7. The potential $K$ never increases and the expected time for $K$ to be decreased by at least 1 is at most $n(n-1)$.

To prove the monotonicity of $K$, similar to the proof of Claim 5, it suffices to consider a solution $\bar{\bf x}$ corresponding to current $K$, and the case that $\bar{\bf x}$ is removed from $P$. In such a case, a newly generated solution ${\bf x^{\prime}}$ satisfies $f_{1}({\bf x^{\prime}})\leq f_{1}(\bar{\bf x})$ and $|{\bf x^{\prime}}|\leq|\bar{\bf x}|$. Such ${\bf x^{\prime}}$ satisfies $|{\bf x^{\prime}}|+f_{1}({\bf x^{\prime}})\leq|\bar{\bf x}|+f_{1}(\bar{\bf x})\leq m\ln\Delta+2m+2$. So $\bf x^{\prime}$ also satisfies the constraint in (9), and thus replacing $\bar{\bf x}$ by ${\bf x^{\prime}}$ will not increase $K$.

To prove the second part of Claim 7, observe that if a mutation picks $\bar{\bf x}$ which corresponds to current $K$ and generates its best offspring $\bar{\bf x}^{\prime}$, then by Claim 3, $f_{1}(\bar{\bf x}^{\prime})\leq f_{1}(\bar{\bf x})-1<K$ and $|\bar{\bf x}^{\prime}|=|\bar{\bf x}|+1$. It follows that $|\bar{\bf x}^{\prime}|+f_{1}(\bar{\bf x}^{\prime})\leq|\bar{\bf x}|+f_{1}(\bar{\bf x})\leq m\ln\Delta+2m+2$ and thus $\bar{\bf x}^{\prime}$ also satisfies the constraint in (9). Hence the new potential $K^{\prime}\leq f_{1}(\bar{\bf x}^{\prime})<K$. The expected time for the occurrence of such an event is at most $n(n-1)$, as in the proof of Claim 5. So, Claim 7 is proved.

Claim 8. Starting from initial individual ${\bf x}^{(0)}$, the expected time for $K$ reaching 2 is at most $n(n-1)(n-2)$.

By Claim 5, the expected time for potential $I$ to decrease from $f_{1}({\bf x}^{(0)})=n$ to $\widetilde{I}^{\prime}=f_{1}(\widetilde{\bf x}^{\prime})$ is at most $\big{(}n-\widetilde{I}^{\prime}\big{)}n(n-1)$. Then by Claim 7, potential $K$ becomes well-defined and keeps decreasing, and the the expected time for $K$ to decrease from $\widetilde{I}^{\prime}=f_{1}(\widetilde{\bf x}^{\prime})$ to 2 is at most $(\widetilde{I}^{\prime}-2)n(n-1)$. Adding them together, the total expected time for $K$ reaching 2 is at most $n(n-1)(n-2)$.

Now, we are ready to finish the proof of the theorem. Suppose ${\bf x}^{A}$ is the individual corresponding to $K=2$, then $f_{1}({\bf x}^{A})=2$ implies that the vertex set corresponding to ${\bf x}^{A}$ is a CDS. Combining this with $f_{1}({\bf x}^{A})+|{\bf x}^{A}|\leq m\ln\Delta+2m+2$ implies that $|{\bf x}^{A}|\leq(2+\ln\Delta)m$, that is, ${\bf x}^{A}$ approximates the optimal solution within a factor at most $2+\ln\Delta$. Furthermore, Claim 8 shows that the expected time to obtain such ${\bf x}^{A}$ is at most $n(n-1)(n-2)$. ∎