Phase Transitions of Dominating Clique Problem and Their Implications to Heuristics in Satisfiability Search

1 Introduction

In this paper, we study the phase transition behavior of the dominating clique problem (DOMC), an NP-complete decision problem which for a given graph, asks if there is a subset of vertices that induces a clique and is a dominating set. Our interest in DOMC stems from an initial observation that its phase transition should occur when the random graph has a constant edge probability (i.e., has on average ✂ ✄ ✆ ✞ ✠ edges). This distinguishes DOMC from many other NP-complete problems previously studied from a phase transition perspective; Well-studied problems such as random SAT, random graph coloring, and Hamiltonian Cycle all have a phase transition when the underlying random graphs are sparse. For random SAT and graph coloring, it is known that randomly-generated instances become typically easy when the density parameter increases as a certain function of the problem size [Franco and Gelder, 2003; Krivelevich, 2002]. For Hamiltonian Cycle, whose edgesvertices ratio threshold is ✂ ✄ ☛ ✌ ✎ ✄ ✆ ✠ ✠ , instances randomlygenerated at the phase transition are already typically easy [Vandegriend and Culberson, 1998].

Another unique feature is that DOMC is a monotone decision problem without any extra parameter other than the problem size and edge density. This is in contrast to other similar partitioning and covering problems studied in the phase transition literature, such as the vertex cover [Hartmann and Weigt, 2003], in which an additional size parameter has to be used as an input.

There has also been recent interest in the study of the typical-case behavior of random problems with some deterministic structures, hoping that these problems might be able to capture more characteristics in real-world applications. Among others, the Quasigroup completion problem [Gomes and Shmoys, 2002], problems defined on the small-world graphs [Walsh, 1999], and problems obtained by "morphing" different problems [Gent et al., 1999] have been proposed as alternatives to random problems with a uniform distribution. The dominating clique problem on random graphs and its CNF-encoding provide another type of distribution with (in some sense) extreme characteristics.

In Section 2, we establish the exact threshold of the phase transition of the dominating clique problem in random graphs. In Section 3, we present a backtracking algorithm for DOMC which will be used in our empirical investigation. In Section 4, we report two sets of interesting observations from our empirical investigation. We conclude in Section 5.

2 Dominating Clique Problem and its Phase Transitions

Consider a graph ✔ ✄ ✖ ✘ ✚ ✠ . A subset of vertices ✖ ✢ ✤ ✖ is called a dominating clique of ✔ ✄ ✖ ✘ ✚ ✠ if ✖ ✢ induces a clique and for any ✫ ✬ ✖ ✯ ✖ ✢ , there is a vertex ✲ ✬ ✖ ✢ such that ✄ ✲ ✘ ✫ ✠ ✬ ✚ . The dominating clique problem is the one that asks the question whether a given graph has a dominating clique.

The property of having a dominating clique is monotone and has a phase transition when the random graph is at the dense stage of the graph evolution process. The following theorem shows the phase transition has an exact threshold ✷ ✸ ✹ ✻ ✽ ✿ ❀ ✞ for a random graph ✔ ✄ ✆ ✘ ✷ ✠ where each of the ✆ ✄ ✆ ❂ ❃ ✠ ❄ ❅ potential edges appears in the graph with probability ✷ .

Theorem 2.1.

To simplify the notations, we will write a0 ✹ ✁ ✂ . Let ✄ ☎ ✄ ✆ ✘ ✝ ✠ be the number of dominating cliques of size ✝ . The expectation of ✄ ☎ ✄ ✆ ✘ ✝ ✠ is

By Stirling's formula, we have

Lemma 2.1. If the edge probability ✷ is such that ☛ ✌ ✎ ★ ✄ a0 ❂ ❃ ✠ ❘ ✁ ✞ , then

Proof. Let

and

Based on the bound ✹ ❊ ✔ ✺ ✼ ✄ ✽ ❊ ✔ ✠ ✔ , ✵ ✄ ✆ ✠ can be estimated as follows:

Since ✿ ★ ✽ ✔ ▼ ❃ if ✆ is sufficiently large, we have ☛ ❇ ❉ ❊ ✵ ✄ ✆ ✠ ✹ ❑ .

For ✭ ✄ ✆ ✠ , we have

