Исследование "критических" наследственных классов в анализе вычислительной сложности задач на графах тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

На правах рукописи

Малышев Дмитрий Сергеевич

ИССЛЕДОВАНИЕ «КРИТИЧЕСКИХ» НАСЛЕДСТВЕННЫХ КЛАССОВ В АНАЛИЗЕ ВЫЧИСЛИТЕЛЬНОЙ СЛОЖНОСТИ ЗАДАЧ

НА ГРАФАХ

01.01.09 — «дискретная математика и математическая кибернетика»

АВТОРЕФЕРАТ диссертации на соискание ученой степени доктора физико-математических наук

2 7 НАР 2014

Москва — 2014 г.

005546401

005546401

Работа выполнена на кафедре математической логики и высшей алгебры ННГУ им. Н. И. Лобачевского

Научный консультант: д.ф.-м.н., проф. Алексеев Владимир Евгеньевич

Официальные оппоненты: д.ф.-м.н., зав. каф., проф. Бондаренко Владимир Александрович (ЯрГУ) д.ф.-м.н., в.н.с. Пяткин Артем Валерьевич (ИМ СО РАН) д.ф.-м.н., проф. Райгородский Андрей Михайлович (МГУ)

Ведущая организация:

Вычислительный центр РАН

Защита диссертации состоится ¿О/хД 2014 года в 11 ча-

сов 00 минут на заседании диссертационного совета Д 501.001.44 при Московском государственном университете им. М.В. Ломоносова по адресу: 119991, ГСП-1, г. Москва, Ленинские горы, 2-ой учебный корпус, аудитория 685.

С диссертацией можно ознакомиться в Фундаментальной библиотеке МГУ имени М.В. Ломоносова. С текстом автореферата можно ознакомиться на официальном сайте факультета ВМК МГУ http:Wcs.msu.ru в разделе «Наука»—«Работа диссертационных советов»—«Д 501.001.44».

Автореферат разослан «_»_2014 года.

Ученый секретарь диссертационного совета

В.А. Костенко

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ Актуальность темы исследований

Принято считать, что алгоритм является эффективным, если время его работы на детерминированной машине Тьюринга (или на каком-нибудь другом универсальном вычислительном устройстве) ограниченно сверху полиномом от длины входных данных1. Вместе с тем, имеется ряд «неподдающихся» (называемых в теории сложности вычислений ИР-полными) задач, для которых в настоящее время не разработано полиномиальных алгоритмов. Накопленный опыт исследования данных задач и практика их решения дают веские основания предполагать, что таких процедур вообще не существует.

На настоящее время имеется огромное количество результатов о полиномиальной разрешимости и о КР-полноте многих задач на графах при разнообразных ограничениях на класс рассматриваемых графов2. Среди направляющих мотивов к получению новых сведений такого рода можно выделить два наиболее распространенных. Это выявление более широких случаев полиномиальной разрешимости задачи и поиск сужений, для которых задача сохраняет ^-полноту. Переход от рассмотрения отдельных классов к рассмотрению семейств классов графов придает определенную систематичность процессу поиска полиномиальных и ИР-полных случаев, а также позволяет рассматривать проблемы более общего содержания, чем, скажем, выяснение вычислительной сложности задачи для какого-нибудь класса. Так, для какой-нибудь задачи на графах можно попытаться получить полное описание «простых» и «сложных» классов из рассматриваемого семейства или исчерпывающее описание «линии водораздела» между «простой» и «сложной» его частями. Некоторые результаты данной работы показывают, что эти цели иногда достижимы.

Реализуемость обозначенных выше намерений обусловлена, как минимум, надлежащим выбором рассматриваемого семейства классов графов.

1 Гэри М., Джонсон Д. Вычислительные машины и труднорешаем ые задачи. — М.: Мир, 1982. — 416 Стр.

2см., например, электронный ресурс http://www.graphclasses.org

Так, удаление графа из класса не меняет сложностного статуса задачи. Это же верно и при добавлении графа к классу. Поэтому целесообразно рассматривать те семейства классов, для которых удаление или добавление одного графа приводит к необходимости выполнения сразу нескольких таких операций (ввиду, например, какой-нибудь замкнутости данных классов).

В диссертации рассматривается континуальное семейство наследственных классов графов, т.е. множеств графов, замкнутых относительно изоморфизма и удаления вершин. Данные классы (и только они) допускают описание через запрещенные порожденные подграфы. Это компактное представление наследственных классов (или порождающих их наследственных свойств) является распространенным способом описания. Повышенный интерес именно к наследственным классам не случаен. Так, В.Е. Алексеевым3 сравнительно недавно было введено понятие граничного класса графов и обоснована его полезность для анализа сложности задач на графах. Именно, наследственный класс с конечным множеством запрещенных порожденных подграфов (конечно определенный класс) является «сложным» для данной задачи тогда и только тогда, когда он содержит некоторый граничный для этой задачи подкласс. Тем самым, если для некоторой задачи известна граничная система (т.е. множество граничных классов графов), то для нее имеет место полное описание всех «простых» и «сложных» конечно определенных классов. Поэтому граничные классы могут быть названы «критическими», поскольку они имеют особое значение в анализе вычислительной сложности. Отметим, что особая роль некоторых классов осознавалась4,5 и ранее публикации3, все они впоследствии оказались граничными для соответствующих задач.

Если исключить работы автора, то можно заметить, что исследования в

'Alekseev V.E. On easy and hard classes of graphs with respect to the independent set problem // Discrete Applied Mathematics. - 2004. — V. 132. - P. 17-26

4Алексеев В.Е. О влиянии локальных ограничений на сложность определения числа независимости графа // Комбинаторпо-алгебраические методы в прикладной математике. — Горький: Изд-во Горьковского ун-та, 1982. — С. 3-13

5Алексеев В.Е., Коробицьт Д.В. О сложности некоторых задач на наследственных классах графов // Дискретная математика. — 1992. - Т.4, №4. — С. 34-40

теории граничных классов графов велись и ведутся только в двух направлениях. Первое из них — выявление граничных классов графов для некоторых задач на графах. Отметим работы В.Е. Алексеева3,4,5,6'7, Р. Боляч7,8, Д.В. Коробицына5,6,7, В.В. Лозина6,7,8,9,10, Н. Корнелайнена9, К. Пурцеля10, А. Тискина9. Второе направление составляют попытки дать полное описание граничных систем для тех или иных задач на графах11.

Для любой задачи на графах элементы границы между «простыми» и «сложными» частями семейства наследственных классов являются естественными «критическими» классами. Ни для одной NP-полной задачи нет максимальных (по включению) «простых» наследственных случаев. В работе В.Е. Алексеева3 это утверждается про задачу о независимом множестве, но все рассуждения легко переносятся и на общий случай. В работе?2 было показано, что для некоторого типа задач нет и минимальных (по включению) «сложных» наследственных случаев. Там же для некоторых задач на графах были выявлены такие классы. Это все, что было известно про элементы границы до результатов настоящей диссертации.

Многие важные вопросы теории «критических» классов графов являлись открытыми, причем некоторые из них в течении нескольких десятилетий. Например, полное описание граничных (или минимальных «сложных») классов для какой-нибудь задачи на графах. Или, напротив, выявление причин неудач в попытках получения такого описания.

Развитию метода «критических» классов графов для решения проблемы демаркации посвящена данная диссертация. В ней, в частности, получены ответы на сформулированные выше вопросы. Некоторые направления

öAlekseev V.E., Korobitsyn D.V., Lozin V.V. Boundary classes of graphs for the dominating set problem // Discrete Mathematics. — 2004. - V. 285. - P. 1-6

7Alekseev V.E., Boliac R., Korobitsyn D.V., Lozin V.V. NP-hard graph problems and boundary classes of graphs // Theoretical Computer Science. — 2007. — V. — 389. — P. 219-236

aBoliac R., Lozin V.V. Independent domination in finitely defined classes of graphs // Theoretical Computer Science. — 2003. - V. 301. - P. 271-284

9Korpe]ainen N., Lozin V.V., Malyshev D.S., Tiskin A. Boundary properties of graphs for algorithmic graph problems //' Theoretical Computer Science. — 2011. — V. 412. — P. 3545 3554

