Задачи аппроксимации графов и наследственных систем

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

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

Актуальность темы

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

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

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

Приведем формулировки исследуемых задач и дадим краткий обзор известных результатов.

Задачи аппроксимации графов.

Задачи аппроксимации графов возникают при анализе систем взаимосвязанных объектов, в частности, в задачах классификации. При этом минимизируется число связей между классами и число недостающих связей внутри классов. Постановки и различные интерпретации этих задач можно найти в работах [21, 23, 31, 34, 37, 59] и др.

Будем рассматривать только обыкновенные графы, т. е. графы без петель и кратных ребер [9]. Следуя Тышкевич [27], обыкновенный граф будем называть М-графом, если каждая его компонента связности является полным графом. Обозначим через А4(У) класс всех М-графов на множестве вершин У, — класс всех М-графов на множестве вершин V, имеющих ровно к непустых компонент связности, Л4^к{У) класс всех М-графов на множестве V, имеющих не более к компонент связности, 2 ^ к < У.

Если = (V, Е) и (?2 = (V, Е2) — помеченные графы на одном и том же множестве вершин V, то расстояние /9(61, С72) между ними определяется как p (Gu G2) = Е^Е2 = Е Е21 + Е2Е11 т. е. p (Gі, G2) — число несовпадающих ребер в графах G и G2.

Впервые задача аппроксимации графа была сформулирована в 1964 г. Заном [59].

Задача А. Дан граф G—{V, E). Найти такой граф М* eM (V), что p (G, М*) = min p (G, М) = t (G).

MeM (V).

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

Задача АкДан граф G = (V, Е) и целое число /с, 2 ^ к ^ Найти такой граф М* єМк (У), что р (С, ЛГ) = min p (G, M) =f rk (G).

MeMk (V).

Задача A^kДан граф G = (V, E) и целое число fc, 2 ^ к ^ |V|. Найти такой граф М* что p (G, М*) = min p (G, М) тф{С). M€M^k{V).

Каждая из величин т (бг), 7*^(6?), Tk (G) называется аппроксимаци-онной сложностью графа G в соответствующей задаче аппроксимации графа. Очевидно, что для любого n-вершинного графа G и А: ^ 2 имеют место неравенства t{G) < r< Tfe (G) ^ n (n~1).

Известны также взвешенные и ориентированные аналоги этих задач. В ориентированных задачах каждая бикомпонента аппроксимирующего орграфа является полным симметрическим орграфом и отсутствуют дуги, ведущие из одной бикомпоненты в другую. Во взвешенных вариантах задана весовая функция т: V х V —>¦ N и Сгг) равно суммарному весу несовпадающих ребер в графах С и Сг.

Первые теоретические результаты, относящиеся к задачам аппроксимации графов, были получены в 60−70-е гг. XX в. В 1964 г. Заном [59] была решена задача, А для графов, представляющих иерархические структуры. В 1971 г. Фридман [28] показал, что задача, А для любого графа без треугольников сводится к построению в нем наибольшего паросочетания. В том же году Вейнер [5] предложил алгоритм решения задачи аппроксимации графов, не содержащих четырехвершинных подграфов ровно с пятью ребрами, однако не доказал, что результатом работы алгоритма действительно является М-граф, оптимально аппроксимирующий данный граф. Обоснование алгоритма Вейнера было дано Фридманом [30]. Он же [29, 31] показал, что для любого тг-вершинного графа С имеет место достижимая оценка.

Более сильный результат был установлен Томеску [55, 56]: для любого к ^ 2 и любого п-вершинного графа п — I)2 т<�к© < 4.

Позже Ильев и Фридман [20] доказали, что для любого к > 2и любого тгвершинного графа С при п ^ Ъ (к — 1) справедлива достижимая оценка.

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

В последние 12 лет задача, А неоднократно переоткрывалась и независимо изучалась под разными названиями (Correlation Clustering [34], Cluster Editing [37, 54]). В этих и других работах изучались и варианты задачи, в которых число кластеров ограничено, а также рассматривались более общие постановки задач.

