<p>Last year I spent some time trying to prove or disprove the following:</p>

<blockquote>
  <p><strong>Conjecture.</strong> 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 <strong>false</strong> branch form a minimum vertex cover of $G$.</p>
</blockquote>

<p>Is this true or false?</p>

<p>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 [<a href="https://scholar.google.com/scholar?q=finding%20small%20equivalent%20decision%20trees%20is%20hard" rel="nofollow noreferrer">Zantema, Bodlaender, <em>Finding Small Equivalent Decision Trees is Hard</em>, 1999</a>]; in particular, their proof uses non-monotone functions.</p>

<hr>

<p><strong>Example.</strong> 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</p>

<p>$$\textbf{if $x$ then (if $y$ then $\top$ else $\bot$) else (if $y$ then (if $z$ then $\top$ else $\bot$) else $\bot$)}$$</p>

<p>with 4 decision nodes, but also by the decision tree</p>

<p>$$\textbf{if $y$ then (if $x$ then $\top$ else (if $z$ then $\top$ else $\bot$)) else $\bot$}$$</p>

<p>with 3 decision nodes. There is no equivalent decision tree with less than 3 decision nodes.</p>

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

<hr>

<p><strong>Random observations</strong>, from foggy memory.</p>

<p><strong>A.</strong> The recursion for minimum vertex covers is similar to the recursion for minimum decision trees:</p>

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

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

<p><strong>B.</strong> 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.</p>

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

<p><strong>D.</strong> Consider two graphs $G_1$ and $G_2$ that share <em>no</em> 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 <strong>true</strong> and 3 are labeled by <strong>false</strong>. 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.</p>

<hr>

<p><strong>Background.</strong> I bumped into this conjecture while trying to prove a lower bound for a problem discussed in a program analysis paper, [<a href="http://arxiv.org/abs/1511.01874" rel="nofollow noreferrer">Yang, Grigore, <em>Abstraction Refinement Guided by a Learnt Probabilistic Model</em>, 2016</a>].</p>

<hr>

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

<p><a href="https://i.sstatic.net/3vFUgm.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/3vFUgm.png" alt="counterexample with 7 vertices"></a></p>

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

CC BY-SA 3.0
2017-01-29T11:47:21.377Z
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$.
holf
CC BY-SA 3.0
2017-01-29T15:23:39.830Z
Your CNF is entirely dual and doesn't change the problem at all. Eryk's counterexample still works.
Radu GRIGore
CC BY-SA 3.0
2017-01-29T18:58:26.993Z
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).
holf
CC BY-SA 3.0
2017-01-29T19:07:00.690Z
The counterexample above *is* a graph. (It obviously isn't a tree, so it can't be a decision tree.)
Radu GRIGore
CC BY-SA 3.0
2017-01-29T19:16:32.853Z
Sorry my bad. I misunderstood. Thanks for the clarifications.
holf
CC BY-SA 3.0
2017-02-01T05:00:30.167Z
@D.W.: 1. The question has always been what the title says, so it is unanswered. 2. The body showed my attempt to answer the question, so it is not mismatched. It's just that now we know that my attempt is doomed to fail. So, one option would be to remove any trace of it.
Radu GRIGore
CC BY-SA 4.0
2019-07-17T16:02:09.610Z
For the question in the title, how do you intend that the input (the function) be represented?  A (not necessarily minimum-size) formula?  A truth table?  It may matter as depending on the representation the input size could vary exponentially.
Neal Young
CC BY-SA 4.0
2019-08-01T07:30:13.613Z
@NealYoung: I'm sorry, I don't recall what I had in mind when I posted the question. Since I'm looking for a lower-bound, I would guess the easiest setting would be to consider the function represented by a circuit.
Radu GRIGore
CC BY-SA 4.0
2019-08-01T16:03:35.733Z
Somewhat related: [This paper](https://doi.org/10.1145/335305.335314) considers the problem of finding a small circuit for a given truth table.  It gives evidence that the problem is unlikely to be either in P or NP-hard.
Neal Young
<graph-theory><boolean-functions>
Is it NP-hard to find (the root of) a small decision tree for a monotone boolean function?
Radu GRIGore
# Is it NP-hard to find (the root of) a small decision tree for a monotone boolean function?

(Asked by: username_0 on 2016-06-08)

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](https://scholar.google.com/scholar?q=finding%20small%20equivalent%20decision%20trees%20is%20hard)]; 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](http://arxiv.org/abs/1511.01874)].

---

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

[![counterexample with 7 vertices](https://i.sstatic.net/3vFUgm.png)](https://i.sstatic.net/3vFUgm.png)

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

**Tags:** graph-theory, boolean-functions

> **Comments:**
> **username_1**: 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$.  
> **username_0**: Your CNF is entirely dual and doesn't change the problem at all. Eryk's counterexample still works.  
> **username_1**: 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).  
> **username_0**: The counterexample above *is* a graph. (It obviously isn't a tree, so it can't be a decision tree.)  
> **username_1**: Sorry my bad. I misunderstood. Thanks for the clarifications.  
> **username_0**: @D.W.: 1. The question has always been what the title says, so it is unanswered. 2. The body showed my attempt to answer the question, so it is not mismatched. It's just that now we know that my attempt is doomed to fail. So, one option would be to remove any trace of it.  
> **username_2**: For the question in the title, how do you intend that the input (the function) be represented?  A (not necessarily minimum-size) formula?  A truth table?  It may matter as depending on the representation the input size could vary exponentially.  
> **username_0**: @NealYoung: I'm sorry, I don't recall what I had in mind when I posted the question. Since I'm looking for a lower-bound, I would guess the easiest setting would be to consider the function represented by a circuit.  
> **username_2**: Somewhat related: [This paper](https://doi.org/10.1145/335305.335314) considers the problem of finding a small circuit for a given truth table.  It gives evidence that the problem is unlikely to be either in P or NP-hard.  

---

## 0 answers

