Относительные граничные классы и факторизация семейства наследственных классов графов Текст научной статьи по специальности «Математика»

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

Похожие темы научных работ по математике , автор научной работы — Малышев Дмитрий Сергеевич

RELATIVE BOUNDARY CLASSES AND FACTORIZATION OF THE FAMILY OF HEREDITARY GRAPH CLASSES

The notion of a relative boundary class is helpful in the analysis of the computational complexity of graph problems in the family of hereditary classes. The article considers the factorization of the lattice of hereditary graph classes with respect to the equality of relative boundary systems. Some features of the lattice are revealed.

Текст научной работы на тему «Относительные граничные классы и факторизация семейства наследственных классов графов»

Вестник Нижегородского университета им. Н.И. Лобачевского, 2013, № 3 (1), с. 181-187

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

© 2013 г. Д-С. Малышев

Национальный исследовательский университет «Высшая школа экономики», Н. Новгород;

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

Поступила в редакцию 04.02.2013

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

Ключевые слова: наследственный класс, относительный граничный класс, факторизация.

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

Класс графов X называется наследственным, если он замкнут относительно изоморфизма и удаления вершин. Любой наследственный класс (и только наследственный класс) графов X может быть задан множеством своих запрещенных порожденных подграфов 5. В этом случае принята запись X = Егее(8). Минимальное по включению множество 5 с таким свойством существует и единственно, оно обозначается через ¥отЬ(Х). Класс X называется конечно определенным, если Forb(X) конечно, и бесконечно определенным в противном случае. Если | Forb(X) |< к, то X называется к< -определенным.

Пусть П - какая-либо КР-полная задача на графах. Наследственный класс графов называется П -простым, если задача П в этом классе полиномиально разрешима. П -сложным называется наследственный класс графов, не являющийся П -простым. На протяжении всей работы считается, что Р^МР, и это условие явно не включается в формулировки утверждений данной работы. Наследственный класс графов В называется П -предельным, если существует такая бесконечная последовательность В 2В 2■■■ из П -сложных классов графов, что

В = П В . Минимальный по включению П -

предельный класс называется П -граничным. Значение понятия граничного класса графов состоит в том, что конечно определенный класс графов является П -сложным тогда и только тогда, когда он содержит какой-нибудь П -граничный класс [1]. Это утверждение неверно для бесконечно определенных классов [1].

Если наследственный класс не включает никакой П -граничный класс, то он обязательно является П -простым [1]. Поэтому было бы интересно исследовать те бесконечно определенные случаи, для которых включение П -граничного класса означает «труднорешае-мость» задачи П. Такого рода исследованию посвящена первая из частей настоящей работы. Именно, для фиксированного к рассматривается возможность включения заданного класса X в некоторый к< -определенный класс У, который, в свою очередь, содержит некоторый П -граничный класс. Основной результат первой части состоит в том, что такого рода класс У существует тогда и только тогда, когда хотя бы

один класс из некоторой конечной совокупности (алгоритмически формируемой по классу X) включает какой-нибудь П -граничный класс.

Знание всех П -граничных классов позволяет полностью описать все конечно определенные П -простые классы. К сожалению, на настоящее время ни для одной задачи на графах не получено полного описания всех граничных классов. Вместе с тем, если рассматривать не все множество наследственных классов, а только какую-то его часть, можно надеяться на исчерпывающее решение проблемы [2, 3]. При этом возникает понятие относительного граничного класса. Пусть X - некоторый П -сложный класс. Класс В называется П -предельным относительно X, если существует такая последовательность В 2 В 2 ■■■ из П -

сложных классов графов, что В = П В . Если В

является минимальным по включению классом с этим свойством, то он называется П -граничным относительно X. Класс У называется конечно определенным относительно X, если существует такое конечное множество графов 5, что У = X Free(5). Справедливо следующее утверждение:

Теорема 1. Конечно определенный относительно X класс графов является П -сложным тогда и только тогда, когда он включает какой-нибудь П -граничный относительно X подкласс.

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

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

В работе приняты следующие обозначения:

0 — класс всех графов; Н - множество всех

наследственных классов графов; Вп (X) -

множество П -граничных относительно X классов графов.

