A Simple and Effective ASP-Based Tool for Enumerating Minimal Hitting Sets
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866908750427717632 |
|---|---|
| author | Kabir, Mohimenul Meel, Kuldeep S |
| author_facet | Kabir, Mohimenul Meel, Kuldeep S |
| contents | The hitting set problem is a fundamental problem in computer science and mathematics. Given a family of sets over a universe of elements, a minimal hitting set is a subset-minimal collection of elements that intersects each set in the family. Enumerating all minimal hitting sets is crucial in various real-world applications.
In this paper, we address the full enumeration of all minimal hitting sets for a given family of sets. We formulate the problem using Answer Set Programming (ASP) and leverage existing ASP solvers for efficient enumeration. We propose an ASP-based tool, MinHit-ASP, and our empirical evaluation shows that it effectively enumerates minimal hitting sets across benchmarks from diverse problem domains. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_09194 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A Simple and Effective ASP-Based Tool for Enumerating Minimal Hitting Sets Kabir, Mohimenul Meel, Kuldeep S Logic in Computer Science The hitting set problem is a fundamental problem in computer science and mathematics. Given a family of sets over a universe of elements, a minimal hitting set is a subset-minimal collection of elements that intersects each set in the family. Enumerating all minimal hitting sets is crucial in various real-world applications. In this paper, we address the full enumeration of all minimal hitting sets for a given family of sets. We formulate the problem using Answer Set Programming (ASP) and leverage existing ASP solvers for efficient enumeration. We propose an ASP-based tool, MinHit-ASP, and our empirical evaluation shows that it effectively enumerates minimal hitting sets across benchmarks from diverse problem domains. |
| title | A Simple and Effective ASP-Based Tool for Enumerating Minimal Hitting Sets |
| topic | Logic in Computer Science |
| url | https://arxiv.org/abs/2507.09194 |