Chapter_34_NP-Completeness/exercises_34.5.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 34.5 NP-Completeness"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 34.5-1\n",
    "\n",
    "> 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."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Prove SIP $\\in$ NP__\n",
    "\n",
    "The certificate $C$ is a permutation of $[1, \\dots, n]$, we need to check:\n",
    "\n",
    "* $|V_1| = |V_2|$\n",
    "* $|E_1| = |E_2|$\n",
    "* 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$\n",
    "* 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$\n",
    "\n",
    "It takes $O(|V_1|^2)$ time to verify the certificate, therefore subgraph-isomorphism problem $\\in$ NP."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Prove SIP $\\in$ NPC by proving CLIQUE $\\le_\\text{P}$ SIP__"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Construction:*\n",
    "\n",
    "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."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*CLIQUE $\\Rightarrow$ SIP:*\n",
    "\n",
    "The clique is a subgraph of $G_2$ and isomorphic to $G_1$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*SIP $\\Rightarrow$ CLIQUE:*\n",
    "\n",
    "A subgraph in $G_2$ has $k$ vertices and is complete."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 34.5-2\n",
    "\n",
    "> 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.)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Prove 0-1-IP $\\in$ NP__"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The certificate is $x$, we can calculate $Ax$ in $O(mn)$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Prove 0-1-IP $\\in$ NPC by proving 3-CNT-SAT $\\le_\\text{P}$ 0-1-IP__"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "_Construction:_\n",
    "\n",
    "(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$)\n",
    "\n",
    "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$:\n",
    "\n",
    "* if $x_j \\in C_i$, set $A_{i, j} = -1$,\n",
    "* if $\\neg x_j \\in C_i$, set $A_{i, j} = 1$.\n",
    "\n",
    "Construct a $m$-vector $b$ that:\n",
    "\n",
    "* if there are $k$ $\\neg$s in $C_i$, set $b_{i} = k - 1$.\n",
    "\n",
    "The construction runs in $O(mn)$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "_3-CNT-SAT $\\Rightarrow$ 0-1-IPP:_\n",
    "\n",
    "Based on how we construct $A$ and $b$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "_0-1-IPP $\\Rightarrow$ 3-CNT-SAT:_\n",
    "\n",
    "By moving back 1s, at least one item in $C_i$ must be 1."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 34.5-3\n",
    "\n",
    "> 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."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Prove ILP $\\in$ NP__\n",
    "\n",
    "The certificate is $x$, we can calculate $Ax$ in $O(mn)$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Prove ILP $\\in$ NPC by proving 0-1-IP $\\le_\\text{P}$ ILP__\n",
    "\n",
    "(Add constrains $0 \\le x_i \\le 1$ $\\Rightarrow$ $-x_i \\le 0$ and $x_i \\le 1$)\n",
    "\n",
    "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$:\n",
    "\n",
    "* if $i <= m$, $A'_{i, j} = A_{i, j}$,\n",
    "* if $i > m$ and $i - m$ is even, $A_{i, (i - m) / 2} = -1$,\n",
    "* if $i > m$ and $i - m$ is odd, $A_{i, (i - m - 1) / 2} = 1$.\n",
    "\n",
    "The constructed $(m + 2n)$-vector $b'$:\n",
    "\n",
    "* if $i <= m$, $b'_{i} = b_{i}$,\n",
    "* if $i > m$ and $i - m$ is even, $b_{i} = 0$,\n",
    "* if $i > m$ and $i - m$ is odd, $b_{i} = 1$.\n",
    "\n",
    "The construction runs in $O(mn)$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 34.5-4\n",
    "\n",
    "> Show how to solve the subset-sum problem in polynomial time if the target value $t$ is expressed in unary."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "0-1 knapsack.\n",
    "\n",
    "```\n",
    "dp[0, .., t] = FALSE\n",
    "dp[0] = TRUE\n",
    "FOR s IN S\n",
    "    FOR i IN [t, .., 0]\n",
    "        IF dp[i - s] THEN\n",
    "            dp[i] = TRUE\n",
    "            BREAK\n",
    "RETURN dp[t]\n",
    "```\n",
    "\n",
    "Runs in $O(|S|t)$, since $t$ is expressed in unary, the time complexity is a polynomial function of the input."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 34.5-5\n",
    "\n",
    "> 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."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Prove SPP $\\in$ NP__\n",
    "\n",
    "The certificate is $A$, just calculate the sum of $A$ and $\\overline{A}$ and check whether the results are the same.\n",
    "\n",
    "The verification runs in $O(|S|)$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Prove SPP $\\in$ NPC by proving SUBSET-SUM $\\le_\\text{P}$ SPP__"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "_Construction:_\n",
    "\n",
    "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."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "_SUBSET-SUM $\\Rightarrow$ SPP:_\n",
    "\n",
    "* 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$,\n",
    "* 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$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "_SPP $\\Rightarrow$ SUBSET-SUM:_\n",
    "\n",
    "* if $t \\le s - t$, then the set contains $s - 2t$ is a solution for SUBSET-SUM after removing $s - 2t$,\n",
    "* if $t > s - t$, suppose set $A$ containts $s - 2t$, then $\\overline{A}$ is a solution for SUBSET-SUM."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 34.5-6\n",
    "\n",
    "> Show that the hamiltonian-path problem is NP-complete."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Prove HAM-PATH $\\in$ NP__\n",
    "\n",
    "Given the vertices $(v_1, \\dots, v_n)$ as certificate, verify in $O(|V|^2)$:\n",
    "\n",
    "* $v_1 = u$,\n",
    "* $v_n = v$,\n",
    "* $v_i \\ne v_j$ $\\forall i, j \\in [1, \\dots, n]$,\n",
    "* $(v_i, v_{i + 1}) \\in E \\forall i \\in [1, \\dots, n - 1]$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Prove HAM-PATH $\\in$ NPC by proving HAM-CYCLE $\\le_\\text{P}$ HAM-PATH__"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "_Construction:_\n",
    "\n",
    "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."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "_HAM-CYCLE $\\Rightarrow$ HAM-PATH:_\n",
    "\n",
    "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)$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "_HAM-PATH $\\Rightarrow$ HAM-CYCLE:_\n",
    "\n",
    "If there is a hamilton path from $u$ to $v$, then there is a hamilton cycle by removing $u$, $v$ and $a'$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 34.5-7\n",
    "\n",
    "> 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."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Decision problem: a simple cycle of size at most $k$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Prove LSC $\\in$ NP__\n",
    "\n",
    "Given the vertices $(v_1, \\dots, v_n)$ as certificate, verify in $O(|V|^2)$:\n",
    "\n",
    "* $v_i \\ne v_j \\forall i, j \\in [1, \\dots, n]$,\n",
    "* $(v_i, v_{i + 1}) \\in E$ $\\forall i \\in [1, \\dots, n - 1]$,\n",
    "* $(v_n, v_1) \\in E$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Prove LSC $\\in$ NPC by proving HAM-CYCLE $\\le_\\text{P}$ LSC__\n",
    "\n",
    "HAM-CYCLE is equivalent to solve LSC with $k = |V|$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 34.5-8\n",
    "\n",
    "> 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."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Prove HALF-3-CNF-SAT $\\in$ NP__\n",
    "\n",
    "Evaluate in $O(n)$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Prove HALF-3-CNF-SAT $\\in$ NPC by proving 3-CNF-SAT $\\le_\\text{P}$ HALF-3-CNF-SAT__"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "_Construction:_\n",
    "\n",
    "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."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "_3-CNT-SAT $\\Rightarrow$ HALF-3-CNF-SAT:_\n",
    "\n",
    "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."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "_HALF-3-CNF-SAT $\\Rightarrow$ 3-CNT-SAT:_\n",
    "\n",
    "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 evalute to 1."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.12"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}