Solving the inequality about a0 , we get a0 ❘ ✻ ▼ ✿ ❀ ✞ , that is, ✷ ▼ ✻ ✽ ✿ ❀ ✞ ✹ ❑ ❙ ◆ ❖ ❃ a80 ◗ ◗ ❙ ❙ ❙ . To prove the case of ✷ ❘ ✻ ✽ ✿ ❀ ✞ , i.e., ☛ ✌ ✎ ★ ✄ a0 ❂ ❃ ✠ ▼ ✁ ✞ , we have to consider the variance of the number of dominating cliques in ✔ ✄ ✆ ✘ ✷ ✠ . Details will be given in the Appendix. Here, we only mention that the first crucial observation is that in this case, we have (A) ✁ ✁ ✽ ✮ ✰ ✱ ✳ ✥ ★ ✽ ✁ ✦ ▼ ❅ and (B) the expected number of dominating cliques of size ❯ ☛ ✌ ✎ ★ ✆ tends to infinity for any constant ❯ such that ✁ ✁ ✽ ✮ ✰ ✱ ✳ ✥ ★ ✽ ✁ ✦ ▼ ❯ ▼ ❅ .

Lemma 2.2. Let ❯ be a constant such that ✁ ✁ ✽ ✮ ✰ ✱ ✳ ✥ ★ ✽ ✁ ✦ ▼ ❯ ▼ ❅ and let ✝ ✹ ❯ ☛ ✌ ✎ ★ ✆ . Then,

Proof. By (2.3), we have

The lemma follows since by assumption we have ❯ ✄ ☛ ✌ ✎ ★ ✄ a0 ❂ ❃ ✠ ❂ ❃ ✠ ❱ ❃ ▼ ❑ and ❃ ❂ ❫ ✞ ❘ ❑ .

3 An Algorithm for the Dominating Clique Problem

We present a brief over view of the elementary algorithm we developed for this problem.

We assume we are given a simple undirected graph ✔ ✹ ✄ ✖ ✘ ✚ ✠ . The algorithm is a basic depth first backtrack algorithm that recursively constructs a potential dominating clique ✄ . We call the set of vertices not adjacent to any vertex in ✄ the uncovered set ❜ . For a vertex to be a candidate for addition to ✄ it must be adjacent to all vertices in ✄ . We call this the selection set ❝ ✹ ❋ ❞ ❡ ❣ ❤ ✬ ✄ ✘ ❋ ❞ ✘ ❤ ❍ ✬ ✚ ❍ .

At each node in the backtrack tree, we select a pivot set ❥ ❦ ❝ such that if the current ✄ can be extended to cover the graph at least one of the vertices must be in ❥ . To this end, we first find a vertex ❤ ✬ ❜ which has a minimum number of neighbors in ❝ . Clearly either ❤ or one of its neighbors in the current ❝ must be in the final ✄ . The effect of this is to greatly reduce the branching factor and the amount of redundant search.

For ✭ ❦ ✖ ✘ ❤ ✬ ✖ we define the closed neighborhood of a vertex ❤ in a subset ✭ as ♠ ♥ ✄ ✭ ✘ ❤ ✠ ✹ ❋ ❞ ✬ ✭ ❡ ❞ ✹ ❤ or ❋ ❞ ✘ ❤ ❍ ✬ ✚ ❍ , and the open neighborhood ♥ ✄ ✭ ✘ ❤ ✠ ✹ ♠ ♥ ✄ ✭ ✘ ❤ ✠ ✯ ❋ ❤ ❍ . Initially, ❜ ✹ ❝ ✹ ✖ and ✄ ✹ ♣ .

At first glance it appears we have eliminated the vertex of minimum degree, ❤ , as a possible member of ✄ . Suppose ❤ is the only vertex in ✄ , then since ❤ is of minimum degree ✔ is a clique and any vertex will do. Otherwise, on the initial step ❤ will be in ❝ ✢ and so is available for inclusion later in the recursion. Correctness then follows by induction on the

