Analysis of Algorithm: NP- Complete Problems

Write a program in C/C++ or Jave for the following: The Independent-Set is to find a maximum-size independent set in G. a) Formulate a related decision problem for the independent-set problem, and prove that it is NP-complete. (Hint: Reduce from the clique problem.) b) Suppose that you are given a "black-box" subroutine to solve the decision problem you defind in part (a). Give an algorithm to find an independent set of maximum size. The running time of your algorithm should be polynominal in |V| and |E|, where queries to the black box are counted as a single step. Although the independent-set decision problem is NP-complete, certain special cases are polynominal-time solvable. c) Give an efficient algorithm to solve the independent-set problem when each vertex in G has degree 2. Analyze the running time, and prove that your algorithm works correctly. d) Give an efficient algorithm to solve the independent-set problem G is bipartite. Analyze the running time, and prove that your algorithm works correctly. 1) No approximation algorithms will be accepted. Only exact solutions required. 2) The program can be done in C or JAVA. 3) The program MUST have comments. 4) There should be a counter that counts how many loops the program goes through. 5) There should be more than five inputs and outputs. Two or three of these inputs should be small enough that a human can find the correct solution by looking at it. Two or three of the inputs should be BIG. A big input should make the machine work at least a half- hour. 6) You may use a random number generator to make your (big) inputs. 7) You may make your program read in input via a file rather than keyboard input. 8) The input should be varied so that the output should be varied. Some input should have no solution or hard to see solutions. 9) Be careful if you use recursion when making combinations or permutations. You might use more stacks than you have. The following must be handed in: a) The program inputs and outputs. b) How the program was implemented? c) What data structures were used? d) What computer was used to implement the algorithm? e) How many loops was the program supposed to makes? f) How many loops did the program, in fact, make? g) How long (time) did the big inputs take? ## Deliverables 1) Complete and fully-functional working program(s) in executable form as well as complete source code of all work done and a word file explaining the work. 2) Deliverables must be in ready-to-run condition, as follows? (depending on the nature? of the deliverables): a)? For web sites or? other server-side deliverables intended to only ever exist in one place in the Buyer's environment--Deliverables must be installed by the Seller in ready-to-run condition in the Buyer's environment. b) For all others including desktop software or software the buyer intends to distribute: A software? installation package that will install the software in ready-to-run condition on the platform(s) specified in this bid request. 3) All deliverables will be considered "work made for hire" under U.S. Copyright law. Buyer will receive exclusive and complete copyrights to all work purchased. (No GPL, GNU, 3rd party components, etc. unless all copyright ramifications are explained AND AGREED TO by the buyer on the site per the coder's Seller Legal Agreement). ## Platform Windows, Microsoft Visual C++ 6.0