10Lozin V.V., Purcell C. Boundary properties of the satisfiability problems// Information Processing Letters. — 2013. — V. 113. - P. 313-317

1'Lozin V.V. Boundary classes of planar graphs // Combinatorics, Probability and Computing. — 2008. — V. 17. — P. 287-295 1гМалышев Д.С. О минимальных сложных классах графов // Дискретный анализ и исследование операций. — 2009. - Т.16, №6. - С. 43-51

исследований в работе являются новыми направлениями в теории «критических» классов графов (теория минимальных «сложных» классов) или новыми разделами ее направлений (количественные вопросы теории «критических» классов).

Цель работы

Целью работы является классификация наследственных классов по алгоритмической сложности некоторых задач на графах, основанная на выявлении «критических» классов графов.

Методы исследования

В диссертации использованы методы теории графов, комбинаторного анализа и теории сложности вычислений.

Основные результаты работы и их научная новизна

Все полученные в диссертации результаты являются новыми. Наиболее важными из них являются следующие:

1. Доказано, что для задач о списковом ранжировании граничные системы относительно класса лесов состоят в точности из трех конкретных классов графов.

2. Впервые рассмотрена факторизация семейства наследственных классов по отношению равенства относительных граничных систем. Сформулирован критерий принадлежности двух наследственных классов общему классу эквивалентности по этому отношению. Показано, что при некоторых условиях граничные системы относительно объединений и пересечений двух наследственных классов выражаются через граничные системы относительно этих наследственных классов. Доказан ряд результатов о представимости и непредставимости подмножеств относительных граничных систем в виде других относительных граничных систем.

3. Рассмотрен вопрос о единственности некоторого класса графов как граничного для задачи о независимом множестве относительно множества субкубических планар-ных графов. Эта единственность эквивалентна полиномиальной разрешимости задачи для некоторого бесконечного семейства классов графов. Установлена полиномиальная разрешимость задачи о независимом множестве для некоторого подсемейства данного семейства.

4. Доказано, что при к > 3 для обеих задач о А-раскраске (вершинного и реберного вариантов), для задач о хроматическом числе и индексе граничные системы являются

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

5. Показано, что каждый граничный класс для задачи о реберной 3-раскраске является граничным и для задачи о хроматическом индексе. С другой стороны, оказалось, что при любом к > 3 существует континуум граничных классов для задачи о реберной к-раскраске, каждый из которых не является граничным для задачи о хроматическом индексе. Доказано, что граничные системы для задач о вершинной ¿'-раскраске не определяют граничную систему для задачи о хроматическом числе. Именно, некоторый конкретный класс графов является граничным для задачи о хроматическом числе, но не является граничным для задачи о вершинной fc-раскраске ни при каком к.

6. Получен критерий эффективной разрешимости задачи о реберном списковом ранжировании (задачи PCP) в некотором достаточно представительном семействе из наследственных классов графов, содержащем все конечно определенные и все минорно замкнутые классы. Из него в качестве следствия получено, что граничную систему для задачи PCP образуют ровно 10 конкретных классов графов. Это первый результат о полном описании граничных систем с момента первой публикации4 по граничным классам. Из полученного критерия также следует, что существует всего пять конечно определенных минимальных PCP-сложных классов и ровно один минорно замкнутый минимальный PCP-сложный класс. Все эти шесть классов явным образом описаны.

7. Доказано достаточное условие существования минимальных сложных классов. На его основе конструктивным образом показано, что для любого натурального к есть задача на графах, имеющая ровно к минимальных сложных классов (которые удается явным образом описать). Это первые примеры полного описания минимальных сложных классов.

8. Приведены примеры, демонстрирующие, что относительный граничный класс не всегда является граничным в абсолютном смысле и что минимальный сложный класс не всегда является граничным.

Теоретическая и практическая значимость

Работа носит теоретический характер. Результаты диссертации могут применяться при сложностном анализе различных задач на графах в семействе наследственных классов графов, разработке и чтении курсов и спецкурсов по теории графов, анализу и разработке алгоритмов.

Личный вклад соискателя

Все перечисленные ранее основные результаты диссертации были получены автором лично.

Результаты работ [1,2] из списка публикаций были получены совместно с В.Е. Алексеевым. Основным результатом в [1] является критерий гранично-сти произвольного класса графов. Он приведен в первой главе диссертации с целью демонстрации более современных методов установления гранично-сти двух известных классов графов, чем использовавшиеся ранее3'6,7. Ни одно из утверждений первой главы диссертации не выносится на защиту. Авторство в публикации [2] в равной степени разделяют В.Е. Алексеев и Д.С. Малышев. Статья [21] была написана В.Е. Алексеевым, В.В. Лозиным, автором и М. Миланичем на паритетных началах. Результаты этих двух публикаций не выносятся на защиту, но используются при доказательстве третьего результата из списка основных. В публикации [9] В.Е. Алексееву принадлежат улучшения в оценках рамсеевского типа, которые не усиливают ее основной результат, изначально полученный Д.С. Малышевым. Он совпадает с первым из основных результатов диссертации. Совместная работа [22] состоит из двух частей. Авторство первой части (про задачу о гамильтоновом цикле) разделяют Н. Корпелайнен, В.В. Лозин, А. Тискин. Вторая часть (про задачу о раскраске) была написана Д.С. Малышевым.

Апробация работы и публикации

Результаты, полученные в диссертации, докладывались и обсуждались на следующих конференциях, семинарах и симпозиумах:

• XV, XVI международные конференции «Проблемы теоретической кибернетики» (Казань, 2008; Нижний Новгород, 2011)

• VIII международная конференция «Дискретные модели в теории управляющих систем» (Моск. обл., 2009)

• X и XI международные семинары «Дискретная математика и ее приложения» (Москва, 2010, 2012)

• 33rd international symposium on mathematical foundations of computer sciencc (Torun, 2008)

• 2nd and 3rd international conferences on network analysis (Nizhniy Novgorod, 2012, 2013)

• 35-ый одесский семинар но дискретной математике (Одесса, 2013)

• семинары кафедры математической кибернетики МГУ «Дискретный анализ» (руководитель A.A. Сапоженко)

• семинар кафедры математической кибернетики МГУ «Дискретная математика и математическая кибернетика» (руководители В.Б. Алексеев, A.A. Сапоженко, С.А. Ложкин)

• семинар Вычислительного Центра РАН по теории сложности вычислений (руководитель В.К. Леонтьев)

• общегородские семинары г. Н. Новгорода по дискретной математике (руководитель В.Н. Шевченко)

• семинар лаборатории алгоритмов и технологий анализа сетевых структур (руководители В.А. Калягин, В.В. Чистяков)

• семинар НИИ ПМК при ННГУ (руководители Д.В. Баландин, Г.В. Осипов, Н.В. Дерендяев)

• семинар лаборатории «Дискретная и вычислительная геометрия» (руководители В.Л. Дольников, В.А. Бондаренко)

• Объединенный семинар отдела теоретической кибернетики ИМ СО РАН (руководители Э.Х. Гимади, А.И. Ерзин)

• межкафедральный семинар МФТИ по дискретной математике (руководитель A.M. Райгородский)

• семинар нижегородского математического общества (руководитель Г.М. Полотовский)

• семинар кафедры математической кибернетики БГУ по теории графов и комбинаторному анализу (руководитель Р.И. Тышкевич)

• семинар института кибернетики им. В.М. Глушкова (руководитель П.И. Стсцюк)

По теме диссертации опубликовано 23 работы из текущего списка ведущих рецензируемых изданий ВАК РФ. Они приведены в конце автореферата. Все публикации, кроме [11] и [17], в журналах, оригинальная или переводная версия которых включена как в базу цитирований Scopus, так и в базу цитирований MathSciNet; публикации [22] и [23] в журналах, включенных в базу цитирований Web of Science.

Исследования, оформленные в диссертацию, были поддержаны грантами РФФИ 10-01-00357-а, 11-01-00107-а, 12-01-00749-а; грантами МинОбрНау-ки РФ в рамках ФЦП «Научные и научно-педагогические кадры инновационной России на 2009-2013 гг.» 16.740.11.0310 и 14.В37.21.0393; грантом Президента РФ МК-1148.2013.1; грантом НФ НИУ ВШЭ 12-01-0035; лабораторией алгоритмов и технологий анализа сетевых структур НИУ ВШЭ, грант Правительства РФ 11.G34.31.0057.

