Take the 2-minute tour ×
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.

The question is: What is the smallest complexity class in which the following problem is contained: Given a graph with $n$ nodes, Is there independent set of size of at least $n-10$?

I have a little difficulty to understand the meaning of being in ${\sf L}$ and examine problems in a correct way for deciding if they are in ${\sf NL}$ or ${\sf L}$

First I know that for being in ${\sf NL}$ I need to provide a verifier for a Turing machine which uses only $O(\log n)$ space on its working tape- So I wonder- I can give as a verifier this set of nodes to be independent set as requested, but how does the checking work? Can it go to all the lists of the pointers to the neighbors of each node , and for every node to check whether all the other nodes in the set given as independent set is not on that list- Is this considered of not using any space and I only need to count the nodes in the list that fulfill the requirement and therefore use only $O(\log n)$ space? Is this correct? Is there a way to prove that the problem is in ${\sf L}$?

share|improve this question
    
Having an independent set of size $n-10$ means that the graph has a vertex cover of size $10$, no? There is an exact algorithm solving this problem in $O(1.3^{10} \cdot n^2)$ time, hence in $O(n^2)$ time. I don't know any lower complexity class than $\mbox{P}$ for which constant-sized vertex cover is a member. –  Pål GD Jan 21 '13 at 20:26
    
@PålGD, I think you're wrong. Consider a graph of $n$ vertices and no edges. Any subset of it's vertices is independent, but only all $n$ form a cover. –  Karolis Juodelė Jan 21 '13 at 20:35
    
@KarolisJuodelė A vertex cover is a set of vertices "covering" all the edges. In an edgeless graph the empty set is a vertex cover. –  Pål GD Jan 21 '13 at 20:59
1  
@Pål The idea is to go over all sets of $10$ vertices. That requires only logarithmic space. –  Yuval Filmus Jan 21 '13 at 21:35
    
@YuvalFilmus Yes, I see now. –  Pål GD Jan 21 '13 at 21:45
add comment

1 Answer 1

Hint: How much space do you need to store a set of $10$ vertices? How much space does it take to go over all pairs of nodes in a graph?

Another hint: How much space does it take to implement the following algorithm? (I replaced 10 with 3 to make it easier to follow)

 int algorithm(int n, int G[n][n]) {
   int x, y, flag;
   int v1, v2, v3;

   for (v1 = 0; v1 < n; v1++)
     for (v2 = 0; v2 < n; v2++)
       for (v3 = 0; v3 < n; v3++) {
         flag = 0;
         for (x = 0; x < n; x++)
           for (y = 0; y < n; y++)
             if ((x != v1) && (x != v2) && (x != v3) &&
                 (y != v1) && (y != v2) && (y != v3))
               flag |= G[x][y];
         if (flag == 0)
           return 1;
       }
   return 0;
 }
share|improve this answer
    
I'm not really sure, as you can read I don't understand the meaning of storing vertices, in which representation I keep them? Your questions is exactly what I dont know and I wondered in my question. –  Ben Benli Jan 21 '13 at 21:20
    
This is not homework if you are concerned. –  Ben Benli Jan 21 '13 at 22:14
2  
Let's say your Turing machine gets as input $n$ (assuming the vertices are labeled from 1 to $n$) and then a list of which vertices are connected. You are looking for a vertex cover of, in Yuval's example, size 3. First you need to iterate through all combinations $(v_1,v_2,v_3)$ for $v_i \leq n$. Then you go through the edges an confirm that all of them has at least one endpoint in $(v_1,v_2,v_3)$. You store $3 \log n$ bits plus some constant for spacings. –  Pål GD Jan 21 '13 at 22:47
add comment

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.