Тестирование свойств для независимых наборов

9

Предположим, нам дан график и параметры . Существуют ли диапазоны значений для (или это выполнимо для всех ), для которых можно проверить, является ли -far из-за наличия независимого набора размера по крайней мере во времени ?гК,εККгεКО(N+поли(1/ε))

Если мы используем обычное понятие -far (т. Е. Для получения такого множества потребуется изменить не более ребер), то проблема тривиальна для . ТакεεN2Кзнак равноО(Nε)

  • Кажется, что если больше, некоторые идеи выборки должны работать для решения проблемы. Это правда ?К
  • Существуют ли другие понятия -far (т. Е., Может быть, ребер вместо), при которых имеются нетривиальные результаты?εε|Е|

Я в основном ищу ссылки на данный момент.

Суреш Венкат
источник

Ответы:

10

Эта проблема действительно была изучена. Голдрайх, Голдвассер и Рон изучили его в своей оригинальной статье, которая начала тестирование свойств графа, а затем Фейге, Лангберг и Шехтман также получили результаты по этому вопросу в своей статье FOCS '02 «Графики с крошечными векторными хроматическими числами и огромными хроматическими числами» ,

В частности, [FLS '02] показывают, что можно отличить графы с независимым набором размера от графов -far от таковых (то есть для создания таких ребер необходимо удалить как минимум ребра независимый набор), выбрав случайный подграф, индуцированный случайными вершинами в графе, и проверив, имеет ли случайный подграф независимый набор размера или не. ([GGR '98] показал более слабую оценку of .) [FLS '02] также показывает нижнюю оценку of .ρNεεN2sзнак равноО~(ρ4/ε3)ρssО~(ρ/ε4)sΩ(ρ3/ε2)

Арнаб
источник
6

Еще одно естественное определение ε-приближается к независимому набору меняется εК2кромки. К сожалению, с таким определением тестирование свойств не представляется возможным за полиномиальное время. Причина в том, что никто не знает, как найти установленную клику (и подобный независимый набор)о(N) вершины в случайном графе N вершины быстрее, чем NО(журналN)время. Можно показать, что подграф, который немного плотнее среднего, можно использовать для нахождения посаженной клики за полиномиальное время. Это доказательство того, что для этого варианта вашей задачи существует алгоритм с полиномиальным временемК между журналN а также N,

Справка: Фейге и Краутгамер. Нахождение и сертификация большой скрытой клики в полуслучайном графе, 1999.

Уоррен Шуди
источник