Сильно регулярный граф и GI-полнота

Не известно , если изоморфизм графов (GI) для сильно регулярных графов (SRGS) в P . Есть ли намеки на то, что это может или не может быть GI- Complete? Есть ли сильные последствия в таких случаях? (Аналогично убеждению, что GI не может быть NP-Complete).

cc.complexity-theory graph-theory graph-algorithms graph-isomorphism structural-complexity DurgaDatta
источник

Лично я считаю, что проблема строго проще, чем GI, из-за алгоритма Спилмана для SRG, у которого показатель степени меньше, чем у Лукса для общих графов. Кажется, что здесь гораздо больше структуры! (что в конечном итоге может ничего не значить)

Тимоти Сан

O (n)

$O(n)$

O (n^{3 / 2})

$O(n^{3/2})$

Ответы:

Я полагаю, что все известные результаты GI-полноты являются функториальными (определение в статье), и Бабай недавно показал (ITCS 2014, бесплатная авторская копия ) - основываясь на оценках структуры групп автоморфизмов сильно регулярных графов - что функториальных нет снижение от GI до строго регулярного GI.

Джошуа Грохов
источник