Недавно я наткнулся на книгу “Topics in Algorithmic Graph Theory” (Cambridge UP, 2021), и честно говоря, она меня впечатлила

Недавно я наткнулся на книгу “Topics in Algorithmic Graph Theory” (Cambridge UP, 2021), и честно говоря, она меня впечатлила. Это сборник глав от разных авторов, но благодаря редакторам всё написано в одном стиле и читается как цельный труд. Это не учебник, а именно сборник обзорных глав, но что приятно они согласованы по стилю, и читаются как единое целое. Главная фишка книги это показать, что сложные алгоритмы часто становятся простыми, если правильно понять структуру графа.

Например, для хордальных графов (те, где нет длинных циклов без хорд) классическая задача минимальной раскраски решается за полиномиальное время динамическими методами. В книге это аккуратно объясняется через понятие perfect elimination ordering.

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

В отдельной главе рассматриваются leaf powers графы, которые можно представить как степени листьев дерева. Для них разработаны специальные алгоритмы распознавания и раскраски.

Кроме того, есть обзор по property testing как случайным образом проверить большое свойство (например, «граф двудольный») за время, меньшее линейного, исследуя лишь малую часть рёбер.

Есть и «тяжёлая артиллерия» главы про гомоморфизмы графов (связь с CSP), про разреженные графы и теорию Нешетрила–Осонна де Мендеса, где через разложение по деревьям и ограниченную плотность открывается целый класс быстрых алгоритмов.

В конце обсуждаются и экспоненциальные алгоритмы, например, для поиска максимального независимого множества используются методы meet-in-the-middle и ограниченные перечисления.

Впечатление у меня такое - это книга-путеводитель для тех, кто уже знаком с теорией графов, но хочет глубже понять, где именно структура «ломает» барьеры сложности. Читается местами непросто, но открывает шикарные перспективы от раскрасок до модель-теоретической сложности.

Телеграм: t.me/ainewsline

Источник: vk.com

Комментарии: