3
$\begingroup$

Given an arbitrary undirected graph $G = (V,E)$, I am interested in a low-polynomial time algorithm which can find several moderately large (ideally $O(n^\epsilon)$ vertices per clique for $\epsilon > 0$) cliques in $G$, provided they exist.

I am aware that the problem of finding the maximal clique is NP-hard. For my purposes, however, I don't need maximality per say. Rather, it would be helpful to have an algorithm which runs relatively quickly and with high probability finds some nontrivial cliques.

I am aware that for fixed $k$, finding a $k$-clique if it exists can be done in $n^k$ time by simply testing all subsets of $k$ vertices. This algorithm appears to be of limited use because of the exponential growth in $k$.

Does there exist an algorithm or multiple which can, with high probability, find multiple moderately large cliques in a general undirected graph?

$\endgroup$
3
$\begingroup$

Suppose that there exists a polytime algorithm which finds a clique of size $n^\epsilon$ if there is any. Then you can approximate maximum clique to within $n^{1-\epsilon}$ (assuming $\epsilon \leq 1/2$), which is NP-hard by a classical result of Håstad. Indeed, run your algorithm (stopping it if it exceeds its advertized running time), and check whether its output is a clique of size at least $n^\epsilon$. If so, output $n^\epsilon$, otherwise output $1$.

You might want to look into the planted clique problem, in which the goal is to find a clique "planted" inside a uniformly random graph. This is possible in polytime (with high probability) as long as the clique is large enough, $\Omega(\sqrt{n})$. Your case may be different, but similar ideas might work in practice.

$\endgroup$

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.