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

Hint: Given an instance of vertex cover problem, build an AND-OR graph whose terminal nodes represent the vertices and the OR nodes represent the edges.

One further hint: Make the root an AND node that has outgoing edges to all the OR nodes (that represent the edges in the vertex cover problem).

Hint: given an instance of set cover problem, build an AND-OR graph whose terminal nodes represent elements and whose OR nodes represent sets.