Эти два графа являются изоморфными

Математик Ласло Бабай (Laszlo Babai) с факультета компьютерных наук и математики Чикагского университета представил быстрый новый алгоритм для решения задачи изоморфизма графов — одной из фундаментальных проблем теории сложности вычислений. Алгоритм приводит проблему очень близко к классу P. По мнению некоторых специалистов, это один из самых значительных результатов в теоретической информатике за десятилетие, если не за несколько десятилетий.

О создании алгоритма Ласло объявил месяц назад. По его словам, алгоритм значительно эффективнее, чем самый лучший из существующих, который был рекордсменом более тридцати лет: его разработал ныне профессор Юджин Люкс в 1983 году, тот решал задачу за субэкспоненциальное время.

Ласло Бабаю, судя по всему, удалось практически свести проблему к задаче класса P: его алгоритм заявлен как вычисляемый в квази-полиномиальное время.

11 декабря 2015 года статья с описанием нового алгоритма наконец-то опубликована в открытом доступе, а также отправлена в Ассоциацию по вычислительной технике. Официальная презентация алголритма состоится на 48-м симпозиуме по теории вычислений.

В течение нескольких десятилетий проблема изоморфизма графов имела особый статус в теории сложности вычислений. В то время как сотни других задач смиренно поддавались классификации по классу P или классу NP, проблему изоморфизма графов никак не могли однозначно классифицировать. Она казалась сложнее, чем лёгкие задачи и легче, чем сложные, занимая уникальное положение как будто между двумя классами задач. Это одна из двух знаменитых задач в этой странной промежуточной области, говорит Скотт Ааронсон (Scott Aaronson), математик из Массачусетского технологического института. Теперь, по его словам «похоже, что одна из двух сдалась».

Вторая общеизвестная задача из «серой» области — факторизация целых чисел.

Задача изоморфизма графов сама по себе выглядит просто: нужно определить, являются два графа изоморфными, то есть можно ли простым передвижением вершин трансформировать один граф в другой, сохраняя связи между вершинами. Вот и всё. Несмотря на кажущуюся простоту, эту задачу трудно решить, потому что даже маленькие графы могут принимать множество разнообразных форм.


Ласло Бабай представляет свой алгоритм для решения задачи изоморфизма графов 10 ноября 2015 года в Чикагском университете

Алгоритм Ласло Бабая работает путём виртуального «окрашивания» вершин графа. Сначала случайным образом выбираются несколько вершин, они «окрашиваются» в разные цвета. Затем выбираются несколько вершин во втором графе, предположительно соответствующих вершинам из первого графа, им присваиваются те же цвета. В конце концов, перебираются все варианты. После первоначального выбора алгоритм окрашивает на обоих графах предположительно изоморфные вершины, соседствующие с первоначально выбранными, в другие цвета до тех пор, пока не остаётся связей между вершинами.

Если алгоритм Бабая пройдёт проверку коллег, то это самое значительное открытие в данном разделе математики за последнее время. «До его объявления вряд ли кто-то, кроме, может быть, его самого, предполагал появление такого результата в ближайшие десять лет, если вообще когда-либо», — говорит Джошуа Грочоу (Joshua Grochow) из института Санта-Фе.

За последние несколько недель Бабай дал несколько лекций с изложением своего алгоритма. Видеозапись первой лекции от 10 ноября представлена ниже.



Задача изоморфизма графов считается «универсальной», то есть к ней можно свести любую проблему, где ставится вопрос об изоморфизме комбинаторных структур. Обычно такая «универсальность» свойственна задачам класса NP. В то же время задача изоморфизма графов демонстрировала одно странное свойство, которого нет ни у одной NP-полной задачи: прохождение «слепого теста» (протокол Артура-Мерлина).

В 2012 году неформальный опрос учёных в области теоретической информатики дал такой результат: 14 из них высказались, что проблема изоморфизма графов принадлежит к классу P, а шестеро сказали, что не принадлежит. До объявления Ласло Бабая мало кто думал, что задачу решат когда-нибудь в ближайшее время. «Я думал, что может она принадлежит к классу P, а может быть нет, но при моей жизни этого никто не узнает», — признался Грочоу.

Ласло Бабай работал над проблемой изоморфизма графов почти 40 лет.

