Structural conditions for cycle completable graphs (Q1126192)

Cycle completable graphs appear in the characterization of partial real symmetric matrices for which there is a choice of the unspecified entries so as to make the given matrix positive definite. The authors characterize cycle completable graphs \(G\) by two equivalent conditions: (1) \(G\) has a cutclique decomposition into chordal and series-parallel pieces, and (2) \(G\) has a mixed elimination ordering (which is a generalization of the well-known perfect elimination ordering). From this result it is derived that cycle completable graphs can be recognized in \(O(nm)\) time.