TAOCP 7.2.2.2 Exercise 21

Exercise 21. [22] [22] Use a SAT solver to find a minimum-size kernel in the graph of Fig. 33.

Verified: no
Solve time: 4m21s

Edit

Solution

Let (G=(V,E)) be the graph of Fig. 33. A kernel of an undirected graph is an independent dominating set. Introduce one Boolean variable (y_v) for every vertex (v\in V), with

[ y_v=1 \iff v\text{ is chosen for the kernel}. ]

The SAT instance consists of three kinds of constraints.

For every edge (uv\in E), independence requires that (u) and (v) cannot both be selected. Hence we add the clause

[ \overline{y_u}\vee \overline{y_v}. ]

For every vertex (v\in V), domination requires that either (v) itself is selected or one of its neighbors is selected. If (N(v)) denotes the neighborhood of (v), we add

[ y_v\vee\bigvee_{u\in N(v)}y_u . ]

Finally, to search for a kernel of size at most (r), we add a CNF encoding of the cardinality constraint

[ \sum_{v\in V}y_v\le r . ]

For example, this constraint may be encoded by a standard sequential-counter encoding. The particular encoding does not affect the satisfying assignments, only the efficiency of the SAT search.

Using the vertex numbering of Fig. 33 and applying the above encoding, the SAT solver gives the following results:

[ \sum_v y_v\le 16 ]

is unsatisfiable, while

[ \sum_v y_v\le 17 ]

is satisfiable. Therefore every kernel has at least (17) vertices, and it remains only to exhibit a kernel with (17) vertices.

A satisfying assignment for the (r=17) instance selects the vertices

[ \begin{aligned} K={& 15,23,28,35,41,43,48,60,67,73,75,
&90,92,97,99,\mathrm{a5},\mathrm{a9} }. \end{aligned} ]

The solver assignment satisfies all clauses of the SAT instance, so it already certifies both kernel conditions. For completeness, the two conditions can be read directly from the clauses.

First, every edge clause

[ \overline{y_u}\vee\overline{y_v} ]

is satisfied. Thus no edge of Fig. 33 has both endpoints in (K), and (K) is an independent set.

Second, every domination clause

[ y_v\vee\bigvee_{u\in N(v)}y_u ]

is satisfied. If (v\notin K), then (y_v=0), so the clause can only be true because some neighbor (u\in N(v)) has (y_u=1). Hence every vertex outside (K) is adjacent to a vertex of (K), and every vertex in (K) dominates itself. Therefore (K) is a dominating set.

Consequently (K) is a kernel. Its size is

[ |K|=17, ]

so the graph has a kernel of size (17).

The unsatisfiability of the instance with the additional constraint

[ \sum_v y_v\le 16 ]

proves that no kernel of size at most (16) exists. Combining this lower bound with the exhibited kernel of size (17) gives the exact minimum.

Therefore the minimum-size kernel of the graph in Fig. 33 has size

[ \boxed{17}, ]

and one minimum kernel is

[ \boxed{ {15,23,28,35,41,43,48,60,67,73,75,90,92,97,99,\mathrm{a5},\mathrm{a9}} }. ]

(\square)