Расширение пределов применимости теоремы 1

Одно из имеющихся доказательств теоремы

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

Лемма 1. Любая бесконечная монотонно убывающая последовательность из наследственных классов, сходящаяся к собственному подмножеству У множества X, содержит включенный в X член тогда и только тогда, когда существует такой конечно определенный класс 2, что У с 2 с X.

Доказательство. Достаточность очевидна, докажем необходимость. Пусть

Forb(У) = . Обозначим через У класс Free(). Ясно, что

У 2 У 2 ■■■ и что У = ПУ . По условию, суще-

ствует такое / , что У. с X . Т.к. сходится

к У с X , то для некоторого / > / имеем

У, с X. Тогда справедливо включение

У с 2 с X, где 2 = У, . Лемма 1 доказана.

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

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

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

Заметим, что в общем случае класс X может быть и бесконечно определенным. Поэтому при формализации понятия алгоритма (т.е. выборе модели вычислений) никакие стандартные модели (оперирующие с кодами входной информации лишь конечной длины) для решения поставленной задачи, видимо, непригодны. Вместе с тем для построения класса У необходимо иметь операции, связанные с «заглядыванием внутрь» класса X и порождением какой-нибудь полезной для этого построения информации. Поэтому в качестве модели вычислений предлагается рассмотреть оракул, запрос к которому в виде произвольного конечного множества графов 5 возвращает подмножество F (5) с Forb(X), для каждого элемента которого ни один граф из 5 не является порожденным подграфом.

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

Если 5 = О, О2 . Оі > - информация, приписанная текущему узлу дерева, то все непосредственные потомки этого узла строятся по следующему правилу. На вход оракулу подается множество 5, и рассматривается множество Г(5). Если оно является пустым и і < к , то текущий узел объявляется нужным листом. Если это множество не пусто и і = к, то узел объявляется ненужным листом. Если же оно не пусто и і < к , то рассматривается произвольный граф Н є Г(5), определяются все его попарно неизоморфные порожденные подграфы Н,Н. Н и к текущему узлу добавляются г пронумерованных непосредственных потомков, ] -му из которых приписано

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

Лемма 2. Если У' с X', то для любого О є ¥огЬ(Х ') существует такой граф Н є ГогЬу '), что О - надграф Н.

Доказательство. Предположим, что такого графа Н не найдется. Тогда граф О должен принадлежать классу У (поскольку он не содержит ни одного графа из ГогЬУ ) в качестве порожденного подграфа). Но тогда включение Ус X не может иметь место, т.к. О й X . Получаем противоречие. Поэтому наше предположение было неверным. Лемма 2 доказана.

Теорема 2. Если существует кй -определенный подкласс X, включающий какой-нибудь П -граничный класс, то существует класс из построенной совокупности с таким же значением.

Доказательство. Пусть У = Ггее(5) - конечно определенное подмножество X , | 51< к , В - П -граничный класс, включенный в У. Дополним для наглядности процедуру построения дерева приписыванием каждому его ребру того графа, который добавляется при переходе от родителя к непосредственному потомку. Рассмотрим путь Р наибольшей длины от корня данного дерева к некоторому его узлу, что приписанные его ребрам графы образуют некоторое подмножество 5 множества 5. Длина этого пути не менее чем 1, т.к. по лемме 2 существует граф из 5 , который является порожденным подграфом графа О .

Покажем, что Р должен заканчиваться в листе дерева. Предположим противное, тогда

обозначим через О граф, приписанный последнему ребру Р, а через О обозначим произвольный граф непустого множества F(5 ). Поскольку О'' е Forb(X), то У с Free(5' и ). Поэтому по той же лемме 2 существует граф из Forb(У), являющийся порожденным подграфом графа О . Отсюда и из правил построения дерева заключаем, что путь Р не является наибольшим. Получаем противоречие с предположением. Конец пути Р совпадает именно с нужным листом дерева, т.к. иначе | 5 |= к, откуда следует, что 5 = 5 (напомним, что 5 с 5 и |5|= к) и У = Free(5) = Free(5') <х X.

