Исследование "критических" наследственных классов в анализе вычислительной сложности задач на графах

• Автор: Малышев, Дмитрий Сергеевич
• Шифр специальности: 01.01.09
• Научная степень: Докторская
• Год защиты: 2014
• Место защиты: Москва
• Количество страниц: 175 с.

Оглавление
Введение
1 Граничные классы графов: значение и примеры
1.1 Некоторые обозначения и определения
1.1.1 Множества
1.1.2 Отношения
1.1.3 Графы и подграфы
1.1.4 Множества вершин и числовые характеристики
1.1.5 Классы графов
1.2 «Критические» наследственные классы графов
1.3 Расширение пределов справедливости теоремы В.Е. Алексеева
1.4 Критерий граничности
1.5 Новые случаи граничности класса Т и его производных
1.5.1 Условия граничности классов Т и V
1.5.2 Множество задач па графах с граничными классами 7~
и Т> континуальной мощности
1.5.3 Древесная ширина и кликовая ширина графов и их применение при установлении граничности классов Т иР
1.5.4 Производные от Т классы и некоторые случаи их граничности
2 Относительные граничные системы и их свойства
2.1 Относительные граничные классы

2.2 Строение относительной граничной системы для ряда задач на
графах
2.2.1 Критерий полноты множества относительных граничных классов
2.2.2 Относительные граничные системы из производных класса Т”
2.2.3 Граничные классы графов для задач о списковом ранжировании относительно лесов
2.3 Факторизация решетки наследственных классов графов и се
свойства
2.3.1 Критерий принадлежности общему фактор-классу и «избыточные» классы эквивалентности
2.3.2 О независимости понятий минимального сложного, абсолютного граничного и относительного граничного классов графов
2.3.3 Об одном свойстве относительных граничных классов в задаче о наибольшем двудольном планарном подграфе
2.3.4 Подмножества относительных граничных систем и их свойства
Полиномиальная разрешимость задачи НМ для некоторых
классов графов
3.1 Гипотеза В.Е. Алексеева и сс варианты
3.2 Расширяющие операторы для задачи о независимом множестве
3.2.1 О НМ-расширясмости оператора {Р,С~,,С} —у
{Р:,.а,Со А',}
3.2.2 О НМ-расширясмости оператора {Рй,С$, Н} —у
{Р5,С-0,НоО2,Н@К1,р}
3.3 Полиномиальная разрешимость задачи НМ в классе планарных
графов, не содержащих больших порожденных яблок
3.3.1 Разделяющие клики и С-блоки
3.3.2 Свойства планарных графов без больших порожденных звезд
3.3.3 Минорно бозапексные графы большой древесной ширины
3.3.4 Доказательство основного результата первой части главы
3.4 Полиномиальная разрешимость задачи НМ в классе субкуби-
чсских планарных графов без порожденного подграфа Т2,г
3.4.1 Вспомогательные результаты
3.4.2 Присоединенные циклы и их разрушение
3.4.3 Гармони и их разрушение
3.4.4 Основные результаты второй части главы
4 О задачах на графах с континуальными граничными системами
4.1 Некоторые результаты из количественной теории граничных
классов и смежные с ними
4.2 Граничные классы графов для задач о 3-раскраске
4.3 Свойства подмножеств З-РР-граиичной системы
4.4 Граничные классы графов для задач о fc-раскраскс
4.5 Сравнительный анализ граничных систем для задач о к-
раскраске и о хроматическом числе и индексе
5 «Критические» классы графов для задачи о реберном списковом ранжировании
5.1 Краткое описание основных результатов пятой главы
5.2 Новые минимальные РСР-сложпыс случаи
5.2.1 О минимальной РСР-сложпости класса графов Bat
5.2.2 О минимальной PCP-сложности классов графов Comb, Camomile и Clique
5.3 Новые РСР-грапичныс случаи

при помощи следующих четырех операций:
• создание новой вершины с любой, в т.н. уже использованной, меткой
• объединение двух любых созданных графов с исисресекагощимися множествами вершин
• выбор двух имеющихся меток І Ф 2 и соединение ребром каждой вершины с меткой г с каждой вершиной с меткой ]
• переименование метки любой вершины па любую другую метку
Эквивалентно, процесс создания графа б может быть представлен в виде корневого дерева, корню которого соответствует сам граф С, листьям соответствуют создания вершин, а всем внутренним узлам — бессвязные объединения уже имеющихся графов и добавления ребер. Переименования меток приписаны некоторым ребрам дерева.
Древесная ширина графа — мера близости к лесу, поскольку Ьш{С) = 1 имеет место тогда и только тогда, когда (7 — лес. С другой стороны, равенство £гн(С) = |И((7)| — 1 выполнено только для полного графа (7. Кликовая ширина графа — более тонкая характеристика графа, чем древесная ширина. Так, например, сги(Кп) = 2 при п > 2 и си>(Сф = 2, сги[Рф) = 3 (и, вообще, сги(Є) < 2 тогда и только тогда, когда (7 Є РгееДРД) [47]). Ограниченность кликовой ширины влечет полиномиальную разрешимость задач для более широких классов графов, чем ограниченность древесной (правда, случаев ограниченности древесной ширины известно гораздо больше, чем случаев ограниченности кликовой). В классах графов с ограниченными степенями вершин ограниченности обеих характеристик эквивалентны [47].
Лемма 1.5 [63]. Для любых графов <7і Є Т, (72 Є V и любого натурального чита сі существует такое число С = С((7і, Сг, <7), что древесная ширина и кликовая ширина любого графа из класса Т>едД) П ТТее({Єі, Са}) ограничены сверху числом С.