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

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

00340^00^

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

ИССЛЕДОВАНИЕ ГРАНИЦ ЭФФЕКТИВНОЙ РАЗРЕШИМОСТИ В СЕМЕЙСТВЕ НАСЛЕДСТВЕННЫХ КЛАССОВ ГРАФОВ

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

2 к оя а

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

Нижний Новгород — 2009 г.

003482882

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

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

Официальные оппоненты: д.ф.-м.н., проф. Иорданский М. А.

к.ф.-м.н., доц. Носков В. В.

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

кибернетики Московского государственного университета им. М. В. Ломоносова

Защита диссертации состоится «.5 » декабря 2009 года в 14 часов 40 минут на заседании совета по защите докторских и кандидатских диссертаций Д.212.166.06 при Нижегородском государственном университете им. Н. И. Лобачевского по адресу: 603950, г. Нижний Новгород, пр. Гагарина, корп. 2, конференц зал.

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

С текстом автореферата можно ознакомиться на официальном сайте Нижегородского государственного университета им. Н. И. Лобачевского http://www.unn.ru. ^ ,___ "^—7-

Автореферат разослан . 2009 года.

Ученый секретарь совета по защите докторских и кандидатских диссертаций Д.212.166.06 к.ф.-м.н., доцент

В. И. Лукьянов

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

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

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

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

В диссертации содержатся результаты исследования наследственных классов гра-

1 Алексеев В. Е. Исследование количественных и сложностных характеристик наследственных классов графов: диссертации на соискание ученой степени доктора физико-математических наук по специальности 01.01.09 — «дискретная математика и математическая кибернетика». — Нижний Новгород, 2002. — 113 Стр.

2Сорочап С. В. Исследование количественных характеристик наследственных классов ориентированных и цветных графов: диссертация на соискание ученой степени кандидата физико-математических наук по специальности 01.01.09 — «дискретная математика и математическая кибернетика». — Нижний Новгород, 2006. — 149 Стр.

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

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

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

Цель работы

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

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

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

4Ллскссси В. Е. Об энтропии фрагмептно замкнутых классов графов // Комбинаторно-алгебраические методы в прикладной математике. — Горький: Из-во Горьк. ун-та, 1986. — Стр. 5-15.

sAlcksccv V. Е. On easy and bard classes of graphs with respect to the independent set problem // Discrete Applied Mathematics. — 2004. — V. 132. — P. 17-26.

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

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

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

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

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

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

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

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

