2 removed thanks, latex typo
source | link

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)$$\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? Thanks

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? Thanks

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?

    Tweeted twitter.com/#!/StackCompSci/status/197282694407790592
1
source | link

Restricted version of the Clique problem?

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? Thanks