Minimal obstructions for partial representations of interval graphs (Q668026)

Summary: \textit{Interval graphs} are intersection graphs of closed intervals. A generalization of recognition called \textit{partial representation extension} was introduced recently. The input gives an interval graph with a \textit{partial representation} specifying some pre-drawn intervals. We ask whether the remaining intervals can be added to create an \textit{extending representation}. Two linear-time algorithms are known for solving this problem. In this paper, we characterize the \textit{minimal obstructions} which make partial representations non-extendible. This generalizes Lekkerkerker and Boland's characterization of the minimal forbidden induced subgraphs of interval graphs. Each minimal obstruction consists of a forbidden induced subgraph together with at most four pre-drawn intervals. A Helly-type result follows: A partial representation is extendible if and only if every quadruple of pre-drawn intervals is extendible by itself. Our characterization leads to a linear-time certifying algorithm for partial representation extension.