Cutset Conditioning Algorithm

Computes an optimal Cutset for a CSP and an existing Cutset $V_{0}$.

Pseudocode

Running Time

The algorithm is exponential only in the number of nodes in $V_{0}$ not in $V$.

However finding optimal cutsets is NP-hard. There exist approximations which can be solved easier.