An O(n2)-time algorithm for the minimal interval completion problem

An interval completion of an arbitrary graph G is an interval graph H, on the same vertex set, obtained from G by adding new edges. If the set of newly added edges is inclusion-minimal among all possibilities, we say that H is a minimal interval completion of G. We give an O(n2)-time algorithm to obtain a minimal interval completion of an arbitrary graph. This improves the previous O(nm) time bound for the problem and lowers this bound for the first time below the best known bound for minimal chordal completion.