DomClq( ✔ ✘ ❝ ✘ ✄ ✘ ❜ ) :: BOOLEAN If ❜ ✹ ♣ then ✄ ✁ ✂ ☎ ☎ ✝ ✹ ✄ . return yes. endif Find ❤ ✬ ❜ such that ✟ ♥ ✄ ❝ ✘ ❤ ✠ ✟ ✹ ❉ ❇ ✡ ☞ ✍ ✏ ✟ ♥ ✄ ❝ ✘ ✓ ✠ ✟ . ❥ ✹ ♥ ✄ ❝ ✘ ❤ ✠ . if ❥ ✹ ♣ return no. ❝ ✢ ✢ ✹ ❝ . while ❥ ✕ ✹ ♣ Select ✫ ✬ ❥ . ✄ ✹ ✄ ✗ ❋ ✫ ❍ . ❝ ✢ ✹ ♥ ✄ ❝ ✢ ✢ ✘ ✫ ✠ . ❜ ✢ ✹ ❜ ✯ ♠ ♥ ✄ ❜ ✘ ✫ ✠ . If DomClq(✔ ✘ ❝ ✢ ✘ ✄ ✘ ❜ ✢ ) return yes. ✄ ✹ ✄ ✯ ❋ ✫ ❍ . ❝ ✢ ✢ ✹ ❝ ✢ ✢ ✯ ❋ ✫ ❍ . ❥ ✹ ❥ ✯ ❋ ✫ ❍ . endwhile return no; end DomClq.

observations given above. Our assumption is that usually the vertex of minimum degree is not in ✄ and so we may reduce the search cost by leaving it out of the initial ❥ . Note that after the initial step ❝ and ❜ are disjoint.

In our program we made no effort to reorder the vertices of ❥ for selection (first statement in the while loop). One obvious candidate is to select ✫ ✬ ❥ to maximize ♥ ✄ ❜ ✘ ✫ ✠ . We would guess that in positive instances this would tend to find solutions quicker. However, the results for the negative instances in table 2 indicate this is unlikely to help in those cases, these are the most expensive and there would be a fair bit of overhead cost to this heuristic. We leave further investigation of selection heuristics as future work.

4 Empirical Studies

In this section, we discuss our empirical investigation on the dominating clique problem at phase transitions. In the first set of experiments, we study the threshold behavior and typicalcase hardness of the dominating clique problem itself. In the second set of experiments, we compare the performance of our algorithm and some state-of-the-art SAT solvers.

4.1 Threshold and Uniformity of Hardness at Phase Transitions

Table 1 shows the preliminary result on empirical value of the threshold. Table 2 summarizes the typical case hardness at ✷ ✹ ❑ ❙ ◆ ✙ ❃ for ✆ ✹ ❅ ✚ ❑ ❙ ❙ ❙ ❃ ❑ ❑ ❑ . The data indicate that the typical-case hardness at phase transitions increases at a superpolynomial rate. More interesting is the fact that for negative instances the variance in the number of the backtracks is tiny as compared to the total number. In other words, randomlygenerated dominating clique instances just beyond the phase transition seem to be "uniformly" hard. This suggests that randomizing the selection within the pivot set ❥ is unlikely to produce the heavy-tailed running time behavior frequently observed in many other problems [Gomes et al., 2000].

4.2 Significance of Using the Right Heuristics: How SAT solvers fail?

The dominating clique problem has a very natural and simple CNF encoding. To make the presentation easier, we adopt the convention that a clause can be viewed as a set of literals. Given a graph ✔ ✹ ✔ ✄ ✖ ✘ ✚ ✠ with ✖ ✹ ❋ ✫ ✁ ✘ ❙ ❙ ❙ ✘ ✫ ❊ ❍ , the dominating clique problem can be encoded as follows.

1. There are ✆ boolean variables ❋ ❞ ✜ ✘ ❃ ✼ ✢ ✼ ✆ ❍ where ❞ ✜ ✹ ❃ signifies that the corresponding vertex ✫ ✜ is in the dominating clique.
2. For each variable ❞ ✜ , there is a clause ☎ ✜ ✹ ❋ ❞ ✜ ❍ ✗ ♥ ✄ ❞ ✜ ✠ , where ♥ ✄ ❞ ✜ ✠ means the variables representing the vertices adjacent to ✫ ✜ . This indicates that each vertex has to be in the dominating clique or have a neighbor in a dominating clique. These clauses will be called the long-positive clauses.
3. For each pair of variables ✄ ❞ ✜ ✘ ❞ ✦ ✠ not in ✚ , there is a clause ✄ ✜ ★ ✦ ✹ ❋ ❞ ✜ ✘ ❞ ✦ ❍ , indicating that at most one of the two non-adjacent vertices can be in a dominating clique. We will call these clauses the short-negative clauses.

Other encodings are also possible such as the support encoding [Gent, 2002] that maps maintaining arc-consistency of CSP algorithms to unit-propagation in SAT algorithms. But similar CNF encoding of the CSP representation for the dominating clique problem at the phase transitions will result in ✂ ✄ ✆ ✻ ✠ clauses of length ✂ ✄ ✆ ✠ .

