1
$\begingroup$

I need some guidance in an assignment I'm doing.

I'm at complete loss, he says the the MAXIMUM INDEPENDENT SET problem is NP-hard and then asks me to prove that there is no polynomial time for the same algorithm and it also guarantees that some inequality holds, which I also don't understand, since $A(G)$ returns the size of a maximal independent set in $G$ and $OBT(G)$ returns the size of an independent set of maximal size for $G$ but isn't the case that a graph could have multiple maximal independent sets? Let's assume that it returns the largest one which reduces the epression to $0 \le K$ which should always holds since $K$ is a natural number?

As for the hint given, I don't see how we can use $H$ if I understand it correctly, it says split $G$ into disjoint sets. Also it says for every instance $G$ which is confusing me.

When I asked the professor she was very reluctant to help me, so please any guidance is appreciated.

The full question: here .

$\endgroup$
  • $\begingroup$ The question is badly worded -- it first mentions "Maximum Independent Set", and then defines it in terms of the size of a maximal independent set, when these are (perhaps surprisingly) very different: A maximal independent set is just one that can't have any further vertices added to it and still remain an independent set; such a set can easily be found in quadratic (probably even linear) time. Also it uses the word "solved" in a non-standard way: "solve" always means "find an optimal solution", but here (I infer that) they sometimes use it to mean "find an approximate solution". $\endgroup$ – j_random_hacker Dec 7 '18 at 20:07
  • $\begingroup$ The hint in that question is good, though. I think your problem is that you are trying to think about a specific G, and perhaps a specific algorithm that does something with it -- that won't help you solve this problem, because you have to show something that works for any graph G. $\endgroup$ – j_random_hacker Dec 7 '18 at 20:16
  • $\begingroup$ Start by assuming to the contrary that there exists a poly-time algorithm that can find the K-approximate solution to any graph G, and then show that there is something you can do to any graph G to make some new graph G' from it that can be given as input to this approximation algorithm, which will result in that algorithm's output "leaking" the true size of the original G's maximum I S. This would mean that you have solved Max I S in poly-time, which contradicts the P!=NP assumption. $\endgroup$ – j_random_hacker Dec 7 '18 at 20:18
  • $\begingroup$ @j_random_hacker Now I think you made it much clearer, but the only sensible way I can think of is to cut the graph to a disjoint union but won't that affect the independent set of the original graph? Or is the union of the independent sets from the chopped graph would be the same as the original graph? $\endgroup$ – Zed Dec 7 '18 at 20:31
  • 1
    $\begingroup$ @j_random_hacker the true size of the largest IS in G is 1 {a} or {b}, the true size of the largest IS in H is 2 {a,c} or {a,d} or {b,c} or {b,d}. so the true size of IS in H is the true size of IS in G times how many copies of G in H. $\endgroup$ – Zed Dec 11 '18 at 18:00
1
$\begingroup$

Suppose that there exists an integer $K$ and a polynomial time algorithm $A$ which, when run on a graph $G$, outputs a value $A(G)$ which satisfies $$ |A(G) - \alpha(G)| \leq K, $$ where $\alpha(G)$ is the maximum size of an independent set in $G$.

We will show that $A$ can be used to determine $\alpha(G)$ in polynomial time, which contradicts the assumption $\mathsf{P} \neq \mathsf{NP}$.

Given a graph $G$, let $H$ consist of $2K+1$ disjoint copies of $G$; note that $\alpha(H) = (2K+1) \alpha(G)$. Run $A$ on $H$ to get a value $A(H)$ which satisfies $$ |A(H) - \alpha(H)| \leq K \Longrightarrow |A(H) - (2K+1) \alpha(G)| \leq K \Longrightarrow \\ (2K+1)\alpha(G) \in \{A(H)-K,\ldots,A(H)+K\}. $$ The set on the right contains $2K+1$ values, exactly one of which is a multiple of $2K+1$, hence we can determine $\alpha(G)$ given $A(H)$.

$\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.