# Proof that AND-OR graph decision problem is NP-hard

Given an directed acyclic AND-OR graph, where each non-terminal nodes are labelled as either AND or OR. The terminal nodes are the nodes which have no outgoing edges. Children of a node are the vertices all the outgoing edges of the node points to.

A solution graph for a node $S$ on an AND-OR graph $G$ is defined as a subgraph $G'$ which satisfies the following

(1) $S\in G'$

(2) If $v\in G'$ and $v$ is an AND node, then all of $v$'s children in $G$ are in $G'$

(3) If $v\in G'$ and $v$ is an OR ndoe, then at least one of $v$'s children in $G$ also belongs to $G'$

I want to show the following decision problem is NP hard:

Instance: An AND-OR graph $G$, a node $S$ in $G$ and a number $k$.

Question: Does there exist a solution graph for $S$ in $G$ which contains $\leq k$ nodes?

I am thinking about reducing some well known NP-hard problem to this problem. However, I am not sure which problem is the most suitable to pick. Please enlighten me! Thank you!

• Try vertex cover or set cover. – Yuval Filmus Mar 30 '18 at 15:54
• @YuvalFilmus Could you elaborate on the transformation? I am quite unsure how a undirected vertex cover graph can be transformed to a DAG And-Or graph. Thanks! – user122049 Mar 30 '18 at 16:00
• It's a nice challenge for you. – Yuval Filmus Mar 30 '18 at 16:02
• I really think finding the answer yourselves is a better idea than awarding a bounty. "What makes you think the point of an exercise is the answer?", as some users say. Ah well, it's your choice in the end, so feel free to ignore my advice if you wish. – Discrete lizard Apr 1 '18 at 17:44
• You have already been given a hint. If you're unsure how to do something, just try it. That said, there's already a slightly more detailed hint. – Discrete lizard Apr 2 '18 at 8:02