Chapter 9 - Intractable Problems and Approximation Algorithms.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Chapter 9: Intractable Problems and Approximation Algorithms (Completed 7/30: 23%)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Transformations and Satisfiability"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 9.1 [2]\n",
    "\n",
    "Give the 3-SAT formula that results from applying the reduction of SAT to 3-SAT for the formula:\n",
    "\n",
    "$$ (x + y + \\bar{z} + w + u + \\bar{v}) \\cdot (\\bar{x} + \\bar{y} + z + \\bar{w} + u + v) \\cdot (x + \\bar{y} + \\bar{z} + w + u + \\bar{v}) \\cdot (x + \\bar{y})$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Solution:*\n",
    "\n",
    "We have 4 clauses:\n",
    "\n",
    "$C_1 = (x + y + \\bar{z} + w + u + \\bar{v})$  \n",
    "$C_2 = (\\bar{x} + \\bar{y} + z + \\bar{w} + u + v)$  \n",
    "$C_3 = (x + \\bar{y} + \\bar{z} + w + u + \\bar{v})$  \n",
    "$C_4 = (x + \\bar{y})$\n",
    "\n",
    "We wish to transform each clause into a set of 3-clauses such that sets of truth assignments that satisty the original clause also satisfy the engendered set of 3-clauses, and vice versa. We will follow the transformation procedure given in the text.\n",
    "\n",
    "$C_1 = (x + y + \\bar{z} + w + u + \\bar{v})$ transforms to\n",
    "\n",
    "$C_1^{1} = (x + y + a_1)$  \n",
    "$C_1^{2} = (\\bar{a_1} + \\bar{z} + a_2)$  \n",
    "$C_1^{3} = (\\bar{a_2} + w + a_3)$  \n",
    "$C_1^{4} = (\\bar{a_3} + u + \\bar{v})$\n",
    "\n",
    "$C_2 = (\\bar{x} + \\bar{y} + z + \\bar{w} + u + v)$ transforms to\n",
    "\n",
    "$C_2^{1} = (\\bar{x} + \\bar{y} + a_4)$  \n",
    "$C_2^{2} = (\\bar{a_4} + z + a_5)$  \n",
    "$C_2^{3} = (\\bar{a_5} + \\bar{w} + a_6)$  \n",
    "$C_2^{4} = (\\bar{a_6} + u + v)$\n",
    "\n",
    "$C_3 = (x + \\bar{y} + \\bar{z} + w + u + \\bar{v})$ transforms to\n",
    "\n",
    "$C_3^{1} = (x + \\bar{y} + a_7)$  \n",
    "$C_3^{2} = (\\bar{a_7} + \\bar{z} + a_8)$  \n",
    "$C_3^{3} = (\\bar{a_8} + w + a_9)$  \n",
    "$C_3^{4} = (\\bar{a_9} + u + \\bar{v})$\n",
    "\n",
    "and $C_1 = (x + y + \\bar{z} + w + u + \\bar{v})$ transforms to\n",
    "\n",
    "$C_4^{1} = (x + \\bar{y} + a_{10})$  \n",
    "$C_4^{2} = (x + \\bar{y} + \\bar{a_{10})}$\n",
    "\n",
    "\n",
    "$C_1$, which contains 6 variables, is transformed into $6-2 = 4$ clauses (every variable except the first and the last gets its own clause) with the addition of $6-3 = 3$ new variables. Since the number of clauses exceeds the number of new variables by 1, the new variables by themselves are not able to ensure that all the clauses are True; at least one of the original literals must also be True, meaning that the original clause must be True. The same reasoning also shows that the satisfiability of clauses 2 and 3 are equivalent to their engendered set of clauses. Similarly, regarding the two clauses engendered by clause 4, the new variable $a_{10}$ cannot make both clauses True. Rather, both can be True only if one of the original two literals is True, which is equivalent to the original clause being True. Therefore the satisfiability of clause 4 is equivalent to the satisfiability of its two engendered clauses.\n",
    "\n",
    "Putting everything together, the equivalent 3-SAT formula is:\n",
    "\n",
    "$$\n",
    "(x + y + a_1)\n",
    "\\cdot (\\bar{a_1} + \\bar{z} + a_2)\n",
    "\\cdot (\\bar{a_2} + w + a_3)\n",
    "\\cdot (\\bar{a_3} + u + \\bar{v})$$\n",
    "$$\\cdot (\\bar{x} + \\bar{y} + a_4)\n",
    "\\cdot (\\bar{a_4} + z + a_5)\n",
    "\\cdot (\\bar{a_5} + \\bar{w} + a_6)\n",
    "\\cdot (\\bar{a_6} + u + v)$$\n",
    "$$\\cdot (x + \\bar{y} + a_7)\n",
    "\\cdot (\\bar{a_7} + \\bar{z} + a_8)\n",
    "\\cdot (\\bar{a_8} + w + a_9)\n",
    "\\cdot (\\bar{a_9} + u + \\bar{v})$$\n",
    "$$\\cdot (x + \\bar{y} + a_{10})\n",
    "\\cdot (x + \\bar{y} + \\bar{a_{10})}\n",
    "$$\n",
    "\n",
    "Note that for every new literal, the equivalent NOT literal appears in the very next clause. It is this sort of chaining that ensures that the new variables don't alter the satisfiability of the original clauses and literals.\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 9.3 [4]\n",
    "\n",
    "Suppose we are given a subroutine which can solve the traveling salesman decision problem of page 318 in, say, linear time. Give an efficient algorithm to find the actual TSP tour by making a polynomial number of calls to this subroutine."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Solution:*\n",
    "\n",
    "The Traveling Salesman Problem as given on page 319 is:\n",
    "\n",
    "*Problem:* The Traveling Salesman Decision Problem  \n",
    "*Input:* A weighted graph $G$ and integer $k$.  \n",
    "*Output:* Does there exist a TSP tour with cost $\\leq k$?\n",
    "\n",
    "Suppose that we have a subroutine that can solve the decision problem version of TSP in $O(m)$ running time. We could use this to find the smallest tour. First we call the subroutine for increasing $k$ until we find the smallest such $k$ such that there exists a tour. This will be $O(mW)$, where $W$ is the total weight of the graph. Then we iterate over the edges in the graph, and for each edge, we delete the edge and recall the subroutine; if there still exists a tour of size $k$, we keep the edge deleted, otherwise we restore it. Only edges that are a part of every tour that is possible with the remaining edges, and therefore are \"necessary\", will remain. But if all remaining edges are part of every remaining possible tour, then there is only one such tour, composed of exactly the remaining edges. Therefore this algorithm finds a tour of weight $k$, where $k$ is optimal. The second part of the algorithm runs in $O(m|E|)$ time, for a total running time of $O(m(W + |E|))$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Basic Reductions"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 9.7 [4]\n",
    "\n",
    "An instance of the *set cover* problem consists of a set $X$ of $n$ elements, a family $F$ of subsets of $X$, and an integer $k$. The question is, does there exist $k$ subsets from $F$ whose union is $X$?\n",
    "\n",
    "For example, if $X = \\{1, 2, 3, 4\\}$ and $F = \\{\\{1, 2\\}, \\{2, 3\\}, \\{4\\}, \\{2, 4\\}\\}$, there does not exist a solution for $k = 2$, but there does for $k = 3$ (for example, $\\{1, 2\\}, \\{2, 3\\}, \\{4\\}$).\n",
    "\n",
    "Prove that set cover is NP-complete with a reduction from vertex cover."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Solution:*\n",
    "\n",
    "We wish to map instances of the Vertex Cover problem (VCP) to equivalent instances of the Set Cover problem (SCP).\n",
    "\n",
    "In VCP, we seek to select a set of vertices such that every edge is covered. In SCP we seek to select a set of sets such that every element in the universal set is covered. This suggests we map each edge $E$ in our graph $G$ to a unique number from $1$ to $|E| = n$, and map each vertex $V$ in $G$ to a set that contains the numbers corresponding to its adjacent edges. If a collection of sets is found whose union is every number from $1$ to $n$, this can be translated back to a set of vertices that are adjacent to every edge.\n",
    "\n",
    "This translation from instances of VCP to SCP can be made in polynomial time, requiring every edge and vertex in the graph to be visited once.\n",
    "\n",
    "With this correspondence in place, if a polynomial-time algorithm was to be found to solve the Set Cover problem, it could also be used to solve the Vertex Cover problem. But the Vertex Cover problem is known to be NP-complete, meaning that no deterministic polynomial-time algorithm is known to solve it; nor is one likely to exist. Therefore none can exist for the Set Cover problem either, otherwise the NP-completeness of VCP would be violated.\n",
    "\n",
    "Therefore the *Set Cover* problem must be at least as hard as the *Vertex Cover* problem, and is therefore NP-complete."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 9.8 [4]\n",
    "\n",
    "The *baseball card collector problem* is as follows. Given packets $P_1, . . . , P_m$, each of which contains a subset of this year’s baseball cards, is it possible to collect all the year’s cards by buying $\\leq k$ packets?\n",
    "\n",
    "For example, if the players are $\\{Aaron,Mays,Ruth, Skiena\\}$ and the packets are\n",
    "\n",
    "$$ \\{\\{Aaron,Mays\\}, \\{Mays,Ruth\\}, \\{Skiena\\}, \\{Mays, Skiena\\}\\}, $$\n",
    "\n",
    "there does not exist a solution for $k = 2$, but there does for $k = 3$, such as\n",
    "\n",
    "$$ \\{Aaron,Mays\\}, \\{Mays,Ruth\\}, \\{Skiena\\} $$\n",
    "\n",
    "Prove that the baseball card collector problem is NP-hard using a reduction from vertex cover."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Solution:*\n",
    "\n",
    "We wish to map instances of the Vertex Cover problem (VCP) to instances of the Baseball Card Collector problem (BCCP).\n",
    "\n",
    "In VCP we seek to select a subset of vertices, while in BCCP we seek to select a subset of packets. This suggests we map vertices in the VCP graph to packets, and the edges adjacent to each vertex to the contents of its corresponding packet. Specifically, label every edge with a unique number from $1$ to $|E| = n$. Packets will contain the numbers of the edges adjacent to the corresponding vertex. The union of the packets is the total set of this year's baseball cards, in this case the total set of edges.\n",
    "\n",
    "An output of BCCP will select a subset of packets (vertices) such that every baseball card (edge in $E$) is contained in their union. This is identical to the definition of every edge being \"covered\" by a subset of vertices. Therefore outputs of BCCP are correct outputs for VCP.\n",
    "\n",
    "With this correspondence between the two problems in place, we can use algorithms for solving BCCP for solving VCP. Since VCP is known to be NP-complete, BCCP must be NP-complete as well. Specifically, if a deterministic polynomial time algorithm was found to solve BCCP, it could be used to solve VCP, thereby violating the purported \"hardness\" of VCP.\n",
    "\n",
    "Another way of thinking about this is that this correspondence between VCP and BCCP shows that BCCP must be \"at least as hard as VCP\". This is because the space of possible inputs to VCP is included in the space of inputs to BCCP; but the space of inputs to BCCP may be larger, meaning there may be inputs to BCCP that do not correspond to VCP inputs. Since BCCP is \"at least as hard as VCP\", and VCP is known to be NP-complete, BCCP must be NP-complete as well. The definition of NP-complete includes being NP-hard. Therefore BCCP is NP-hard and NP-complete."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Creative Reductions"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 9-13 [5]\n",
    "\n",
    "Prove that the following problem is NP-complete:\n",
    "\n",
    "*Problem:* Hitting Set  \n",
    "*Input:* A collection $C$ of subsets of a set $S$, positive integer $k$.  \n",
    "*Output:* Does $S$ contain a subset $S'$ such that $|S'| \\leq k$ and each subset in $C$ contains at least one element from $S'$?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Solution:*\n",
    "\n",
    "This is a selection problem, and therefore we will try to use a reduction from the Vertex Cover problem (VCP), the archetype of \"Selection\".\n",
    "\n",
    "VCP is NP-complete. Therefore if we can map instances of VCP to instances of the Hitting Set problem (HSP), then HSP must be at least as hard as VCP, otherwise an algorithm for HCP could be used to violate the hardness of VCP.\n",
    "\n",
    "Note that a graph is already in the form of an input to HCP. Specifically, the set of vertices $V$ is the set $S$, and the collection of edges $E$ is the collection $C$ of subsets of $S$, where each edge is a subset of size 2 containing the two vertices it connects.\n",
    "\n",
    "The output from HCP is whether there is a subset (of vertices) of size less than or equal to $k$ such that each subset (edge) in $C$ ($E$) contains at least one element from this subset. The condition that every edge contain an element from $S'$ ($V'$) is the definition of what it means for every edge to be \"covered\". Therefore a solution to HSP is a solution to the equivalent VCP problem.\n",
    "\n",
    "Interestingly, note that the size of the input space to HSP is larger than that of VCP, since every input of VCP has an equivalent HSP input, but most HSP inputs can't be mapped to VCP inputs. Specifically, subsets of $S$ that have more than 2 elements can't be interpreted as edges of a graph. So even if we were to restrict the types of inputs of HSP to allow only subsets of size 2, the problem would still be NP-complete. This reduction elucidates what makes HSP difficult, mainly that it is a problem of selection."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Algorithms for Special Cases"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## P=NP?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 9.23 [4]\n",
    "\n",
    "Show that the following problems are in NP:\n",
    "- Does graph $G$ have a simple path (i.e. , with no vertex repeated) of length $k$?\n",
    "- Is integer $n$ composite (i.e. , not prime)?\n",
    "- Does graph $G$ have a vertex cover of size $k$?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Solution:*\n",
    "\n",
    "A problem is in NP if a potential solution can be verified in polynomial time.\n",
    "\n",
    "**- Does graph $G$ have a simple path (i.e. , with no vertex repeated) of length $k$?**\n",
    "\n",
    "If given a potential path $P$, we could traverse the path, keeping track of which vertices we have visited and maintain a counter of how many we have visited. If we never revisit a vertex and if the counter equal $k$ at the end of the path, then the solution is valid. This traversal will take linear time, which is polynomia time. Therefore this problem is in NP.\n",
    "\n",
    "**- Is integer $n$ composite (i.e. , not prime)?**\n",
    "\n",
    "If given a number $n$ that is supposedly not prime, can we verify this in polynomial time? Yes. We can try dividing $n$ by all numbers from $2$ to $\\sqrt{n}$. If any of them evenly divides $n$, i.e. produces integers, then $n$ is not prime. This is $O(\\sqrt{n})$. Therefore this problem is in NP.\n",
    "\n",
    "**- Does graph $G$ have a vertex cover of size $k$?**\n",
    "\n",
    "If given a graph $G$ and a subset of vertices $V'$, can we verify that $V'$ is a cover of size $k$ in polynomial time? Yes. We can iterate over the vertices in $V'$ and for each vertex, delete its adjacent edges from $E$ and increment a counter. After the iteration is complete, we check that the counter equals $k$ and that there are no edges remaining in $E$. This involved a loop of size $\\leq |V|$ over the cover vertices, and for each vertex a loop of size $\\leq |E|$ over the adjacent edges. Therefore this verification algorithm is $O(|V| \\times |E|)$ and so the problem is in NP."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Approximation Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "### 9.25 [4]\n",
    "\n",
    "In the *maximum-satisfiability* problem, we seek a truth assignment that satisfies as many clauses as possible. Give an heuristic that always satisfies at least half as many clauses as the optimal solution."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Solution*:\n",
    "\n",
    "First some terminology. Say we have a clause $C = (v_1, \\bar{v_2})$. This clause contains the *literals* $v_1$ and $\\bar{v_2}$, which are determined by the state of the *variables* $v_1$ and $v_2$.\n",
    "\n",
    "An idea for a simple heuristic is to iterate over either the claues or the variables, making greedy truth assignments while keeping track of the consequences of your decisions.\n",
    "\n",
    "Here is such a simple heuristic.\n",
    "\n",
    "$\\hspace{2em}$For every variable $v$:  \n",
    "$\\hspace{4em}$Assign $v$ the truth value that makes the greater number of undeleted clauses True  \n",
    "$\\hspace{4em}$Delete the clauses that contained literals of variable $v$\n",
    "\n",
    "In the heuristic, for each variable $v$, a subset of the remaining clauses is considered, at least half of them are made to be True, and then they all are deleted. Since every clause contains variables, every clause is deleted in this process. Therefore the total collection of clauses is broken down into this disjoint chain of subsets of clauses, and in each subset, at least half of the clauses are made to be True. Therefore more than half of all the clauses will be True. Since the optimal solution can make at most all of the clauses True, this heuristic satisfies at least half as many clauses as the optimal solution.\n",
    "\n",
    "As a very simple example, look at the set of clauses:\n",
    "\n",
    "$$ (v_1 + v_2)\\cdot(v_1 + \\bar{v_2})\\cdot(\\bar{v_1} + v_2)\\cdot(\\bar{v_1} + \\bar{v_2})$$\n",
    "\n",
    "The algorithm will start with $v_1$ and see that 2 clauses contain $v_1$ and 2 clauses contain $\\bar{v_1}$. Assigning $v_1$ as either True of False will make 2 clauses True and 2 False. So let's say that the algorithm assigns $v_1 = $ True and deletes all the clauses that contained a literal of the variable $v_1$. In this case, all the clauses did, so there are no more clauses and $v_2$ can be set to anything. Half the clauses were directly satisfied by the algorithm, and the random assignment of $v_2$ will satisfy another clause.\n",
    "\n",
    "As another example:\n",
    "\n",
    "$$ (v_1 + \\bar{v_2})\\cdot(v_2)\\cdot(v_2)\\cdot(\\bar{v_2})$$\n",
    "\n",
    "$v_1$ only appears in one clause, and so the algorithm will set $v_1 = $ True and delete that clause. In the remaining 3 clauses, $v_2$ appears twice and $\\bar{v_2}$ appears once. Therefore the algorithm will set $v_2 =$ True and delete these clauses. In total, 3 out of 4 clauses were satisfied.\n",
    "\n",
    "A possible way to improve the heuristic is to only delete the clauses that are now being made True by the variable assignment, not all the clauses that contain the variable."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.5.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}