Chordal completion

Applications of chordal completion include modeling the problem of minimizing fill-in when performing Gaussian elimination on sparse symmetric matrices, and reconstructing phylogenetic trees.

It has bandwidth at most k if and only if G has at least one chordal completion that is a proper interval graph with maximum clique size at most k + 1.

[2] And it has tree-depth k if and only if it has at least one chordal completion that is a trivially perfect graph with maximum clique size at most k.[3] The original application of chordal completion described in Computers and Intractability involves Gaussian elimination for sparse matrices.

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.

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

The graph G (excluding red edges) is a subgraph of the chordal graph H (including red edges) which shares the same vertex set, making H a chordal completion of G . Removing any of the newly added red edges causes the graph to no longer be chordal, making it a minimal chordal completion. There were 9 edges added to G to make H , the lowest amount possible for G to become a chordal graph, making it a minimum chordal completion.