# 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. Commented Mar 30, 2018 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! Commented Mar 30, 2018 at 16:00
• It's a nice challenge for you. Commented Mar 30, 2018 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. Commented Apr 1, 2018 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. Commented Apr 2, 2018 at 8:02