13
$\begingroup$

Consider the following version of the Clique problem where the input is of size $n$ and we're asked to find a clique of size $k$. The restriction is that the decision procedure cannot change the input graph into any other representation and cannot use any other representation to compute its answer, other than $\log(n^k)$ extra bits beyond the input graph. The extra bits can be used for example in the brute-force algorithm to keep track of the status of the exhaustive search for a clique, but the decision procedure is welcome to use them in any other way that still decides the problem.

Is anything known at this point about the complexity of this? Has any work been done on other restrictions of Clique, and if so, could you direct me to such work?

Improve this question
$\endgroup$
2
  • $\begingroup$ Do you intend the constant $k$ in $\lg n^k$ to be the same as the clique size $k$? $\endgroup$
    – Lucas Cook
    May 1, 2012 at 11:10
  • $\begingroup$ @LucasCook Yes. $\endgroup$
    – ShyPerson
    May 2, 2012 at 3:48

1 Answer 1

Reset to default
5
$\begingroup$

This sounds like you are asking whether or not the NP-complete clique problem can be solved in logarithmic space. Using Turing machines, one tape is read only and stores the input graph. The other tape is bounded so that there's $c \lg n$ space available for some constant $c$. The class of problems solvable in this model is known as $L$, deterministic logarithmic space. (See wikipedia or in the complexity zoo)

It is unknown whether $\mathrm{CLIQUE} \in L$, but a positive answer would imply that $P = NP$, so you (almost surely?) won't find an answer. $L \subseteq P \subseteq NP$ and $\mathrm{CLIQUE} \in L$ implies $\mathrm{CLIQUE} \in P$, which implies $P = NP$.

Edit in case I misinterpreted the problem:

If you intend that the $k$ in $ \lg n^k = k \lg n $ is the same as the clique size $k$ (i.e. the amount of memory scales with input $k$), then there's a simple brute force algorithm: you can loop through all possible sets of $k$ nodes and check if they form a $k$-clique. A starting point for searching for better solutions might be the references of [1].

[1] Virginia Vassilevska, "Efficient algorithms for clique problems" pdf link

Improve this answer
$\endgroup$
6
  • $\begingroup$ @ShyPerson Ok. The input string is often immutable in space-restricted models (like sublinear space TMs in $L$ or $NL$), so that might be a good place to look. I'm not sure of a formal way to say that "you cannot make another representation" besides simply limiting the space. If I'm allowed the space to make another copy of $G$, what exactly constitutes another representation? What if I "accidentally" build a sufficient representation for a particularly sparse or compressible graph? $\endgroup$
    – Lucas Cook
    May 2, 2012 at 5:46
  • 1
    $\begingroup$ $\mathrm{kCLIQUE}$ is not NP-complete! (unless $\mathrm{P}= \mathrm{NP}$) $\endgroup$
    – Alex ten Brink
    May 2, 2012 at 11:02
  • $\begingroup$ @AlextenBrink Do you mean that kCLIQUE is the function problem? I changed the name to CLIQUE above (I always confuse them!), but it's strange to me to say kCLIQUE is in NP if you mean the function problem. $\endgroup$
    – Lucas Cook
    May 2, 2012 at 15:03
  • $\begingroup$ Meant search problem, in this case. $\endgroup$
    – Lucas Cook
    May 2, 2012 at 15:10
  • 4
    $\begingroup$ $\mathrm{kCLIQUE}$ is the $\mathrm{CLIQUE}$ problem for fixed $k$, while the $\mathrm{CLIQUE}$ has $k$ as part of the input. By checking all subgraphs of size $k$ you have an $O(n^k)$ algorithm, which is polynomial if $k$ is fixed but superpolynomal if for instance $k=\Theta(n)$. $\endgroup$
    – Alex ten Brink
    May 2, 2012 at 15:42

Your Answer

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

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