- INSTANCE: Graph .
- SOLUTION:
A chordal graph completion, i.e., a superset
*E'*containing*E*such that is chordal, that is, for every simple cycle of more than 3 vertices in*G'*, there is some edge in*E'*that is not involved in the cycle but that joins two vertices in the cycle. - MEASURE:
The size of the completion, i.e., .

*Good News:*Approximable within [384].*Comment:*Also known as*Minimum Fill-in*. Approximable within [384], where denotes the minimum number of fill edges needed. Approximable within for graphs with bounded degree [322], and within [384]. See results on related problems under MINIMUM TREE WIDTH.*Garey and Johnson:*OPEN4