Last year I spent some time trying to prove or disprove the following:

Conjecture. Consider a graph $G$ and define a 2-DNF formula $\phi$ that contains a term $x \land y$ iff $x\mathrel{-\!-}y$ is an edge of $G$. Now consider a decision tree $T$ that represents the same boolean function as $\phi$, and has a minimum number of nodes. (The decision nodes of $T$ are labeled by variables of $\phi$, which are vertices of $G$.) The labels encountered by starting at the root of $T$ and always following the false branch form a minimum vertex cover of $G$.

Is this true or false?

If the conjecture is true, then it is NP-hard to find the root of a minimal decision tree which represents a monotone boolean function given in DNF. In turn, this would imply that it is NP-hard to minimize a decision tree that represents a monotone boolean function. A related but weaker result appears in [Zantema, Bodlaender, Finding Small Equivalent Decision Trees is Hard, 1999]; in particular, their proof uses non-monotone functions.

Example. Consider the path graph $x \mathrel{-\!-} y \mathrel{-\!-} z$. The associated 2-DNF formula is $(x\land y)\lor(y\land z)$. This can be represented by the decision tree

$$\textbf{if $x$ then (if $y$ then $\top$ else $\bot$) else (if $y$ then (if $z$ then $\top$ else $\bot$) else $\bot$)}$$

with 4 decision nodes, but also by the decision tree

$$\textbf{if $y$ then (if $x$ then $\top$ else (if $z$ then $\top$ else $\bot$)) else $\bot$}$$

with 3 decision nodes. There is no equivalent decision tree with less than 3 decision nodes.

In the first, non-minimal decision tree we encounter $x$ and $y$ by following the else branch always. In the second, minimal decision tree we encounter only $y$ by following the else branch always. The set $\{y\}$ is a minimum vertex cover for the graph we started with.

Random observations, from foggy memory.

A. The recursion for minimum vertex covers is similar to the recursion for minimum decision trees:

$$\begin{align} {\it VC}(G) &= \min_{x \in G} \bigl( 1 + {\it VC}(G -x- N(x)) \bigr)\\ {\it DT}(G) &= \min_{x\in G} \bigl( 1 + {\it DT}(G-x-N(x)) + N(x) + {\it DT}(G-x)\bigr) \end{align}$$

Here, $N(x)$ is the set of vertices that are adjacent to $x$. (The recursion for decision trees is not completely obvious. One needs to show that in the true branch of the decision tree it's OK to first greedily check all the neighbors of the root $x$.)

B. If $G$ is a tree, then one can build a minimum decision tree by using an algorithm similar to that for finding vertex covers of trees: always label the root of the decision tree by a vertex that has a neighbor of degree 1.

C. The size ${\it DT}(G)$ of a minimum decision tree can be exponential in the size of $G$. For an example, consider path graphs.

D. Consider two graphs $G_1$ and $G_2$ that share no vertex. Somewhat surprisingly, there seems to be no simple way of obtaining a minimum decision tree for $G_1 \cup G_2$ by combining two given minimum decision trees for $G_1$ and $G_2$. For an example, let each of $G_1$ and $G_2$ be path graphs on 4 vertices. Each minimum decision tree of $G_1$ has 5 decision nodes; thus, there are 6 leaves. It turns out that out of these leaves, 3 are labeled by true and 3 are labeled by false. Since $G_2$ is isomorphic to $G_1$, its minimum decision trees have similar shapes. Composing a minimum decision tree for $G_1$ with a minimum decision tree for $G_2$ (using the obvious algorithm for disjunction between decision trees) gives a decision tree with $5 + 3\times 5=20$ decision nodes. However, there exists a decision tree with only 19 decision nodes.

Background. I bumped into this conjecture while trying to prove a lower bound for a problem discussed in a program analysis paper, [Yang, Grigore, Abstraction Refinement Guided by a Learnt Probabilistic Model, 2016].

Update (Jan 2017): The conjecture is false, as shown by this counterexample found by Eryk Kopczyński:

counterexample with 7 vertices

The question in the title (Is it NP-hard to find a small decision tree for a monotone boolean function?) remains unanswered.

  • $\begingroup$ What if you construct a monotone CNF from a graph $G = (V,E)$ as $\bigwedge_{(x,y) \in E} (x \lor y)$ and follows the true branches in a minimal decision tree $T$? Each solution of this CNF is a vertex cover of $G$. Moreover, if you follow the true branches, I think you find a minimal vertex cover. Indeed, if your vertex cover is not minimal then at some point in the path you have found a minimal vertex cover. Everything that follows is then useless. You can remove it which contradicts the minimality of $T$. $\endgroup$
    – holf
    Jan 29, 2017 at 11:47
  • $\begingroup$ Your CNF is entirely dual and doesn't change the problem at all. Eryk's counterexample still works. $\endgroup$ Jan 29, 2017 at 15:23
  • $\begingroup$ Sorry if I am stupid here but could you elaborate your counter-example a bit by giving the graph. Moreover, it seems to be a confusion as decision-trees cannot reuse computation contrary to the DAG you have given in the counter-example. If you are talking about decision-diagrams (also called FBDD) then I agree that your conjecture is wrong. Please clarify (the paper of Boadlander et al. you give is for decision-trees, with underlying directed trees). $\endgroup$
    – holf
    Jan 29, 2017 at 18:58
  • $\begingroup$ The counterexample above is a graph. (It obviously isn't a tree, so it can't be a decision tree.) $\endgroup$ Jan 29, 2017 at 19:07
  • $\begingroup$ Sorry my bad. I misunderstood. Thanks for the clarifications. $\endgroup$
    – holf
    Jan 29, 2017 at 19:16


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.