Consider the BubbleSort Algorithm described as follows. Given an input \(x_1,\dots,x_n\) consisting of \(n\) real numbers, while there exists two consecutive elements of the list in which the first element is greater than the second, swap the two elements. When no such elements exist, then the algorithm outputs the final list. For example, with an input of \(1,4,2,3,6,5\text{,}\) the lists produced at each step of the algorithm would be as follows:
Step 0: \(1,4,2,3,6,5\)
Step 1: \(1,2,4,3,6,5\)
Step 2: \(1,2,3,4,6,5\)
Step 3: \(1,2,3,4,5,6\text{.}\)
What is the maximum possible running time of this algorithm in Big O notation? Your answer should be of the form \(\Theta(f(n))\) for some function \(f(n)\text{.}\) Note that you must prove a lower bound as well as an upper bound on the maximum running time.
Describe an algorithm for the 3-Colourability Problem with a running time of \(O(n^23^n)\) on any graph \(G\) with \(n\) vertices. Explain why it has this running time.
Consider the 2-Colourability Problem in which one is asked to decide whether, for a given input graph \(G\text{,}\) there exists a function \(f:V(G)\to\{1,2\}\) such that \(f(u)\neq f(v)\) for all \(uv\in E(G)\text{.}\) Prove that the 2-Colourability Problem is in P.
Suppose that \(D\) is a digraph, \(\ell:A(D)\to[0,\infty)\) is a length function, \(s,t\in V(D)\) and that \(P\) is the unique minimum length path from \(s\) to \(t\text{.}\) Explain how you can find the length of the second shortest path from \(s\) to \(t\) in polynomial time.
Imagine that you are a delivery truck driver. Your truck is very wide and so driving on narrow streets makes you nervous. For this reason, you always prefer to follow routes which maximize the minimum width of any street on the route. We abstract this to an optimization problem as follows. Let \(D\) be a digraph and \(w:A(D)\to\mathbb{R}\) be a function \(w(uv)\) denotes the width of the arc \(uv\text{.}\) Describe a polynomial-time algorithm for finding a path from a vertex \(s\) to a vertex \(t\) such that the minimum width of an arc in this path is maximized. Prove that it is correct and that it runs in polynomial time. Hint: Modify the Dijkstra Algorithm.
Suppose that every edge \(e\) of a graph is assigned to a value \(0\leq r(e)\leq 1\) representing the reliability of that edge. For example, in a transportation network, the edge \(e\) could represent a road and \(r(e)\) could be the probability that the given road is currently open. Define the reliability of a path to be equal to the product of the reliabilities of its edge. Show that the problem of finding the path of maximum reliability between nodes \(s\) and \(t\) can be reduced to the Shortest Path Problem. Hint: Logarithms are your friend.
Two graphs \(G_1\) and \(G_2\) are isomorphic if and only if there exists a bijection \(\varphi:V(G_1)\to V(G_2)\) such that \(\varphi(u)\varphi(v)\) is an edge of \(G_2\) if and only if \(uv\) is an edge of \(G_1\) (such a function is called an isomorphism). Consider the following problem.
Problem1.7.1.Graph Isomorphism.
Input: Two graphs \(G_1\) and \(G_2\text{.}\)
Question: Are \(G_1\) and \(G_2\) isomorphic?
Explain why the Graph Isomorphism Problem is in NP.
For an integer \(k\geq1\text{,}\) the \(k\)-Colourability Problem is defined in the same way as the 3-Colourability Problem except that the function \(f\) has co-domain \(\{1,\dots,k\}\text{.}\) Prove that the \(k\)-Colourability Problem can be reduced to the \((k+1)\)-Colourability Problem in polynomial time for all \(k\geq1\text{.}\)
Is it true that any two problems in P are polynomial-time equivalent? What about any two NP-complete problems? What about any two problems in NP? Justify your answers.
Consider the following problem.
Problem1.7.2.Antichain.
Input: A finite poset \((P,\succeq)\) and an integer \(k\geq1\text{.}\)
Question: Does \((P,\succeq)\) contain an antichain of cardinality \(k\text{?}\)
Prove that the Antichain Problem is in \(\text{NP}\cap\text{co-NP}\text{.}\) You may assume that there is a polynomial-time algorithm to determine, for \(x,y\in P\text{,}\) whether or not \(x\succeq y\text{.}\)Hint: Use one of the theorems stated near the end of Section 1.1.
A stable set (sometimes called an independent set) in a graph \(G\) is a subset \(S\subseteq V(G)\) with the property that \(uv\notin E(G)\) for all \(u,v\in S\text{.}\) A clique is a set \(C\subseteq V(G)\) with the property that \(uv\in E(G)\) for all distinct pairs \(u,v\in C\text{.}\) Consider the following two problems.
Problem1.7.3.Stable Set.
Input: A graph \(G\) and an integer \(k\geq1\text{.}\)
Question: Does \(G\) contain a stable set of cardinality \(k\text{?}\)
Problem1.7.4.Clique.
Input: A graph \(G\) and an integer \(k\geq1\text{.}\)
Question: Does \(G\) contain a clique of cardinality \(k\text{?}\)
Prove that Stable Set and Clique are polynomial-time equivalent.
Prove that 3-Colourability (from Problem 1.4.3) reduces to Stable Set. Hint: Given an instance \(G\) of 3-Colourability with \(n\) vertices and \(m\) edges, your reduction should involve constructing an instance of Stable Set in which the graph has \(3n\) vertices and \(3n+3m\) edges.
Prove that 3-SAT reduces to the Stable Set Problem (Problem 1.7.3). Hint: Let \(C_1\land C_2\land \cdots C_k\) be any CNF with \(k\) clauses, each consisting of at most three literals (although the number of literals will not be important). In polynomial time, construct a graph \(G\) such that \(G\) contains a stable set of cardinality \(k\) if and only if the formula is satisfiable.
Explain why the Stable Set Problem is NP-complete. (Don’t forget to prove that it is in NP).
Say that a graph \(G\) is \(k\)-connected if, for every \(S\subseteq V(G)\) such that \(|S|\leq k\text{,}\) the graph \(G\setminus S\) obtained by deleting all vertices of \(S\) and all edges incident to such vertices is connected. Consider the following problem.
Problem1.7.5.Connectivity.
Input: A graph \(G\) and an integer \(k\geq1\text{.}\)
Question: Is it true that \(G\) is \(k\)-connected?
Prove that the Connectivity Problem is in \(\text{NP}\cap\text{co-NP}\text{.}\)Hint: Use one of the theorems stated in Section 1.1.
Describe an explicit polynomial time reduction from the Hamiltonian Cycle Problem (Problem 1.4.5) to SAT (Problem 1.5.5).
Describe an explicit polynomial time reduction from the Hamiltonian Cycle Problem (Problem 1.4.5) to the Hamiltonian Path Problem (i.e. the problem asking whether there is a path in a graph \(G\) that includes all vertices of the graph). Using the fact that the Hamiltonian Cycle Problem is NP-complete, conclude that the Hamiltonian Path Problem is NP-complete as well (don’t forget to show that it is in NP).
Prove that the Shortest Path Problem on graphs is NP-hard if we do not have any restrictions on the length function (e.g. if we allow all edges to be negative). Note that the Shortest Path Problem is not NP-complete because it is not a decision problem and therefore is not in NP.
An instance of the HORNSAT Problem is a CNF formula with the property that, in every clause, all but at most one literal is a negated variable, and the goal is to determine whether it has a satisfying assignment. Provide an algorithm for solving HORNSAT in polynomial time. (Don’t forget to analyze the running time of your algorithm).
Prove that 2-SAT is in P. (Don’t forget to analyze the running time of your algorithm).
Find an infinite family of examples of CNF formulas with the property that every equivalent DNF formula in the same variables has exponential size with respect to the original formula. Two formulas are equivalent if they evaluate to the same output for every possible choice of input variables.
Find an infinite family of examples of DNF formulas with the property that every equivalent CNF formula in the same variables has exponential size with respect to the original formula.
