TY - GEN
T1 - Number of Minimal Hypergraph Transversals and Complexity of IFM with Infrequency
T2 - 18th International Conference of the Italian Association for Artificial Intelligence, AI*IA 2019
AU - Saccà, Domenico
AU - Serra, Edoardo
N1 - Publisher Copyright:
© 2019, Springer Nature Switzerland AG.
PY - 2019
Y1 - 2019
N2 - Hypergraph Dualization (also called as hitting set enumeration) is the problem of enumerating all minimal transversals of a hypergraph H, i.e., all minimal inclusion-wise hyperedges (i.e., sets of vertices) that intersect every hyperedge in H. Dualization is at the core of many important Artificial Intelligence (AI) problems. As a contribution to a better understanding of Dualization complexity, this paper introduces a tight upper bound to the number of minimal transversals that can be computed in polynomial time. In addition, the paper presents an interesting exploitation of the upper bound to the number of minimal transversals. In particular, the problem dealt with is characterizing the complexity of the data mining problem called IFM I (Inverse Frequent itemset Mining with Infrequency constraints), that is the problem of finding a transaction database whose frequent and infrequent itemsets satisfy a number of frequency/infrequency patterns given in input.
AB - Hypergraph Dualization (also called as hitting set enumeration) is the problem of enumerating all minimal transversals of a hypergraph H, i.e., all minimal inclusion-wise hyperedges (i.e., sets of vertices) that intersect every hyperedge in H. Dualization is at the core of many important Artificial Intelligence (AI) problems. As a contribution to a better understanding of Dualization complexity, this paper introduces a tight upper bound to the number of minimal transversals that can be computed in polynomial time. In addition, the paper presents an interesting exploitation of the upper bound to the number of minimal transversals. In particular, the problem dealt with is characterizing the complexity of the data mining problem called IFM I (Inverse Frequent itemset Mining with Infrequency constraints), that is the problem of finding a transaction database whose frequent and infrequent itemsets satisfy a number of frequency/infrequency patterns given in input.
KW - Hypergraph dualization
KW - Hypergraph transversal
KW - Inverse data mining
UR - https://www.scopus.com/pages/publications/85076727698
UR - https://scholarworks.boisestate.edu/cs_facpubs/214/
U2 - 10.1007/978-3-030-35166-3_14
DO - 10.1007/978-3-030-35166-3_14
M3 - Conference contribution
SN - 9783030351656
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 193
EP - 209
BT - AI*IA 2019 – Advances in Artificial Intelligence - 18th International Conference of the Italian Association for Artificial Intelligence, 2019, Proceedings
A2 - Alviano, Mario
A2 - Greco, Gianluigi
A2 - Scarcello, Francesco
Y2 - 19 November 2019 through 22 November 2019
ER -