Given a set system (also well-known as a hypergraph) H = {U, X }, where U is a set of elements
and X is a set of subsets of U , an exact hitting set S is a subset of U such that each subset in X
contains exactly one element in S. We refer to a set system as exactly hittable if it has an exact
hitting set. In this work, we consider a special graph class namely the interval graphs. A given set of
intervals defines a unique interval graph, but an interval graph can have many interval representations.
We say that an interval graph is an exactly hittable interval graph if and only if it has at least one exactly
hittable interval representation. We ask the following question - if there is an exactly hittable
intersection model for every interval graph, where the intersection model consists of subpaths on a path.
Interestingly, the answer is no. We refer to the class of interval graphs that are the intersection graphs
of a set of intervals that have an exact hitting set, as the class of Exactly Hittable Interval Graphs (
EHIG). We present a forbidden structure characterization for EHIG, by defining a family F of simple
graphs as follows:
• For each k ≥ 1, F k denotes the set of connected interval graphs whose vertex set can be
partitioned into an induced path P consisting of k vertices and the open neighbourhood of P
(consisting of only those vertices which are not in P ) which is an independent set of size
k + 3. Further, F is defined to beＵF k .
k≥1

Our main contribution is to prove that every graph in F is a forbidden structure for EHIG. We also show
that the class of proper interval graphs is a strict subclass of EHIG. Finally, we give an algorithm that runs
in polynomial time to recognize graphs belonging to the class of EHIG.