Computing the Minimum Fill-In is NP-Complete
Mihalis Yannakakis · SIAM Journal on Algebraic and Discrete Methods · 1981
We show that the following problem is NP-complete. Given a graph, find the minimum number of edges (fill-in) whose addition makes the graph chordal. This problem arises in the solution of sparse symmetric positive definite systems of linear equations by Gaussian elimination.