Dualization

Here is a (very) succinct survey on the dualization of monotone Boolean functions, and its generalizations, through the different shapes it takes on graphs, hypergraphs, and lattices. Parts of this text come from my Ph.D. thesis you may find here; other sources of interest include [EG95] and [EGM08].

Boolean logic

A Boolean function is a mapping $f:\{0,1\}^n\rightarrow \{0,1\}$. We call arity of $f$ the integer $n$, call Boolean vector a tuple $v$ in $\{0,1\}^n$, and note $v_i$ the value of vector $v$ on coordinate $i$. We note $u\leq v$ if $u_i\leq v_i$ for all $i$, and call Boolean algebra of dimension $n$ the set of all vectors $v\in \{0,1\}^n$ ordered by $\leq$. See Figure 1 below for an illustration of a Boolean algebra of dimension 4. A Boolean function $f$ is said to be monotone if $u\leq v$ implies $f(u)\leq f(v)$ for all $u,v\in \{0,1\}^n$. It is well known that a Boolean function $f$ is monotone if and only if it admits a conjunctive normal form (CNF)

\[\varphi=\bigwedge_{I\in F}\ \bigvee_{i\in I}\ x_i\]

such that ${f=\varphi}$, i.e., $f(x_1,\dots,x_n)=1$ if and only if the assignment $x_1,\dots,x_n$ satisfies $\varphi$, and where no literal $x_i$ is negated. Such a formula is called prime if in addition $I_1\not\subseteq I_2$ for any two distinct clauses $I_1,I_2\in F$. To every monotone Boolean function corresponds in fact a unique such prime CNF. An example of a monotone Boolean function and its prime CNF is given in Figure 1. Another essential representation of a monotone Boolean function $f$ consists of its prime disjunctive normal form (DNF)

\[\psi=\bigvee_{J\in G}\ \bigwedge_{j\in J}\ x_j\]

such that ${f=\psi}$, where no literal $x_j$ is negated, and where $J_1\not\subseteq J_2$ for any two distinct terms $J_1,J_2\in G$; this representation is also unique.

The dual $f^d$ of a Boolean function $f$ is defined by $f^d(v)=\overline{f}(\overline{v})$, where $\overline{f},\overline{v}$ respectively denote the complement of $f$ and $v$, i.e., $\smash{\overline{f}(v)=1-f(v)}$ and $\smash{\overline{v}=(1-v_1,\dots,1-v_n)}$. It is monotone as well, and by definition, it satisfies the equality $\smash{(f^d)^d=f}$. It is well known that if $\varphi$ is a prime CNF formula for $f$, then a prime DNF formula $\psi$ for $f^d$ is obtained by exchanging $\vee$ and $\wedge$, as well as the constants $0$ and $1$. For example, the dual prime DNF of $\varphi=(1\vee 2) \wedge (3\vee 4)$ is $\psi=13 \vee 14 \vee 23 \vee 24$. Then, expanding $\psi$ into a CNF using De Morgan’s laws yields a prime CNF for the dual. Note that the size of the prime CNF of $f^d$ may be exponential in the size of the prime CNF of $f$. A canonical example is the formula $\varphi^\star=(1\vee 2) \wedge (3\vee 4) \wedge (5\vee 6)$, generalized to any arity. In that case, expanding the dual function is still reasonable if we want to produce the prime CNF of the dual in polynomial time in its size. This is however not always the case, and the expanding approach may result, unfortunately, into an exponential blowup in the sizes of the two functions at hand. A canonical example of this phenomenon is the formula $\varphi^{\star\star}={(1\vee 2)\wedge (2\vee 3)\wedge (3\vee4)}$ and its dual, generalized to any arity.

Figure 1. The Boolean algebra of dimension four, the monotone Boolean function $f$ of prime CNF $\varphi=(1\vee 2)\wedge (3\vee 4)$, and its dual. Vectors $v$ such that $f(v)=1$ are in the gray area, vectors such that $f^d(v)=1$ are in bold. It can be checked that $\smash{f(v)=\overline{f}(\overline{v})}$.

