# Exactly Hittable Interval Graphs

Source: [Exactly Hittable Interval Graphs](<https://www.sota2.com/research/paper/68fa72361e209131cea54f73>)

Collection index: [llms.txt](<https://www.sota2.com/research/llms.txt>)

Data updated: 2025-10-27T06:30:07.638Z

Authors: S.M. Dhannya, N.S. Narayanaswamy, K.K. Nisha

Published: 2023-01-01T11:33:28.000Z

## Abstract

Given a set system $\\mathcal{X} = \\{\\mathcal{U},\\mathcal{S}\\}$, where $\\mathcal{U}$ is a set of elements and $\\mathcal{S}$ is a set of subsets of $\\mathcal{U}$, an exact hitting set $\\mathcal{U}'$ is a subset of $\\mathcal{U}$ such that each subset in $\\mathcal{S}$ contains exactly one element in $\\mathcal{U}'$. We refer to a set system as exactly hittable if it has an exact hitting set. In this paper, we study interval graphs which have intersection models that are exactly hittable. We refer to these interval graphs as exactly hittable interval graphs (EHIG). We present a forbidden structure characterization 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.

## Recorded benchmark results

A research result applies to its stated dataset, split, metric and evaluation configuration. Compare like-for-like settings, preserve the metric's unit and direction, and distinguish paper-reported results from independent reproduction. The best result recorded here is not a claim of exhaustive, current global coverage.

## Original sources and implementation

[Original paper](<https://arxiv.org/abs/2301.00387>)

[PDF](<https://arxiv.org/pdf/2301.00387.pdf>)
