k-Vertex Cover problem is in parameterized Log space

Question

$k$-Vertex Cover:

Given a graph $G = (V, E)$ where $V$ is a set of vertices and $E$ a set of edges, and an integer $k$, the $k$-Vertex Cover problem determines if there exists a subset of vertices $V'$ of $V$ of size at most $k$, such that every edge of $E$ has at least one vertex in $V'$.

Can we solve $k$-Vertex Cover problem in $f(k)+c\log|V|$ space where $c>0$ is some constant?

yes. (proof given in link page number 126 and Theorem 2.3). Can you give Simple proof?

Can we get all mimimum vertex covers of size $k$ from this proof with in
$f(k)+c\log|V|$ space?

There is an other method (bounded search tree method proof given in [link] (http://www.mrfellows.net/papers/CCDF97_AdviceClasses.pdf) page number 127 proof(2)) to show that k-Vertex Cover problem is in parameterized Log space.

Other method goes as follows: There are 2^k possible vertex covers. Think $P$ is at most $k$ length 0's and 1's bit string. For each value of $P$, we can generate the vertex set of size at most $k$ and it may become potential vertex cover. Clearly we can say $P$ is the path in bounded search tree. For generating for all $P$'s need 2^k space. Now we need to find vertex cover for given $P$ and $P$ is at most $k$ length 0's and 1's bit string.

Function $F(P,1)$ returns us first vertex by choosing the lex least edge and then the lex least vertex and this function will take constant space.

Function $F(P,2)$ returns us vertex of lex least edge not connected to the first one ($F(P,1)$).

$F(P,2)$ needs output of $F(P,1)$ and enumerate edges to find the lex least edge not connected to the first one. $F(P,2)$ needs one logspace

Function $F(P,3)$ returns us vertex of lex least edge not connected to $F(P,1)$ and $F(P,2)$. But we are not store the output of $F(P,1)$ and $F(P,2)$. We need to enumerate the edges and find the lex least edge not connected to $F(P,1)$ and $F(P,2)$. For this for each edge, we call $F(P,1)$ and $F(P,2)$ sequentially and check whether edge connected to $F(P,1)$ and $F(P,2)$. For each edge we need one logspace and $F(P,2)$ one logspace $F(P,3)$ needs two logspace

Similarly $F(P,i)$ returns us vertex least edge not connected to $F(P,1) \cdots F(P,i-1)$. we are not store the outputs of $F(P,1) \cdots F(P,i-1)$. We need to call sequentially. We need to enumerate the edges and find the lex least edge not connected to $F(P,1) \cdots F(P,i-1)$. For this for each edge, we call $F(P,1) \cdots F(P,i-1)$ sequentially and check whether edge connected to $F(P,1) \cdots F(P,2)$. So $F(P,i)$ needs (i-1) logspace

Clearly $F(P,k)$ needs k.logspace. But algorithms should takes only $f(k)+c\log n$ space?.

Am I missing something?. Please help out this process where it went wrong?

Answer 1

Here is an algorithm that uses $2k^2 + O(\log n)$ space. This is just the observation that the well known "Buss kernel" for Vertex Cover can be computed in log-space:

Say that a vertex has big degree if it has degree at least $k+1$. All vertices of big degree must be in every vertex cover of size at most $k$. If $v$ does not have big degree it has small degree. Call a vertex $v$ interesting if it has small degree and has at least one neighbor of small degree. Any inclusion minimal vertex cover of $G$ of size at most $k$ must contain all vertices of big degree, and out of the vertices of small degree, it can only contain interesting vertices.

One can easily verify that in $O(\log n)$ space one can determine whether a given vertex has small or big degree, and whether it is interesting or not. Further, we can count the number of big degree / small degree / intersting vertices before $v$ in input. Thus, given an integer $j$ we can also find the $j$'th vertex of big degree / small degree or the $j$'th interesting vertex.

The algorithm computes the number $b$ of vertices of big degree, if $b > k$ the algorithm outputs that there is no vertex cover of size at most $k$. The algorithm computes the number $i$ of interesting vertices. If $i > 2k^2$ it outputs that there is no vertex cover of size at most $k$ (because one has to cover at more than $k^2$ edges using only vertices of degree at most $k$).

Now the algorithm goes over all the $2^i$ possible binary strings on length $i$. For each such string, we interpret the $j$'th bit as whether the $j$'th interesting vertex is in the vertex cover or not.

For each string compute the total size of the proposed solution ($b$ + the number of ones in the binary string), and check whether the proposed solution is a vertex cover by going over every pair of interesting vertices, checking whether they are adjacent, and whether both are $0$ in the binary string. This concludes the algorithm.

Remark: because the number of interesting vertices is at most $O(k^2)$ and we can determine whether a given vertex is interesting or not, one could run any vertex cover algorithm on the subgraph induced on the interesting vertices (for example the $O(1.2738^k + nk)$ time algorithm by Chen, Kanj and Xia), and this would still only use $f(k) + O(\log n)$ space.