Поскольку путь Р заканчивается в нужном листе, то Free(5 ) принадлежит сформированному множеству классов, причем Free(5 ) с X. Поскольку 5 с 5, то В с Free(5) с Free(5 ). Теорема 2 доказана.

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

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

Отношение равенства относительных граничных систем на множестве всех наследственных классов будем обозначать через Я . Иными словами, классы X,УеН находятся в отношении Я , если и только если Вп (X) = ВП (У). Легко видеть, что данное отношение является отношением эквивалентности и поэтому по теореме о факторизации оно разбивает Н на классы эквивалентности. Класс эквивалентности, содержащий наследственный класс X, будем

обозначать через Нп (X). Другими словами, Н п (X) = . Критерием принадлежности двух наследственных множеств одному классу эквивалентности по отношению Я* является следующее утверждение.

Теорема 3. Равенство Вп (X) = ВП (У) имеет место тогда и только тогда, когда для любого конечного множества графов 5 классы XnlFree(5) и У П| Free(5) либо одновременно П -простые, либо одновременно П -сложные.

Доказательство. Докажем сначала необходимость. Пусть существует такое конечное множество графов, что один из классов Xt^Free(5) и У П| Free(5) является П -простым, а другой П -сложным при выполнении равенства Вп (X) = Вп (У). Но тогда, по теореме 1 обязан существовать класс В еВп (X) ^ Вп (У), включенный ровно в один из упомянутых двух классов. Но тогда В еВп (X) ®ВП (У). Это невозможно, т.к. Вп (X) = ВП (У). Получаем противоречие с предположением. Докажем теперь достаточность. Пусть 2 - произвольный П -предельный класс либо относительно X , либо относительно У, а множество Forb(Z) совпадает с множеством . Рассмотрим две последовательности из классов графов X Free() 2 2XП|Free() 2■■■ и У Free() 2

2 У П| Free() 2 ■■■. Из определения класса 2 и посылки достаточности следует, что обе упомянутые последовательности обязательно состоят из П -сложных классов. Значит, если 2 является П -предельным относительно X (соответственно, относительно У ), то класс У2 (соответственно, X2) является П -предельным относительно У (соответственно, относительно X ).

Пусть В еВп (X) (соответственно, В е еВп (У)). Тогда УВ (соответственно, XВ) является П -предельным относительно У (соответственно, относительно X ). Отсюда и из вывода из предыдущего абзаца следует, что класс XУВ является П -предельным как относительно X , так и относительно У . Из этого факта и включений XУВ с ХВ с В , XУВ с УВ с В следует, что XУВ=ХВ = УВ = В , а значит, В еВп (X) и В еВп (У). Теорема 3 доказана.

Известная факторизация множества Н по отношению Я* позволяет решать задачу определения множества относительных граничных классов только для одного элемента из фактор-класса. Следующее утверждение позволяет су-

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

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

Доказательство. Очевидно, что любой элемент из Вп (XX) является П -предельным классом относительно У, вложенным в класс X. Покажем, что каждый класс из является П -предельным классом относительно YX. Отсюда будет следовать утверждение теоремы 4.

Пусть В еВп(У), В с X и В 2 В 2 ■■■ -последовательность из П -сложных частей У , сходящаяся к В . По лемме 1 существует такое число / , что В с X. Обозначим через В'

класс В . Последовательность В, 2 В9 2 ■■■

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

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

Я** : (X,У) ^35,|5|<да, X = У пFree(S) VУ = = X п Free(5) , затем взять по одному множеству графов из каждого фактор-класса по этому отношению и уже на совокупности этих представителей рассматривать отношение Я . Например, все конечно определенные классы (включая и множество всех графов) попадают в один класс эквивалентности по отношению Я** и поэтому в качестве представителя данного фактор-класса можно рассматривать множество О. Во-вторых, для конечно определенных графов X и У верны следующие «законы взаимности»:

(откуда следует, что Вп (XY) = В (X) п В (У)) и =

Отметим, что ни теорема 4, ни представленные следствия из нее в общем случае (т.е. когда X может быть и бесконечно определенным) не верны. Соответствующий пример был построен в работе [4].

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

Лемма 3. Объединение конечного числа конечно определенных классов является конечно определенным классом.

