2 -Way vs.d -Way Branching for CSP

Most CSP algorithms are based on refinements and extensions of backtracking, and employ one of two simple “branching schemes”: 2-way branching or

d

-way branching, for domain size

d

. The schemes are not equivalent, but little is known about their relative power. Here we compare them in terms of how efficiently they can refute an unsatisfiable instance with optimal branching choices, by studying two variants of the resolution proof system, denoted

C

 − 

RES

and

NG

 − 

RES

, which model the reasoning of CSP algorithms. The tree-like restrictions,

tree

 − 

C

 − 

RES

and

tree

 − 

NG

 − 

RES

, exactly capture the power of backtracking with 2-way branching and

d

-way branching, respectively. We give a family instances which require exponential sized search trees for backtracking with

d

-way branching, but have size

O

(

d

2

n

) search trees for backtracking with 2-way branching. We also give a natural branching strategy with which backtracking with 2-way branching finds refutations of these instances in time

O

(

d

2

n

2

). The unrestricted variants of

C

 − 

RES

and

NG

 − 

RES

can simulate the reasoning of algorithms which incorporate learning and

k

-consistency enforcement. We show exponential separations between

C

 − 

RES

and

NG

 − 

RES

, as well as between the tree-like and unrestricted versions of each system. All separations given are nearly optimal.