Chordal completion

Content sourced from Wikipedia, licensed under CC BY-SA 3.0.

Chordal completion of a graph G is a chordal graph on the same vertices that contains G. A minimal completion adds as few edges as possible while staying chordal; a minimum completion uses the smallest possible number of added edges. A completion that minimizes the largest clique size in the result helps define the treewidth of G.

Chordal completions are useful for characterizing several graph families:
- G is AT-free iff every minimal chordal completion of G is an interval graph.
- G is claw-free AT-free iff every minimal chordal completion is a proper interval graph.
- G is a cograph iff every minimal chordal completion is a trivially perfect graph.

Relationships to other graph measures:
- G has treewidth at most k iff there exists a chordal completion with maximum clique size at most k+1.
- G has pathwidth at most k iff there is a chordal completion that is an interval graph with clique size at most k+1.
- G has bandwidth at most k iff there is a chordal completion that is a proper interval graph with clique size at most k+1.
- G has tree-depth at most k iff there is a chordal completion that is a trivially perfect graph with clique size at most k.

Why this matters:
- In Gaussian elimination for sparse matrices, you want to minimize fill-in (new nonzero entries). The filled pattern corresponds to a chordal graph, and the minimum fill-in problem equals the minimum chordal completion problem.
- In phylogeny, a perfect evolutionary tree exists exactly when a coloring of an overlap graph allows a chordal completion that respects the colors.

Complexity and algorithms:
- The minimum chordal completion problem (minimum fill-in) is NP-hard. If you add k edges, you can always obtain a chordal completion with at most 8k^2 added edges in polynomial time.
- Computing treewidth, pathwidth, and related parameters is NP-hard and unlikely to be approximable within a constant factor, though logarithmic approximations exist.
- There are exponential-time exact algorithms, for example roughly O(1.9601^n) for an n-vertex graph.
- For planar graphs, you can get a chordal completion with at most O(n log n) edges.

Note:
- The term “triangulations” is sometimes used for chordal completions, but that word can also mean something else in graph theory.

This overview shows how chordal completions connect graph structure, algorithms, and real-world applications.