Посаженная клика в G (n, p), варьирующаяся p

В задаче о посаженной клике необходимо восстановить -клику, заложенную в случайном графе Эрдоша-Реньи . В основном это рассматривалось для , и в этом случае известно, что оно решаемо за полиномиальное время, если и предположило трудно для .$k$$G(n,p)$$p=\frac{1}{2}$$k > \sqrt{n}$$k< \sqrt{n}$

Мой вопрос: что известно / верит о других значениях ? В частности, когда является константой в ? Есть ли доказательства того, что для каждого такого значения существует некоторый для которого задача является вычислительно сложной?$p$$p$$[0,1]$$p$$k=n^{\alpha}$

Ссылки были бы особенно полезны, поскольку мне не удалось найти какую-либо литературу, которая рассматривает проблему для значений, отличных от .$p=\frac{1}{2}$

Если является константой, то размер максимальной клики в модели почти всегда является постоянным кратным , причем константа пропорциональна . (См. Боллобас, с.283 и следствие 11.2.) Следовательно, изменение должно влиять на сложность установки клики с вершинами пока клика слишком мала для существующего алгоритмического подхода к работе. Поэтому я ожидаю, что при постоянном жесткость Planted Clique должна вести себя так же, как в случае , хотя вполне возможно, что случай очень близкий к 0 или 1, может вести себя по-другому.$p$$G(n,p)$$\log n$$\log (1/p)$$p$$\omega(\log n)$$p \ne 1/2$$p=1/2$$p$

В частности, для применяется тот же порог для для размера установленной клики, выше которого задача становится полиномиальной. Здесь значение равно (а не некоторому другому значению), поскольку тета-функция Ловаша для почти наверняка находится в пределах и , в результате Юхаса. Алгоритм Feige и Krauthgamer использует тэта-функцию Lovász для поиска и сертификации самой большой клики, поэтому он использует этот пороговый размер для установленной клики.$p\ne 1/2$$\Omega(n^{\alpha})$$\alpha = 1/2$$\alpha$$1/2$$G(n,p)$$0.5\sqrt{(1-p)/p}\sqrt{n}$$2\sqrt{(1-p)/p}\sqrt{n}$

Конечно, может быть другой алгоритм, который не использует тэта-функцию Ловаша, и что для значений далеких от можно найти посаженную клику с, скажем, вершинами. Насколько я могу сказать, это все еще открыто.$p$$1/2$$n^{1/3}$

Feige и Krauthgamer также обсуждают, когда не является постоянной величиной, но зависит от , и либо близко к 0, либо близко к 1. В этих случаях существуют другие подходы для поиска посаженных клик, и пороговый размер отличается.$p$$n$

• Бела Боллобас, Случайные графы (2-е издание), издательство Кембриджского университета, 2001.
• Ференц Юхас, Асимптотическое поведение функции Ловаша для случайных графов$\vartheta$ , Combinatorica 2 (2) 153–155, 1982. doi: 10.1007 / BF02579314
• Уриэль Фейдж и Роберт Краутгамер, Нахождение и сертификация большой скрытой клики в полуслучайном графе , Случайные структуры и алгоритмы 16 (2) 195–208, 2000. doi: 10.1002 / (SICI) 1098-2418 (200003) 16: 2 <195 :: АИД-RSA5> 3.0.CO; 2-A

установленная клика для является частным случаем этой проблемы и новых результатов (нижних границ), как указано в p2 и т. д., и включает соответствующие ссылки. (2015)$p \neq \frac{1}{2}$

Мы показываем, что, принимая (детерминистическую) гипотезу об экспоненциальном времени, различая граф с индуцированным -кликом и граф, в котором все -подграфы имеют плотность не более , требуется время.$k$$k$$1 −\varepsilon$$n^{\tilde{\Omega}(\log n)}$

• ETH Твердость для плотного -подграфа с совершенной полнотой$k$ / Браверман, Ко, Рубинштейн, Вайнштейн

Вот новая статья, которая имеет алгоритм для произвольного p ≠ ½ на основе алгоритма SVD. см. стр.4 для анализа скрытой (установленной) клики.

Простой алгоритм SVD для поиска скрытых разделов Ван Ву

Аннотация. Поиск скрытого раздела в случайной среде является общей и важной проблемой, которая содержит в качестве подзадач многие известные вопросы, такие как поиск скрытой клики, поиск скрытой раскраски, поиск скрытого двунаправленного текста и т. Д. В этой статье мы предоставляем простой SVD Алгоритм для этого, отвечая на вопрос McSherry. Этот алгоритм очень прост в реализации и работает для разреженных графов с оптимальной плотностью.