17.3.2. Analysis

A Simple Analysis

To have a point of reference for evaluating the effectiveness of applying Measure and Conquer to this algorithm, let us investigate first how good a time bound we can prove by simply considering the input size of each invocation. A natural notion of the "size" of an input \((U, \mathcal{S})\) is \(|U| + |\mathcal{S}|\), especially because any set cover instance derived from a dominating set instance satisfies \(|U| = |\mathcal{S}| = n\). Since Rule 6 branches only on sets \(S \in \mathcal{S}\) with \(|S| \ge 3\), the instance \((U \setminus S, \mathcal{S} - S)\) satisfies \(|U \setminus S| \le |U| - 3\) and \(|\mathcal{S} - S| \le |\mathcal{S}| - 1\). Thus, \(|U \setminus S| + |\mathcal{S} - S| \le |U| + |\mathcal{S}| - 4\). The instance \((U, \mathcal{S} \setminus \{S\})\) clearly satisfies \(|\mathcal{S} \setminus \{S\}| = |\mathcal{S}| - 1\). Thus, the branching vector of Rule 6 is \((1,4)\), which gives a running time of \(O^*\bigl(1.39^{|U|+|\mathcal{S}|}\bigr)\). Since every set cover instance derived from a dominating set instance satisfies \(|U| = |\mathcal{S}| = n\), this algorithm can be used to solve the dominating set problem in \(O^*\bigl(1.39^{2n}\bigr) = O^*(1.91^n)\) time. Next we use Measure and Conquer to obtain the bound in Corollary 17.6, which substantially improves on this naïve bound.

A Measure & Conquer Analysis

The intuition behind the weight function we use in our analysis is the following:

Let the frequency \(f_e\) of an element \(e \in U\) be the number of sets in \(\mathcal{S}\) that contain \(e\). Now consider a set \(S \in \mathcal{S}\). If we branch on this set, we either include it in \(\mathcal{S}\), in which case we remove \(|S|\) elements from \(U\), or we do not, in which case we remove \(S\) from \(\mathcal{S}\) and thereby decrease the frequency of every element in \(S\). Every element of frequency \(1\) forces the unique set in \(\mathcal{S}\) that contains \(e\) to be included in the set cover, as done in Rule 3 of our algorithm, and thus reduces the instance further. Thus, the larger the set \(S\) is that Rule 6 branches on, the greater the reduction of the size of \(U\) in the case when \(S\) is included in the set cover and the greater the number of elements in \(U\) that come closer to having frequency \(1\) and forcing the inclusion of another set in the set cover without branching. This suggests that large sets are more beneficial to the algorithm and should have a greater weight.¹ Thus, we define weights \(0 = w_1 \le w_2 \le \cdots\), where \(w_s\) is the weight of a set of size \(s\). We set \(w_1 = 0\) because singleton sets are removed by Rule 2 or Rule 3.

We can make a similar argument for the elements in \(U\). Whenever we remove an element \(e\) from \(U\) because it is covered by the set just chosen, this reduces the size of \(f_e - 1\) sets. Thus, the greater \(f_e\), the more the complexity of the remaining instance is reduced. This suggests that we should assign weights \(0 = v_1 \le v_2 \le \cdots\) to the elements, where \(v_f\) is the weight of an element \(e\) with frequency \(f_e\). We set \(v_1 = 0\) because elements with frequency 1 are removed by Rule 3 without branching.

The weight of an instance is now defined as

\[w(U,\mathcal{S}) = \sum_{e \in U} v_{f_e} + \sum_{S \in \mathcal{S}} w_{|S|}.\]

Note that this definition of \(w(U,\mathcal{S})\) involves up to \(|U| + |\mathcal{S}| \le 2n\) distinct weights. Finding the optimal combination of that many weights is infeasible even using a computer-aided exhaustive search. We therefore set \(v_i = w_i = 1\) for all \(i \ge 6\), which leaves us with the problem of choosing 8 weights: \(v_2, \ldots, v_5\) and \(w_2, \ldots, w_5\).

