exercises_34.5.md

34.5 NP-complete problems

34.5-1

The subgraph-isomorphism problem takes two undirected graphs $G_1$ and $G_2$, and it asks whether $G_1$ is isomorphic to a subgraph of $G_2$. Show that the subgraph-isomorphism problem is NP-complete.

Prove SIP $\in$ NP

The certificate $C$ is a permutation of $[1, \dots, n]$, we need to check:

• $|V_1| = |V_2|$
• $|E_1| = |E_2|$
• for each pair of nodes $u_i, v_i \in V_1$: $(u_{C_{u_i}}, v_{C_{v_i}}) \in E_2$ if $(u_i, v_i) \in E_1$
• for each pair of nodes $u_i, v_i \in V_1$: $(u_{C_{u_i}}, v_{C_{v_i}}) \notin E_2$ if $(u_i, v_i) \notin E_1$

It takes $O(|V_1|^2)$ time to verify the certificate, therefore subgraph-isomorphism problem $\in$ NP.

Prove SIP $\in$ NPC by proving CLIQUE $\le_\text{P}$ SIP

Construction:

Suppose we want to check whether $G_2$ contains a clique of size $k$. We can construct a complete graph $G_1$ that has $k$ vertices, and check whether $G_1$ is isomorphic to a subgraph of $G_2$. The construction takes $O(|V|^2)$ time since $k \le |V|$ without the loss of generality.

CLIQUE $\Rightarrow$ SIP:

The clique is a subgraph of $G_2$ and isomorphic to $G_1$.

SIP $\Rightarrow$ CLIQUE:

A subgraph in $G_2$ has $k$ vertices and is complete.

34.5-2

Given an integer $m \times n$ matrix $A$ and an integer $m$-vector $b$, the 0-1 integer-programming problem asks whether there exists an integer $n$-vector $x$ with elements in the set $\{0, 1\}$ such that $Ax \le b$. Prove that 0-1 integer programming is NP-complete. (Hint: Reduce from 3-CNF-SAT.)

Prove 0-1-IP $\in$ NP

The certificate is $x$, we can calculate $Ax$ in $O(mn)$.

Prove 0-1-IP $\in$ NPC by proving 3-CNT-SAT $\le_\text{P}$ 0-1-IP

Construction:

(To satisfy $x_1 \vee \neg x_2 \vee \neg x_3$, we can convert it to $x_1 + (1 - x_2) + (1 - x_3) \ge 1$ $\Rightarrow$ $-x_1 + x_2 + x_3 \le 1$)

Suppose in 3-CNT-SAT the formula $\phi$ has $m$ clauses and $n$ variables. Construct a matrix $A$ of size $m \times n$, that for each clause $C_i$:

• if $x_j \in C_i$, set $A_{i, j} = -1$,
• if $\neg x_j \in C_i$, set $A_{i, j} = 1$.

Construct a $m$-vector $b$ that:

• if there are $k$ $\neg$s in $C_i$, set $b_{i} = k - 1$.

The construction runs in $O(mn)$.

3-CNT-SAT $\Rightarrow$ 0-1-IPP:

Based on how we construct $A$ and $b$.

0-1-IPP $\Rightarrow$ 3-CNT-SAT:

By moving back 1s, at least one item in $C_i$ must be 1.

34.5-3

The integer linear-programming problem is like the 0-1 integer-programming problem given in Exercise 34.5-2, except that the values of the vector $x$ may be any integers rather than just 0 or 1. Assuming that the 0-1 integer-programming problem is NP-hard, show that the integer linear-programming problem is NP-complete.

Prove ILP $\in$ NP

The certificate is $x$, we can calculate $Ax$ in $O(mn)$.

Prove ILP $\in$ NPC by proving 0-1-IP $\le_\text{P}$ ILP

(Add constrains $0 \le x_i \le 1$ $\Rightarrow$ $-x_i \le 0$ and $x_i \le 1$)

Suppose the original $A$ in 0-1-IP is of size $m \times n$, then the extended $A'$ is of size $(m + 2n) \times n$:

• if $i <= m$, $A'_{i, j} = A_{i, j}$,
• if $i > m$ and $i - m$ is even, $A_{i, (i - m) / 2} = -1$,
• if $i > m$ and $i - m$ is odd, $A_{i, (i - m - 1) / 2} = 1$.

The constructed $(m + 2n)$-vector $b'$:

• if $i <= m$, $b'_{i} = b_{i}$,
• if $i > m$ and $i - m$ is even, $b_{i} = 0$,
• if $i > m$ and $i - m$ is odd, $b_{i} = 1$.

The construction runs in $O(mn)$.

34.5-4

Show how to solve the subset-sum problem in polynomial time if the target value $t$ is expressed in unary.

0-1 knapsack.

dp[0, .., t] = FALSE
dp[0] = TRUE
FOR s IN S
    FOR i IN [t, .., 0]
        IF dp[i - s] THEN
            dp[i] = TRUE
            BREAK
RETURN dp[t]

Runs in $O(|S|t)$, since $t$ is expressed in unary, the time complexity is a polynomial function of the input.

34.5-5

