On finding minimal w-cutset
This work addresses a computational bottleneck in graphical model inference for AI and reasoning systems, but it is incremental as it builds on known w-cutset concepts.
The paper tackles the problem of finding a minimal w-cutset in a graph to reduce the complexity of reasoning tasks in graphical models, relating it to the set multi-cover problem to prove NP-completeness and proposing a greedy algorithm with empirical evaluation.
The complexity of a reasoning task over a graphical model is tied to the induced width of the underlying graph. It is well-known that the conditioning (assigning values) on a subset of variables yields a subproblem of the reduced complexity where instantiated variables are removed. If the assigned variables constitute a cycle-cutset, the rest of the network is singly-connected and therefore can be solved by linear propagation algorithms. A w-cutset is a generalization of a cycle-cutset defined as a subset of nodes such that the subgraph with cutset nodes removed has induced-width of w or less. In this paper we address the problem of finding a minimal w-cutset in a graph. We relate the problem to that of finding the minimal w-cutset of a treedecomposition. The latter can be mapped to the well-known set multi-cover problem. This relationship yields a proof of NP-completeness on one hand and a greedy algorithm for finding a w-cutset of a tree decomposition on the other. Empirical evaluation of the algorithms is presented.