سؤال

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?

لا يوجد حل صحيح

مرخصة بموجب: CC-BY-SA مع الإسناد
لا تنتمي إلى cs.stackexchange
scroll top