On Dualization over Distributive Lattices

Elbassioni, Khaled

Discrete mathematics & theoretical computer science, Tome 24 (2022) no. 2.

Résumé

Given a partially order set (poset) $P$, and a pair of families of ideals $\mathcal{I}$ and filters $\mathcal{F}$ in $P$ such that each pair $(I,F)\in \mathcal{I}\times\mathcal{F}$ has a non-empty intersection, the dualization problem over $P$ is to check whether there is an ideal $X$ in $P$ which intersects every member of $\mathcal{F}$ and does not contain any member of $\mathcal{I}$. Equivalently, the problem is to check for a distributive lattice $L=L(P)$, given by the poset $P$ of its set of joint-irreducibles, and two given antichains $\mathcal{A},\mathcal{B}\subseteq L$ such that no $a\in\mathcal{A}$ is dominated by any $b\in\mathcal{B}$, whether $\mathcal{A}$ and $\mathcal{B}$ cover (by domination) the entire lattice. We show that the problem can be solved in quasi-polynomial time in the sizes of $P$, $\mathcal{A}$ and $\mathcal{B}$, thus answering an open question in Babin and Kuznetsov (2017). As an application, we show that minimal infrequent closed sets of attributes in a rational database, with respect to a given implication base of maximum premise size of one, can be enumerated in incremental quasi-polynomial time.

Détail

DOI : 10.46298/dmtcs.6742

Classification : 06B23, 68Txx