The next problems naturally arise.

Dualization of Monotone Conjunctive Normal Forms (Dualization)
Input: A pair $f,g$ of monotone Boolean functions given by their prime CNF.
Question: Are $f$ and $g$ dual?

Generation version of Dualization
Input: A monotone Boolean function $f$ given by its prime CNF.
Output: The prime CNF of the dual function $f^d$.

Observe that the problem could have been equivalently stated as the dualization of monotone disjunctive normal forms, by exchanging $\wedge$ and $\vee$. This is the representation considered in the landmark paper [FK96], while the one presented here can be found in the important work [EGM03] and survey [EGM08].

Since the size of the CNF of $f^d$ may be exponential in that of $f$ (consider $\varphi^{\star}$ as above), aiming at an (input) polynomial-time algorithm to solve the generation version of Dualization is not a reasonable, let alone meaningful, efficiency criterion goal. Here the goal is to get a polynomial-time algorithm in the sizes of both the input and the output: we call total-polynomial (or output-polynomial) such an algorithm. Further, Bioch and Ibaraki have shown in [BI95] that a polynomial-time algorithm for Dualization exists if and only if a total-polynomial time algorithm exists for its generation version.

Another remark is that if $f^d$ has prime CNF $\smash{\varphi’=\bigwedge_{I\in F} \bigvee_{i\in I} x_i}$, then $f$ has for prime DNF $\smash{\psi=\bigvee_{I\in F} \bigwedge_{i\in I} x_i}$. Hence, computing the prime CNF of $\smash{f^d}$ from the prime CNF of $f$ amounts to computing the DNF of $f$ from its prime CNF. As $\smash{(f^d)^d=f}$, computing the prime CNF of $f$ from its prime DNF is equivalent to computing the prime DNF of $f$ from its prime CNF. This yields the following alternative—and perhaps more easily defined—version of Dualization, and its two generation versions.

Dualization of Monotone Boolean Functions (Dual)
Input: A pair $f,g$ of monotone Boolean functions—$f$ given by its prime CNF,
and $g$ by its prime DNF.
Question: Are $f$ and $g$ equal?

First generation version of (Dual)
Input: A monotone Boolean function $f$ given by its prime CNF.
Output: The prime DNF of $f$.

Second generation version of (Dual)
Input: A monotone Boolean function $f$ given by its prime DNF.
Output: The prime CNF of $f$.

Testing the duality of two monotone Boolean functions, i.e., solving either Dualization or Dual, is ubiquitous in many areas of computer science [EG95]. The problem has become so central in enumeration theory that it is now common, in order to characterize the complexity of an enumeration problem, either to exhibit a total-polynomial time algorithm, or to show that the problem is at least as hard as the dualization, a line of research that in part emerged from [KLMN14]. For harder problems, it is often desirable to obtain an output quasi-polynomial time algorithm by reduction to the dualization, see e.g., [AN07, BMN17]. Hence depending on the problem, the dualization of monotone Boolean functions either plays a tractable, or an intractable frontier, concerning the complexity of a problem. Its precise complexity status is thereby one of the most challenging open question in enumeration theory.

To date, the best known algorithm is due to Fredman and Khachiyan [FK96] and runs in quasi-polynomial time $N^{o(\log N)}$ where $N=|\varphi|+|\psi|$, with $\varphi$ and $\psi$ being the prime CNF and DNF of two functions $f$ and $g$, and where $|\varphi|$ denotes the number of clauses in $\varphi$. In consequence, the problem is unlikely to be NP-hard. Furthermore, this algorithms guarantees incremental (quasi-polynomial) delay on the output; see e.g., [JYP86, Str19] for more details on the complexity of enumeration algorithms.

Since the algorithm of Fredman and Khachiyan, progress has been made on various subclasses of monotone functions. Most importantly, total-polynomial time algorithms were obtained in degenerate CNFs, read-$k$ CNFs, acyclic CNFs and formulas of bounded treewidth [EGM03], or formulas of bounded conformality generalizing those of bounded clause-intersections [KBEG07].

