Tell me more ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.
up vote 4 down vote favorite

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.

share|improve this question
$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) – Luke Mathieson Nov 26 '12 at 23:40
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}$). – HdM Nov 27 '12 at 11:42
@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. – Luke Mathieson Nov 27 '12 at 13:42

1 Answer

up vote 5 down vote accepted

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.

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.