Next: MINIMUM COLOR SUM Up: Subgraphs and Supergraphs Previous: MINIMUM INTERVAL GRAPH COMPLETION Index

### MINIMUM CHORDAL GRAPH COMPLETION

- 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., |E' - E|.

- Good News: Approximable within O(|V|) [363].

- Comment: Also known as Minimum Fill-in. Approximable within [363], where denotes the minimum number of fill edges needed. Approximable within for graphs with bounded degree [305], and within [363].

  See results on related problems under MINIMUM TREE WIDTH.

- Garey and Johnson: OPEN4