Graphs

A dominating set in a graph $G$ is a set $D\subseteq V(G)$ such that every vertex of $G$ is either in $D$ or is adjacent to some vertex of $D$, i.e., such that $V(G)=N[D]$. It is (inclusion-wise) minimal if it does not contain any other dominating set as a subset.

Minimal dominating sets enumeration (Dom-Enum)
Input: a graph $G$.
Output: the set $\mathcal{D}(G)$ of minimal dominating sets of $G$.

Decision version: given $G$ and a family $\mathcal{S} \subseteq 2^{V(G)}$ decide whether $\mathcal{S} = \mathcal{D}(G)$.

This problem was shown equivalent to Dualization (by the intermediate of Trans-Enum below) in [KLMN14], even when restricted to co-bipartite graphs. In the same paper, they show the split case to be tractable. Later on in [BDH+20] the bipartite case (in fact any $K_t$-free graph for a constant $t$) is shown to be tractable as well. Other tractable cases include $\log n$-degenerate graphs [EGM03], chordal graphs [KLM+16], or graphs of bounded clique-width [Cou09]. See [GHK+14] for more tractables cases. Important open cases include comparability graphs, or $C_4$-free graphs [BDH+20].

Hypergraphs

A transversal in a hypergraph $\mathcal{H}$ is a set of vertices $T$ that intersects every edge of $\mathcal{H}$. It is (inclusion-wise) minimal if it does not contain any other transversal as a subset.

Minimal transversals enumeration (Trans-Enum)
Input: a hypergraph $\mathcal{H}$.
Output: the set $Tr(\mathcal{H})$ of minimal transversals of $\mathcal{H}$.

Decision version: given $\mathcal{H}$ and a family $\mathcal{S} \subseteq 2^{V(\mathcal{H})}$ decide whether $\mathcal{S} = Tr(\mathcal{H})$.

This problem is known to be equivalent to Dualization since decades, see e.g. [EG95]. It has received considerable attention since then and has been shown to be tractable for degenerate hypergraphs [EGM03], $\alpha$ and $\beta$ acyclic hypergraphs [EG95, EGM03], hypergraphs without small holes [KKP18], variants of hypergraphs with bounded edge intersection [KBEG07], or in some geometric cases [ERR19]. Important open cases include hypergraphs of bounded VC-dimension.

Lattices dualization

An implicational base $(X,\Sigma)$ is a set $\Sigma$ of implications of the form $A\rightarrow B$ over a groundset $X$, i.e., with $A\subseteq X$ and $B\subseteq X$. A set $S\subseteq X$ is closed in $\Sigma$ if for every implication $A\rightarrow B$ in $\Sigma$, $\smash{A\subseteq S}$ entails $B\subseteq S$. To $\Sigma$ we associate the closure operator $\phi$ which maps every set $S\subseteq X$ to the smallest closed set containing $S$. The set of all closed sets of $\Sigma$ is denoted by $\mathcal{C}_\Sigma$. It is well known that every lattice can be defined as the set $\mathcal{C}_\Sigma$ of all closed sets of an implicational base $(X,\Sigma)$, ordered by inclusion. We note $\mathcal{L}_\Sigma=(\mathcal{C}_\Sigma,\subseteq)$ such a lattice. If the implicational base is empty, then $\mathcal{L}_\Sigma$ is Boolean; see Figure 1 above for an example of a Boolean lattice.

An antichain of $\mathcal{L}_{\Sigma}$ is a set of inclusion-wise incomparable closed sets of $\Sigma$. The ideal of an antichain $\mathcal{A}$ of $\mathcal{L}_\Sigma$ is the set $\smash{\downarrow \mathcal{A}=\{C \in \mathcal{C}_\Sigma \mid C\subseteq A\ \text{for some}\ A\in \mathcal{A}\}}$. The filter of $\mathcal{A}$ is the dual $\smash{\uparrow \mathcal{A}=\{C \in \mathcal{C}_\Sigma \mid C\supseteq A\ \text{for some}\ A\in \mathcal{A}\}}$. A pair $(\mathcal{A},\mathcal{B})$ of antichains of $\mathcal{L}_\Sigma$ is called dual if