A SAT algorithm for the CNF-encoding of DOMC

We noticed that SATZ and ZChaff cannot solve any of the DOMC instances of size more than 600 in reasonable time. Therefore we translated our dominating clique algorithm to a SAT solver, called DCS, that solves the CNF-encoding of the dominating clique problem almost as efficiently as the orginal algorithm.

The solver does not use any of the current efficient data structures such as the technique of watched literals, nor does it use any advanced learning mechanism and heuristics, other than those directly translated from our dominating clique search algorithm. In the context of CNF formulas our algorithm reads as follows: (1) always pick an unassigned variable in the shortest remaining long-positive clause; (2) conduct a one-step unit propagation based on the information in short-negative clauses; and (3) stop as soon as all the long positive clauses are satisfied, or backtrack if a long-positive clause becomes empty. As has been discussed at the end of Section 3, our solver's performance may be further improved on satisfiable instances if we add the heuristic to select an unassigned variable that satisfies a maximum number of longpositive clauses.

Results on the CNF encodings of DOMC and Subgraph Isomorphism

We have performed a series of experiments comparing the performance of our solver DCS and some state-of-the-art SAT solvers, including BerkMin(BM) 1 , MarchEq(MQ) 2 and Satz(SZ).

First, we compared the performance of our solver DCS and other solvers on the CNF encoding of DOMC at phase transitions. We generated 100 random instances of the dominating clique problem at the edge probability ✷ ✹ ❑ ❙ ◆ ◗ ❖ for ✆ ✹ ❃ ✚ ❑ and ◆ ❑ ❑ . According to our experiment on the threshold, ✷ ✹ ❑ ❙ ◆ ◗ ❖ is roughly the edge probability where ✚ ❑ percent of the instances are satisfiable. The median running time (in seconds) of these solvers is summarized in Table 3.

Inspired by the efficiency of DCS on DOMC we investigated its performance on Subgraph Isomorphism (SGI) instances. Given two graphs ✔ ✄ ✖ ✁ ✘ ✚ ✁ ✠ and ☎ ✄ ✖ ✆ ✘ ✚ ✆ ✠ , the subgraph isomorphism problem asks if there exists a subgraph ☎ ✁ of ☎ such that ✔ is isomorphic to ☎ ✁ . A SGI instance can be naturally converted to SAT using an encoding similar to the one used for DOMC (direct encoding); the resulting SAT instance has ✟ ✖ ✁ ✟ ✟ ✟ ✖ ✆ ✟ variables, ✟ ✖ ✁ ✟ long positive clauses and ✁ ✄ ✟ ✖ ✁ ✟ ✞ ✟ ✟ ✖ ✆ ✟ ✞ ✠ short-negative clauses. SAT encodings of random SGI (SERSGI) are difficult for (deterministic) SAT solvers. 3

We generated 5 sets of SERSGI instances with 528 variables. Each set consisted of 50 instances generated around the cross over point of SGI. DCS consistently outperformed all the other solvers on each set (Table 4). DCS is one or two orders of magnitude faster than MarchEq and Satz. This is remarkable especially considering the simplicity of DCS. To further investigate the speed up factor we compared the performances of DCS and BerkMin on the SERSGI instances used in the 2004 SAT competition (Table 5). With a single exception, DCS performance was comparable or better than that of BerkMin. Thus we conclude that DCS outperforms state of the art solvers on SERSGI instances.

It may be possible to extend this conclusion to other classes of SAT instances which have only long-positive and short negative clauses, but more work needs to be done to see what are the structural properties that DCS can exploit. However, we do not expect that DCS will work efficiently on any type of CNF formulas with a long-short clause structure. We noticed that on random k-SAT instances, it is at least one order of magnitude slower than Satz. We consider this behavior an evidence against the idea of an efficient universal sat solver that does not consider any problem structure.

5 Conclusions

Most of the well-investigated NP-complete problems in the literature have a phase transition when the underlying graph is very sparse. There is also evidence that randomly-generated instances at the phase transition are typically not hard if the threshold can be accurately established such as the Hamiltonian Cycle problem. DOMC studied in this paper is distinguished from a phase transition and typical-case complexity perspective. On the one hand, it has an exact threshold at a very dense stage of the random graph evolution process. Our empirical results, on the other hand, indicate that randomly-generated instances are still typically (and uniformly for negative instances) hard. As has been demonstrated by our SAT solver's outstanding performance advantage on the CNF-encoding of DOMC and other problems with similar structures, DOMC might serve as a prototypical problem to further investigate the relationship among the problem structure, the encoding efficiency, and the use of relevant heuristics in satisfiability search.