Комментарии (24)


  1. lostmsu
    16.12.2015 04:42
    +1

    А для каких практических задач нужно решение этой проблемы? Список в википедии довольно короткий и не подробный.


    1. DoctorChaos
      16.12.2015 06:51
      +21

      Вы ждете ответа от ализара? Он хорошо если сам хотя бы половину слов из этой статьи понимает)
      Ализар, может, вам на гиктаймсе все-таки жить? Так хорошо тут было без ваших «сенсаций».


    1. Scratch
      16.12.2015 06:59

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


    1. Mrrl
      16.12.2015 08:00
      +8

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


      1. netmaxed
        16.12.2015 08:38

        а есть, кстати, что-нибудь интересное на этом поприще? какие-нибудь прорывы?


        1. Mrrl
          16.12.2015 08:56

          Понятия не имею. Когда мне нужно что-то подобное, я пишу очередной велосипед. Пока лучше всего работает алгоритм с использованием матриц, в которых вычисляется вероятность соответствия для каждой пары вершин — но я уже забыл, откуда он взялся и как называется.


      1. mihaild
        16.12.2015 10:03
        +11

        А вот это уже NP-полная задача.
        И даже проверка наличия полного подграфа из k вершин тоже np полна.


      1. knagaev
        16.12.2015 10:49
        +3

        Дополню, если позволите.
        Алгоритмы работы с графами сейчас в большинстве популярных случаев применяются в обработке данных соцсетей.
        И Вы абсолютно правы — это фактически подзадача для задачи поиска паттерна в графе.
        Поиск паттерна практически можно отнести к классу «почти универсальных» методов обработки связанных данных.

        А статья (точнее новость, в ней упомянутая) мне показалась интересной, хоть Ализар и считается любителем «скандалов, интриг, расследований».


      1. 0xd34df00d
        16.12.2015 19:28

        Компьютерная алгебра, оптимизация символьных выражений.

        Что приятно, там вылезают всячкие интересные категориальные объекты вроде копроизведения в категории графов.


        1. Mrrl
          16.12.2015 19:33

          Но там ориентированные графы, да ещё и ациклические. Может быть, для них эта задача проще?


          1. 0xd34df00d
            16.12.2015 19:36

            Если я правильно помню, то простоты из этого особой извлечь не удаётся. Но я могу помнить неправильно — так, почитал немножко книг и статей, когда раздумывал о том, делать связанные с этим вещи частью дипломной работы или нет.


            1. Mrrl
              16.12.2015 19:40
              +2

              Действительно. Задача о неориентируемых графах элементарно сводится к ориентируемым ациклическим, с утроенным числом вершин (на всякий случай, чтобы думать меньше).


    1. yorko
      16.12.2015 13:40
      +1

      Есть еще одно приложение, где часто возникает необходимость проверки изоморфизма подграфу (задача 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 в классификации графовых данных — это ядерные методы, в большинстве из которых все равно надо часто проверять изоморфизм подграфу.


    1. Hypuk
      16.12.2015 13:51

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


    1. BalinTomsk
      16.12.2015 19:37

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


  1. QtRoS
    16.12.2015 09:44
    +2

    Алгоритм Ласло Бабая работает путём виртуального «окрашивания» вершин графа. Сначала случайным образом выбираются несколько вершин, они «окрашиваются» в разные цвета. Затем выбираются несколько вершин во втором графе, предположительно соответствующих вершинам из первого графа, им присваиваются те же цвета. В конце концов, перебираются все варианты. После первоначального выбора алгоритм окрашивает на обоих графах предположительно изоморфные вершины, соседствующие с первоначально выбранными, в другие цвета до тех пор, пока не остаётся связей между вершинами.

    Но ведь идея крайне простая, где за этими словами кроется трюк? Или это из-за перевода?


    1. Mrrl
      16.12.2015 10:16
      +12

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


    1. Nashev
      17.12.2015 10:04

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


      1. mihaild
        17.12.2015 18:24
        -1

        Что такое «P/NP полнота»? (что такое P-полнота знаю, что такое NP-полнота знаю, что такое P/NP полнота — не знаю)
        И что такое анализ алгоритма на нее? (что такое анализ алгоритма на P полноту — не знаю, что такое анализ алгоритма на NP полноту — не знаю)

        А новизна в том, что предложен алгоритм, работающий быстрее чем всё, что было известно раньше.


    1. PsyHaSTe
      22.12.2015 10:18

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


    1. avsmal
      22.12.2015 17:34

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

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


      1. Nashev
        25.12.2015 00:55

        Вы разобрались, в чём фишка? Можете пересказать?


        1. avsmal
          25.12.2015 03:03

          Насколько я понимаю, там нет какой-то «фишки», по которой можно понять так сразу как алгоритм работает. Это сложный алгоритм с очень сложным анализом. Сейчас объяснение основных идей алгоритма и оценки его времени работы занимает три лекции для хорошо подготовленной аудитории. Для этого нужен определённый бекграунд, необходимо понимать, что это за задача, и какие есть проблемы на пути к её решению. В CS клубе был соответствующий курс: old.compsciclub.ru/courses/graphisomorphism
          Но для понимания алгоритма этого недостаточно — нужно намного больше знаний и в т.ч. очень хорошее понимание алгебры.
          Можете для интереса глянуть в статью: arxiv.org/pdf/1512.03547v1.pdf
          Если не готовы читать оригинал, то смотрите обзорные статьи вроде этой:
          jeremykun.com/2015/11/12/a-quasipolynomial-time-algorithm-for-graph-isomorphism-the-details


  1. stas404
    16.12.2015 22:29
    +2

    Бабая боятся не только дети, но и изоморфные графы.