[Solved]: Restricted version of the Clique problem?

Problem Detail: 

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?

Asked By : ShyPerson

Answered By : Lucas Cook

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

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/1606