On the interval completion of chordal graphs ?
For a given graph G=(V,E) G = ( V , E ) , the interval completion problem of G is to find an edge set F  such that the supergraph H=(V,E?F) H = ( V , E ? F ) of G  is an interval graph and |F| | F | is minimum. It has been shown that it is equivalent to the minimum sum cut problem, the profile minimization problem and a kind of graph searching problems. Furthermore, it has applications in computational biology, archaeology, and clone fingerprinting. In this paper, we show that it is NP-complete on split graphs and propose an efficient algorithm on primitive starlike graphs.
interval completion chordal graphs split graphs starlike graphs threshold completion pathwidth graph algorithms