Which monotone DNFs are evasive?

A Boolean function $$\phi$$ on variables $$X$$ is evasive if every decision tree for $$\phi$$ has height $$|X|$$. In other words, for any strategy that picks variables of $$X$$ and asks for their value, an adversary can answer the queries such that the strategy needs to ask about the value of all variables of $$X$$ to know the value to which $$\phi$$ evaluates.

A monotone DNF is a disjunction of conjunction of variables, representing a monotone Boolean function on the set $$X$$ of variables that it uses.

Which monotone DNFs are evasive? Is there a characterization of them? What is the complexity, given a monotone DNF, of determining whether it is evasive?

Examples of evasive monotone DNFs include single-clause DNFs, e.g., $$x \land y \land z$$, where we must query the value of every variable (and the adversary can answer $$1$$) until the last one which determines the value of the formula. For another example, take $$(x \land y) \lor (y \land z)$$: if I ask about $$x$$ or $$z$$ then the opponent answers $$0$$ and I'm left with evaluating the other clause, if I ask about $$y$$ the opponent answers $$1$$ and I must evaluate $$x \lor z$$ which requires me to query both variables.

However, not all monotone DNFs are evasive. For instance, for $$(s \land t) \lor (t \land u) \lor (u \land v)$$, I can query variable $$t$$. If it is false, then I know that clauses $$s\land t$$ and $$t \land u$$ are false, so I can evaluate the function just knowing $$u$$ and $$v$$ (I don't need to query $$s$$). If it is true, then I have to evaluate $$s \lor u \lor (u \land v)$$, and as the second clause subsumes the third, I just need to know $$s$$ and $$u$$ (I don't need to query $$v$$).

Playing a bit with the problem in the case of graph DNFs (with two variables per clause), it looks like for a path $$(x_0 \land x_1) \lor \cdots \lor (x_{n-1} \land x_{n})$$ with $$n>0$$ the function is not evasive iff $$n$$ is a multiple of 3, and this seems to generalize to trees if there is some kind of tree structure on nodes that are 3 steps apart. For general graphs, I have no idea. I have looked for related work about evasiveness and decision tree complexity for monotone CNFs and DNFs but I didn't find anything relevant.

On graph DNFs, the problem can be seen as a kind of game on the graph of the formula. You pick a vertex $$v$$ (= variable) on the graph, and the opponent can choose between:

• removing $$v$$ and all its incident edges (= $$v$$ evaluates to $$0$$, all clauses involving it are removed), or
• removing the open ball of radius 2 centered on $$v$$, i.e., $$v$$, its adjacent edges, the neighbors of $$v$$, and their adjacent edges (= $$v$$ evaluates to $$1$$, all clauses involving $$v$$ become singleton clauses involving $$v$$'s neighbors, you will need to ask about each of these neighbors because each has a singleton clause involving it, but these singleton clauses subsume all other clauses involving the neighbors so you get to remove them).

The question is about characterizing and recognizing the graphs $$G$$ for which you have a strategy that guarantees that you win, where "winning" means "reaching a graph with an isolated vertex" (= a variable that you do not need to ask about).