Based on these weights, we can also define the drop in the weight of a set when its size decreases from \(s\) to \(s-1\) and the drop in the weight of an element when its frequency decreases from \(f\) to \(f-1\):

\[\begin{aligned} \Delta w_s &= w_s - w_{s-1} \ge 0 && \forall s \ge 2\\ \Delta v_f &= v_f - v_{f-1} \ge 0 && \forall f \ge 2. \end{aligned}\]

A final assumption we make is that these weight differences are non-increasing as \(s\) or \(f\) increases:

\[\begin{aligned} \Delta w_s &\ge \Delta w_{s+1} && \forall s \ge 2\\ \Delta v_f &\ge \Delta v_{f+1} && \forall f \ge 2. \end{aligned}\]

This assumption is made mainly for the purpose of restricting the search for suitable weights further but they also have an intuitive justification: Decreasing the size of a set by 1 or decreasing the frequency of an element by 1 moves the set or element closer to being a singleton set or an element of frequency 1 and thus closer to removal without branching. However, if the set is large or the element has a high frequency, many more modifications of the input are required before the set finally has size 1 or the element has frequency 1. Thus, the impact of decreasing the size of a set or the frequency of an element on the running time of the algorithm seems to be greater for small sets and infrequent elements.

Now consider an application of Rule 6. In the recursive call on \((U, \mathcal{S} \setminus \{S\})\), \(S\) is no longer part of the input. This reduces the weight of the input by \(w_{|S|}\).

Every frequency-\(f\) element in \(S\) becomes a frequency-\((f-1)\) element as a result of removing \(S\). Thus, if \(m_f\) is the number of frequency-\)f\) elements in \(S\), the weight of the input \((U, \mathcal{S} \setminus \{S\})\) is further reduced by

\[\sum_{f \ge 2} \Delta v_f \cdot m_f = \sum_{f=2}^6 \Delta v_f \cdot m_f.\]

Frequency-\(2\) elements have the greatest impact because they become frequency-\(1\) elements and thus immediately trigger the application of Rule 3 in the recursive call on \((U, \mathcal{S} \setminus \{S\})\). Let \(S_1, \ldots, S_h\) be the sets in \(\mathcal{S} \setminus \{S\}\) that share at least one frequency-\(2\) element with \(S\) and, for \(1 \le i \le h\), let \(o_i\) be the number of frequency-\(2\) elements in \(S\) that are in \(S_i\). We have \(|S_i| \ge o_i + 1\) because \(S_i \not\subseteq S\). Thus, the removal of \(S_i\) from the input by Rule 3 reduces the weight of the input \((U, \mathcal{S} \setminus \{S\})\) by \(w_{|S_i|} \ge w_{o_i+1}\) (because weights are non-decreasing). Since \(S_1, \ldots, S_h \not\subseteq S\), the removal of all these sets in the recursive call on \((U, \mathcal{S} \setminus \{S\})\) removes at least one additional element \(e'\) not in \(S\), which reduces the weight of the input by \(v_{f_{e'}} \ge v_2\). By distinguishing the first few possible values of \(m_2\) and of the size of \(S\), we obtain a reduction of the weight of the input due to the application of Rule 3 to \(S_1, \ldots, S_h\) by at least

\[\delta = \begin{cases} 0 & \text{if } m_2 = 0\\ v_2 + w_2 & \text{if } m_2 = 1\\ v_2 + w_3 & \text{if } m_2 = 2\\ v_2 + w_2 + w_3 & \text{if } m_2 = 3 \text{ and } |S| = 3\\ v_2 + w_4 & \text{if } m_2 \ge 3 \text{ and } |S| \ge 4. \end{cases}\]