1 BerkMin is the predecessor of Forklift the winner of the Industrial Category at the 2003 SAT competition. Our experience indicates that Zchaff (winner of 2004) is not efficient for this type of instances

2 Winner of the Hand Crafted Category at the 2004 SAT competition

3 At the 2004 SAT competition[LeBerre and Simon, 2004], no deterministic solver could solve any SERSGI instance.

Appendix: proof of Theorem 2.1

To estimate the second moment of the number of dominating cliques of size ✝ , we need the following lemma on the probability that two vertex subsets both dominate the rest of the vertices in a random graph.

Lemma 5.1. Let ❜ and a0 be two vertex subsets of size ✝ such that ✟ ❜ ✁ a0 ✟ ✹ ☎ and let ❥ ✄ ☎ ✠ be the probability that ❜ and a0 both dominate all the vertices outside of ❜ ✗ a0 . Then,

1.

Proof. (1). Let ✫ be a vertex outside of ❜ ✗ a0 . The probability that ✫ is not connected to any vertices in ❜ ✁ a0 is ✄ ❃ ❂ ✷ ✠ ✟ . The probability that ✫ is dominated by both ❜ ✯ a0 and a0 ✯ ❜ is

Thus, ❥ ✄ ☎ ✠ is

(2). Since ☎ ✕ ✗ ★ ✄ a0 ❂ ❃ ✠ ❂ ❃ ▼ ❑ , we have

For ❃ ✼ ☎ ✼ ✝ , we have

Since

and ❯ ✄ ☎ ✕ ✗ ★ ✄ a0 ❂ ❃ ✠ ❂ ❃ ✠ ❱ ❃ ▼ ❑ , conclusion 2(a) follows.

Proof of Theorem 2.1. The fact that

for ✷ ▼ ✻ ✽ ✿ ❀ ✞ follows from Lemma 2.1 and Markov's inequality.

To prove that ☛ ❇ ❉ ❊ ❥ ✝ ❋ ✔ ✄ ✆ ✘ ✷ ✠ has a dominating clique ❍ ✹ ❃ for ✷ ❘ ✻ ✽ ✿ ❀ ✞ , we will show that

where ✝ ✹ ❯ ☛ ✌ ✎ ★ ✆ and ✁ ✁ ✽ ✮ ✰ ✱ ✳ ✥ ★ ✽ ✁ ✦ ▼ ❯ ▼ ❅ . From Lemma 2.2, we have

By Chebyshev's inequality, we have

The expectation of ✄ ☎ ✞ ✄ ✆ ✘ ✝ ✠ is

where ✹ ❊ ✔ ✺ ✹ ✔ ✟ ✺ ✹ ❊ ✽ ✔ ✔ ✽ ✟ ✺ is the total number of pairs of vertex subsets of size ✝ that have ☎ vertices in common, and ✷ ✞ ✄ ✑ ✓ ✠ ✽ ✄ ✙ ✓ ✠ ❥ ✄ ☎ ✠ is the probability that such a pair of vertex subsets are both dominating cliques. Recall that

We write a0 ✁ ✂ ✄ ✓ ✥ ❊ ★ ✔ ✦ ✆ a0 ✓ ✁ ✂ ✄ ✥ ❊ ★ ✔ ✦ ✆ as

where

and

We will prove that ☛ ❇ ❉ ❊ ✠ ❊ ✹ ❃ and ☛ ❇ ❉ ❊ a0 ❊ ✹ ❑ . Since ✄ ❋ ❅ ✑ ✑ ✠ ✄ ❋ ✑ ✠ ✍ ❃ and ✔ ✄ ❋ ❅ ✑ ✑ ❅ ❆ ✠ ✄ ❋ ✑ ✠ ✍ ❑ , by Lemma 5.1(2.a and 2.b) we have

FromLemma 5.1 (2.b), we have for ✆ ❘ ♥ ✸

Since ✝ ✹ ❯ ☛ ✌ ✎ ★ ✆ with ❯ ▼ ❅ , we have

a0 ❊ ✼ ✁ ✄ ❃ ✠ ✝ ✌ ✝ ✞ ✆ ✁ ✽ ❫ ✧ ✞ ✚ a0 ✎ ✔ ✍ ❑ ❙ This completes the proof.