Опубликован быстрый алгоритм для задачи изоморфизма графов

Мне бы такая штука пригодилась когда я писал диплом по триангуляции поверхностей. А так, написали же, что многие комбинаторные задачи сводятся к графам

Чаще нужна ещё более общая задача — найти в графе A фрагмент, изоморфный графу B. Может быть очень полезна в компьютерном зрении, в задачах совмещения изображений и сцен (особенно с нелинейными искажениями), распознавании объекта по топологической схеме… Про поиски фрагментов программ и схем для оптимизации и прочего уже писали.

Есть еще одно приложение, где часто возникает необходимость проверки изоморфизма подграфу (задача NP-полна) — машинное обучение на графах. Успешнее всего применяется в химинформатике при анализе зависимости типа «структура-свойство» (QSAR). Обучающая выборка может выглядеть так: молекулярные графы этих веществ — положительные объекты (обладают свойством, например, токсичностью, канцерогенностью, мутагенностью и т.д.), молекулярные графы других веществ — отрицательные объекты (то есть вешества соот-но не токсичны, не канцерогенны, не мутагенны). Самая простая идея — настроить подграфы всех обучающих графов и представить каждый граф бинарным вектором, где 1 стоит там, где соответствующий «маленький» граф изоморфен подграфу обучающейго графа. (Банальный пример: помеченные графы A-B-C и B-C-D представятся векторами [1,1,1,0,1,1,0] и [0,1,1,1,0,1,1], в признаковом пространстве подграфов [A, B, C, D, A-B, B-C, C-D]). Вычислительная сложность такого представления очень высокая, потому что подграфов очень много, а также много раз необходимо проверять изоморфизм подграфу. Тем не менее, GBoost работает именно так — это «обычный» бустинг вот в таком признаковом пространстве подграфов, где «деревянным» методом важности признаков определяются важные для классифкации подграфы (их потом можно принести и показать эксперту, и он скажет, что да, например, такой подграф — бензольное кольцо — действительно свидетельствует о таком-то свойстве вещества).
Но state-of-the-art в классификации графовых данных — это ядерные методы, в большинстве из которых все равно надо часто проверять изоморфизм подграфу.

Тут больше теоретическая важность — уменьшилось количество задач в NP-intermediate кандидатах.
Сложность алгоритма квази-полиномиальная и особого значения в «реальном» мире иметь не будет. Сам Бабай в одной из лекций говорил что существующие эвристические и вероятностные алгоритмы более полезны для реальных задач.

поиск рож по базе, поиск генов по базе днк

«предположительно изоморфные вершины». Почему именно эти вершины «предположительно изоморфны», где гарантия, что мы ничего не потеряем, и при этом не уйдём в комбинаторный взрыв? И что при неудаче получим доказательство, что графы неизоморфны?

Вот тоже пришёл в комменты за этим вопросом. Это ж тупой перебор в лоб, если выкинуть мистику слова «предположительно» и брать всё подряд, отказываясь от гипотезы при обломе, и начиная проверять другую. Единственно, могу предположить что новизна в том, что впервые кто-то проанализировал этот алгоритм на P/NP-полноту

Есть мнение, что большинство реально крутых алгоритмов простые. И чем проще, тем круче :) Равно как и простое объяснение как правило вернее сложного (из истории можно припомнить хотя бы те же эпициклы против объяснения Коперника)

Настолько простая, что потребовалось три лекции, чтоб её объяснить =)
Только если эту идею применить в лоб, то получится экспоненциальный алгоритм.

Это ооочень поверхностное описание одной из идей, которые в этом алгоритме используются.
Почитайте, например, тут: rjlipton.wordpress.com/2015/11/21/a-little-more-on-the-graph-isomorphism-algorithm