On finding minimal wcutset
Bozhena Bidyuk, Rina Dechter
Abstract:
The complexity of a reasoning task over a graphical model is tied to the induced width of the underlying graph. It is wellknown 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 cyclecutset, the rest of the network is singlyconnected and therefore can be solved by linear propagation algorithms. A wcutset is a generalization of a cyclecutset defined as a subset of nodes such that the subgraph with cutset nodes removed has inducedwidth of w or less. In this paper we address the problem of finding a minimal wcutset in a graph. We relate the problem to that of finding the minimal wcutset of a treedecomposition. The latter can be mapped to the wellknown set multicover problem. This relationship yields a proof of NPcompleteness on one hand and a greedy algorithm for finding a wcutset of a tree decomposition on the other. Empirical evaluation of the algorithms is presented.
Keywords: null
Pages: 4350
PS Link:
PDF Link: /papers/04/p43bidyuk.pdf
BibTex:
@INPROCEEDINGS{Bidyuk04,
AUTHOR = "Bozhena Bidyuk
and Rina Dechter",
TITLE = "On finding minimal wcutset",
BOOKTITLE = "Proceedings of the Twentieth Conference Annual Conference on Uncertainty in Artificial Intelligence (UAI04)",
PUBLISHER = "AUAI Press",
ADDRESS = "Arlington, Virginia",
YEAR = "2004",
PAGES = "4350"
}

