is a hard problem. As a result, a small cycle cutset may be used instead of a minimal one.

Another alternative to reduce the running time of search is to place more burden on the inference part. In particular, inference can be relatively efficient even if the problem graph is not a forest but a graph of small induced width. This can be exploited by doing search on a set of variables that is not a cycle cutset but leaves the problem, once removed, to be have induced width bounded by some value . Such set of variables is called a -cutset