4. Рассмотрено понятие минимального сложного класса графов, т.е. тупикового наследственного класса соответствующей сложности (понятие максимального простого класса оказывается бессмысленным, поскольку из результатов В. Е. Алексеева5 следует, что ни для одной задачи на графах таких классов нет). Основополагающий мотив (помимо очевидной полезности для решения задачи разграничения) обращения к таким классам — полное отсутствие каких-либо результатов о них. В диссертации решается вопрос о существовании минимальных сложных классов графов для некоторых задач на графах. Во-первых, доказывается, что для задачи распознавания принадлежности любому наследственному классу графов ни один сложный класс не является минимальным. Во-вторых, для задач о списковом ранжировании8,9 (вершинного и реберного

8Dcreniowski D. Tlic complexity of list ranking оГ trees // Ars Combinatoria. — 2008. — V. 86. — P. 07-114

9Jamison R..E. Coloring parameters associated with rankings of graphs // Congressus Numerantur». — 2003. — V. 164. —

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

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

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

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

Уточнение понятия граничного класса графов принадлежит В. Е. Алексееву. Формулировка и доказательство критерия граничности (теорема 1.3), а также некоторых из условий граничности (теорема 1.4, лемма 1.3) получены совместно с научным руководителем. Остальные результаты первой главы диссертации (оставшиеся условия граничности и все излагаемые случаи граничности) получены соискателем лично.

Во второй главе работы, посвященной продвижениям на пути к доказательству единственности некоторого класса графов, как граничного относительно класса пла-нарных графов для задачи о независимом множестве, ряд результатов получен в соавторстве. При этом доказательство теорем 2.1, 2.2, идея использования звезд в теоремах 2.2 и 2.3, а также идея сведения задачи о независимом множестве к планарным графам невысокой степени (лемма 2.10) принадлежат автору. В. Е. Алексееву принадлежит идея использования аппарата сжатий, позволившего при формулировке леммы 2.10 существенно понизить порядок параметра г. Теорема 2.3 доказана В. Е. Алексеевым, В. В. Лозиным, соискателем и М. МШатс'ем на паритетных началах.

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

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

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

• VI и VII молодежные международные научной школы по дискретной математике и ее приложениям (Москва, 2007, 2009),

Р. 111-127.

• XV международная конференция студентов, аспирантов и молодых ученых «Ломоносов 2008» (Москва, 2008),

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

• 33rli international symposium on Mathematical Foundations of Computer Science (Torun, 2008),

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

• семинар ВМиК МГУ «Дискретный анализ» (руководитель А. А. Сапоженко),

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

По теме диссертации имеется 1G работ, список которых приводится в конце автореферата. Среди них одна статья в изданиях, рекомендованных ВАК РФ для публикаций материалов диссертаций по математике и механике (в журнале «Дискретная математика»), а также 7 работ в ведущих рецензируемых изданиях из списка ВАК РФ (б статей в журнале «Дискретный анализ и исследование операций» и одна в журнале «Вестник Нижегородского государственного университета»).

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

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

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

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

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

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

Напомним, что наследственным называется класс графов, замкнутый относительно удаления вершин. Известно, что любой такой класс X может быть задан множеством запрещенных порожденных подграфов Г, при этом принята запись X = Free(F). Минимальное по включению множество с данным свойством существует, единственно и обозначается через Forb(X). Если Forb(X.) конечно, то X называется конечно определенным.

Пусть П — произвольная NP-полная задача на графах. Наследственный класс называется И-простым, если задача П для графов из этого класса полиномиально разрешима, и П-сложным в противном случае. Наследственный класс графов X называется Tl-пределъным, если существует такая бесконечная последовательность Xi Э Хг 2 • • •

оо

П-сложных классов графов, что X = П X*. Минимальный по включению П-предельный

тт i=1

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

Значение понятия граничного класса графов состоит в том, что произвольный конечно определенный класс является П-сложным тогда и только тогда, когда он содержит некоторый П-граничный класс5,6,7. В тех же работах в качестве граничных фигурировали два класса графов. Одним из них является класс Т — класс графов, каждая компонента связности которых является деревом с не более чем 3 листьями. Иными словами, данный класс состоит из всевозможных графов, у которых каждая компонента связности либо простой путь, либо триод. Под триодом Tij^ понимается дерево, имеющее ровно одну вершину степени 3 и ровно три листа, отстоящих от вершины степени 3 на расстояниях i,j,k соответственно. Другой такой класс — класс D, состоящий из всех графов, являющихся графами ребер графов из Т.

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

Теорема 1.3. П-предельный класс А является П-граничным тогда и только тогда, когда для каждого G 6 А существует такое конечное множество графов X С Forb{А), что класс Free(K U {G}) является П-простым.

В четвертом разделе на основе общего результата формулируется ряд критериев и достаточных условий граничности классов Т и D. Среди них наиболее полезным оказывается утверждение, использующее понятие древесной ширины графа. Это обусловлено тем, что для любой наперед заданной константы некоторые задачи на графах полиномиально разрешимы в классе, у которых древесная ширина ограничена этой константой10.

Пусть Deg(3) — класс графов, степень каждой из вершин которых не превосходит 3, TW(3, t) — множество графов из Deg(3), древесная ширина которых не превосходит t, £(TW(3, i)) — совокупность графов, являющихся графами ребер графов из TW(3,t).

i0Bod]aender II. L. Dynamic programming on graphs with bounded trccwidth // Automata, Languages and Programming (Tampere, 11-15 July 1988). Proc. in Lecture Notes iri Computer Science. — 1988. — V. 317. — P. 105-118.

Лемма 1.7. Если класс Т является П-пределъным и для любого t задача П полиномиально разрешима в классе TW(3, ¿) П Ргее({Сз}), то класс Т является П-граничным. Если класс D является П-предсльным и для любого t задача П полиномиально разрешима в классе L(TW(3, t)) П Deg(3), то класс D является П-граничным.

Пятый и шестой разделы главы 1 посвящены выявлению новых случаев гра-ничности классов Т и D. Так, в пятом разделе рассматриваются некоторые частные случаи общей задачи о наибольшем подграфе. Наиболее интересными из них являются задачи о вершинно наибольшем Х-подграфе (называемая далее ВНП[Х]), о реберно наибольшем Х-подграфе (называемая далее РНП[Х]). Задача РНП[Х] состоит в том, чтобы для заданных графа G и числа к определить, содержит ли этот граф подграф из класса X, число ребер которого не менее к. Задача ВНП[Х] состоит в том, чтобы для заданных графа G и числа к определить, содержит ли этот граф порожденный подграф из класса X, число вершин которого не менее к.

Пусть Planar — класс планарных графов, Bipartite — класс двудольных графов, Perfect — класс совершенных графов, Path — класс простых путей, Cycle — класс простых циклов, ТО — класс транзитивно ориентируемых графов.

