An independent set $I$ is a subset of the nodes of a graph $G$ where: no 2 nodes in $I$ are adjacent in $G$. For natural number $k$, the problem $k-\text{IND}$ asks if there is an independent set of size $k$.

I'd really love your help with showing that $k-\text{IND} \in {\sf L}$, i.e., can be decided using deterministic logarithmic space.

  • $\begingroup$ $k$-Independent Set is NP-complete, so can't be in L unless (at least) P=NP. Do you mean IND to be a different problem to $k$-IND? Perhaps just the existence of any independent set? (This case is trivial, the answer is Yes if there is at least one vertex in the graph) Or perhaps Maximal Independent Set, where we want an independent set that can't be made any larger? (This is at least in P, and at a cursory glance also in L) $\endgroup$ Nov 26 '12 at 23:40
  • 1
    $\begingroup$ It depends on your notion, but from my experience, $\mathsf{IndependentSet}$ is NP-complete, whereas $k-\mathsf{IndependentSet}$ is in P. The reason is simply that in the former Language, $k$ is part of the input, while in the latter, it is not (i.e. you're looking at concrete numbers, for instance at $5-\mathsf{IndependentSet}$). $\endgroup$
    – HdM
    Nov 27 '12 at 11:42
  • $\begingroup$ @HdM, quite true, from my background it wouldn't be clear, but I have to seen it written in a variety of possible ways. I was hoping for a clarification, but A.Schulz has covered this possibility already. $\endgroup$ Nov 27 '12 at 13:42

You can use the following algorithm.

I assume that the vertices are labeled $1,\ldots,m$. You enumerate all $k$-tuples $\{1,\ldots , m\}^k$. This can be done by reserving $k$ counters on the TM tape. Since $k$ is not part of your input this needs only $O(\log m )\subseteq O(\log n)$ space. However for every $k$-tuple you can test if it is an independent set. Simpy test all pair of selected vertices if there are not connected by an edge. Again, since $k$ is fixed the edges you have to test (depending on the current tuple) are known. Thus this test can be hard-wired into the TM program, and therefore needs no extra-space.


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.