13. Exam 4 Review

study

• Integer programming
• proving an approximation
• proving reduction - prove certificates are equal

Alpha Approximation

Max Approximation (lower bound)

$ALG/OPT\ge \alpha$ where $\alpha \le 1$

Min Approximation (upper bound)

$ALG/OPT\le \alpha$ where $\alpha \ge 1$

Chain of Reductions

3-SAT → IND_SET → VERTEX_COVER 3-SAT → DIRECTEDHAMILTONIANCYCLES → HAMCYCLE 3-SAT → INTEGER PROGRAMMING

Proving NP or NP hard

NP ← verified with polynomial time alg NP-hard ← take any known NP problem A and reduce it to B to prove NP-hard NP-complete ← both NP and NP-hard

Problems

1. In P or not? Determine if $a^b$ is even.

Divide exponentiated value by 2 until value ⇐ 1 if value = 0 then it is even

Perform division some $a$ times. Division takes $b$ steps. $O(ab)$

2. Prove if polynomial time alg for SAT, then polynomial-time alg to find assignment.

Run SAT changing one bit to 0 every single run while keeping track of bits that result in a YES for SAT. Brute force.

3a. If A is NP-complete, then B can be proved to be NP-complete if $B\in NP$ and A reduces to B.

True by def

3b. If A is NP-complete and B reduces to A, B is NP-Complete

False. Must reduce a problem in NP to B. Not the other way around.

3c. If P alg for 3-SAT, then P alg for 4-SAT

True because I assume 4-SAT is in NP.

3d. Vice versa 3c

True

3e. True

3f. True

3g. If A reduces to B and B reduces to C, then A can reduce to C

True

3h. True

4. Prove the following problem is NP-complete: if a graph has a strongly independent set of size k

Prove NP

we take a certificate of the vertices in the SIS and check for every vertex if there’s an edge to any of the other vertices and then for every one of it’s neighboring vertices in the graph, we check if it’s connected to a vertex in the SIS.

Prove NP-hard

We prove both ways st. G has an IS iff G’ has a SIS size k.

Assume it has an independent set $A$ of size k. We add an intermediary vertex for every edge in G. Any edge $(u,v)$ becomes $(u,a)$ and $(a,v)$ for the new vertex $a$. Call this graph $G^{\prime }$. Consider every vertex pair in $A$. Since they do not have an edge, then these vertices must not have a path of length two since the only way for there to be a path of length 2 is if they shared an edge in the original graph. Therefore, $A$ is a SIS.

Assume $G^{\prime }$ has a SIS $B$. We take every intermediary vertex out that does not belong to G. The only way for there to be an edge between two vertices in $B$ is for these vertices to have a path of length 2 in $G^{\prime }$. This contradicts the definition of an SIS. Therefore, there must not be an edge in G between any vertex pair in $B$. Therefore, B must be an IS.

5. Prove G has a dominating set of size k is an NP-complete problem

Prove NP

Use vertex sets V and D to check for every vertex if it is either in D or adjacent to a vertex in D

Prove NP-hard