Теорема 1.6. Класс Т является PHI I [Planar]-граничим.«, PHn[Bipartite]-граничным, PHnlPerfectj-граки-шъш и РИЩТО\-граничным.

Теорема 1.9. Класс Т является граничным для задач ВНП|Р1апаг], BHn[BipartitcJ, BHn[Perfect], а класс D является граничным для задач ВНП[Р1апаг], BHn[Perfect], BHn[Path] и ВНП[Сус1е].

В том же пятом разделе указывается континуальное семейство различных задач на графах, для каждой из которых Т и D являются граничными одновременно. Каждая из этих задач — задача о вершинно наибольшем порожденном Х-подграфе, где X — некоторое расширение класса планарных графов. В шестом разделе показывается (теорема 1.11), что класс Т является граничным для задач о покрытии полными двудольными графами, о разбиении графа, о лесе с ограниченными компонентами, о независимом реберном доминирующем множестве, о непересекающихся путях, а класс D является граничным для задач о разбиении на клики и о разобщенном множестве.

Наконец, в седьмом разделе приводятся первые примеры задач на графах с граничными классами со(Т) = {G : G € Т} и co(D) = {G : G 6 D}. Именно доказывается, что класс со(Т) — граничный для задачи о наибольшей клике и для задачи об ахроматическом числе графа, а класс co(D) — граничный для задачи о вершинной раскраске. Результаты главы 1 опубликованы в работах [2,5,9,13].

В главе 2 вводится понятие относительного граничного класса и исследуется вопрос о полном описании множества граничных классов для задачи о независимом множестве (задачи НМ) относительно класса планарных графов.

Первый раздел начинается с формулировки некоторой гипотезы о структуре НМ-граничных классов графов, принадлежащей В. Е. Алексееву5. Именно, в этой работе было доказано, что класс Т является граничным для задачи НМ и выдвинуто предположение об его единственности, как НМ-граничного. Там же показано, что доказательство этого предположения эквивалентно доказательству того факта, что для любого G 6 Т класс Free({G}) — НМ-простой. К настоящему времени это доказано лишь для нескольких случаев (наиболее важные из них, когда G = Я411 и G = Т1ДД12) и остается открытым сложностной статус задачи НМ в классах iYee({Ps}) и Free^Ti^})-

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

Пусть Y — какой-нибудь П-сложный класс. Наследственный класс графов X называется П-граничным относительно класса Y, если существует такая последователь-

оо

ность Xi 2 Х2 Э ... П-сложньгх подклассов класса Y, что П X; = X. Минимальный

;=1

по включению П-предельный относительно Y класс называется П-граничным относительно Y классом.

Класс Т является граничным относительно класса Planar и его единственность эквивалентна тому, что любого G 6 Т класс Planar П Free({G}) — НМ-простой.

Во втором разделе показывается, что при любом фиксированном к задача НМ в классе Planar П Free({Pk}) полиномиально разрешима (следствие из леммы 2.1).

В третьем разделе двумя способами (как следствие из леммы 2.4 и в теореме 2.1) доказывается, что при любом фиксированном i класс Planar П Free({Ti l i}) является НМ-простым.