Структура и объем работы

Диссертация состоит из введения, шести глав и списка литературы, включающего 78 наименований. Общий объем диссертации составляет 175 страниц. Нумерация всех теорем и лемм ведется независимо внутри каждой главы, причем номер каждого такого утверждения состоит из двух частей, первая из которых соответствует номеру главы, вторая порядковому номеру внутри главы.

КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ

Во введении обосновывается актуальность темы исследований и кратко излагаются основные результаты диссертации.

В главе 1 приводится ряд определений, вводятся понятия граничного и минимального сложного классов графов, расширяются пределы приме-

нимости теоремы В.Е. Алексеева, доказываются условия граничности, а также устанавливается граничность некоторых классов для ряда задач на графах.

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

Напомним, что наследственным классом называется множество графов, замкнутое относительно изоморфизма и удаления вершин. Известно, что любой такой класс X может быть задан множеством своих запрещенных порожденных подграфов при этом принята запись X = Ргее{5). Для любого наследственного класса X минимальное по включению множество 5 с данным свойством существует, единственно и обозначается через РогЬ(Х). Если РогЬ(Х) конечно, то X называется конечно определенным.

Пусть П — произвольная NP-пoлнaя задача на графах. Наследственный класс называется П-простым, если задача П для графов из этого класса полиномиально разрешима, и П-сложным в противном случае. На протяжении всей работы предполагается, что Р ^ А1Р и это условие не включается явно в формулировки соответствующих утверждений. Например, такого: если задача П является ^-полной в классе X, то X является П-сложным. Если несколько иначе определить понятие П-сложного класса графов (как наследственного класса с NP-полной задачей П), то подавляющее большинство утверждений диссертации (именно в представленной формулировке) также справедливы (а, значит, независимо от гипотезы Р Ф МР). Наследственный класс графов X называется 11-предельным, если существует такая бесконечная последовательность Х\ Э Хъ 2 • • • П-сложных классов

с»

графов, что X = |"| Х{. Минимальный по включению П-предельный класс «=1

называется П-граничным.

Понятие граничного класса графов было введено В.Е. Алексеевым, им же было доказано следующее утверждение, показывающее значение этого понятия.

Теорема 1.1. Конечно определенный класс являетсяП-сложным тогда

и только тогда, когда в нем содержится какой-либо И-граничный класс.

Минимальные по включению П-сложные классы и максимальные по включению П-простые классы названы в диссертации минимальными П-сложными и максимальными П-простыми соответственно. Во втором разделе объясняется, почему ни для одной ИР-полной задачи на графах нет максимальных простых случаев.

В третьем разделе диссертации расширяется множество «сложных» случаев по сравнению с конечно определенными классами, включающими граничные классы. Именно, показывается, каким образом при известной граничной системе для заданных наследственного класса X и числа к проверить существование класса У С X с не более чем к запрещенными фрагментами, который включает некоторый граничный класс.

В четвертом разделе доказывается следующий критерий граничности произвольного класса графов.

Теорема 1.3. П-предельный класс X является П-граничным тогда и только тогда, когда для каждого С? е X существует такое конечное множество графов С РогЪ(Х), что класс Ргее(За и {С?}) является П-простым.

В пятом разделе на основе общего критерия граничности формулируются достаточные условия граничности некоторых двух классов графов. Один из них — класс Т, состоящий из лесов, каждая компонента связности которых имеет не более трех листьев. Множество реберных графов к графам класса Т обозначается через Т>. В пятом разделе первой главы выявляются новые случаи граничности классов Т иТ>. Например, там приводится континуальная совокупность задач на графах, для каждой из которых оба этих класса являются граничными одновременно (теорема 1.5). Там же приводятся случаи граничности некоторых производных от Т классов графов. Результаты первой главы опубликованы в работах [2,4,23].

В главе 2 вводится понятие относительного граничного класса, описываются относительные граничные системы для ряда случаев и исследуется

факторизация семейства наследственных классов по отношению равенства относительных граничных систем.

В первом разделе вводится понятие относительного граничного класса, формулируемое следующим образом. Пусть X — какой-нибудь П-сложный класс. Наследственный класс графов [У называется П-предельным относительно класса А", если существует такая последовательность Ух 3 у2 3 ...

оо

П-сложных подклассов класса X, что Р| = У- Минимальный по вклю-

! = 1

чению П-предельный относительно X класс называется П-граничным относительно X классом. Значение понятия П-граничного класса относительно X состоит в том, что класс X П Ргсе(Б), где 5 — произвольное конечное множество графов, является П-сложным тогда и только тогда, когда X П Ргее{Б) включает какой-нибудь П-граничный относительно X класс. Через £$п{Х) обозначается XI-граничная относительно X система, т.е. множество П-граничных относительно X классов графов.

Во втором разделе рассматриваются некоторые задачи на графах. Одна из них — задача о доминирующем множестве (задача ДМ), состоящая в том, чтобы найти в заданном графе б = (V, Е) такое подмножество V' С V минимальной мощности, что каждая вершина из V \ V' смежна хотя бы с одной вершиной из V'. Другими задачами являются задачи о списковом ранжировании, постановки которых состоят в следующем.

Пусть заданы граф б с множеством вершин V и множество £ = {Ь(у) : V 6 V}, где каждое Ь(у) — конечное множество натуральных чисел (цветов, в которые разрешается покрасить вершину у). Аранжированием вершин графа С называется такая раскраска с его вершин, что:

1) с(у) е Ь(у) для каждой вершины у,

2) если с(ух) = с(у2), VI ф У2, то каждый путь, соединяющий У\ и г>2, содержит такую вершину г^з, что с(г>з) > с(у{).

Задача о вершинном списковом ранжировании (задача ВСР) состоит в том, чтобы по данным С и £ определить, существует ли ¿-ранжирование вершин графа <3. Уточним, что под ВСР-простым классом графов далее

понимается такой наследственный класс, что задача ВСР решается для графов из этого класса за полиномиальное время при любом назначении £. Понятия ¿-ранжирования ребер графа, задачи о реберном списковом ранжировании (задачи РСР) вводятся по аналогии путем замены слова «вершина» на слово «ребро». Аналогично уточняется понятие РСР-простого класса.

Задачи о списковом ранжировании имеют приложения в параллельном вычислении разложения Холецкого13, в проектировании СБИС14, в параллельной обработке запроса к базе данных15, в сборке изделия, состоящего из нескольких модулей16.

Наследственным 'замыканием класса X (которое обозначается через \Х\) называется совокупность порожденных подграфов графов из X. Для множества графов X через Q(X) обозначается множество {G : ЗЯ G X,V(G) = V(H) U Е(Н) и E(G) = : «1,«2 е У(Н),ы ф v2) U

{(v,e) : v € V{H),e € E{H), вершина v в графе Я инцидента ребру е}}. Через Q обозначается множество всех графов.

Во втором разделе доказано следующее утверждение.

Теорема 2.3. Класс [Q(T)] является единственным ¡Щ-граничным относительно [Q(Q)]-

Триодом Titj:k (i,j,k > 0) называется дерево, получаемое соединением одной вершины с тремя другими простыми путями длины i,j,k соответственно. Через Si обозначается граф, получаемый подразбиением каждого ребра графа Kiti. Граф Com, — результат отождествления вершины степени i графа Кс одним из концов пути Р,. Через Т, Star, Comet обозна-

' ОО ОО 00