\[\uparrow \mathcal{A}\ \cap \downarrow \mathcal{B} = \emptyset\text{ and }\uparrow \mathcal{A}\ \cup \downarrow \mathcal{B} = \mathcal{C}_\Sigma.\]

Dualization in lattices given by implicational bases
Input: an implicational base $(X,\Sigma)$ that codes a lattice $\mathcal{L}_\Sigma$, and an antichain $\mathcal{A}$ of $\mathcal{L}_\Sigma$.
Output: the antichain $\mathcal{B}$ such that $(\mathcal{A},\mathcal{B})$ is dual in $\mathcal{L}_\Sigma$.

Decision version: given $(X,\Sigma)$ and $\mathcal{A},\mathcal{B}\subseteq 2^X$, decide whether $(\mathcal{A},\mathcal{B})$ is dual.

For this problem, it was shown in [BK17] that no total-polynomial time algorithm exists unless P=NP. This result was strengthened in [DN20] to implicational base with premises of size at most two. If $\Sigma$ is empty, then the problems is equivalent to Dualization [EGM08, NP14]. If $\Sigma$ only contains implications of premises’ size one, then the lattice is distributive and the problem is known to admit an output quasi-polynomial time algorithm [Elb22]. The case of $\Sigma$ being acyclic is open.

Lattices representations

Recall that if $\mathcal{L}$ is a lattice, then $\mathcal{L}=(\mathcal{C}_\Sigma,\subseteq)$ for some implicational base $(X,\Sigma)$. A set $M \subseteq X$ is a meet-irreducible element of $\mathcal{L}$ if $M\in \mathcal{C}_\Sigma$, $M\neq X$, and for all $C_1, C_2 \in \mathcal{C}_\Sigma$ such that $M=C_1\cap C_2$ it follows that $C_1 = M$ or $C_2 = M$. In other words, meet-irreducible element are the elements of $\mathcal{L}$ having a unique successor in the lattice. We note $\mathcal{M}(\mathcal{L})$ the set of all meet-irreducible elements of $\mathcal{L}$. It is well known that $\mathcal{L}$ can be reconstructed by intersections of $\mathcal{M}(\mathcal{L})$. Hence just as $(X,\Sigma)$ does, $\mathcal{M}(\mathcal{L})$ yields another (sometimes very compact) representation of $\mathcal{L}=(\mathcal{C}_\Sigma,\subseteq)$.

Meet-irreducible enumeration
Input: an implicational base $(X,\Sigma)$ coding the lattice $\mathcal{L}=(\mathcal{C}_\Sigma,\subseteq)$.
Output: the set $\mathcal{M}(\mathcal{L})$ of meet-irreducible elements of $\mathcal{L}$.

Implicational base construction
Input: a family $\mathcal{M}\subseteq 2^X$ coding a lattice $\mathcal{L}$.
Output: an implicational base $(X,\Sigma)$ of minimum size such that $\mathcal{L}=(\mathcal{C}_\Sigma,\subseteq)$.

Decision version: given $(X,\Sigma)$ and $\mathcal{M}\subseteq 2^X$, decide whether $\mathcal{M}=\mathcal{M}(\mathcal{L}_\Sigma)$.

Despite decades of extensive research, the complexity status of this problem remains open [Kha95]. For rather simple cases of lattices, the problems is known to be equivalent to Dualization [Wil17], but its links with Lattice Dualization remain unclear for most classes of lattices. To date, tractable cases were shown to include $k$-meet-semidistributive lattices [BMN17] or ranked convex geometries [DNV21]. Important open cases include (acyclic) convex geometries.

If you are interested in working on dualization, feel free to message me!
TL;DR version here.