MINIMUM INTERVAL GRAPH COMPLETION

• INSTANCE: Graph $G=\left(V,E\right)$.
• SOLUTION: An interval graph $G'=\left(V,E'\right)$ that contains G as a subgraph, i.e., $E\subseteq E'$. An interval graph is a graph whose vertices can be mapped to distinct intervals in the real line such that two vertices in the graph have an edge between them if and only if their corresponding intervals overlap.
• MEASURE: The cardinality of the interval graph, i.e., $\vert E'\vert$.

  
  

• Good News: Approximable within $O(\log\vert T\vert)$ [416].
• Garey and Johnson: GT35