
| Instances           | Backbone robustness   |                 |         |         |
|---------------------|-----------------------|-----------------|---------|---------|
| 10th percentile     | Median                | 90th percentile |         |         |
| Preserve-backbone C | 0, C0                 | 8.5845          | 12.9700 | 20.6300 |
| Preserve-backbone C | 5, C0                 | 7.7374          | 12.0317 | 19.1700 |
| Preserve-backbone C | 10, C0                | 7.1977          | 11.0851 | 17.3500 |
| Preserve-backbone C | 20, C0                | 6.0690          | 9.3913  | 14.5351 |
| Preserve-backbone C | 40, C0                | 4.2622          | 6.4899  | 9.9900  |
| Preserve-backbone C | 80, C0                | 2.0745          | 2.8661  | 3.9851  |
| BMS                 | 1.0200                | 1.0600          | 1.1600  |         |

Table 4: The eect of Preserve-backbone on backbone robustness.

6.2 Interpolating Between an Instance and one of its BMSs Once BMS C0 has been established, we can also study the eects of interpolation between C and C0 by removing at random from C some of the clauses which do not appear in C0 This is equivalent to removing clauses at random such that the backbone is preserved.

Preserve-backbone C mr C0will denote C with mr clauses, which do not appear in the BMS C0 removed at random. The resulting instance will have the same backbone as C

$$m\,/n$$
Just as increasing m=n while controlling the backbone size causes backbone robustness

to increase, we have found that deleting clauses such that the backbone is unaected causes

backbone robustness (as measured above) to decrease, as one might expect.

BMSs of the threshold instances are so backbone-fragile that the removal of just one clause

from them is likely to reduce the backbone by half or more.

for local search increases because the backbone robustness decreases. It is conceivable,

near the threshold generally makes their cost for local search increase. If this were the

case, any increase in cost during interpolation towards BMS could merely be due to the

To control for this possibility we also removed clauses according to two other procedures.

We used 500 Random 3-SAT instances with n 100 and m=n :29. For each instance we found one BMS. We then used Preserve-backbone to interpolate with mr set at various values. Table shows the eect of increasing mr on backbone robustness. The Our hypothesis predicts that as this interpolation from C to C0 proceeds, the cost although it would be very surprising, that removing any clauses from random instances removal of clauses per se rather than the removal of clauses whilst preserving the backbone.

The procedure Random C mr removes mr clauses from C at random. The procedure Reduce-backbone C mr removes mr clauses such that each time clause is removed, the size of the backbone is reduced. The clause to be removed is chosen randomly from all such clauses. This procedure therefore uses the opposite removal criterion to Preservebackbone If the backbone becomes empty, no further clauses are removed.

Figure 12 shows the eect on per-instance cost of applying the three clause removal procedures to the same set of 500 Random 3-SAT threshold instances. Each plot is the median per-instance cost.

