[Solved]: Showing that Independent set of size $k$ can be decided using logarithmic space

Problem Detail: 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.

Asked By : Joni

Answered By : A.Schulz

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.
Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/6933  Ask a Question  Download Related Notes/Documents