чаются наследственные замыкания множеств U U {Сот{}

i= 1 »=1 ¿=1

соответственно.

Теорема 2.8. ВС?-граничная система относительно класса лесов со-

lsl,iu J. The role of elimination trees in sparse factorization // SIAM J. Matrix Analysis and Appl. — 1990. — V. 11. — P. 134-172

'"Leiserson C. Area-efficient graph layout (for VLSI) // Proc. 21st Ann IEEE Symp. on Foundations of Computer Science. - 1980. - P. 270 -281

"Makino K., Uno. Y, Ibaraki T. Minimum edge ranking spanning trees of threshold graphs // Lecture Notes in Computer

Scince. - 2002. - V. 2518. - P. 428-440 "Dereniowski D. Edge ranking of weighted trees // Discrete Applied Mathematics. - 2006. - V. 154. - P. 1198-1209

стоит из классов Comet, Star и Т. Они oice образуют РСР-граничную систему относительно класса лесов.

Во всех ранее известных результатах о полном описании относительных граничных систем утверждалось, что классы Т и V одновременно образуют относительную граничную систему. Соответствующие доказательства следуют ходу рассуждений, намеченному Лозиным11, поскольку одновременная относительная граничность Т и V означает появление ряда «хороших» свойств. Теоремы 2.3 и 2.8 являются первыми результатами о полном описании относительных граничных систем, не вписывающимися в эту схему.

До результатов диссертации для относительных граничных систем рассматривались только вопросы полного их описания. В третьем разделе впервые рассматриваются вопросы более общего содержания. Там, например, рассматривается отношение равенства относительных граничных систем на множестве всех наследственных классов. Критерием принадлежности двух наследственных классов общему классу эквивалентности по этому отношению является следующее утверждение.

Теорема 2.9. Равенство = &п(У) имеет место тогда и

только тогда, когда для любого конечного множества графов S классы X ПFree{S) uj'n Free{S) либо одновременно П-простые, либо одновременно П-сложные.

Удается обнаружить некоторые закономерности между

&п(ХУ),&п(ХиУ) и &и(Х)МУ).

Теорема 2.10. Пусть X является конечно определенным классом. Тогда для любого наследственного класса У справедливо равенство &п(У П

X) = {В е &п(У) ■ вех}.

В диссертации показывается, что для произвольного наследственного класса X формула &П(У П X) = {В 6 @п(У) ■ В С X} не верна. Приведены примеры, демонстрирующие, что возможны оба включения: ^п(УПХ) Э{В€ &П(У) : ВС X} и ^п(УГ)Х) С {В € &П(У) : В С X}.

14

Поэтому, в общем случае существование функциональной связи между ^п(УПХ) и маловероятно. Вместе с тем, граничная систе-

ма относительно объединения двух наследственных классов выражается через граничные системы относительно этих наследственных классов при довольно слабых предположениях.

Лемма 2.9. Если в классе графов X и У задача распознавания принадлежности графа хотя бы одному из наследственных классов X, У решается за полиномиальное время, то &п{Х и У) =< ЗЩ) и ЯП(У) >.

В третьем разделе приведены примеры, демонстрирующие, что относительный граничный класс не всегда является граничным и что минимальный сложный класс не всегда является граничным (теорема 2.12). Эти примеры довольно неожиданны, т.к. долгое время предполагалось обратное. Поэтому теория минимальных сложных классов не является лишь частью теории граничных классов.

Теорему 2.10 можно интерпретировать как возможность представления некоторых подмножеств множества &ц(Х) в виде других относительных П-граничных систем. Интересно было бы узнать, какие подмножества П-граничной системы относительно X представляются таким образом, а какие нет.

Теорема 2.14. Если \@п(Х)\ < оо, то для любого подмножества & £ ^п(Х) существует такое конечное множество графов 5, что @п{Х П ^гее(5)) = .

В четвертой главе диссертации указываются конкретные задача на графах П', класс графов X' и бесконечное подмножество ¿¡8' С &П>(Х'), что для любого наследственного класса У множества и &п'(У) не равны (лемма 4.9). Результаты главы 2 опубликованы в работах [9,11,17].

В главе 3 рассматривается задача о независимом множестве (задача НМ), состоящая в том, чтобы найти в заданном графе множество попарно несмежных вершин наибольшей мощности. Там вводится понятие НМ-расширяющего оператора, выявляется несколько таких отображений,

исследуются вопросы о нолном описании НМ-граничных систем относительно класса планарных графов и относительно класса субкубических планарных графов.

Первый раздел начинается с формулировки некоторой гипотезы о структуре НМ-граничных классов графов, принадлежащей В.Е. Алексееву3. Им было доказано, что класс Т является граничным для задачи НМ и выдвинуто предположение об его единственности, как НМ-граничного. В.Е. Алексеевым было также показано, что эта единственность эквивалентна тому, что для любого G G Т класс Free({G}) является НМ-простым. К настоящему времени это доказано лишь для нескольких случаев, наиболее важным из которых является G = Ты,г17- Вместе с тем, вот уже более 20 лет остается открытым сложностной статус задачи НМ в классе Free({Ps}). Для связных графов G с не более чем пятью вершинами вычислительный статус задачи НМ в классе Free({P5, G}) не известен только для случаев G = Рь и G = С518.

Во втором разделе предлагается систематический способ генерации НМ-простых подмножеств множества Free({Pb, С5}), основанный на введенном в диссертации понятии НМ-расширяющего оператора. Отображение / : S —> S' (функция одного или многих аргументов — графов из S) называется ИЫ-расширяющим оператором, если:

1. для любых значений аргументов / справедливо строгое включение Free(S) С Free{S')

2. для любых значений аргументов / справедлива импликация: если класс Free{S) является НМ-простым, то и класс Free(S') тоже НМ-простой

Во втором разделе показано, что некоторые отображения являются НМ-расширяющими операторами. Именно, там доказано, что отображения {Ръ, С5, G} —> {Р5, Сь, G о Кг} и {Р5, С5, G} —> {Р5, С5, G о 02, G 0 Khp} являются НМ-расширяющими операторами (следствия из теорем 3.2 и 3.4).

17 Алексеев В. Е. Полиномиальный алгоритм для нахождения наибольших независимых множеств в графах без вилок // Дискретный анализ и исследование операций. Серия 1. — 1999. — T.6, N4. — С. 3-19

18Mosca R. Some observations on maximum weight stable sets in certain P // European Journal of Operational Research. — 2008. — V. 184, №3. - P. 849-859

Через Gi ® G2 обозначается граф (V'(Gi) U V(G2), E(Gi) U £(G2)), а через Gi о Gi граф с множеством вершин V(Gi) U V(G2) и множеством ребер E(Gi) U E(G2) U V(Gi) x V(G?).

Если рассматривать какую-нибудь собственную наследственную часть множества всех графов, то можно надеяться хотя бы на более глубокое продвижение в исследовании проблемы единственности Т (как относительного НМ-граничного), чем в общем случае. Эти надежды в той или иной степени действительно оправдываются.

Если класс Т является НМ-граничным относительно какого-нибудь НМ-сложного класса X, то его единственность эквивалентна тому, что для любого G е Т класс ХГ\Free({G}) является НМ-простым. В работе19 фактически рассматривался случай X = Veg(d) (где Veg(d) — множество графов со степенями всех вершин не более чем d) и было показано, что для любых фиксированных d,i класс Veg{d) П Free({Tuj}) является НМ-нрос.тым.

В третьем разделе рассматривается случай X = V (V — класс пла-нарных графов) и показывается, что для любого фиксированного г класс V П Free{{Titi^i\) является НМ-простым (следствие из теоремы 3.5).

Все попытки получить результат с Тг,г,г как относительно Veg(d), так и относительно V оканчивались неудачей. Поэтому было предложено рассматривать класс субкубичсских планарных графов Т-'(З) = Т>ед{3) П V, где можно было надеяться на получение такого результата. Данная идея возникла в 2008 г., но тогда никаких даже минимальных продвижений получить не удалось и эта инициатива сошла на нет. Автор вернулся к этому вопросу в 2011 г., тогда удалось соответствующий результат. Он (теорема 3.9) является основным в четвертом разделе.

Теорема 3.9. При любом фиксированном г задача НМ для графов из класса V(3) П ^ггее({То12,;}) полиномиально разрешима.

Результаты главы 3 опубликованы в работах [1,13,14,18,19,21].

Глава 4 диссертации посвящена некоторым вопросам количественной

19Lozin V. V., Millanic М. Maximum independent sets in graphs of low degree //' Proceedings of the ACM-STAM symposium on descrete algorithms (New Orleans, 2007). - P. 874-880

теории граничных классов и смежным с ними. Важнейшими ее результатами являются утверждения о континуальности граничных систем для ряда задач на графах.

Первый раздел посвящен мотивации обращения к количественной теории граничных классов и перечислению полученных в пятой главе результатов. В пятой главе рассматриваются задачи о ^-раскраске и о хроматическом числе и индексе. Приведем постановки этих задач. Хроматическое число графа С — наименьшее число цветов, для которого можно так покрасить (правильным образом) вершины С, что любые две его соседние вершины покрашены в разные цвета. В задаче о вершинной к-раскраске требуется определить, верно ли, что хроматическое число задаваемого графа б не больше, чем фиксированное число к. Формулировка задачи о реберной ¿-раскраске аналогична постановке задачи о вершинной /с-рас краске (только в ней фигурирует хроматический индекс — минимальное количество цветов, необходимое для правильного окрашивания ребер графа). Задачи о хроматическом числе и индексе — «предельные» варианты задач о ^-раскраске. В задаче о хроматическом числе (соответственно, хроматическом индексе) необходимо найти хроматическое число (соответственно, индекс) заданного графа.

Второй раздел посвящен конструктивному доказательству континуальности граничных систем для вершинного и реберного вариантов задачи о 3-раскраске (теорема 4.1). Тем самым, доказано предположение о существовании задач на графах с бесконечным множеством граничных классов7.

В третьем разделе доказывается одно свойство некоторых подмножеств граничной системы для задачи о реберной 3-раскраске (лемма 4.9).

В четвертом разделе доказывается (частично конструктивно), что для любого к > 3 граничные системы для вершинного и реберного вариантов задачи о /с-раскраске являются континуальными (теоремы 4.2 и 4.3). Теоремы 4.1, 4.2 и 4.3 наталкивают на мысль о том, что граничные системы для задач о /с-раскраскс слишком сложно устроены и поэтому попытки дать их полные описания, по-видимому, заведомо обречены на неудачу.

В пятом разделе исследуются общие черты и особенности строения граничных систем для задач о fc-раскраске и для задач о хроматическом числе и индексе. Оказалось, что все граничные классы для задачи о реберной 3-раскраске являются граничными для задачи о хроматическом индексе (теорема 4.4). По теореме 4.5 при любом к > 3 существует континуум граничных классов для задачи о реберной fc-раскраске (соответственно, для задачи о вершинной fc-раскраске), каждый из которых не является граничным для задачи о хроматическом индексе (соответственно, для задачи о хроматическом числе). Граничная система для задачи о хроматическом числе не определяется граничными системами для задач о вершинной к-раскраске. Именно, класс со{Т>) = {G : С в V) является граничным для задачи о хроматическом числе, но не является граничным для задачи о вершинной А:-раскраске ни при каком к (теорема 4.6). Результаты главы 4 опубликованы в [3,5,7,12,15,22].

Глава 5 посвящена, в основном, успешной демонстрации метода «критического» класса графов — полной характеризации классов графов из некоторого достаточно представительного семейства по сложности задачи PCP.

В первом разделе описываются основные полученные в пятой главе результаты.

Во втором разделе доказывается, что некоторые классы графов являются PCP-граничными и минимальными РСР-сложными.

Обозначим через Combi граф, получающийся добавлением к ребра, инцидентного обеим вершинам степени г. Граф Сагщ — граф, получаемый соединением ребрами вершины степени г графа Si со всеми его листьями. Через Bat,Comb,Camomile обозначаются наследственные замыкания

оо оо оо

множеств (J {K2,i}, и {Combi}, (J {Cam,} соответственно. Класс Clique — i=i ' ï—1 i=i множество полных графов. В первом параграфе второго раздела доказывается следующее утверждение.

Теорема 5.1. Класс Bat является минилшльным PCP-слоэ/сиъш.

Во втором параграфе второго раздела описывается некоторое полиномиальное сведение, которое оказывается весьма полезным для построения новых PCP-сложных случаев. Для его формулировки приведем несколько определений.

Граф H называется минором графа G, если Я получается стягиванием ребер некоторого подграфа графа G. Класс графов, замкнутый относительно перехода к минорам его графов, называется минорно замкнутым.

Класс графов X будем называть минором класса У, если для любого графа II Е X существует такой граф Gey, что H — минор графа G. Эффективным аналогом понятия минора класса графов является понятие сильного минора класса графов. Класс X будем называть сильным минором класса У, если существует полиномиальный алгоритм, который по произвольному графу H & X вычисляет граф G 6 У и последовательность действий над ним, состоящую из серии удалений вершин и ребер, а затем из серии стягиваний ребер, выполнение которой приводит к графу Н.

Теорема 5.2. Пусть X — класс графов, для которого задача PCP не является полиномиально разрешимой. Тогда таким свойством обладает любой класс, для которого X является сильным минором.

При помощи теорем 5.1 и 5.2 нетрудно показать справедливость теоремы 5.3.

Теорема 5.3. Классы Comb, Camomile и Clique являются минимальными PCP-сложными.

По аналогии с доказательством теоремы 2.6 показывается, что классы Bat, Comb, Camomile и Clique являются PCP-граничными.

В третьем разделе описываются три класса графов и утверждается, что по аналогии с доказательством РСР-граничности класса Т можно доказать граничность каждого из них для задачи PCP. По строению своих графов каждый из этих трех классов близок к классу Т. Поэтому приведем определения всех четырех классов (включая класс Т) с единых позиций.

Аддитивным замыканием класса X называется множество всевозмож-

ных графов, каждая компонента связности которых принадлежит X.

1. Т — наследственное замыкание аддитивного замыкания множества всевозможных графов, которые получаются добавлением вершины к некоторому пути и ребра, инцидентного добавленной вершине и некоторой вершине пути

2.2? — наследственное замыкание аддитивного замыкания множества всевозможных графов, которые получаются добавлением вершины к некоторому пути и ребер, инцидентных добавленной вершине и некоторым двум последовательным вершинам пути

3. Т — наследственное замыкание аддитивного замыкания множества всевозможных графов, которые получаются добавлением вершины к некоторому пути и ребер, инцидентных добавленной вершине и некоторым двум вершинам пути, отстоящим в пути друг от друга на расстоянии 2

4. Т> — наследственное замыкание аддитивного замыкания множества всевозможных графов, которые получаются добавлением вершины к некоторому пути и ребер, инцидентных добавленной вершине и трем последовательным вершинам пути

В четвертом разделе получены полная классификация классов графов из некоторого семейства по вычислительной сложности задачи PCP и ряд следствий из нее.

Определим семейство Ж классов графов следующим образом. Наследственный класс графов X принадлежит M, если выполняется одно из условий:

• ни один из классов Bat,Star,Comet не является минором X

• если хотя бы один из классов Bat, Star, Comet является минором X, то хотя бы один из них является и сильным минором X.

Семейство M является достаточно представительным. Так, каждый минорно замкнутый класс принадлежит Ж (что прямо следует из опредсле-

ния) и каждый конечно определенный класс ему тоже принадлежит (лемма 5.8). Критерий эффективной разрешимости задачи PCP в семействе^ сформулирован далее.

Теорема 5.4. Задача PCP является полиномиально разрешимой для класса X б Ж тогда и только тогда, когда пи один из классов Bat, Star, Comet не является минором X.

При помощи этого критерия показывается, что PCP-граничную систему образуют ровно 10 конкретных классов графов.

Теорема 5.5. PCP-граничная система совпадает с {Bat, Star, Comet, Comb, Camomile, Clique, T, Т>, Т, V}.

Теорема 5.5 — первый пример полного описания граничных систем для задач на графах (со времен первой публикации4 по граничным классам).

На настоящее время не известно, каким образом устроено множество минимальных PCP-сложных классов. При помощи теорем 5.4 и 5.5 нетрудно перечислить все конечно определенные минимальные PCP-сложные классы и все минорно замкнутые минимальные PCP-сложные классы.

Теорема 5.6. Существует ровно 5 конечно определенных минимальных PCP-сложных классов. Это Bat, Star, Clique, Comb, Camomile. Единственным минорно замкнутым минимальным PCP-сложным классом является класс Comet.

Результаты, полученные в главе 5, опубликованы в [8,10,20].

В главе 6 для семейства наследственных классов исследуются элементы границы между П-простыми и П-сложными классами для некоторых задач П. Там, например, для некоторых задач на графах впервые приводятся полные описания совокупностей минимальных сложных классов.

В первом разделе рассматривается задача распознавания принадлежности графа классу X (обозначаемая через РП[Л"]) и доказывается следующее утверждение.

Теорема 6.1. Если X — наследственный класс графов, то любой

РП[Х]-слоэ1сный класс не является минимальным.

В первом разделе приведены конкретные примеры ИР-полных задач распознавания принадлежности графа наследственному классу.

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

Теорема 6.2. Если X является П-сложным классом и X является вполне упорядоченным множеством по отношению Л» = «быть порожденным подграфом», то X содержит некоторый минимальный П-сложный подкласс.

Во втором разделе показывается, что теорема 6.2 необходимым условием минимальной П-сложности не является.

Во втором разделе рассматриваются задачи на графах, для каждой из которых удается полностью описать все множество минимальных сложных классов. Данные задачи образуют последовательность, постановка к-ого члена (обозначаемого через Щ) которой состоит в следующем. В задаче Щ заданы граф <3 и отображение с : Е(С) —> {-1, +1}. Требуется найти такой подграф Я графа что Я имеет правильную 3-раскраску вершин и величина и>(Н) является максимально возможной. Значение ш(Я) определяется следующим образом: ш(Я) = 0, если размер наибольшего независимого множества б равен к, и и)(Н) = £ с(е) в противном случае.

ееЕ(Н)

Уточним, что под Пк-простпым понимается наследственный класс графов, для которого данная задача полиномиально разрешима для любой функции с.

Для любого натурального к определим семейство классов графов &{к) = {Х{,Х£,...,Х£}. Для любого 1 < г < к через X* обозначает-

оо ____

ся наследственное замыкание множества графов и {А'; © К] © Кк-{\ (где

___ у=1

К к © К] Ф К0 считается равным Кк © К3).

Теорема 6.3. Все множество минимальных П¡¡-сложных классов совпадает с множеством (к).

Задачи Iii, Н2,... — первые примеры задач на графах, для которых удастся полностью описать совокупность минимальных сложных классов.

Третий раздел главы G посвящен исследованию связей между понятиями граничного и минимального сложного классов графов. Там сформулированы критерии о том, когда П-граничный класс является минимальным П-сложным (теорема 6.4) и когда минимальный П-сложный класс является П-граничным (теорема 6.5). Конечно определенный класс является П-граничным тогда и только тогда, когда он является минимальным П-сложным (лемма 6.4). Минимальный П-сложный класс не всегда является П-граничным (но теореме 2.12). Результаты главы 6 опубликованы в работах [6,16].

ПУБЛИКАЦИИ

[1]. Алексеев В.Б., Малышев Д.С. Классы планарных графов с полиномиально разрешимой задачей о независимом множестве // Дискретный анализ и исследование операций. — 2008. — Т. 15, №1. — С. 3-10 (Имеется перевод: Alekseev V.E., Malyshev D.S. Planar graph classes with the independent set problem solvable in polynomial time // Journal of Applied and Industrial Mathematics. - 2009. — V. 3, №1. — P. 1-4).

[2]. Алексеев B.E., Малышев Д.С. Критерий граничности и его применения // Дискретный анализ и исследование операций. — 2008. — Т. 15, №6. - С. 3-10.

[3]. Малышев Д.С. О бесконечности множества граничных классов графов в задаче о реберной 3-раскраске // Дискретный анализ и исследование операций. - 2009. - Т. 16, №1. - С. 37-43 (Имеется перевод: Malyshev D.S. On the infinity of the set of boundary classes for the edge 3-colorability problem // Journal of Applied and Industrial Mathematics. - 2010. - V. 4, №2. - P. 213-217).

[4]. Малышев Д.С. Граничные классы графов для некоторых задач распознавания // Дискретный анализ и исследование операций. —

2009. - Т. 16, т. - С. 85-94.

[5]. Малышев Д.С. Континуальные множества граничных классов графов для задач о раскраске // Дискретный анализ и исследование операций. - 2009. - Т. 16, №5. - С. 41-51.

[6]. Малышев Д.С. О минимальных сложных классах графов // Дискретный анализ и исследование операций. — 2009. — Т. 16, №6. — С. 43-51.

[7]. Малышев Д.С. О количестве граничных классов графов в задаче о 3-раскраске // Дискретная математика. — 2009. — Т. 21, №4. — С. 129134 (Имеется перевод: Malyshev D.S. On the number of boundary classes in the 3-colouring problem // Discrete Mathematics and Applications. —

2010. - V. 19, №6. - P. 625-630).

[8]. Малышев Д.С. Минимальные сложные классы графов для задачи о реберном списковом ранжировании /'/ Дискретный анализ и исследование операций. - 2011. - Т. 18, №1. - С. 70-76.

[9]. Малышев Д.С., Алексеев В.Е. Граничные классы для задач о списковом ранжировании относительно лесов // Дискретный анализ и исследование операций. — 2011. — Т. 18, №6. — С. 61-70.

[10]. Малышев Д.С. Анализ сложности задачи о реберном списковом ранжировании для наследственных классов графов с не более чем тремя запретами // Дискретный анализ и исследование операций — 2012. - Т. 19, №1. - С. 74-96.

[11]. Малышев Д.С. О связи понятий граничного и минимального сложного классов графов // Вестник нижегородского университета им. Н.И. Лобачевского. - 2012. - №2. - С. 149-151.

[12]. Малышев Д.С. О пересечении и симметрической разности семейств граничных классов графов для задач о раскраске и о хроматическом

числе // Дискретная математика. - 2012. - Т. 24, №2. - С. 75-78 (Имеется перевод: Malyshev D.S. On intersection and symmetric difference of families of boundary classes in the problems on colouring and on the chromatic number // Discrete Mathematics and Applications. — 2011. — V. 21, №5-6. - P. 645-649).

[13]. Малышев Д.С. Полиномиальная разрешимость задачи о независимом множестве в классе графов без порожденных простых пути и цикла с пятью вершинами и большой клики // Дискретный анализ и исследование операций. - 2012. - Т. 19, №3. - С. 58-64.

[14]. Малышев Д.С. Полиномиальная разрешимость задачи о независимом множестве для одного класса графов малого диаметра // Дискретный анализ и исследование операций. — 2012. — Т. 19, №4. — С. 66-72.

[15]. Малышев Д.С. Исследование граничных классов графов для задач о раскраске // Дискретный анализ и исследование операций —

2012. - Т. 19, №6. — С. 37-48 (Имеется перевод: Malyshev D.S. A study of the boundary graph classes for colorability problems // Journal of Applied and Industrial Mathematics. - 2010. - V. 7, №2. - P. 221-228).

[16]. Малышев Д.С. Экстремальные множества графов при решении задачи демаркации в семействе наследственно замкнутых классов графов // Дискретная математика. - 2012. - Т. 24, №4. - С. 91-103 (Имеется перевод: Malyshev D.S. Extremal sets of graphs in the problem of demarcation in the family of hereditary closed classes of graphs // Discrete Mathematics and Applications. - 2012. - V. 22, №5-6. - P. 595-608).

[17]. Малышев Д.С. Относительные граничные классы и факторизация семества наследственных классов графов // Вестник нижегородского университета им. Н.И. Лобачевского. — 2013. — №3. — С. 181— 187.

[18]. Малышев Д.С. Расширяющие операторы для задачи о независимом множестве // Дискретный анализ и исследование операций. —

2013. — Т. 20, №2. — С. 75-87 (Имеется перевод: Malyshev D.S. Expanding

operators for the independent set problem // Journal of Applied and Industrial Mathematics. - 2013. - V. 7, №3. - P. 412-419)

[19]. Малышев Д.С. Классы субкубических планарных графов, для которых задача о независимом множестве полиномиально разрешима // Дискретный анализ и исследование операций. — 2013. — Т. 20, №3. — С. 26-44 (Имеется перевод: Malyshev D.S. Classes of subcubic planar graphs for which the independent set problem is polynomially solvable // Journal of Applied and Industrial Mathematics. - 2013. - V. 7, №4. - P. 475- 489).

[20]. Малышев Д.С. Критические классы графов для задачи о реберном списковом ранжировании // Дискретный анализ и исследование операций. - 2013. - Т. 20, №6. - С. 59- 76.

[21]. Alekseev V.E., Lozin V.V., Malyshev D.S., Milanic M. The maximum independent set problem in planar graphs // Lecture Notes in Computer Science. - 2008. - V. 5162, №4. - P. 96-107.

[22]. Korpelainen N., Lozin V.V., Malyshev D.S., Tiskin A. Boundary properties of graphs and algorithmic graph problems // Theoretical Computer Science. - 2011. - V. 412. - P. 3545 -3554.

[23]. Malyshev D.S. Boundary graph classes for some maximum induced subgraph problems // Journal of Combinatorial Optimization. — 2013. - V. 7, №. - P. 345-354.

Нижегородский государственный университет им. Н. И. Лобачевского факультет вычислительной математики и кибернетики

На правах рукописи

05201450900

Малышев Дмитрий Сергеевич

ИССЛЕДОВАНИЕ «КРИТИЧЕСКИХ» НАСЛЕДСТВЕННЫХ КЛАССОВ В АНАЛИЗЕ ВЫЧИСЛИТЕЛЬНОЙ СЛОЖНОСТИ ЗАДАЧ НА ГРАФАХ

01.01.09 — «дискретная математика и математическая кибернетика»

Диссертация на соискание ученой степени доктора физико-математических наук

Научный консультант: д.ф.-м.и., проф. Алексеев Владимир Евгеньевич

Нижний Новгород — 2013 год

Оглавление

Введение 6

1 Граничные классы графов: значение и примеры 13

1.1 Некоторые обозначения и определения...............13

1.1.1 Множества ....................................................13

1.1.2 Отношения....................................................14

1.1.3 Графы и подграфы......................14

1.1.4 Множества вершин и числовые характеристики .....16

1.1.5 Классы графов........................16

1.2 «Критические» наследственные классы графов..........18

1.3 Расширение пределов справедливости теоремы В.Е. Алексеева . 22

1.4 Критерий граиичпости........................26

1.5 Новые случаи граничности класса Т и его производных.....27

1.5.1 Условия граиичпости классов Т и V............27

1.5.2 Множество задач па графах с граничными классами Т

и Т> континуальной мощности................29

1.5.3 Древесная ширина и кликовая ширина графов и их применение при установлении граничности классов Т и Т> . 34

1.5.4 Производные от Т классы и некоторые случаи их граиичпости ............................38

2 Относительные граничные системы и их свойства 40

2.1 Относительные граничные классы.................40

2.2 Строение относительной граничной системы для ряда задач иа

графах.................................42

2.2.1 Критерий полноты множества относительных граничных классов..........................42

2.2.2 Относительные граничные системы из производных класса Т............................42

2.2.3 Граничные классы графов для задач о списковом ранжировании относительно лесов...............44

2.3 Факторизация решетки наследственных классов графов и ее

свойства................................57

2.3.1 Критерий принадлежности общему фактор-классу и «избыточные» классы эквивалентности..........57

2.3.2 О независимости понятий минимального сложного, абсолютного граничного и относительного граничного классов графов ..........................64

2.3.3 Об одном свойстве относительных граничных классов в задаче о наибольшем двудольном планарном подграфе . 65

2.3.4 Подмножества относительных граничных систем и их свойства............................67

3 Полиномиальная разрешимость задачи НМ для некоторых

классов графов 71

3.1 Гипотеза В.Е. Алексеева и ее варианты..............71

3.2 Расширяющие операторы для задачи о независимом множестве 74

3.2.1 О НМ-расширясмости оператора —)• {Р^Сь.СоК,}........................ 75

3.2.2 О НМ-расширясмости оператора Н} —> {Р5,С-0,НоО2,Н®К1,р}..................80

3.3 Полиномиальная разрешимость задачи НМ в классе планарных

графов, не содержащих больших порожденных яблок......87

3.3.1 Разделяющие клики и С-блоки...............87

3.3.2 Свойства планарных графов без больших порожденных звезд..............................87

3.3.3 Минорно безапекспые графы большой древесной ширины 90

3.3.4 Доказательство основного результата первой части главы 91 3.4 Полиномиальная разрешимость задачи НМ в классе субкубических планарных графов без порожденного подграфа ■ • 97

3.4.1 Вспомогательные результаты................97

3.4.2 Присоединенные циклы и их разрушение.........99

3.4.3 Гармони и их разрушение..................108

3.4.4 Основные результаты второй части главы.........115

4 О задачах на графах с континуальными граничными системами 118

4.1 Некоторые результаты из количественной теории граничных классов и смежные с ними .....................118

4.2 Граничные классы графов для задач о 3-раскраске.......119

4.3 Свойства подмножеств 3-РР-граничной системы.........128

4.4 Граничные классы графов для задач о fc-раскраске.......130

4.5 Сравнительный анализ граничных систем для задач о к-раскраске и о хроматическом числе и индексе ..........132

5 «Критические» классы графов для задачи о реберном списковом ранжировании 136

5.1 Краткое описание основных результатов пятой главы......13G

5.2 Новые минимальные РСР-сложныс случаи............137

5.2.1 О минимальной РСР-сложпости класса графов Bat . . . 137

5.2.2 О минимальной РСР-сложпости классов графов Comb, Camomile и Clique ..................141

5.3 Новые РСР-грапичиыс случаи...................143

5.4 Полная классификация классов графов из некоторого семейства по вычислительной сложности задачи PCP и следствия из

нее...................................144

5.4.1 Оценки количеств вершин, степеней вершин и диаметров графов из некоторых классов................145

5.4.2 О принадлежности каждого конечно определенного класса семейству Ж.....................151

5.4.3 Критерий эффективной разрешимости задачи PCP в семействе и следствия из него...............154

Минимальные сложные классы графов 158

6.1 О задачах на графах без минимальных сложных случаев . . . .158

6.2 Условия и примеры существования минимальных сложных классов графов............................159

6.3 О связи и о независимости понятий минимального сложного и граничного классов графов.....................165

Литература 167

Введение

Развитие теории сложности вычислений способствовало формированию фактических стандартов эффективной разрешимости и «труднорешаемости». В соответствии с этой концепцией под быстрой (эффективной) разрешимостью массовой задачи понимается возможность ее решения на детерминированной машине Тьюринга за время, ограниченное полиномом от длины входных данных. В то же время, имеется ряд «неподдающихся» (МР-полпых) задач, для которых в настоящее время не получено полиномиальных алгоритмов. Накопленный опыт исследования данных задач и практика их решения дают основания предполагать, что таких процедур вообще не существует.

Одним из способов преодоления алгоритмической сложности МР-полиых задач является сужение, т.е. наложение ограничений на рассматриваемый класс входных данных. Иногда учет этого обстоятельства, т.е. принадлежности данных только определенному классу, действительно приводит к созданию эффективных алгоритмов. В других случаях удастся доказать КР-полноту задачи в этом классе. При рассмотрении целых семейств бесконечных классов индивидуальных данных (т.е. семейств массовых задач) можно ставить проблемы более общего характера, чем анализ сложности для конкретного класса. В частности, можно поставить целью выявление «линии водораздела» между «простыми» и «сложными» случаями. По-видимому, реализуемость этих намерений обусловлена надлежащим выбором и семейства классов и соответствующего понятийного аппарата. Узость рассматриваемой совокупности массовых задач малопривлекательна для исследователя. Вместе с этим, содержательность проблемы демаркации имеет место далеко не для всех представительных совокупностей массовых задач. Так, удаление/добавление индивидуальной задачи из/к массовой не меняет ее слож-ностного статуса. Поэтому целесообразно рассматривать тс семейства мас-

совых задач, для которых удаление или добавление одной индивидуальной задачи приводит к необходимости выполнения сразу нескольких таких операций (ввиду некоторой замкнутости).

В настоящей диссертации в качестве объекта исследований рассматривается семейство наследственных классов графов. Наследственные классы, т.е. множества графов, замкнутые относительно изоморфизма и удаления вершин, образуют представительную континуальную совокупность. Данные классы графов (и только они) допускают описание через запрещенные порожденные подграфы (фрагменты). Если X — наследственный класс, a S — множество его запрещенных фрагментов, то пишем X = Free(S). Семейство наследственных классов включает известные подсемейства монотонных и минорно замкнутых классов (замкнутых помимо удаления вершин еще и относительно других операций). В работе выделение «границы» между «простыми» и «сложными» наследственными случаями ведется в рамках поиска «критических» классов графов, т.е. классов, играющих особую, определяющую роль в анализе сложности рассматриваемой задачи па графах.

Граничные классы графов являются одним из типов «критических» классов. Понятие граничного класса было введено В.Е. Алексеевым в работе [32], там же была обоснована полезность этого понятия для анализа сложности задач на графах в семействе конечно определенных классов графов (т.е. наследственных классов с конечным множеством запрещенных порожденных подграфов). Именно, любой такой класс является «сложным» для данной задачи тогда и только тогда, когда он содержит некоторый граничный для этой задачи класс. Тем самым, даже частичная информация о структуре множества граничных классов (граничной системе) представляет определенный интерес.

В первой части первой главы диссертации расширяется множество «сложных» случаев по сравнению с конечно определенными классами, включающими граничные классы. Именно, показывается, каким образом при известной граничной системе для заданных наследственного класса X и числа

к проверить существование класса У С X с не более чем к запрещенными фрагментами, который включает некоторый граничный класс. Во второй части первой главы доказываются критерии граничпости произвольного класса графов и некоторого конкретного класса графов. Это класс Т, состоящий из лесов с не более чем тремя листьями в каждой компоненте связности. Известны примеры задач на графах, для которых классы Т и Т> (множество графов, являющихся реберными к графам из 7") являются граничными [32, 34, 33]. В диссертации для некоторых задач доказывается граничпость класса Т и производных от него. Результаты первой главы опубликованы в работах [6, 13, 67].

Во второй главе диссертации рассматривается понятие относительного граничного класса, обобщающее понятие (абсолютного) граничного класса. До результатов недавнего времени ии для одной задачи на графах не удавалось полностью описать абсолютную граничную систему. Вместе с тем, надежды на получение исчерпывающего решения в случае относительных граничных классов действительно оправдываются (см., например, [60]). Во всех ранее полученных такого рода результатах утверждалось, что классы Т и Т) образуют относительную граничную систему. Соответствующие доказательства похожи друг па друга и следуют плану, намеченному в работе [60]. Первый результат с другой парадигмой рассуждений получен во второй главе. Здесь доказывается, что некоторые три класса графов (далекие по «внешнему виду» от Т и от V) составляют граничную систему для задач о списковом ранжировании (вершинного и реберного вариантов) относительно класса лесов. В оставшейся части второй главы впервые рассматривается более общая проблематика, чем описание относительных граничных систем. Именно, там изучается факторизация семейства наследственных классов по отношению равенства относительных граничных систем. Формулируется критерий принадлежности двух наследственных классов общему классу эквивалентности. Показывается, что при некоторых условиях граничные системы относительно объединений и пересечений двух наследственных классов выражаются через

граничные системы относительно этих наследственных классов. Доказывается ряд результатов о представимости подмножеств относительных граничных систем в виде других относительных граничных систем. Приводятся примеры, показывающие, что при малом изменении условий некоторые из утверждений второй части второй главы превращаются в неверные высказывания. Один из примеров также демонстрирует, что относительный граничный класс не всегда является абсолютным граничным. Эти результаты опубликованы в [19, 21, 27].

В работе [32] рассматривалась задача о независимом множестве (задача НМ), там же было доказано, что класс Т является граничным для этой задачи. До сих пор не известно, существуют ли для задачи НМ граничные классы, отличные от класса Т. Существование таких классов эквивалентно существованию графа С 6 Т, что класс Ргее({Ст}) является «сложным» для задачи НМ [32]. О трудности поиска такого графа О (или получения доказательства его отсутствия) говорит тот факт, что сложиостиой статус задачи НМ для Ргее({Р^}) является открытым уже более 20 лет [72]. Имеются десятки работ, в которых к простому пути с пятью вершинами добавляется один или несколько других запрещенных порожденных подграфов и доказывается эффективная разрешимость задачи НМ для получившегося класса графов [ЗС, 41, 40, 62, 70, 71, 72, 77]. Доказано, что для любого графа Сг с не более чем пятью вершинами, отличного от Р5 и С5, задача НМ полиномиально разрешима в классе графов Ргее({Р$, С}) [72]. Вопрос о сложности задачи НМ для класса Ргее({Р5,Съ}) остается открытым вот уже более 10 лет. В первой части третьей главы диссертации выявляются новые наследственные случаи полиномиальной разрешимости задачи НМ, которые являются подмножествами класса Ргее({Р$, С5}). Предлагается систематический способ порождения таких случаев, основанный на введенном в диссертации понятии НМ-расширяющего оператора. Вопросы о единственности класса Т, как НМ-граничиого относительно множества планарпых графов и как НМ-граничного относительно множества субкубичсских планарпых графов, рас-

сматриваются во второй части третьей главы. Соответствующая единственность эквивалентна тому, что для любого С 6 Т задача НМ в классе (субкубических) планарпых графов, не содержащих порожденного подграфа С, полиномиально разрешима. Хотя и здесь этого доказать не удается, имеется более значительный прогресс к достижению намеченной цели, чем в общем случае. Именно, устанавливается полиномиальная разрешимость задачи НМ для бесконечного семейства классов графов описанного выше типа. Результаты, изложенные в третьей главе, опубликованы в [5, 23, 24, 28, 29, 35].

Трудности, возникающие при попытках дать полное описание множества граничных классов для той или иной задачи на графах, приводят к мысли о том, что для некоторых задач это множество может быть весьма сложно устроенным и поэтому попытки дать его описание, по-видимому, обречены на неудачу. Эта мысль (которую можно назвать геделевским аргументом) действительно находит свое подтверждение, т.к. при к > 3 для обеих задач о ^-раскраске (вершинного и реберного вариантов), задач о хроматическом числе и индексе граничные системы оказываются континуальными. Тем самым доказано предположение из [33] о существовании задач на графах с бесконечным множеством граничных классов. Задачи о хроматическом числе и индексе — «предельные» варианты задач о раскраске. Поэтому было бы интересно исследовать общие черты и особенности строения граничных систем для задач о ^-раскраске и для задач о хроматическом числе и индексе. Оказалось, что все граничные классы для задачи о реберной 3-раскраске являются граничными для задачи о хроматическом индексе. Вместе с тем, при любом к > 3 существует континуум граничных классов для задачи о реберной к-раскраске (соответственно, для задачи о вершинной /г-раскраске), каждый из которых не является граничным для задачи о хроматическом индексе (соответственно, для задачи о хроматическом числе). Граничная система для задачи о хроматическом числе не определяется граничными системами для задач о вершинной ^-раскраске. Именно, класс со(Т>) = {С? : С 6 Т>} является граничным для задачи о хроматическом числе, по не является граничным

для задачи о вершинной fc-раскраске ни при каком к. Перечисленные в этом абзаце результаты составляют содержание четвертой главы диссертации. Они опубликованы в [12, 14, 16, 22, 25, 57]

Пятая глава диссертации посвящена успешной демонстрации метода «критического» класса графов. В ней получен критерий эффективной разрешимости задачи о реберном списковом ранжировании (задачи PCP) в некотором достаточно представительном семействе из наследственных классов графов, содержащем все конечно определенные и минорно замкнутые классы. Именно, класс X из этого семейства является «простым» для задачи PCP тогда и только тогда, когда для трех конкретных классов графов Уг,У2,Уз найдутся графы G\ £ У\, G2 G У2, G3 Е Уз, что ни один граф из X по содержит пи G1, ни G2, ни G3 в качестве минора. Из данного утверждения следует, что граничную систему для задачи PCP образуют ровно 10 конкретных классов графов. Это первый результат о полном описании граничной системы с момента первой публикации [2] по граничным классам. Излагаемые в пятой главе результаты опубликованы в [18, 20, 30].

Наследственный класс графов, определяемый бесконечным минимальным множеством запрещенных порожденных подграфов и содержащий некоторый граничный класс, не обязательно будет «сложным». Таким образом, для решения задачи демаркации в решетке всех наследственных классов необходимо помимо граничных рассматривать и другие типы «критических» классов. Естественными кандидатами являются максимальные «простые» и минимальные «сложные» классы, т.е. тупиковые классы графов соответствующей сложности из рассматриваемой решетки. Испо