From lucia@site.uottawa.ca Wed Nov 13 12:13:28 2002 Date: Wed, 13 Nov 2002 11:58:29 -0500 (EST) From: Lucia Moura To: undisclosed-recipients: ; Cc: Lucia Moura Subject: A2-Q3 hint Dear csi4105 students, A student asked, and I answered below: > > I have a question about assignment 2 question 3. > If I understand, we should find the maximum independent > set(the vetivces themselves and not just the > number of vertices) from the decision problem. Yes. You are right. > I was thinking about using > the black box to know the number of vertices that composes > the maximum independent set. You are right that you can call the black box several times in order to determine the "size" of the independent set. > But I still have to check > which vertices give me this size which is not polynomial.C (M,N)! > You are right that if you know the size of the independent set is K on a graph with N vertices, and you check all (N choose K) combinations of vertex who could give the independent set, this will take O(N^K) iterations which is not poilynomial, since K is part of the input and is on the exponent. > Will you please give me a hint about this problem . > The hint I can give you is that you can modify the graph and interactively ask questions to the black box. For instance: suppose the size of your maximum independent set is 10. Now, suppose you pick a vertex and remove the vertex plus all edges incident to it - building another graph, say G'. What could have happened to the size of the max independent set in G'? ... Two possibilitites: - there is still an independent set of size 10 - the max independent set now has size 9 what can you say about the vertex v you removed in either case? what you should do to G', if anything, at the next interation, before you call the black box again? This is what your algorithm should do. That is all I can say. What is the lesson from this exercise, when a polynomial time black box doesn't exist, as it is probably the case for an NP-complete problem? If decision is done in polytime then search is doable in polytime. In other words: the search problem (finding the specific vertices of the maximal independent set) is no harder than solving the decision problem (knowing whether G has an independent set of size k). This is an instance of how solving a decision problem is equivalent to solving a more complicated optimiation/search problem, in terms of polytime solvability. Have fun solving this puzzle. Lucia