Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Consider the following NP problem called A: its input is a graph G and a number k > 1. Its witness, if there is one, is a pair $S;T$ of sets of points in $G$ such that S is an independent set of size $k$ and $T$ is a clique of size $k$. Show that this problem is NP-complete.

Any help would be appreciated. Not really sure where to even start.

share|improve this question
    
Do you know that Independent Set is an NP-Complete problem? –  Alex Becker Mar 20 '13 at 11:56

1 Answer 1

First, the general lecture part:

To show that a problem is NP-complete, the typical approach is to:

  1. Show that the problem is in NP, and
  2. Show that the problem is NP-hard, by construction a reduction from an NP-hard problem to the one we're interested in.

In certain cases we have other options (especially for step 2.) such as proof by restriction (though this is really just an observation that there is a trivial reduction from a restricted version of the problem).

In this case however, constructing a reduction is relatively simple.

To show 1. (that the problem is in NP), we have to show one of two equivalent things:

  • That there is a nondeterministic Turing Machine that can decide the problem in time bounded by a polynomial in the size of the input1, or
  • That given a certificate for a solution to an instance of the problem, we can check that the certificate is correct in deterministic polynomial time2.

Both of these tend to be relatively easy to do: a nondeterministic algorithm can be as simple as guessing (using the magic of nondeterministism) which elements constitute a solution and then checking that they do form a solution in polynomial time; or just demonstrating that given an alleged solution, you can check that it is a real solution in polynomial time. Note that both options involve checking the validity of a solution, so it's usually simpler just to do that!

To show 2. (that the problem is NP-hard), we have to take a problem that we already know is NP-hard, and give a mapping that converts instances of the hard problem to the "new" problem. This mapping has to be computable in polynomial time and preserve the solution (in that a yes-instance should map to a yes-instance and no to no - remember we are dealing decision problems, so they're either yes or no).

Note also that NP-hard is superset of NP-complete, and typically the NP-hard problems we talk about will actually be NP-complete, it's just that we're particularly interested in the hardness part.

Now some hints specific to your case:

For 1., it suffices to show that you can check the validity of a solution quickly - this should be easy to do, just think of what constitutes a solution and what properties it has to have.

For 2., you need to find an NP-hard problem to reduce from. In theory, if your problem is NP-complete, then any other NP-complete problem will do. In practice of course you want to pick something that's already reasonably close.

In your case, there's two classic NP-complete problems that should be jumping out at you that you could use for the reduction (one has been suggested in the comments to the question). In fact they should not just be jumping but screaming hey look at me.

When you've picked one, you then need to convert an instance of the problem you've chosen to a graph such that if the chosen problem's source instance is a yes-instance, your graph has a $k$-clique and a $k$-independent set and vice versa.

I'll give a couple more additional hints in spoilers, but you should be able to go from here, or at least give it a good try.

Just before that, you might be interested to know that there's a stackexchange site just for questions like this: Computer Science. Assuming that you're studying further in CS, you may find it a useful resource.

The two problems that a screaming to be the source problem for the reduction are $k$-CLIQUE and $k$-INDEPENDENT SET. In this case picking either is as easy as the other, as independent sets and cliques have a special relationship - a $k$-clique in a graph $G$ is a $k$-independent set in $\overline{G}$, the complement graph of $G$ where we swap edges and non-edges. This should give you way more than enough to start with one of these two problems and build a graph that has both a $k$-clique and $k$-independent set iff the source instance has a $k$-clique or $k$-independent set (depending on which you chose to start with).

Footnotes

  1. When we say "time bounded by", for a Turing Machine this means the same as "number of steps bounded by", so you don't need to worry about how long it takes a Turing Machine to perform an action. When we say polynomial in the size of the input, most strictly, this should be polynomial in the length of a reasonable encoding of the input (i.e. the number of cells it takes up on the Turing Machine's tape), in practice of course, we can take any proxy for this length that is at most a polynomial factor different (as polynomials of polynomials are still polynomials), so, for example, the number of vertices in a graph is a reasonable measure of the size of the input with regards to NP-hardness/completeness, even though the size of the encoding may be more like $O(|V|^{2}\log|V|)$.

  2. Note here the move from nondeterministic to deterministic. So for the first point, we can make clever guesses in the sense that at any given state if there is a valid transition that leads to acceptance, the Turing Machine will take it (note that it will head toward acceptance even if it shouldn't - hence we still have to verify the guesses). In the second case, we can think of this as just a normal algorithm, we just get to say that someone else gives us the solution and all we have to do is verify that it's correct.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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