The case \(m_2 = 0\) is obvious because Rule 3 is not applied to any elements if \(m_2 = 0\) because the removal of \(S\) does not create any frequency-\(1\) elements in this case.

If \(m_2 = 1\), then exactly one set \(S_1\) is removed, which has weight at least \(w_2\). Thus, the weight reduces by at least \(w_2\) plus the weight of the element \(e'\) in \(S_1 \setminus S\), which has weight at least \(v_2\). The weight reduction is at least \(v_2 + w_2\) in this case.

If \(m_2 = 2\), then either \(h = 1\) and \(o_1 = 2\) or \(h = 2\) and \(o_1 = o_2 = 1\). In the first case, the weight of \(S_1\) is at least \(w_3\). In the second case, both \(S_1\) and \(S_2\) have weight at least \(w_2\). Thus, the weight of the input is reduced by at least \(v_2 + \min(2w_2, w_3)\). Finally, observe that \(\min(2w_2, w_3) = w_3\) because \(w_3 = w_2 + \Delta w_3 \le w_2 + \Delta w_2 = w_2 + w_2\) because we assumed that the \(\Delta w_s\) are non-increasing and \(\Delta w_2 = w_2\).

The analysis of the case \(m_2 = 3\) and \(|S| = 3\) is analogous: If \(m_3 = 3\) and \(|S| = 3\), then \(h = 2\) or \(h = 3\); the case \(h = 1\) is impossible because this would imply that \(|S_1| \ge 4\) but \(|S| = 3\) and \(S\) is the largest set in \(\mathcal{S}\). Since \(\sum_{i=1}^h o_i = m_2 = 3\), this gives w.l.o.g. \(o_1 = 2\) and \(o_2 = 1\) or \(o_1 = o_2 = o_3 = 1\). Thus, the application of Rule 3 to \(S_1, \ldots, S_h\) decreases the weight of the input by at least \(v_2 + \min(3w_2, w_2 + w_3) = v_2 + w_2 + w_3\) because we just argued that \(2w_2 \ge w_3\) and thus \(3w_2 \ge w_2 + w_3\).

In the final case, applying Rule 3 to more and larger sets can only help. Thus, the worst case arises when \(m_2 = 3\) and \(|S| = 4\). In this case, we have \(1 \le h \le 3\) and either \(o_1 = 3\), \(o_1 = 2\) and \(o_2 = 1\) or \(o_1 = o_2 = o_3 = 1\). Thus, the weight of the input is reduced by at least \(v_2 + \min(3w_2, w_2 + w_3, w_4)\). Since \(3w_2 \ge w_2 + w_3\), as just argued, this is at least \(v_2 + \min(w_2 + w_3, w_4)\). Since \(w_4 = w_3 + \Delta w_4 \le w_3 + \Delta w_2 = w_3 + w_2\), this is at least \(v_2 + w_4\). In summary, after applying the non-branching reduction rules Rule 1–3 to the input \((U, \mathcal{S} \setminus \{S\})\), we obtain an input of weight at most

\[w(U,\mathcal{S}) - \left(w_{|S|} + \sum_{f=2}^6 (\Delta v_f \cdot m_f) + \delta\right).\tag{17.1}\]

Now consider the recursive call on \((U \setminus S, \mathcal{S} - S)\). Let \(m_{\ge f} = \sum_{i \ge f} m_f\) be the number of elements of frequency at least \(f\) in \(S\). The removal of an element of frequency \(f\) from \(U\) decreases the weight of the input by \(v_f\). Thus, the removal of the elements in \(S\) from \(U\) reduces the weight of the input by

\[\sum_{f \ge 2} v_f m_f = \sum_{f=2}^6 v_f m_f + m_{\ge 7}\tag{17.2}\]

because \(v_f = 1\) for \(f \ge 7\).

For a frequency-\(f\) element \(e\) in \(S\), let \(S_1, \ldots, S_{f-1}\) be the other \(f-1\) sets containing \(e\). The removal of \(e\) from \(U\) decreases the size of \(S_1, \ldots, S_{f-1}\) by one and thus decreases the weight of the input by \(\sum_{i=1}^{f-1} \Delta w_{|S_i|}\). The choice of \(S\) ensures that \(|S_i| \le |S|\) and, thus, \(\Delta w_{|S_i|} \ge \Delta w_{|S|}\) for all \(1 \le i \le f-1\). Thus, we can lower-bound this decrease of the weight by \(\Delta w_{|S|}(f - 1)\). If no two elements in \(S\) are contained in the same set in \(\mathcal{S} \setminus \{S\}\), this gives a lower bound of

\[\Delta w_{|S|} \sum_{f \ge 2} (f - 1)m_f \ge \Delta w_{|S|} \left(\sum_{f=2}^6 (f-1) m_f + 6 \cdot m_{\ge 7}\right) \tag{17.3}\]

on the decrease of the weight due to the decrease of the size of the sets sharing elements with \(S\). In the case when some set \(S'\) shares \(t \ge 2\) elements \(e_1, \ldots, e_t\) with \(S\), the removal of these elements decreases the weight of \(S'\) by \(\Delta w_{|S'|} + \Delta w_{|S'|-1} + \cdots + \Delta w_{|S'|-t+1}\). Since the \(\Delta w_s\) values are non-increasing, this is at least \(\Delta w_{|S'|} \cdot t\). The decrease in the weight of the input is thus minimized when no set shares more than one element with \(S\). By combining inequality (17.2) and (17.3), we obtain

\[\begin{multline} w(U \setminus S, \mathcal{S}') \le w(U, \mathcal{S}) - {}\\ \left( w_{|S|} + \sum_{f=2}^6 v_f m_f + m_{\ge 7} + \Delta w_{|S|} \left( \sum_{f=2}^6 (f - 1)m_f + 6 \cdot m_{\ge 7} \right) \right). \tag{17.4} \end{multline}\]

Inequalities (17.1) and (17.4) show that Rule 6 has a branching vector \((b_1, b_2)\) with

\[\begin{aligned} b_1 &= w_{|S|} + \sum_{f=2}^6 (\Delta v_f \cdot m_f) + \delta\\ b_2 &= w_{|S|} + \sum_{f=2}^6 v_f m_f + m_{\ge 7} + \Delta w_{|S|} \left( \sum_{f=2}^6 (f - 1)m_f + 6 \cdot m_{\ge 7} \right). \end{aligned}\]

Finally, observe that \(\sum_{f=2}^6 m_f + m_{\ge f} = |S|\). Thus, given a set \(S\) of a particular size, there are only a finite number of possible vectors \((b_1, b_2)\). Since \(\Delta w_{|S|} = 0\) for \(|S| \ge 7\), every branching vector for a set \(S\) with \(|S| \ge 8\) is dominated by a branching vector for a set \(S\) with \(|S| = 7\) in the sense that some branching vector for \(|S| = 7\) achieves a larger branching number than the chosen branching vector for \(|S| \ge 8\). Thus, to bound the branching number of Rule 6, we only need to consider sets of size \(2 \le |S| \le 7\) and consider all possible branching vectors \((b_1, b_2)\) obtained for each such choice of \(|S|\). In total, we obtain a finite (albeit large) number of branching vectors.

A randomized local search carried out by Fomin and Kratsch now produces the following weights as (nearly) optimal choices that minimize the branching number of Rule 6:

\[\begin{aligned} w_2 &= 0.3774 & v_2 &= 0.3994\\ w_3 &= 0.7549 & v_3 &= 0.7676\\ w_4 &= 0.9094 & v_4 &= 0.9299\\ w_5 &= 0.9764 & v_5 &= 0.9856 \end{aligned}\]

These weights result in the branching number \(1.24\) (determined by evaluating all branching vectors during the local search), which proves Theorem 17.5.