0
$\begingroup$

I was hoping someone would be able to help me with this question.

The Maximum Independent Set search problem is, given an undirected graph G, to output an independent set in G of maximum size.

Give a polynomial time algorithm for the Maximum Independent Set search problem which can use an oracle that solves instances of the Independent Set decision problem.

I can't see how you would do this without inputting every possible combination of the vertices into the Independent Set Problem, which obviously won't be polynomial time.

$\endgroup$
1
$\begingroup$

It is certainly possible to do so, as every $\mathcal{NP}-$complete problem is self-reducible.

Let us first remember the definition of decisional maximum independent set: given an undirected graph $G=(V,E)$ and $k \in \mathbb{N}$, does there exist $S \subseteq V$ with $|S| = k$ such that $\forall x, y \in S \ . \ (x, y) \notin E$ ?

By a standard binary search argument, we can find the size of the maximum independent set with a polynomial number of queries to that oracle.

Let $s$ be the size of the maximum independent set of $G$. We pick some $v \in V$ and we use our construction to determine the size of the maximum independent set of $G \setminus v$. That can be either $s$ or $s-1$. If it's $s$, then there exists a maximum independent set in $G$ that does not include $v$, therefore we can exclude $v$ from our search.

Eventually, we'll reach a point where we can't exclude any other node. That means that the remaining nodes form a maximum independent set.

$\endgroup$

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.