Доказательство. Пусть Х1,Х2,•••Хk - конечно определенные классы. Очевидно, что к

множество Forb(U Х ) состоит из графов, каж-

дый из которых является порожденным подграфом некоторого графа из 5 , где 5 - множество графов, содержащих каждый граф из

и Forb(X.) в качестве порожденного подграфа

и являющихся минимальными (относительно удаления вершин) с этим свойством. Поэтому

любой граф из 5 содержит не более чем 2 N

вершин, где N - суммарное количество вершин в графах из Forb(Xi). Значит, множество

5 конечно и поэтому множество Forb(UХ )

является конечным. Лемма 3 доказана.

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

Рассуждая по аналогии с доказательством соответствующего утверждения из [5], нетрудно показать справедливость следующего критерия относительной граничности.

Теорема 5. П -предельный относительно X класс В является П -граничным относительно X тогда и только тогда, когда для каждого О е В существует такое конечное множество графов 5 с Forb(В), что класс X п

пFree(5 ^ ) является П -простым.

Лемма 4. Ни один из П -граничных относительно X классов графов не покрывается конечным числом других П -граничных относительно X классов графов.

Доказательство. Предположим противное, т.е. что некоторый класс В еВп (X) покрывается отличными от В классами В,В. В, В (X). Поскольку В не включает ни один из классов В,В. В, то для любого г е 1,к существует граф О,. е В \В. По теореме 5 для любого г е 1, к существует такое множество £ с ГогЪ(В), что класс X о

о¥гее(£ ^) является П -простым. Ясно,

что ВВ с X о ¥гее(£ и>). Отсюда и из

включения В с и В следует, что В с X о

о и¥гее(£. ). Заметим, что объединение

конечного числа конечно определенных простых классов является простым классом. Это следует из того факта, что для любого графа за полиномиальное время от числа его вершин можно определить, каким из данных конечно определенных классов он принадлежит (или определить, что он не принадлежит ни одному из них). Отсюда и из леммы 3 следует, что В -подмножество П -простого конечно определенного относительно X множества к

X о и¥гее(£. ). Поэтому существует

такое конечное множество £ с ЕогЪ(В), что

Х о ¥гее(£) с X о и¥тее(£. ^ ). Поэтому

класс Х о ¥гее(£) является П -простым. Но по теореме 1 он является П -сложным. Получаем противоречие. Значит, наше предположение было неверным. Лемма 4 доказана.

Лемма 4 оказывается неверной в случае бесконечных относительных граничных систем. В работе [6] была выявлена совокупность граничных для задачи о реберной 3-раскраске классов графов, равномощная множеству всех бесконечных двоичных последовательностей. Каждый такой класс Тл задается бесконечной бинарной последовательностью п (его описание можно найти в [6]). Пусть п0 - бесконечная последовательность из нулей, а п - бесконечная двоичная последовательность, только г -й член которой равен 1. Для любого г > 0 класс Т является граничным для задачи о реберной 3-раскраске относительно О .

Далее будет доказан интересный результат о возможности представления любого подмноже-

ства произвольного конечного множества Вп (X) в виде другой относительной П -граничной системы.

Теорема 6. Если | Вп (X) |< да, то для любого

подмножества В ' с В (X) существует такое конечное множество графов £, что Вп (X о ¥гее(£)) = В'.

Доказательство. Рассмотрим множество Вп(Xо^гее(£))\В ’. По лемме 4 ни один его

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

В еВп (X о ¥тее(£)) \ В ’ существует граф О е В , не принадлежащий и В . Обозна-

чим через £ множество и . Ясно, что

Вп (X о ¥гее(£)) = = В ' (теорема 4). Теорема 6 доказана.

Для бесконечных множеств В (X) теорема

6 неверна даже при снятии ограничения на конечность множества £ . Пусть П - задача о реберной 3-раскраске, X = О, В ' = В \ , где

В - совокупность всех граничных классов для задачи о реберной 3-раскраске, п. = (0,1,0,0,0,1,1,01,1,0,0,0. ).

Лемма 5. Для любого множества £ множество В не равно ВП (Оо¥гее(£)).

Доказательство. Пусть существует такое множество £, что В (О о ¥гее