Семинар МЛ ТИ "Исследование трудоемкости задач. О доминирующем множестве и о вершинной 3-раскраске в некоторых наследственных классах графов"

Дата: 29 января 2026 г., 18:10 - 19:30

Докладчик: Григорий Дахно, аспирант, Нижний Новгород

Аннотация: Задачи о доминирующем множестве и о вершинной 3-раскраске являются классическими задачами алгоритмической теории графов. Первая из них состоит для заданных графа и числа k  в том, чтобы определить, а имеется ли в графе подмножество из k вершин такое, что любая вершина графа вне подмножества имеет соседа в подмножестве. Вторая задача для заданного графа состоит в том, чтобы распознать, а можно ли множество его вершин разбить на три подмножества попарно несмежных вершин.

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

Для задач о доминирующем множестве и о вершинной 3-раскраске известны полные классификации их трудоемкостей для порожденных запрещенных фрагментов с 5 вершинами каждый. Следующий шаг – рассмотрение 6-вершинных запретов для продвижения фронтира о полных дихотомиях сложности. Доклад, в основном, будет посвящен результатам, полученным в этом направлении. Это доклад автора по его подготовленной кандидатской диссертации.

Место проведения:

Онлайн: Zoom

Идентификатор конференции: 879 9957 4812
Код доступа: 411952