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