6
$\begingroup$

$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?

$\endgroup$
  • $\begingroup$ What is this question about right now? You asked a question ("Can we solve VC in parametrized log space?"), and you received an answer. You should accept that answer. This is not the place solicits proofreaders of your algorithms/proofs. $\endgroup$ – Sasho Nikolov May 5 '17 at 13:56
10
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Can we get all minimum vertex covers of size at most $k$ from the above algorithm with $f(k)+c \log |V|$ space? $\endgroup$ – GOLD Mar 1 '17 at 16:46
  • $\begingroup$ Yes - this follows from the remark. $\endgroup$ – daniello Mar 1 '17 at 20:03
  • $\begingroup$ Can we use the bounded search tree method for find all minimum vertex covers in $f(k)+O(\log n)$ space? If yes then can you give simple process? $\endgroup$ – GOLD Mar 31 '17 at 13:06
  • $\begingroup$ Yes -- the algorithm above can output a graph G' on O(k^2) vertices and integer k' such that there is a log-space computable one to one correspondence between vertex covers of G of size at most k, and vertex covers of G' of size at most k'. Now enumerate minimum size vertex covers of G' and use the correspondence to list the corresponding vertiex covers in G. $\endgroup$ – daniello Mar 31 '17 at 19:04

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.