3
$\begingroup$

The following exercise is difficult for me:

Show that for each $k \in \mathbb{N}$ the question of existence of a $k$-clique within a graph lies in $\text{L}$.

Hint: A $k$-clique denotes $k$ verteces within a graph that are all connected with each other.

Annotation: if the question also considers $k$ as parameter, then the problem is $\text{NP}$-complete.

So $\text{L}$ is "the complexity class containing decision problems which can be solved by a deterministic Turing machine using a logarithmic amount of memory space". Now I'm wondering if this exercise isn't a catchy question, since I've found this paper and it says "We give an algorithm for $k$-clique that runs in (...) $O(n^{\varepsilon})$ space, for all $\varepsilon > 0$, on graphs with $n$ nodes"?

Furthermore, I also don't understand the annotation, because how should it be possible to not consider $k$ for the $k$-clique problem?

$\endgroup$
  • $\begingroup$ Designing an algorithm for k-clique which runs just in log-space is indeed an exercise. This is completely different from designing an algorithm for k-clique which runs in O(n^k/(ε log n)^(k−1)) time and O(n^ε) space, which is nontrivial because of the bold part (which you omitted). $\endgroup$ – Tsuyoshi Ito Dec 1 '12 at 3:07
  • $\begingroup$ @TsuyoshiIto: Can you please explain how to design such an algorithm, since I really have difficulties with this exercise (BTW: this is the original exercise, i.e. I did nohting omit)? $\endgroup$ – Uriel Dec 3 '12 at 20:55
  • 1
    $\begingroup$ I do not have any more hint than what adrianN wrote. I just wanted to point out that your question is completely different from the question answered by the paper which you cited. $\endgroup$ – Tsuyoshi Ito Dec 3 '12 at 21:41
  • $\begingroup$ @TsuyoshiIto: Sorry for misunderstanding you. Anyway, feel free to provide further help, if you have the time and knowledge, since I have enough difficulties with this exercise and a solution won't be provided... $\endgroup$ – Uriel Dec 4 '12 at 16:14
5
$\begingroup$

If you consider $k$ a constant, then k-clique can be solved be enumerating all $O(n^k)$ sets of vertices and checking that there are edges present in polynomial time (since the exponent is constant).

Enumerating k-Tuples of numbers up to n can be done in $k\log n$ space, you only have to figure out how to check for the presence of an edge between two vertices without using much space. Depending on how much details you have to give this is either obvious or very tedious to write down.

$\endgroup$
  • $\begingroup$ Do you perhaps have a useful link for this exercise or a further explanation, because actually I have no idea how to solve this exercise? $\endgroup$ – Uriel Dec 3 '12 at 20:59
  • 1
    $\begingroup$ Assume your vertices are numbered 1..n, and your k is fixed, say k=3. To check whether your graph has a 3-clique you look at all triples (a,b,c), with $a,b,c\in [1..n]$ and check whether your adjacency matrix has ones at the right positions. To do this in logspace you need to figure out how to enumerate all (a,b,c). But this is just counting to $n^4-1$ in base n. $\endgroup$ – adrianN Dec 4 '12 at 10:30
  • $\begingroup$ I'm looking at the first graph here: link. But how do I manage to let the checking be in logspace? $\endgroup$ – Uriel Dec 4 '12 at 11:19
  • 1
    $\begingroup$ If your adjacency matrix is stored sensibly, you only need to count to about $r\cdot n+c$ to access row $r$ and column $c$. Where do you think you would need more space than a constant number of values between 1 and n? $\endgroup$ – adrianN Dec 4 '12 at 11:25
  • $\begingroup$ I don't understand the meaning of constant $n$, because for accessing matrix entry $m_{r,c}$, I need $r+c$ steps. Furthermore, if a=1, b=2 and c=5, then I need to check whether entries $m_{1,2}=1$, $m_{1,5}=1$, $m_{2,1}=1$, $m_{2,5}=1$, $m_{5,1}=1$ and $m_{5,2}=1$, but I think this needs more than logspace? $\endgroup$ – Uriel Dec 4 '12 at 11:57

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.