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.
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.