The original application of chordal completion described in
Computers and Intractability involves
Gaussian elimination for
sparse matrices. During the process of Gaussian elimination, one wishes to minimize fill-in, coefficients of the matrix that were initially zero but later become nonzero, because the need to calculate the values of these coefficients slows down the algorithm. The pattern of nonzeros in a sparse
symmetric matrix can be described by an undirected graph (having the matrix as its
adjacency matrix); the pattern of nonzeros in the filled-in matrix is always a chordal graph, any minimal chordal completion corresponds to a fill-in pattern in this way. If a chordal completion of a graph is given, a sequence of steps in which to perform Gaussian elimination to achieve this fill-in pattern can be found by computing an elimination ordering of the resulting chordal graph. In this way, the minimum fill-in problem can be seen as equivalent to the minimum chordal completion problem. In this application,
planar graphs may arise in the solution of two-dimensional finite element systems; it follows from the
planar separator theorem that every planar graph with vertices has a chordal completion with at most edges. Another application comes from
phylogeny, the problem of reconstructing evolutionary trees, for instance trees of organisms subject to genetic mutations or trees of sets of ancient manuscripts copied one from another subject to scribal errors. If one assumes that each genetic mutation or scribal error happens only once, one obtains a
perfect phylogeny, a tree in which the species or manuscripts having any particular characteristic always form a connected subtree. As describes, the existence of a perfect phylogeny can be modeled as a chordal completion problem. One draws an "overlap graph" in which the vertices are attribute values (specific choices for some characteristic of a species or manuscript) and the edges represent pairs of attribute values that are shared by at least one species. The vertices of the graph can be
colored by the identities of the characteristics that each attribute value comes from, so that the total number of colors equals the number of characteristics used to derive the phylogeny. Then a perfect phylogeny exists if and only if has a chordal completion that respects the coloring. ==Computational complexity==