Естественные, непроверяемые свойства графа

22

Во время тестирования свойств графов, алгоритм запрашивает целевой график на наличие или отсутствие ребер и потребностей , чтобы определить , либо имеет ли целевые определенное свойство или ε -far от того , свойства. (Алгоритм можно попросить преуспеть с 1-сторонней или 2-сторонней ошибкой.) Граф имеет ε -далее от того, чтобы иметь свойство, если никакие ребра могут быть добавлены / вычтены, чтобы сделать его иметь собственность.ε(N2)

Свойство называется тестируемым, если его можно протестировать указанным выше способом в сублинейном количестве запросов или, что еще лучше, в ряде запросов, не зависящих от (но не ). Понятие, что такое свойства, также может быть формализовано, но оно должно быть ясным.Nε

Есть много результатов, характеризующих, какие свойства являются тестируемыми, и множество примеров естественных тестируемых свойств. Однако я не знаю многих естественных свойств, о которых известно, что они не поддаются тестированию (скажем, в постоянном количестве запросов), и мне знакомо это тестирование на изоморфизм данного графа.

Итак, мой вопрос: какие естественные свойства графа не проверяются?

Лев Рейзин
источник
2
(1) Чтобы уточнить, ищете ли вы такие свойства в соседней матричной модели? В модели списка смежности (которая отличается от написанной вами формулировки) для многих задач требуется больше, чем постоянное количество запросов. (2) Вы, вероятно, знаете это, но Голдрайх, Голдвассер и Рон (Предложение 10.2.3.2 JACM 1998 ) доказывают, что в NP есть (не обязательно естественное) графовое свойство, которое требует Ω (n ^ 2) запросов, используя вероятностный метод.
Tsuyoshi Ito
1
Спасибо - модель матрицы смежности в порядке. Я знаю их результат, но я бы хотел явные природные свойства, в отличие от существования некоторых свойств.
Лев Рейзин
Я не уверен в этом, поэтому я не перечисляю это как ответ, но я думаю, что способность Шеннона графа не проверяется. mathworld.wolfram.com/ShannonCapacity.htmlΘ(г)
Димитрис

Ответы:

11

В матричной модели смежности существует нижняя граница сложности запроса проверки, является ли nΩ(N)N состоит вершинный граф из двух изоморфных копий некоторого вершинного графа (см. Введение в тестирование свойств графа - Голдрайх для опрос).N/2

Кроме того, есть много нижних границ, которые зависят от для тестеров с односторонней ошибкой, например: проверка ρNρ клика, вырезки и ρ- деления (см. Тестирование свойства и его связь с обучением и приближением - Goldreich, Goldwasser, Рон )ρρ

Кроме того, в модели графа ограниченной степени для проверки 3-колорибельности требуется запросов, тогда как для тестирования 2-колорибельности (т. Е. Двудольности) требуется Ω ( Ω(N) (см.Проверка свойств в ограниченных графах степеней - Гольдрайх, Рон).Ω(N)


источник