Part 2 Please
Project: Copying with NP-completeness Project Summary: Recall that given a graph G=(V,E), a vertex cover is a set of vertices ?? ⊆ ??, where every edge is incident to at least one vertex in S. In this project, we will be exploring different problems and algorithms associated with these structures. Part 1: Vertex cover – Search and Approximation Learning Objectives: Understand the difference between exact, heuristic, and approximation algorithms; Master two approximation algorithms for the vertex cover problem; Benchmark the algorithms to observe runtime and approximation factors for each. Part 2: Vertex cover – Reduction and Verification Learning Objectives: Understand two critical components for showing that a problem is NP-complete. Part 3: Vertex cover – Kernelization Learning Objectives: Learn about preprocessing techniques to make the vertex-cover problem tractable when fixing the parameter k. Part 1: Vertex Cover – Approximation There is no known polynomial time algorithm for finding a minimum vertex cover in the graph. A naïve algorithm for finding a minimum vertex cover is shown below: Algorithm 1 – Minimum Vertex Cover INPUT: A graph G=(V,E) OUTPUT: A minimum vertex cover in G. 1. For k from 1 to n-1 1. For each ?? ⊆ ?? of size k 1. Check if S is a vertex cover; If so, return S The above algorithm requires powerset generation and hence has an exponential time and space complexity. Even for small graphs, this algorithm will become intractable. At the cost of exactness, a heuristic or approximation algorithm can be used to find a small vertex cover that may or may not be the minimum. Although, these techniques may not find the true answer, they are generally much faster. Moreover, approximation algorithms will have some guarantees on how far away they may be from the true answer. Two approximation algorithms are described below. Algorithm 2 – Approximation Greedy Vertex INPUT: A graph G=(V,E) OUTPUT: A vertex cover in G that is at most twice the size of a minimum VC. 1. ?? = ∅ 2. While |E| > 0 1. Select the highest degree vertex v in G 2. ?? = ?? ∪ {??} 3. Remove v and all adjacent edges from G 3. Return C Algorithm 3 – Approximation Greedy Edge INPUT: A graph G=(V,E) OUTPUT: A vertex cover in G that is at most twice the size of a minimum VC. 1. ?? = ∅ 2. While |E| > 0 1. Select an edge {u,v} in E 2. ?? = ?? ∪ {??,??} 3. Remove any edges incident to u or v in E 3. Return C These algorithms have polynomial time complexity as opposed to exponential. This improved time complexity comes at the cost of an inexact solution. Algorithm 2 can produce a vertex cover whose size is off by a factor of Ө(log(n)), where n is the number of vertices in the graph. Algorithm 3 is said to be a 2-factor approximation because it will never be off from the minimum solution by more than a factor of 2. In fact, this is the best-known approximation algorithm for finding the minimum vertex cover. For this part of the project you are to do the following tasks: I. Implement Algorithms 2 and 3 in Python. The code must take two arguments as input: 1. An edge-list text file defining a graph. Each edge is listed on a line and the two vertices in the edge are separated by a space. Vertices are integers and they are not necessarily consecutive. Note: no singleton vertices can be represented in this format. 2. A string ‘greedy-vertex’ or ‘greedy-edge’ that specifies whether to run the greedy vertex or greedy edge algorithm. II. The code must then run the algorithm and output: 1. A text file call approxOutput.txt, where each line contains a vertex in the vertex cover. 2. Generate a plot of the runtime on graphs of different sizes. Compare both algorithms on a single plot. 3. Generate a plot of the vertex cover sizes for various graphs. Compare how similar the sizes were between both approximation algorithms (plot on the same graph using different colors). The plots for the second and third parts do not have to be done programmatically; that is, the plots can be generated by plugging numbers into a charting program manually, for example. What to Submit: A single zip file containing your (1) your python code (.py files only) with the runnable code in a file called VertexCoverApproximation.py and (2) the plots. Make this a flat directory, namely, all files in a single directory and no subdirectories. NOTE: We will run the command: python VertexCoverApproximation.py [graph-file] [greedy-vertex|greedy-edge] and look for the file “approxOutput.txt,” hence it is critical your code follows the conventions listed above. No external graph packages should be used. Part 2: Vertex Cover – Reduction and Verification For this part of the project, you will solve the vertex cover problem via a reduction to the clique problem. That is, you will be tasked with finding a vertex cover of size k using a subroutine that finds a clique of size k'. Illustration 1: Example input file and the graph it defines. Algorithm 3 – Reduction INPUT: A graph G=(V,E) and an integer k OUTPUT: “yes” if G contains a vertex cover of size k, no otherwise 1. Let G' be the complement of G. 2. k' = |V| - k 3. Return CLIQUE(G', k') A polynomial time reduction like this shows that the clique problem is at least as hard as the vertex cover problem. For example, if we knew that vertex cover is in the NP-complete class of problems, then we know that the clique problem is NP-hard. If we didn't know the complexity class of the vertex cover problem and we wanted to show that vertex cover is in the class NP, then we need to show that a solution to the vertex cover problem can be verified in polynomial time. That is, given a set of vertices, determine in polynomial time whether that set of vertices is a vertex cover. For the clique subroutine, you will utilize an external Python package called networkx. This is a pure Python implementation of various graph analysis tasks. The easiest way to install is through pip or anaconda package manager. Or, since it is a pure python implementation, simply download the entire module and place it in the folder you will code; this should allow you to import the module. You will only be using this module to call the find_cliques function. To use this function, you must create a networkx graph object, so you must first create your graph outside of networkx, build the complement graph, then create a networkx graph object of this complement graph. Note: you cannot use the networkx complement function for this step, you must code your own method. The find_cliques function finds all maximal cliques, it does not give you a yes/no decision answer, so you will need to handle that part based on the results you get from find_cliques. For this part of the project you are to do the following tasks: I. Implement the above reduction from VC to clique in Python. Your code should just print a simple “yes” or “no” to the console to indicate if there exists a vertex cover of size k. II. Implement an algorithm that will verify in polynomial time whether a set of vertices is a vertex cover. The code must take three arguments as input: 1. A graph which is given as an edge-list text file (see Part 1). 2. A text file with a candidate solution listed on each line (each vertex in the candidate solution should be separated by a space). 3. Integer value k. III. The code must then output: https://networkx.github.io/ https://networkx.github.io/documentation/networkx-1.9.1/reference/generated/networkx.algorithms.clique.find_cliques.html#networkx.algorithms.clique.find_cliques 1. “yes” or “no” printed to console (separated by newlines) for each candidate solution in the input text file. A “yes” indicates the candidate solution is a vertex cover of size k. 2. A “complement.graph” text file edge list of the complement graph. What to Submit: A single zip file containing your Python code (.py files only) with a main function (i.e., runnable code) listed in the “VertexCoverReduction.py” and “VertexCoverVerification.py” files. Make this a flat directory, that is, all files and jar in a single directory and no subdirectories. NOTE: We will run the commands: python VertexCoverReduction.py [graph-file] [k] and python VertexCoverVerification.py [graph-file] [candidate-solution-file] [k] Hence, it is critical your code follows the conventions listed above. Part 3: Kernelization The idea behind kernelization is to improve the efficiency of an algorithm by performing a preprocessing step that transforms the input, in this case a graph G and parameter k, into a smaller input. In this part of the project, we will be examining one kernelization technique – crown reduction – for the problem of finding a vertex cover of at most size k. For more details, the original work behind the methods we will discuss can be found here. Crown Reduction This kernelization technique finds two sets of vertices (H,I) such that 1. H = N(I), where N(I) is a set of vertices containing neighbors for every vertex in I. 2. I is a nonempty independent set. 3. The edges connecting H and I contain a matching where all elements of H are matched.