В 2004 г. Бансал, Блюм и Чаула [34] и независимо Шамир, Шаран и Цур [54] показали, что задача, А является iVP-трудной, а Ильев и Та-левнин (см. [26]) установили, что взвешенная задача А^ iVP-трудна при любом фиксированном к ^ 2. В [54] доказано также, что задача Ak NP-трудна при любом фиксированном к ^ 2- в 2006 г. Гиотис и Гурусвами [46] опубликовали более простое доказательство этого результата. В том же году независимо Агеев, Ильев, Кононов и Талевнин [2] показали, что задачи, А 2 и А^{2Р-трудны} уже на кубических графах, откуда вывели, что все упомянутые варианты задачи аппроксимации графа, а также их взвешенные и ориентированные аналоги являются ./VP-трудными.

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

Полиномиальный алгоритм решения задачи минимизации называется а-приближенным, если он находит допустимое решение, для которого значение целевой функции не более чем в, а раз хуже оптимального значения. Величина, а называется гарантированной оценкой точности этого алгоритма. Говорят, что задача комбинаторной оптимизации принадлежит классу АРХ, если для нее существует а-приближенный алгоритм, где, а — некоторая константа.

Семейство алгоритмов Ае приближенного решения задачи на минимум называют полиномиальной приближенной схемой, если для любого? > 0 каждый алгоритм из А£ является (1 +^{-приближенным} алгоритмом.

Для исследования качества приближенных алгоритмов часто используется следующая идея построения алгоритмов с оценками (г, 6), предложенная Гимади, Глебовым и Перепелицей [6].

Пусть /С — некоторый класс задач минимизации, V — семейство вероятностных мер, определенных на /С. Для К е К. обозначим ОРТ (К) — оптимальное значение целевой функции, а, А {К) — значение, найденное алгоритмом А.

Говорят, что алгоритм, А имеет оценки (г, 8) относительно V, если.

Р{А{К) > (1 + ?)ОРТ (К)} ^ 6 для всех К € К. и Р Е V. Параметры ей 5 могут трактоваться как оценки относительной погрешности и вероятности несрабатывания алгоритма А, соответственно. Для подкласса Кп С /С задач размерности п говорят о семействах и оценках (еп, 5п).

Примером алгоритма с оценками (?п, 5п) является алгоритм Боров-кова [4] для класса К, п задач коммивояжера, в которых распределения из Тп получаются в результате случайного выбора п точек в ограниченной, односвязной области г-мерного евклидова пространства с достаточно гладкой границей.

Алгоритм, А называется асимптотически точным на классе задач /С, если существуют такие последовательности (?п, 6п), что для любого п алгоритм, А имеет оценки (?п, 8п) на подмножестве Кп С /С, причем £п -*" 0, 6п —> 0 при п —> оо.

Если при этом все 5п = 0, то такой алгоритм называется гарантированно асимптотически точным. Другими словами, алгоритм, А гарантированно асимптотически точен на классе задач /С, если существует такая последовательность єп, что для любого п.

А{К) < (1 + єп)ОРТ (І<) на подмножестве Кп С /С задач размерности п, причем еп —> 0 при п —>• оо.

Пусть @п — такое семейство п-вершинных графов, что для любого графа Є = (У, Е) Є 9п выполнено ^ ст^, где, а > О, 0 < /? < 2 — некоторые константы. Графы семейства Оп назовем неплотными.

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

В 2004 г. Бансал, Блюм и Чаула [34] предложили простой З-приближен-ный алгоритм для задачи А<^ и полиномиальный приближенный алгоритм с константной оценкой точности для задачи А, а также доказали, что взвешенная задача, А АРХ-трудна. В 2005 г. Чарикар, Гурусвами и Вирт [40] показали, что невзвешенная задача, А является ЛРХ-трудной и предложили для нее 4-приближенный алгоритм. В 2008 г. Айлон, Чарикар и Ньюман [33] предложили 3-приближенный алгоритм для невзве-шенной задачи, А и 2.5-приближенный алгоритм для ее взвешенной версии.

В 2006 г. Агеев, Ильев, Кононов и Талевнин [2] доказали существование рандомизированной полиномиальной приближенной схемы для задачи, а Гиотис и Гурусвами [46] предложили рандомизированную полиномиальную приближенную схему для задачи А^к (для любого фиксированного к ^ 2). В том же году Навроцкая, Ильев и Талевнин [19, 24] показали, что алгоритм локального поиска является гарантированно асимптотически точным для задачи на неплотных графах. Указав, что сложность полиномиальной приближенной схемы из [46] лишает ее перспективы практического использования, Колман, Саундерсон и Вирт [42] в 2008 г. предложили 2-приближенный алгоритм для задачи применив процедуру локального поиска к допустимому решению, полученному с помощью 3-приближенного алгоритма из статьи [34]. Для задачи А2 в работе [17] Ильевым, Ильевой и Навроцкой предложен простой (3 — 6/п)-приближенный алгоритм.

В диссертации исследуется также новый вариант задачи аппроксимации графа. Отличие новой постановки в том, что ограничения накладываются не на количество компонент связности, а на их мощность. Обозначим через A4P (V) множество всех М-графов на множестве V, в которых мощность каждой компоненты связности равна целому числу р, 2 ^ р ^ |V|, при этом |V| кратно р. Будем говорить, что М-граф принадлежит классу A4.

Задача Ар. Дан граф G = {V, E) такой, что |V| = pq, где p, q — целые положительные числа. Найти такой граф М*? A4P (V), что p (G, M*)= min p (G, M).

MeMP (V).

Задача А<�р. Дан n-вершинный граф G = (V, Е) и целое число р, 2 ^ р ^ п. Найти такой граф М*? M.

MeM.

Данные постановки рассматриваются впервые.

Задачи аппроксимации наследственных систем.

Задача аппроксимации графа является частным случаем задачи аппроксимации наследственной системы. Пусть V — непустое конечное множество, А С 2У — непустое семейство его подмножеств, удовлетворяющее следующей аксиоме наследственности:

Ах еЛ, А2 С, А Л2 в А.

Множества семейства, А называются независимыми, все остальные подмножества V — зависимыми. Семейство, А обычно называют системой независимости или наследственным семейством на V [48].

Семейство всех зависимых множеств обозначим V. Очевидно, что семейство V обладает свойством наследственности «вверх»:

1 е ?>, А С Д> ?>2 е V.

Каждое из семейств А, Т> однозначно определяет другое, поэтому естественно рассматривать их как различные стороны одного и того же объекта — наследственной системы [13, 50].

Наследственной системой 5 на множестве V называется разбиение семейства 2У всех подмножеств V на два непересекающихся семейства, А и V, где, А — система независимости, а Т> = 2У А. Базами наследственной системы 5 называются максимальные по включению независимые, а циклами — минимальные ио включению зависимые множества. Семейства всех баз и всех циклов системы 5 будем обозначать через В и С, соответственно. Очевидно, что каждое из семейств А, В, С и Т> однозначно определяет наследственную систему поэтому будем записывать? = (V, А), 5 = (V, В),? = (V, С) или? = (V, V) в зависимости от того, какая сторона наследственной системы будет нас интересовать.

В качестве примеров можно привести наследственные системы, в которых независимыми множествами являются линейно независимые семейства вектор-столбцов матрицы, паросочетания в графе, а также системы, зависимыми множествами которых являются /¿—связные остов-ные подграфы или вершинные покрытия графа. Еще одним примером наследственной системы является наследственная система графа. Рассмотрим произвольный связный граф = (V, Е) и наследственную систему Бс = (V, где Ас — семейство всех независимых множеств вершин графа С. Легко видеть, что любой цикл системы во имеет мощность 2 и соответствует ребру графа С.

Гиперграфом называется пара Н = (У, Е), где V — непустое конечное множество, а Е — семейство подмножеств V. Элементы множества V называются вершинами, а элементы семейства Е — ребрами гиперграфа Н. Произвольной наследственной системе в = (V, V) поставим в соответствие гиперграф = (У, Е), ребра которого взаимно однозначно соответствуют циклам этой системы. Наоборот, любой гиперграф Н порождает наследственную систему = циклами которой являются минимальные по включению ребра гиперграфа Н. Поэтому наследственную систему можно отождествлять с гиперграфом, никакое ребро которого не содержит другое ребро в качестве подмножества. Гиперграф Н = (У, Е) называется линейным [39], если любые два ребра гиперграфа Н пересекаются не более чем по одной вершине.

Пусть 5 = (V, С) — наследственная система, С — семейство ее циклов. Наследственная система называется линейной, если любые два ее цикла имеют не более одного общего элемента [47]. Очевидно, частным случаем линейной наследственной системы является наследственная система графа.

Важным частным случаем понятия наследственной системы является понятие матроида, введенное Уитни [58].

Матроид на множестве У может быть определен как наследственная система М = (У, А), в которой все базы любого множества И7 6 У имеют одинаковую мощность (базой множества IV называется любое его максимальное по включению независимое подмножество). Рангом матроида называется мощность любой базы множества У.

Наследственная система графа 6? = (У, Е) является матроидом тогда и только тогда, когда (7 — М-граф [38]. Такой матроид называется матроидом разбиения. Имеется в виду разбиение множества V вершин М-графа С на подмножества У,., 14, гДе У% ~~ множество попарно смежных вершин г-й компоненты связности, г — 1,., к. Таким образом, наследственная система М-графа может служить примером матроида.

С каждой наследственной системой 5 = (У, А) тесно связана дополнительная система или косистема & = (У, Т>'), семейство зависимых множеств которой определяется какТ>' =: А 6 А}. Наследственная система, дополнительная к матроиду, называется коматроидом.

Примером коматроида является коматроид разбиения — наследственная система, дополнительная к матроиду разбиения. Циклами этого коматроида являются вершинные покрытия М-графа С.

Наследственные системы и их частные случаи — матроиды и коматро-иды — естественным образом возникают в различных областях математики, таких как линейная алгебра, теория графов, теория трансверсалей (см. [3, 8, 57]) и других разделах комбинаторного анализа, а также в комбинаторной оптимизации [11, 12, 13, 15, 18, 27, 44, 45, 50, 51, 52, 53].

Рассмотрим одну из центральных оптимизационных задач на наследственных системах — задачу о максимальном независимом множестве наследственной системы. Пусть V — конечное множество, /: V —> П+ — весовая функция, Л — семейство независимых множеств наследственной системы = (V, А). Требуется найти шах{/(Х): X € Л}, (1) где /(.X) = ?/(*). х€Х.

Многие известные оптимизационные задачи являются частными случаями задачи (1). Некоторые из них полиномиально разрешимы (задача об остовном дереве максимального веса [51, 52], задача о максимальном паросочетании [43]). Однако, большая часть этих задач относится к классу А^Р-трудных (задача о рюкзаке, о максимальном независимом множестве вершин и о максимальной клике в графе, задача о 3-сочетании и другие).

Очень часто для приближенного решения N Р-труддых задач, сводящихся к схеме (1), применяется жадный алгоритм [36, 44, 45, 49].

Как следует из теоремы Радо-Эдмондса [45, 53], задача (1) разрешима жадным алгоритмом, если наследственная система 5 является матрои-дом. В связи с этим представляет интерес следующий вопрос: как сильно данная наследственная система отличается от матроида? Этот вопрос приводит нас к задаче аппроксимации наследственных систем, самая общая постановка которой такова.

Пусть АЛ (у) — некоторый класс матроидов на множестве V. Для заданной наследственной системы 5 = (V, Л) найти матроид М из класса Л4(У), который в каком-то смысле является самым близким к системе 5.

Мера близости т (5) наследственной системы? и матроидов класса Л4(У) (аппроксимационная сложность системы 5) может определяться по-разному в различных задачах.

Одна из постановок задачи матроидной аппроксимации, впервые сформулированная Р. И. Тышкевич, получается, если Sq = {V, Ag) — наследственная система графа G = (V, Е), АА (у) — класс всех матроидов разбиений на множестве V, a t (Sg) равно минимуму (по всем Me Л4(У)) мощности симметрической разности семейств циклов системы Sc и мат-роида М. Такая задача матроидной аппроксимации эквивалентна задаче аппроксимации графа. Непосредственным обобщением этой задачи является задача аппроксимации линейной наследственной системы, если S = (V, А) — линейная наследственная система, A4(V) — класс всех линейных наследственных систем, являющихся матроидами на V, a r (S) равно минимуму (по всем М € A4(V)) мощности симметрической разности семейств циклов системы S и матроида М.

В связи с задачей о максимальном независимом множестве (1) представляет интерес следующая постановка задачи аппроксимации наследственной системы.

Пусть ЛЛ (у) — класс всех матроидов разбиений с носителем V, величина t (S) определяется следующим образом: t (S) = min f (OptS) — f (OptM)I,.

MeM (V) где OptS — оптимальное решение задачи (1) на системе S = (V, A), а OptM ~ оптимальное решение аналогичной задачи на матроиде М с той же самой целевой функцией.

Получаем следующую задачу матроидной аппроксимации.

Для заданной наследственной системы S = (V, A) найти такой матроид разбиения М* € A4(V), что f (OptS) — f (OptM*) = t (S).

Если определить аппроксимациониую сложность наследственной системы 5 как г!*- тах /(°РШ) то оценка величины т (5) может рассматриваться как гарантированная оценка точности жадного алгоритма приближенного решения задачи (1).

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

Пусть У — конечное множество, /: У —" — весовая функция, V — семейство зависимых множеств наследственной системы Б = (V, Т>). Необходимо найти тт{/(1) :XeV}, (2) где = х€Х.

Многие задачи комбинаторной оптимизации, такие как задача о минимальном остовном А>связном подграфе [22, 25, 41], о минимальном вершинном покрытии [35], о покрытии множества [1] и другие, сводятся к задаче о минимальном зависимом множестве.

В работе [50] доказана теорема, являющаяся аналогом теоремы Радо-Эдмондса, из которой следует, что задача (2) разрешима «обратным» жадным алгоритмом, если наследственная система 5 является коматро-идом. Тогда возникает следующий вопрос: как сильно данная наследственная система отличается от коматроида? Так мы приходим к задаче аппроксимации наследственных систем коматроидамц самая общая постановка которой такова.

Пусть /С (У) — некоторый класс коматроидов на мноснсествеУ. Для заданной наследственной системы 5 = (V, Т>) найти коматроид К из класса К (У), который в каком-то смысле является самым близким к системе 5.

Мера близости т (Б) наследственной системы 5 и коматроидов класса /С (У) (аппроксимационная сложность системы 5) может определяться по-разному в различных задачах.

Пусть 1С (у) — класс всех коматроидов разбиений с носителем V. В связи с задачей (2) величина т (5) может быть введена следующим образом: т{8) = тіп^fiOptS) — !{ОріК)І, где ОуЬБ — оптимальное решение задачи (2) на системе 5 = (V, Р), а ОрЬК — оптимальное решение аналогичной задачи на коматроиде К с той же самой целевой функцией.

Рассмотрим следующую задачу аппроксимации наследственных систем коматроидами.

Для заданной наследственной системы Б = (V, Т>) найти такой ко-матроид разбиения К* Є /С (У), что fiOptS) — /(ОрШ*) = т (£). Можно также рассмотреть другое определение величины т (5):

• КОрж) и задачу аппроксимации наследственных систем коматроидами с новой величиной т (5).

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

Структура диссертации.

Диссертационная работа состоит из введения, трех глав, заключения и списка литературы.

Основные результаты диссертационной работы:

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

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

3. Рассмотрена новая постановка задачи аппроксимации графами с компонентами связности ограниченного размера. Выделены полиномиально разрешимые случаи. Доказано, что задача аппроксимации графами, мощность компонент связности которых не превосходит р, ./УР-трудна для любого фиксированного р ^ 3. Для случая р = 3 предложен алгоритм приближенного решения задачи и получена его гарантированная оценка точности.

Заключение

.

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