2
$\begingroup$

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!

$\endgroup$
  • 1
    $\begingroup$ Try vertex cover or set cover. $\endgroup$ – Yuval Filmus Mar 30 '18 at 15:54
  • $\begingroup$ @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! $\endgroup$ – user122049 Mar 30 '18 at 16:00
  • 2
    $\begingroup$ It's a nice challenge for you. $\endgroup$ – Yuval Filmus Mar 30 '18 at 16:02
  • 1
    $\begingroup$ 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. $\endgroup$ – Discrete lizard Apr 1 '18 at 17:44
  • 1
    $\begingroup$ 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. $\endgroup$ – Discrete lizard Apr 2 '18 at 8:02
1
+100
$\begingroup$

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).

$\endgroup$
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.