COS 423 Problem Set No. 5 Due: Dean's Date, Tuesday May 15Spring 2007 No collaboration1. (Set sudoku) The set sudoku problem is as follows. Given is an integer k and acollection of sets 1 2S , S ,..., S ,m each of size .k Let S be the union of the sets S .i (Thesesets are allowed to intersect in arbitrary ways.) The problem is to label the elements of Swith integers 1 through k so that each set Si contains each label exactly once. (Instandard sudoku, the set S is a nine by nine grid, the sets are the rows, columns, and thenine aligned three by three subgrids of the grid. In addition, certain cells of the grid areprelabeled, and the problem is to complete the labeling. Furthermore, it is guaranteedthat there is exactly one way to complete the labeling. In our version of the problem, noelement is prelabeled, and there is no guarantee as to whether there is a solution, norwhether there is a unique solution.)(a) Phrase set sudoku as a yes-no question and prove that it is NP-complete.(b) Provide a polynomial-time algorithm (as efficient as you can) to solve set sudoku fork= 2.(c)(extra credit) Can you prove set sudoku NP-complete for some fixed value of ?k If so,how small can you make ?k2. (Zero-weight cycles) Given a directed graph with integer arc weights that can bepositive, negative, or zero, the zero-weight cycle problem is to find a simple cycle (onewith no repeated vertex) whose total arc weight is zero, if there is one. Let U be themaximum of the absolute values of the edge weights.(a) Phrase the zero-weight cycle problem as a yes-no question and prove that it is NP-complete, even if U .n�(b) (extra credit) Suppose U k� for some fixed value of ,k independent of the graphsize. What can you say about the computational complexity of the problem? (Give apolynomial-time algorithm for k as large as possible and/or prove the problem NP-complete for k as small as possible.)3. A Boolean formula in conjunctive normal form (CNF) is said to be unit-negative ifevery clause contains at most one negated variable.(a) Give a polynomial-time algorithm (as fast as you can) to test whether a unit-negativeformula is satisfiable.(b) What can you say about the computational complexity of the problem of testingwhether a unit-negative formula is a tautology (true for all truth assignments)?(c) (extra credit) (Disguised unit-negative formulas) A CNF Boolean formula isdisguised unit-negative if it can be made unit-negative by flipping the sense of some ofits literals. (To flip a literal means replacing all positive occurrences by negativeoccurrences and vice-versa.) What can you say about the computational complexity oftesting whether a formula is disguised unit-negative?4. (bottleneck tour) The bottleneck tour problem on an undirected complete graph withweighted edges is the problem of finding a simple cycle that contains all the vertices andthat minimizes the maximum weight of an edge on the cycle. Assume that the edgeweights satisfy the triangle inequality. Give a polynomial-time algorithm to find a tourthat is bottleneck-minimum to within a factor of