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

- $ \forall (u,v) \in E, \{u,v\}\nsubseteq S$
- $ \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?