| Title | : | Minimum Membership Hitting Sets of Hypergraphs |
| Speaker | : | Dhannya S M (IITM) |
| Details | : | Tue, 31 Jul, 2018 2:00 PM @ A M Turing Hall |
| Abstract: | : | The Minimum Membership Set Cover (MMSC) problem is a well studied variant among set covering problems. We study the dual of MMSC problem which we refer to as Minimum Membership Hitting Set (MMHS) problem. An MMHS of a hypergraph H is a hitting set of H that minimizes the maximum number of times (over all) hyperedges in H is hit. We show that the MMHS problem for hypergraphs induced by horizontal axis parallel segments intersected by vertical axis parallel segments is NP-complete. In the case when the horizontal segments are intersected by vertical lines (instead of vertical segments), we give an algorithm to optimally solve the MMHS problem in polynomial time. Exact Hitting Set (EHS) problem is a special case of MMHS problem that seeks to find if there exists a hitting set of hypergraph H such that every hyperedge of H is hit exactly once. If a hypergraph has an exact hitting set, we call it an exactly hittable hypergraph. We introduce a graph class which we call Exactly Hittable Interval Graphs. These are interval graphs that have exactly hittable intersection models. We present a forbidden structure characterization for this class of graphs. |
