| Title | : | Exactly Hittable Interval Graphs |
| Speaker | : | Nisha K K (IITM) |
| Details | : | Mon, 4 Mar, 2024 3:30 PM @ SSB-334 |
| Abstract: | : | 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. |
