1
$\begingroup$

Consider the Independent Dominating Set problem with a directed graph $G=(V,E)$ as instance and the properties that:

  1. $\forall (u,v) \in E, \{u,v\}\nsubseteq S$
  2. $\forall v \in V: v \in S \lor \exists (u,v) \in E: u \in S$

then consider the function $f$ which is a many-one reduction from IDS to SAT for $G$: $$f(G)= \bigwedge_{(u,v) \in E}(\neg x_u \lor \neg x_v) \land \bigwedge_{v \in V}(x_v \lor \bigvee_{(u,v) \in E}x_u)$$

Theorem: $G$ is a yes-instance of IDS $\iff$ $f(G)$ is a yes-instance of SAT

Proof:

"$\Leftarrow$": Assume that $f(G)$ is a yes-instance of SAT:

Consider the propositional atoms $x_u$ and $x_v$ which represent the vertices of an edge. $x$ is $true$ iff is is in $S$. To proof a CNF-formula true we have to proof all conjuncted subformulas true.

Now consider since $\bigwedge_{(u,v) \in E}(\neg x_u \lor \neg x_v)$ holds and tells us that only one of the vertices $u,v$ is allowed to be in $S$ at the same time, this implies $\forall (u,v) \in E, \{u,v\}\nsubseteq S$.

For the second part we know that $\bigwedge_{v \in V}(x_v \lor \bigvee_{(u,v) \in E}x_u)$ only evaluates to true if either $v \in S$ or any $u \in S$ which is connected by an edge to $v$. This implies $\forall v\in V: v \in S \lor \exists(u,v) \in E: u \in S$.

Therefore we are done.

Is my proof for "$\Leftarrow$" of the theorem correct?

Assumption: The proof is correct and the reduction is valid:

Now we know that IDS is NP-hard, for completeness of IDS we still have to show NP-membership of IDS, right? Furthermore we have to provide an efficient algorithm which uses non-determinism to show that IDS is a member of NP, correct?

$\endgroup$

1 Answer 1

1
$\begingroup$

Yes, your proof of $\Rightarrow$ is correct, but note that you still have to prove the second direction to complete the reduction.

Now we know that IDS is NP-hard

Unfortunately, we don't. We'd need a reduction from SAT to IDS and not the other way around.
To convince yourself of why it makes sense, a reduction from $A$ to $B$ means that if we had an algorithm that solves $B$, we could use it to trivially solve $A$. So, in your case - if we had an algorithm that solves SAT we would be able to solve IDS, but that's not what we want to show. We want to claim that if we could solve IDS then we could solve SAT, which means IDS is "at least as hard as SAT".

Also, notice that you need a karp reduction and not just a many-one reduction. That is, a many-one reduction which can be computed in polynomial time (your reduction achieves that)

Furthermore we have to provide an efficient algorithm which uses non-determinism to show that IDS is a member of NP, correct?

Correct.
Assuming we have provided a karp reduction from SAT to IDS, or equivalently - we proved that $\text{SAT}\le_p \text{IDS}$, then all we know is that IDS is NP-hard, and we need to prove that $\text{IDS} \in \text{NP}$ to get that IDS is NP-complete.

$\endgroup$
4
  • $\begingroup$ Thank you, you really helped me a lot with your answer! So, just to clarify, reducing SAT to IDS basically means we are using SAT to solve IDS which means that SAT cannot be harder than IDS. Now we know that, on the other hand, IDS has to be at least as hard to solve as SAT (=> NP-hardness). ... So i just kept on thinking and immedialty came to the conclusion that there (technically) could be an easier $PTIME$-reduction (for example) for IDS aswell, but this would mean that P=NP since IDS is NP-complete, is this correct? If yes, then this is the first time i really got a grasp on this topic! $\endgroup$
    – null1
    Jan 6, 2020 at 22:09
  • 1
    $\begingroup$ No, it's the other way around - reducing SAT to IDS means we can use IDS to solve SAT (thus IDS is "harder" in that sense). I guess that when you say PTIME-reduction you mean karp reduction (reduction that can be computed in poly-time), but that won't always prove that P=NP (and also notice that you first have to prove that IDS is NP-complete). If you would show a karp reduction from IDS to a problem known to be in P then yes, you have proved P=NP, as now intuitively the problem in P can be used to solve IDS which can be used to solve SAT which can be used to solve in problem in NP. $\endgroup$ Jan 6, 2020 at 22:22
  • $\begingroup$ Okay. Thank you, i think i understand now. Since reducing IDS to SAT would prove that SAT is at least as hard as IDS this implies that IDS is at most as hard as SAT, correct? But since we know that SAT is NP-complete and therefore in NP, wouldn't that also imply that IDS is in NP since, by reduction from IDS to SAT, we proved that SAT is harder? Every problem "easier" than SAT lies in NP, correct? $\endgroup$
    – null1
    Jan 6, 2020 at 23:26
  • 1
    $\begingroup$ Yes, exactly! So in order to prove IDS is in NP-complete you can show SAT reduces to IDS (NP-hardness) and that IDS reduces to SAT (IDS is in NP) although directly proving the IDS is NP is obviously easier. To see formally why a karp reduction to a problem in NP implies being in NP we can construct a nondeterminstic machine that computes the reduction and simulates the nondeterminstic machine of the problem known to be in NP and returns its answer $\endgroup$ Jan 6, 2020 at 23:36

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.