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!