Although listed as an open problem in the 1979 book Computers and Intractability, the computational complexity of the minimum chordal completion problem (also called the minimum fill-in problem) was quickly resolved: Yannakakis (1981) showed it to be NP-complete.
Bár az 1979-es Computers and Intractability megoldatlanként kezeli, a minimális élszámú merev körű kiegészítés problémája (avagy a minimális feltöltődés (minimum fill-in) probléma) bonyolultsága gyorsan eldőlt: (Yannakakis 1981) igazolta, hogy NP-teljes.