An integer programming model for the Minimum Interval Graph Completion Problem

The minimum interval graph completion problem consists of, given a graph G = ( V , E ) , finding a supergraph H = ( V , E ∪ F ) that is an interval graph, while adding the least number of edges | F | . We present an integer programming formulation for solving the minimum interval graph completion problem recurring to a characterization of interval graphs that produces a linear ordering of the maximal cliques of the solution graph.