Chordal completion

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.^[4] 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 n vertices has a chordal completion with at most O(n log n) edges.^[5]

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 Buneman (1974) describes, the existence of a perfect phylogeny can be modeled as a chordal completion problem. One draws an "overlap graph" G 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 G has a chordal completion that respects the coloring.^[6]

Although listed as an open problem in the 1979 book Computers and Intractability,^[7] the computational complexity of the minimum chordal completion problem (also called the minimum fill-in problem) was quickly resolved: Yannakakis (1981) showed it to be NP-complete.^[8] If the minimum chordal completion adds k edges to a graph G, then it is possible to find a chordal completion using at most 8k² added edges, in polynomial time.^[9] The problem of finding the optimal set of k edges to add can also be solved by a fixed-parameter tractable algorithm, in time polynomial in the graph size and subexponential in k.^[10]

The treewidth (minimum clique size of a chordal completion) and related parameters including pathwidth and tree-depth are also NP-complete to compute, and (unless P=NP) cannot be approximated in polynomial time to within a constant factor of their optimum values; however, approximation algorithms with logarithmic approximation ratios are known for them.^[11]

Both the minimum fill-in and treewidth problems can be solved in exponential time. More precisely, for an n-vertex graph, the time is O(1.9601ⁿ).^[12]