Семинар по алгоритмам и структурам данных "Полиномиальный алгоритм распознавания точной степени 3 графов-деревьев"

14 октября 2025 в 18:10

Докладчик: Никита Мануйленко, ФКН НИУ ВШЭ

Тема: Полиномиальный алгоритм распознавания точной степени 3 графов-деревьев.

Аннотация: Вопрос степеней графов изучается с 1960-го года. Степень n графа G — это граф G’ на том же множестве вершин, где между парой вершин есть ребро тогда и только тогда, когда длина пути между этими вершинами в G не превосходит n. Доказано, что распознавание, является ли данный граф степенью 2 какого-то графа — NP-полная задача, и может быть решена за полиномиальное время только для некоторых подклассов графов.
Вопрос точной степени n графа G очень похож, но здесь мы ограничиваемся ребрами в графе G’ тогда, когда между соответствующей парой вершин в графе G существует простой путь длины n. Доказано, что возможно за полиномиальное время определить, является ли граф точной степенью 2 какого-то графа. В нашей работе нам удалось доказать, что задача распознавания, является ли граф точной степенью 3 графа-дерева, также является полиномиально разрешимой.

Место проведения: Покровский бульвар 11, аудитория D109.