The set-partition problem takes as input a set $S$ of numbers. The question is whether the numbers can be partitioned into two sets $A$ and $\overline{A} = S - A$ such that $\sum_{x \in A} x = \sum_{x \in \overline{A}} x$. Show that the set-partition problem is NP-complete.

Prove SPP $\in$ NP

The certificate is $A$, just calculate the sum of $A$ and $\overline{A}$ and check whether the results are the same.

The verification runs in $O(|S|)$.

Prove SPP $\in$ NPC by proving SUBSET-SUM $\le_\text{P}$ SPP

Construction:

Suppose the target is $t$ in SUBSET-SUM, the sum of $S$ is $s$, then $\sum_{x \in A} x = t$, $\sum_{x \in \overline{A}} x = s - t$. We construct $S' = S \cup \{ |s - 2t| \}$ for set-partition problem.

SUBSET-SUM $\Rightarrow$ SPP:

• if $t \le s - t$, we add $s - 2t$ to $A$, then $\sum_{x \in A} x = t + s - 2t = s - t = \sum_{x \in \overline{A}} x$,
• if $t > s - t$, we add $2t - s$ to $\overline{A}$, then $\sum_{x \in \overline{A}} x = s - t + 2t - s = t = \sum_{x \in A} x$.

SPP $\Rightarrow$ SUBSET-SUM:

• if $t \le s - t$, then the set contains $s - 2t$ is a solution for SUBSET-SUM after removing $s - 2t$,
• if $t > s - t$, suppose set $A$ containts $s - 2t$, then $\overline{A}$ is a solution for SUBSET-SUM.

34.5-6

Show that the hamiltonian-path problem is NP-complete.

Prove HAM-PATH $\in$ NP

Given the vertices $(v_1, \dots, v_n)$ as certificate, verify in $O(|V|^2)$:

• $v_1 = u$,
• $v_n = v$,
• $v_i \ne v_j$ $\forall i, j \in [1, \dots, n]$,
• $(v_i, v_{i + 1}) \in E \forall i \in [1, \dots, n - 1]$.

Prove HAM-PATH $\in$ NPC by proving HAM-CYCLE $\le_\text{P}$ HAM-PATH

Construction:

Choose a vertex $a$ arbitrarily, add a vertex $a'$ to the graph and $\forall (a, v_i) \in E$ add edges $(a', v_i)$. Add edge $(u, a)$ and $(v, a')$. The construction takes $O(V)$ time.

HAM-CYCLE $\Rightarrow$ HAM-PATH:

If there is a hamilton cycle in $G$, suppose the two vertices connects to $a$ are $c_1$ and $c_2$, then there is a hamilton path $(u, a, c_1, \dots, c_2, a', v)$.

HAM-PATH $\Rightarrow$ HAM-CYCLE:

If there is a hamilton path from $u$ to $v$, then there is a hamilton cycle by removing $u$, $v$ and $a'$.

34.5-7

The longest-simple-cycle problem is the problem of determining a simple cycle (no repeated vertices) of maximum length in a graph. Formulate a related decision problem, and show that the decision problem is NP-complete.

Decision problem: a simple cycle of size at most $k$.

Prove LSC $\in$ NP

Given the vertices $(v_1, \dots, v_n)$ as certificate, verify in $O(|V|^2)$:

• $v_i \ne v_j \forall i, j \in [1, \dots, n]$,
• $(v_i, v_{i + 1}) \in E$ $\forall i \in [1, \dots, n - 1]$,
• $(v_n, v_1) \in E$.

Prove LSC $\in$ NPC by proving HAM-CYCLE $\le_\text{P}$ LSC

HAM-CYCLE is equivalent to solve LSC with $k = |V|$.

34.5-8

In the half 3-CNF satisfiability problem, we are given a 3-CNF formula $\phi$ with $n$ variables and $m$ clauses, where $m$ is even. We wish to determine whether there exists a truth assignment to the variables of $\phi$ such that exactly half the clauses evaluate to 0 and exactly half the clauses evaluate to 1. Prove that the half 3-CNF satisfiability problem is NP-complete.

Prove HALF-3-CNF-SAT $\in$ NP

Evaluate in $O(n)$.

Prove HALF-3-CNF-SAT $\in$ NPC by proving 3-CNF-SAT $\le_\text{P}$ HALF-3-CNF-SAT

Construction:

Suppose $p, q, r$ are variables not in $\phi$, we add $m$ clauses $(p \vee \neg p \vee q)$ which are always evaluated to 1 and $2m$ clauses $(p \vee q \vee r)$. The construction takes $O(m)$ time and results in $4m$ clauses.

3-CNT-SAT $\Rightarrow$ HALF-3-CNF-SAT:

The original $\phi$ has $m$ clauses evaluate to 1, let $p = q = r = 0$, then there are $2m$ clauses evaluate to 0 and $2m$ clauses evaluate to 1.

HALF-3-CNF-SAT $\Rightarrow$ 3-CNT-SAT:

There is no solution if any one of $p, q, r$ is 1 since there will be at least $3m$ clauses evaluate to 1. Therefore the rest $m$ clauses in original $\phi$ must evaluate to 1.