Четвертый раздел содержит важный результат (лемма 2.10) о сведении задачи о независимом множестве в классе Planar nFree({S'i}) к задаче НМ для графов из того же класса, степени вершин которых не превосходят 16г2 — 1 (звезда — граф, получаемый подразбиением каждого ребра графа КНа его основе доказана следующая

Теорема 2.2. При любом фиксированном к класс PlanarnFree({Ti2 fc}) является НМ-простым.

Пятый раздел посвящен доказательству самого важного утверждения всей главы. Здесь рассматриваются яблоки, где яблоко А* — граф, получаемый соединением ребром изолированной вершины и цикла Ct. Основным результатом второй главы является

"Corncil D. G., Per] Y., Stewart L. К. Л linear recognition algorithm for cographs // S1AM J. Comput. — 1985. — V. 14.

- P. 926-934.

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

Теорема 2.3. Для любого фиксированного к > 3 задана НМ в классе Planar П Free({Ak, Ak+ ь • • •}) полиномиально разрешима.

Из теоремы 2.3 легко следует, что при любых фиксированных i,j класс Planar П Free({Titij}) является НМ-простым (для этого достаточно положить к = г + j + 1 и заметить, что Free({Tijj}) С Free({Ai,, At+i,...})). Результаты главы 2 опубликованы в работах [1,3,4,6,15,16].

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

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

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

Пусть В — граф, получаемый добавлением одной вершины к графу Р5 и всех ребер, соединяющих эту вершину с вершинами данного пути, а В,- граф, получаемый из графа 2Л"3 добавлением двух ребер, соединяющих пары вершин степени 2 из разных треугольников.

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

Операция замены ребра е = (а, Ь) некоторого графа графом G состоит в удалении этого ребра с последующим отождествлением вершины а с одной вершиной степени 2 графа G и вершины Ь с другой вершиной степени 2 графа G. Считаем, что граф G содержит автоморфизм, переводящий вершины степени 2 друг в друга, поэтому получившийся граф не зависит от того, какая именно вершина степени 2 графа' G отождествляется с вершиной а.

Для произвольной бинарной последовательности (Вгп(оо)-последовательности) 7т = {ttj , щ,...} обозначим через Тж граф, получаемый из Т заменами некоторых его ребер. Для каждой компоненты Т и для любого натурального i все три ребра, отстоящие от вершины степени 3 на расстоянии 2i— 1, заменяются графом Кц — е, если 7Г; = 0, или графом В, если 7г; = 1. Через Dж обозначим граф, получаемый из D заменой каждого ребра, не принадлежащего треугольникам. Любая такая операция состоит в замене

трех ребер каждой компоненты связности, отстоящих от соответствующих вершин треугольника на расстоянии i — 1, графом К^ — е, если тг( = 0, или графом В, если 7r¡ = 1. Граф D'n — результат применения к графу Т^ определенной процедуры. Она состоит в том, что к каждой его вершине х, окрестность которой порождает пустой граф из трех вершин 2/i,j/2, Уз, применяются следующие действия:

1. Вершина х заменяется на три попарно смежные вершины x¡, хг и х3.

2. Добавляются ребра (хиУ1),(хьУ2)Лхз,Уз)-

Пусть Т„ — множество конечных графов, являющихся порожденными в графе Т„. Аналогично вводятся классы D„ и D,. Основными результатами главы 3 являются следующие утверждения.

Теорема 3.1. Для любой Вт(со)-последователъности ж класс D* является 3-ВР-граничным.

Теорема 3.2. Для произвольной Вт(оо)-последователъности 7Г класс Т„ и класс D, являются 3-РР-граничными.

В замечаниях ко второму разделу показывается, что найденные в обоих теоремах семейства граничных классов не совпадают со всем множеством таких классов ни для одной из рассматриваемых задач. Здесь также показывается, что для произвольного подмножества N С {5,6,7,...} совокупность граничных классов для задачи ВНП[ЕСо1ог(3) П Free({Ka : s £ N})} континуальна (EColor(3) — множество графов, не являющихся реберно 3-раскрашиваемыми).

Третий раздел посвящен случаям полного описания множества относительных граничных классов. Здесь дается обзор известных таких указаний и добавляется несколько новых. Результаты главы 3 опубликованы в работах [7,8,10,12,13].

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

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

Задан граф G и список Z/<G> = {Lv^{Vl),Lv^(v2),... ,Lv^(vn)} (V(G) = {i/i, i>2, •.., tfn})- Множество Lv^(ví) — конечное множество номеров разрешенных цветов для вершины v¡, при этом номер цвета отождествляется с самим цветом.

раскраской называется такое отображение с : V(G) —» (j Lv^c\ví), что выполняются

í=I

следующие два условия:

(1). Для любой вершины х число с(х) принадлежит множеству х).

(2). Каждый путь, соединяющий две одноцветные вершины и и v, содержит такую

вершину w, что c(w) > с(и).

Задача о вершинном списковом ранжировании (задача ВСР) для данного графа G и множества состоит в том, чтобы определить, имеет ли этот граф V раскраску. Смысл множества LE^C\ понятия Ь^'^-раскраски и задачи о реберном списковом ранжировании (задачи PCP) определяются по аналогии.

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

Теорема 4.1. Если X — наследственный класс графов, то любой РП[Х)-слодаснмй класс не является минимальным.

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

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

1. Cornet — множества деревьев, в которых существует вершина, инцидентная всем

листьям, кроме одного.

2. Hammer — графов ребер графов из Comet.

оо

3. Star — множества (J

¿—1

4. Sun — графов ребер графов из Star.

Четвертый раздел начинается с установления связей между понятиями минимального сложного и граничного классов. Именно, доказывается, что П-сложный граничный класс является минимальным сложным (теорема 4.3) и что в семействе конечно определенных классов эти понятия совпадают (теорема 4.4). Показывается, что Star и Sun — конечно определенные классы графов (лемма 4.10), а также, что классы Comet и Hammer таким свойством не обладают (лемма 4.9). Одними из основных результатов всей диссертации являются

Теорема 4.5. Класс Comet является как минимальным ВСР-сложным, так и минимальным PCP-сложным. Класс Hammer является минимальным ВСР-сложным.

Теорема 4.6. Класс Star является минимальным ВСР-сложным и минимальном РСР-сложнъш, а класс Sun является минимальным ВСР-сложным.

Данные первые примеры минимальных сложных классов являются и граничными классами для соответствующих задач. Тем самым, конструктивно доказано предположение о существовании П-сложных граничных классов7. Полученные в главе 4 результаты опубликованы в работах [11,14).

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

[1]. Алексеев В. Е., Малышев Д. С. Классы планарных графов с полиномиально разрешимой задачей о независимом множестве // Дискретный анализ и исследование операций. - 2008. - Том 15, №1. - Стр. 3-10.

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

[3]. Малышев Д. С. Граничные классы для задачи о независимом множестве в классе планарных графов // Вестник Нижегородского университета им. Н. И. Лобачевского. Раздел «Математика». — 2007. — №2. — Стр. 165-168.

[4]. Малышев Д. С. Граничные классы относительно класса планарных графов для задачи о независимом множестве // Материалы VI молодежной научной школы по дискретной математике и ее приложениям (Москва, 16-21 апреля 2007 г.), часть II. — Стр. 16-20.

[5]. Малышев Д. С. Граничные классы для задач на графах // Вестник Нижегородского университета им. Н. И. Лобачевского. Раздел «Математическое моделирование и оптимальное управление». — 2008. — №6. — Стр. 141-146.

[6]. Малышев Д. С. О единственности граничного класса для задачи о независимом множестве в классе планарных графов // Материалы XV международной конференции студентов, аспирантов и молодых ученых «Ломоносов 2008» (Москва, 9-12 апреля 2008 г.), секция «Вычислительная Математика и Кибернетика». — Стр. 43-44.

[7]. Малышев Д. С. О бесконечности множества граничных классов для задачи о 3-раскраске // Тезисы докладов XV международной конференции «Проблемы теоретической кибернетики» (Казань, 2-7 июня 2008 г.). — Стр. 79.

[8]. Малышев Д. С. О бесконечности множества граничных классов в задаче о реберной 3-раскраске // Дискретный анализ и исследование операций. — 2009. — Т. 16, т. - Стр. 37-43.

[9]. Малышев Д. С. Граничные классы графов для некоторых задач распознования // Дискретный анализ и исследование операций. — 2009. — Т.16, №2. — Стр. 85-94.

[10]. Малышев Д. С. Континуальные множества граничных классов графов для задач о раскраске // Дискретный анализ и исследование операций. — 2009. — T.1G, Л'«5. - Стр. 41-51.

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

[12]. Малышев Д. С. О количестве граничных классов в задаче о 3-раскраске // Дискретная математика. — 2009. — Т. 21, JV>4.

[13]. Малышев Д. С. О недавних результатах в теории граничных классов графов // Материалы VIII международной конференции «Дискретные модели в теории управляющих систем» (Моск. обл., 6-9 апреля 2009 г.). — Стр. 132-136.

[14]. Малышев Д. С. О минимальных сложных элементах решетки наследственных классов графов // Материалы VII молодежной научной школы по дискретной математике и ее приложениям (Москва, 18-23 мая 2009 г.).

[15]. Alekseev V. Е., Lozin V. V., Malyshev D. S., Millanic M. The maximum independent set problem in planar graphs // Mathematical Foundations of Computer Science (Torun, 25-29 August 2008). Proc. in Lecture Notes in Computer Science. - V. - 5162. -P. 96-107.

[16]. Alekseev V. E., Malyshev D. S. Planar graph classes with the independent set problem solvable in polynomial time // (Russian) translation in Journal of Applied and Industrial Mathematics. — 2009. — V. 3, №1. — P. 1-5.

Подписано в печать 21.10.2009. Формат 60x84 1/16. Бумага офсетная. Печать офсетная. Усл. печ. л. 1. Тир. 100. Зак. 600.

Типография Нижегородского госуниверситета 603000, Н. Новгород, ул. Б. Покровская, 37.

Введение

1 Критерий граничности и его применения

1.1 Терминология и обозначения.

1.1.1 Множества, графы и подграфы.

1.1.2 Множества вершин и метрические характеристики

1.1.3 Классы графов.

1.2 П-граничные классы графов

1.3 Критерий граничности.

1.4 Условия граничности классов Т и D.

1.4.1 Применение критерия граничности к рассматриваемым классам графов.

1.4.2 Понятие древесной ширины графа и доказательство достаточного условия граничности классов Т и D.

1.5 Граничные классы для задачи о наибольшем подграфе.

1.5.1 Задача о ребер но наибольшем Х-подграфе.

1.5.2 Задача о вершинно наибольшем Х-подграфе.

1.5.3 Задача о наибольшем связном подграфе.

1.5.4 Некоторые замечания.

1.6 Применение понятия древесной ширины к поиску новых случаев граничности классов Т и D.

1.6.1 Покрытия и разбиения.

1.6.2 Множества вершин и ребер.

1.6.3 Задача о непересекающихся путях.

1.6.4 Новые случаи граничности классов Т и D

1.7 О граничности классов со(Т) и co(D).

2 НМ-граничные классы относительно класса планарных графов

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

2.1.1 Относительные П-граничные классы.

2.1.2 Рассматриваемый случай.

2.2 О сложности задачи НМ в классе планарных графов, не содержащих длинных порожденных путей

2.3 Полиномиальный алгоритм решения задачи НМ в классе планарных графов без порожденного подграфа Тхд^-.

2.3.1 Некоторые определения и вспомогательные результаты

2.3.2 Эффективный алгоритм решения задачи НМ в рассматриваемом случае.'.

2.4 О сложности задачи о независимом множестве в классе планарных графов без порожденного подграфа Т\$,к

2.4.1 Планарные графы, не содержащие больших порожденных звезд;.

2.4.2 Планарные графы без порожденного подграфа ■ ■ ■

2.5 Полиномиальная разрешимость задачи НМ в классе планарных графов, не содержащих больших порожденных яблок.

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

2.5.2 Доказательство основного результата.

3 Оценки мощности множества граничных классов

3.1 Количественные аспекты теории граничных классов.

3.2 Задачи с континуальным множеством граничных классов . 71 3.2.1 Задача о вершинной 3-раскраске.

3.2.2 Задача о реберной 3-раскраске.

3.2.3 Некоторые замечания.

3.3 Новые случаи полного описания множества относительных граничных классов.

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

4.1 Вопросы существования минимальных сложных элементов решетки наследственных классов графов

4.2 О несуществовании минимальных сложных классов для некоторых задач теории графов.

4.3 Вычислительная сложность задач о списковом ранжировании в некоторых классах графов

4.4 Минимальные сложные классы графов для задач о списковом ранжировании

4.4.1 О связях между минимальными сложными и граничными классами.

4.4.2 Наследственные замыкания комет и молотов.

4.4.3 Наследственные замыкания звезд и солнц.

Изучение тех или иных классов графов уже достаточно давно составляет содержание значительной части работ по теории графов и ее приложениям. Вместе с тем, с некоторого времени наметился устойчивый интерес к исследованию не отдельных классов графов, а именно целых семейств классов графов, обладающих некоторым общим свойством [3, 22]. Одной из фундаментальных научных проблем, на решение которых направлена часть этих работ и сама постановка которых выводит на такой высокий уровень общности, является задача анализа сложности задач на графах.

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

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

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

В работе [24] рассматривалась задача о независимом множестве, а также класс Т — класс всех графов, у которых каждая компонента связности является деревом с не более чем 3 листьями. Там же было установлено, что этот класс является граничным для задачи о независимом множестве. Исследования по нахождению граничных классов были продолжены в статьях [25, 26], в которых помимо класса Т рассматривался еще и класс D, а также задачи, для которых эти классы являются граничными. Класс D состоит из графов, каждая компонента связности которых является либо простым путем, либо получается отождествлением всех вершин треугольника с тремя концевыми вершинами трех простых путей.

В первой главе настоящей диссертации исследуются общие свойства задач на графах, для которых два указанных класса являются граничными. Внимание именно к этому вопросу обусловлено тем обстоятельством, что к настоящему времени доказана граничность класса Т для 9 задач, а класса D для 5 задач. В данной главе понятие граничного класса уточняется и доказывается критерий граничности произвольного класса графов. Здесь также формулируются условия граничности двух рассматриваемых классов графов и на их основе к известным случаям граничности этих классов добавляется определенное количество новых. Большинство из данных примеров принадлежат списку Гэри и Джонсона [7]. В первой главе решается вопрос о мощности множества задач на графах, для которых классы Т и D — граничные одновременно. Именно, конструктивным образом доказывается, что оно несчетно. Наконец, указываются первые примеры задач, для которых классы, состоящие из графов, дополнительных к графам из Т и D, являются граничными. Результаты первой главы опубликованы в работах [5, 12, 16, 20].

До сих пор неизвестно, существуют ли граничные классы для задачи о независимом множестве, отличные от класса Т. Вопрос о существовании таких классов эквивалентен вопросу о существовании такого графа G & Т, что эта задача в наследственном классе графов, определяемом запрещенным порожденным подграфом G, не является полиномиально разрешимой [24]. О трудности проблемы говорит тот факт, что в настоящее время не известен сложностной статус указанного класса даже для случая G = Р5.

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

Единственность класса Т эквивалентна доказательству того, что для любого G £ Т задача о независимом множестве в классе планарных графов, не содержащих порожденного подграфа G, полиномиально разрешима. Хотя и здесь этого доказать не удается, имеется более значительный прогресс к достижению намеченной цели, чем в общем случае. Именно, во второй главе устанавливается полиномиальная разрешимость рассматриваемой задачи для бесконечного количества различных классов графов исследуемого типа. Эти результаты опубликованы в [4, 10, 11, 13, 27, 28].

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

Вторая часть, в основном, посвящена обзору известных случаев полного описания множества относительных граничных классов. Эти сведения могут быть полезными при оценках мощности множества просто граничных классов или при выдвижении предположений о его строении. Данная часть завершается полным указанием рассматриваемой совокупности для ряда новых случаев. Полученные в третьей главе результаты опубликованы в [14, 15, 17, 19, 20].

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

Четвертая глава диссертации нацелена на исследование существования минимальных «сложных» классов. Основополагающим мотивом обращения к данному вопросу являлось отсутствие какой-либо информации о таких классах графов. В первой части главы рассматривается задача распознавания принадлежности наследственному классу графов и показывается, что для любой такой NP-полной задачи нет ни одного минимального «сложного» класса. В частности, это верно при любом фиксированном к > 3 для обеих задач о fc-раскраске. Вторая часть посвящена доказательству минимальности некоторых классов для задач о списковом ранжировании. Данные классы графов для этих задач являются еще и граничными. Тем самым получен ответ на выдвинутое в работе [25] предположение о существовании «сложных» граничных классов, поскольку все известные до этого граничные классы являлись «простыми». Результаты, полученные в четвертой главе, опубликованы в работах [18, 21].

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

1. Алексеев В. Е. О сжимаемых графах // В сб. Проблемы кибернетики, вып. 36, 1979. - Стр. 23-32.

2. Алексеев В. Е., Малышев Д. С. Классы планарных графов с полиномиально разрешимой задачей о независимом множестве // Дискретный анализ и исследование операций. — 2008. — Том 15, №1. - Стр. 3-10.

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

4. Алексеев В. Е., Таланов В. А. Графы. Модели вычислений. Алгоритмы.Н.Новгород: Из-во Нижегородского университета, 2005. — 308 Стр.

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

6. Емеличев В. А., Мельников О. И., Сарванов В. И., Тышкевич Р. И. Лекции по теории графов. — М.: Наука, гл. ред. физ.-мат. лит., 1990. — 384 Стр.

7. Зыков А. А. Основы теории графов. —- М.: Наука, 1987. — 383 Стр.

8. Малышев Д. С. Граничные классы для задачи о независимом множестве в классе плапарных графов // Вестник Нижегородского университета им. Н. И. Лобачевского. Раздел «Математика». — 2007. — №6. — Р. 165-168.

9. Малышев Д. С. Граничные классы относительно класса планарных графов для задачи о независимом множестве // Материалы VI молодежной научной школы по дискретной математике и ее приложениям (Москва, 16-21 апреля 2007 г.), часть II. — Стр. 16-20.

10. Малышев Д. С. Граничные классы для задач на графах // Вестник Нижегородского университета им. Н. И. Лобачевского. Раздел «Математическое моделирование и оптимальное управление». — 2008. — №6. Р. 141-146.

11. Малышев Д. С. О бесконечности множества граничных классов для задачи о 3-раскраске // Тезисы докладов XV международной конференции «Проблемы теоретической кибернетики» (Казань, 2-7 июня 2008 г.). — Стр. 79.

12. Малышев Д. С. О бесконечности множества граничных классов в задаче о реберной 3-раскраске // Дискретный анализ и исследование операций. 2009.- Т.16, т. - Стр. 37-43.

13. Малышев Д. С. Граничные классы графов для некоторых задач расноз-нования // Дискретный анализ и исследование операций. — 2009.— Т.16, №2. Стр. 85-94.

14. Малышев Д. С. О количестве граничных классов в задаче о 3-раскраске // Дискретная математика. — 2009. — Т. 21. (принято к публикации).

15. Малышев Д. С. О недавних результатах в теории граничных классов графов // Материалы VIII международной конференции «Дискретные модели в теории управляющих систем» (Моск. обл., 6-9 апреля 2009 г.).- Стр. 132-136.

16. Малышев Д. С. О минимальных сложных элементах решетки наследственных классов графов // Материалы VII молодежной научной школы по дискретной математике и ее приложениям (Москва, 18-23 мая 2009 г.) (в печати).

17. Харари Ф. Теория графов. — М.: Мир, 1982. — 301 Стр.

18. 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.

19. Alekseev V. E., Malyshev D. S. Planar graph classes with the independent set problem solvable in polynomial time // (Russian) translation in Journal of Applied and Industrial Mathematics. 2009. — V. 3, №1. - P. 1-5.

20. Arnborg S., Proskurowski A. Linear time algorithms for NP-hard problems, restricted to partial &-trees // Discrete Applied Mathematics. — 1989. — V. 23. P. 11-24.

21. Bodlaender H. L. Dynamic programming on graphs with bounded treewidth // Automata, Languages and Programming (Tampere, 11-15 July 1988). Proc. in Lecture Notes in Computer Science. — 1988. — V. 317. — P. 105-118.

22. Breu H., Kirkpatrick D.G. Unit disk graph recognition is NP-hard // Computational Geometry. — 1998. — V. 9. P. 3-24.

23. Chudnovsky M., Robertson N., Seymour P., Thomas R. The strong perfect graph theorem // Arm. of Math. — 2006. V. 164. — P. 51-229.

24. Courcelle В., Makowsky J. A., Rotics U. Linear time solvable optimization problems on graphs of bounded clique-width // Theory Comput. Syst. — 2000. V. 33. - P. 125-150.

25. Corneil D. G., Perl Y., Stewart L. K. A linear recognition algorithm for cographs // SIAM J. Comput. 1985. - V. 14. - P. 926-934.

26. Dereniowski D. The complexity of list ranking of trees // Ars Combinatoria.- 2008. V. 86. - P. 97-114.

27. Faria L., Figueiredo С. H., Gravier S., Mendonga C. F. X., Stolfi J. On maximum planar induced subgraphs // Discrete Applied Mathematics. — 2006. V. 154. - P. 1774-1782.

28. Faria L., Figueiredo С. H., Mendonga C. F. X. Splitting number is NP-complete // Discrete Applied Mathematics. — 2001. — V. 108. — P. 65-83.38| Gallai T. Transitiv orientierbare graphen // Acta Math. Acad. Sci. Hung. — 1967. V. 18. - P. 25-66.

29. Hladky J. Structural properties of graphs — probabilistic and deterministic point of view (Biparite subgraphs in a random cubic graph) // Bachelor's degree thesis, Department of Applied Mathematics, Charles University in Prague, 2006.

30. Holyer I. The NP-completeness of edge-coloring // SIAM J. Comput. — 1981.- V. 10, m. P. 718-720.

31. Jamison R.E. Coloring parameters associated with rankings of graphs // Congressus Numerantum. — 2003. V. 164. — P. 111-127.

32. Kochol M., Lozin V., Randerath B. The 3-colorability problem on graphs with maximum degree four// SIAM J.Comput. — 2003. — V. 32, №5. — P. 1128-1139.

33. Ladner R. E. The computational complexity of provability in systems of modal prepositional logic // SIAM J. Comput. — 1977. — V. 6. — P. 467-480.

34. Lozin V. V. Boundary classes of planar graphs // Combinatorics, Probability and Computing. 2008. - V. 17. - P. 287-295.

35. Lozin V. V., Rautenbach D. On the band-, tree- and clique-width of graphs with bounded vertex degree // Discrete Mathematics. — 2004. — V. 18. — P. 195-206.

36. Lozin V. V., Millanic M. Maximum independent sets in graphs of low degree // Proceedings of the ACM-SIAM symposium on descrete algorithms (New Orleans, 7-9 January 2007). P. 874-880.

37. Middendorf M., Pfeiffer F. On the complexity of the disjoint path problem // Combinatorica. 1993. - V. 13, K°- 1. — P. 97-107.

38. Minty G. J. On maximal independent sets in claw-free graphs // J. Cornbin Theory, Series B. 1980. - V. 28, №3. - P. 284-304.

39. Muradian D. The bandwidth minimization problem for cyclic caterpillars with hairs length 1 is NP-complete // Theoretical Computer Science. — 2003. — V. 307. P. 567-572.

40. Roussopoulos N. A max{m,n} algorithm for determining the graph H from its line graph G // Information Processing Letters. — 1973. V. 2, № 4. — P. 108-112.

41. Robertson N., Seymour P. Graph minors. III. Planar tree-width // J. Combin. Theory, Series B. 1986. - V. 41. - P. 92-114.

42. Scheffier P. A practical linear algorithm for vertex disjoint path in graphs with bounded treewidth // Technical report № 396, Department of Mathematics, Technische Universitat Berlin. — 1994. — P. 21.

43. Sprague A.P. An 0(n^opn)-algorithm for bandwidth of interval graphs // J. Discr. Math. 1994. - V. 9. - P. 213- 220.