MHB Maximizing Independent Set in Graphs: Proving NP-Completeness

[evinda]

Hello! (Wave)

An independent set of a graph $G=(V,E)$ is a subset $V' \subseteq V$ of vertices such that each edge in $E$ is incident on at most one vertex in $V'$. The independent-set problem is to find a maximum-size independent set in $G$.

• Formulate a related decision problem for the independent-set problem, and prove that it is NP-complete. (Hint: Reduce from the Clique problem)

I have tried the following:

A non-deterministic Turing machine first "guesses" the set and then it verifies that this set contains the maximum number of vertices such that each edge of the graph is incident on at most one vertex in the set in $O(V+E)$ time.

Thus, the independent-set problem is in NP.

Let $(G_1,k)$ be an arbitrary instance of the clique problem, where $k$ is the number of the vertices of the clique.
We can construct an instance of the independent-set problem as follows:

Let $G=G_1$.
The graph $G_1$ has a clique iff there is an independent set of size $k$.
So we have that $G_1$ has a clique iff $G$ has a maximum-size independent set.

So the instance of the independent-set problem has a solution iff the initial instance of the clique problem has a solution.
Thus, the independent- set problem is NP-complete.
But, this proposition:

[m]So we have that $G_1$ has a clique iff $G$ has a maximum-size independent set. [/m]

would hold if we would require that each edge in $E$ is incident on at least one vertex in $V'$, right?

What could we say in our case?

 

[Evgeny.Makarov]

• Formulate a related decision problem for the independent-set problem, and prove that it is NP-complete. (Hint: Reduce from the Clique problem)

I have tried the following:

A non-deterministic Turing machine first "guesses" the set and then it verifies that this set contains the maximum number of vertices such that each edge of the graph is incident on at most one vertex in the set in $O(V+E)$ time.

You have not formulated a related decision problem for the independent-set problem, so it makes no sense to discuss an algorithm for solving it.

The graph $G_1$ has a clique iff there is an independent set of size $k$.

"There is an independent set of size $k$" in which graph?

So we have that $G_1$ has a clique iff $G$ has a maximum-size independent set.

Every graph has a clique, and every graph has a maximum-size independent set.

 

[evinda]

You have not formulated a related decision problem for the independent-set problem, so it makes no sense to discuss an algorithm for solving it.

I can't think of which related decision problem we could take.

At the clique problem we want to find complete subgraphs in a graph, where each pair of elements is connected.
But at the independet-set problem we want to find the maximum set of vertices where there is at most one vertex of all the edges of the graph.

How could we relate these two problems? Could you give me a hint?

 

[Evgeny.Makarov]

For converting maximization problems into decision problems see any textbook, such as Lewis and Papadimitriou. For a hint about the connection between clique and independent set, see Wikipedia.

 

[evinda]

For converting maximization problems into decision problems see any textbook, such as Lewis and Papadimitriou. For a hint about the connection between clique and independent set, see Wikipedia.

So could the decision problem be the following?

Suppose that we have a graph $G=(V,E)$.
Determine if $G$ has an independent set of size $s$.

 

[Evgeny.Makarov]

Yes. Lewis et al. define it as follows: "Determine if $G$ has an independent set of size $\ge s$".

 

[evinda]

Yes. Lewis et al. define it as follows: "Determine if $G$ has an independent set of size $\ge s$".

A ok... And then could we show that the problem is in NP as follows?

A non-deterministic Turing machine first "guesses" the set and then it verifies in time $O(E)$ that this set is independent and that its size is at least $k$.

 

[Evgeny.Makarov]

Yes.

 

[evinda]

Could we show as follows that the independent-set problem is NP-complete?

Let $(G_1,k)$ be an arbitrary instance of the clique problem, where $k$ is the number of vertices of the clique.
We can construct an instance for the independent-set problem in polynomial time as follows:
Let $G$ be the complement of the graph $G_1$.
$G_1$ has a clique of size $k$ iff its complement has an independent set of size $k$.
So we have that $G_1$ has a clique iff $G$ has an independent set.
Thus, the instance of the independent-set problem has a solution iff the initial instance of the clique problem has a solution.
Since the clique problem is NP-complete and can be reduced to the independent-set problem, we can deduce that the latter is also NP-complete.

 

[Evgeny.Makarov]

I agree overall but have a couple of remarks.

Let $(G_1,k)$ be an arbitrary instance of the clique problem, where $k$ is the number of vertices of the clique.
We can construct an instance for the independent-set problem in polynomial time as follows:
Let $G$ be the complement of the graph $G_1$.
$G_1$ has a clique of size $k$ iff its complement has an independent set of size $k$.
So we have that $G_1$ has a clique iff $G$ has an independent set.

You did not describe exactly the instance of the Independent Set problem that you construct from $(G_1,k)$. Namely, you need to specify that the size goal for the independent set is the same $k$, i.e., the output of the reduction is $(G,k)$. Also, the last sentence in the quote above does not add anything to the second last sentence. In fact, the last sentence is trivially true because every graph has both a clique and an independent set, in the worst case of size 1.