1
$\begingroup$

In the following graph, each node represents a computational problem. An arrow like A -> F indicates that there is a polynomial time Karp reduction from A to F. Observe that there could be more reductions than the ones indicated. C -> D -> A -> E -> B -> C & F ->E

Suppose further that problem C is the (decision version of the) Independent Set problem.

According to the solution to the problem all problems belong to PSPACE, I don't understand why F belongs to this class. Why does this happen?

$\endgroup$

1 Answer 1

3
$\begingroup$

This just boils down to connectivity. If there is a path from the vertex $A$ to the vertex $B$, then the problem $A$ reduces to the problem $B$. There can be additional vertices on the path. Say, $A\rightarrow C\rightarrow B$, then you can reduce the problem $A$ to the problem $C$ first, then to the problem $B$.

In case of your particular graph, there is a path from $F$ to $C$: $F\rightarrow E\rightarrow B\rightarrow C$. This implies $F$ is reducible to the decision version of the Independent Set problem.

$\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.