Computing the Minimum Fill-In is NP-Complete
- 1 March 1981
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Algebraic Discrete Methods
- Vol. 2 (1) , 77-79
- https://doi.org/10.1137/0602010
Abstract
Summary:In probability theory, Bayesian statistics, artificial intelligence and database theory the minimum cross-entropy principle is often used to estimate a distribution with a given set $P$ of marginal distributions under the proportionality assumption with respect to a given ``prior'' distribution $q$. Such an estimation problem admits a solution if and only if there exists an extension of $P$ that is dominated by $q$. In this paper we consider the case that $q$ is not given explicitly, but is specified as the maximum-entropy extension of an auxiliary set $Q$ of distributions. There are three problems that naturally arise: (1) the existence of an extension of a distribution set (such as $P$ and $Q$), (2) the existence of an extension of $P$ that is dominated by the maximum entropy extension of $Q$, (3) the numeric computation of the minimum cross-entropy extension of $P$ with respect to the maximum entropy extension of $Q$. In the spirit of a divide-and-conquer approach, we prove that, for each of the three above-mentioned problems, the global solution can be easily obtained by combining the solutions to subproblems defined at node level of a suitable tree
This publication has 5 references indexed in Scilit:
- Some simplified NP-complete graph problemsPublished by Elsevier ,2002
- Node-Deletion Problems on Bipartite GraphsSIAM Journal on Computing, 1981
- Algorithmic Aspects of Vertex Elimination on Directed GraphsSIAM Journal on Applied Mathematics, 1978
- Algorithmic Aspects of Vertex Elimination on GraphsSIAM Journal on Computing, 1976
- A GRAPH-THEORETIC STUDY OF THE NUMERICAL SOLUTION OF SPARSE POSITIVE DEFINITE SYSTEMS OF LINEAR EQUATIONSPublished by Elsevier ,1972