Algorithms for Dualization over Products of Partially Ordered Sets
Khaled Elbassioni · SIAM Journal on Discrete Mathematics · 2009
Let $\mathcal P=\mathcal P_1\times\cdots\times\mathcal P_n$ be the product of n partially ordered sets (posets). Given a subset $\mathcal A\subseteq\mathcal P$, we consider problem $\mathrm{DUAL}(\mathcal P,\mathcal A,\mathcal B)$ of extending a given partial list $\mathcal B$ of maximal independent elements of $\mathcal A$ in $\mathcal P$. We give quasi-polynomial time algorithms for solving problem $\mathrm{DUAL}(\mathcal P,\mathcal A,\mathcal B)$ when each poset $\mathcal P_i$ belongs to one of the following classes: (i) semilattices of bounded width, (ii) forests, that is, posets with acyclic underlying graphs, with either bounded in-degrees or out-degrees, or (iii) lattices defined by a set of real closed intervals.