5
$\begingroup$

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

$\endgroup$
5
  • $\begingroup$ 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. $\endgroup$
    – Pål GD
    Jan 21, 2013 at 20:26
  • $\begingroup$ @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. $\endgroup$ Jan 21, 2013 at 20:35
  • $\begingroup$ @KarolisJuodelė A vertex cover is a set of vertices "covering" all the edges. In an edgeless graph the empty set is a vertex cover. $\endgroup$
    – Pål GD
    Jan 21, 2013 at 20:59
  • 1
    $\begingroup$ @Pål The idea is to go over all sets of $10$ vertices. That requires only logarithmic space. $\endgroup$ Jan 21, 2013 at 21:35
  • $\begingroup$ @YuvalFilmus Yes, I see now. $\endgroup$
    – Pål GD
    Jan 21, 2013 at 21:45

1 Answer 1

5
$\begingroup$

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;
 }
$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – Ben Benli
    Jan 21, 2013 at 21:20
  • $\begingroup$ This is not homework if you are concerned. $\endgroup$
    – Ben Benli
    Jan 21, 2013 at 22:14
  • 2
    $\begingroup$ 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. $\endgroup$
    – Pål GD
    Jan 21, 2013 at 22:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.