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!

Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ Try vertex cover or set cover. $\endgroup$
    – Yuval Filmus
    Commented Mar 30, 2018 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
    Commented Mar 30, 2018 at 16:00
  • 2
    $\begingroup$ It's a nice challenge for you. $\endgroup$
    – Yuval Filmus
    Commented Mar 30, 2018 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 ♦
    Commented Apr 1, 2018 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 ♦
    Commented Apr 2, 2018 at 8:02

2 Answers 2

Reset to default
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).

Improve this answer
$\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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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