2
$\begingroup$

The problem is given an oracle $O(G, k)$ that would say if graph G contains IS of size k devise an algorithm for finding independent set of max cardinality that makes poly number of calls to the oracle. My attempt has been that first finding the maximal possible size and then try to find the set of that size by removing vertices one at a time. I understand for a given node it either has to be in or not in the set, then I noticed that that there are multiple overlaps between chain of removals and I could devise a DP algorithm of sorts. But I'm just really stuck after that and was wondering if any hint could be given.

$\endgroup$
0
$\begingroup$

Let $O(G)$ be an oracle that returns the maximum cardinality of an independent set in $G$; you can implement it given your oracle using binary search.

Pick an arbitrary vertex $v$, and form a graph $G'$ by removing $v$ and all its neighbors. If $O(G') < O(G) - 1$ is false, then $v$ doesn't participate in a maximum cardinality independent set, and we try more vertices until we find a vertex that does. If $O(G') = O(G) - 1$, then we put $v$ aside, and continue in the same way with $G'$.

Taking all vertices put aside, we obtain a maximum cardinality independent set of $G$.

$\endgroup$
  • $\begingroup$ Wow, thank you so much. Is there some sort of methodology for approaching problems like this or is it just intuition? $\endgroup$ – pcon Dec 8 '19 at 21:56
  • $\begingroup$ This is a very standard search-to-decision reduction. After seeing this one, you will be able to come up with many more. $\endgroup$ – Yuval Filmus Dec 8 '19 at 21:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.