Сложность и методы решения алгоритмических проблем теории раскрасок графов и теории обобщенных паросочетаний : отчет о научно-исследовательской работе (заключительный) / БГУ ; научный руководитель О. И. Дугинов

Abstract

Объектами исследования являются реберные раскраски графов и обобщенные паросочетания графов. Цель работы – исследование сложности решения оптимизационных графовых задач в содержательных классах графов, а также получение новых структурных свойств графов, которые могут быть полезны в такого рода исследованиях. Основные результаты исследований. Предложены оценки наибольшего (наименьшего) числа вершин в максимальном диссоциирующем множестве графа. Установлено, что задача нахождения максимального диссоциирующего множества наибольшей мощности NP-трудна для квазихордальных двудольных графов. Кроме этого, установлено, что задача нахождения максимального диссоциирующего множества наименьшей мощности NP-трудна для хордальных двудольных графов, двудольных графов с максимальной степенью вершин, равной 3, планарных графов с большим обхватом, а также для классов графов, характеризуемых конечными списками запрещенных порожденных двусвязных подграфов. Предлагается линейный алгоритм решения последней задачи в классе деревьев. Установлено, что задача разбиения графа на простые цепи фиксированной длины NP-трудна в классе двудольных планарных субкубических графов с большим обхватом, в классе расщепляемых графов (в случае, когда длина цепей не меньше 4). Предложен полиномиальный алгоритм решения варианта этой задачи в предположении, что длины цепей равны трем и граф расщепляемый. Показано, что запрещение любого субкубического 8-рёберного леса порождает класс с полиномиальной разрешимостью задачи о рёберной раскраске, кроме случаев, образованных дизъюнктной суммой одного из четырёх лесов и пустого графа.