научная статья по теме ОБ АФФИННОЙ СВОДИМОСТИ КОМБИНАТОРНЫХ МНОГОГРАННИКОВ Математика

Текст научной статьи на тему «ОБ АФФИННОЙ СВОДИМОСТИ КОМБИНАТОРНЫХ МНОГОГРАННИКОВ»

ДОКЛАДЫ АКАДЕМИИ НАУК, 2012, том 443, № 6, с. 661-663

МАТЕМАТИКА

УДК 519.85

ОБ АФФИННОМ СВОДИМОСТИ КОМБИНАТОРНЫХ МНОГОГРАННИКОВ © 2012 г. А. Н. Максименко

Представлено академиком Ю.И. Журавлевым 30.06.2011 г. Поступило 23.11.2011 г.

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

Обычно комбинаторный многогранник задается следующим образом. Рассматривается множество X с {0, 1}й вершин й-мерного 0/1-куба, удовлетворяющее некоторому, специфичному для каждой задачи, набору ограничений. Сам многогранник определяется как выпуклая оболочка множества X, одновременно являющегося множеством его вершин. Поэтому далее много -гранник будет отождествляться с множеством его вершин.

Исследования графовых свойств комбинаторных многогранников приобрели особую популярность в 70-х годах прошлого века [1, 2] в связи с потенциальной возможностью решения соответствующих комбинаторных задач на основе техники локального поиска (которую, в частности, использует симплекс-метод). В настоящее время уже стало правилом начинать поиск эффективного решения комбинаторной задачи с изучения свойств ассоциированного многогранника. Один из популярных вопросов этого направления — поиск простого критерия смежности вершин многогранника. Из работ Пападимитриу [3], Мацуи [4], Бондаренко и Юрова [5], Альфаки и Мурти [6], Фиорини [7] известно, что для некоторых семейств комбинаторных многогранников задача распознавания несмежности вершин МР-полна. В связи с этим появляется естественный вопрос о наличии у рассмотренных в работах [3—7] многогранников некой общей конструктивной особенности, определяющей сходство свойств. Оказывается (и об этом подробно будет рассказано ниже), каждый из указанных многогранников

Ярославский государственный университет им. П.Г. Демидова

содержит в качестве грани многогранник задачи 0/1-программирования специального вида. Одно из свойств последнего — МР-полнота распознавания несмежности вершин.

Перейдем к перечислению многогранников, рассмотренных в работах [3—7], условно разбив их на две группы. Многогранники первой группы хорошо описываются в виде задач 0/1-програм-мирования. В этом случае предполагаем х = (хь х2, ..., хй) е {0, 1}й. Ко второй группе относятся многогранники, связанные с задачами на графах. Если речь в них идет о полном неориентированном графе О = (V, Е) на п вершинах, то значение

1г\ 1 л - 1)/2

координаты Ху, 1 < I <у < п, вектора х е {0, 1} символизирует наличие или отсутствие ребра (у, у) в подграфе О(х) графа О. В таких случаях х часто называют характеристическим вектором графа О(х). Аналогично для полного ориентированного графа Б = {V, А} на п вершинах множество векторов х е {0, 1}п(п -1) взаимно однозначно связано с множеством всех подграфов Б(х) графа Б.

Многогранник покрытий ^Ста) определяется как выпуклая оболочка всех решений х е {0, 1}й неравенства Ах > 1, где А — 0/1-матрица размера т х й, а 1 — т-мерный вектор, все координаты которого равны 1.

Многогранник двойных покрытий (Б8Стй) есть множество решений равенства Ах = 2, где А — 0/1-матрица размера т х й, 2 — т-мерный вектор, все координаты которого равны 2. Далее будем рассматривать только тот частный случай, когда каждая строка матрицы А содержит ровно четыре единицы.

Многогранник задачи о рюкзаке (ККтй). Задан целочисленный вектор а > 0 и целое число Ь > 0, причем ^2Ь < т. Множество вершин многогранника задается неравенством агх < Ь.

Многогранник суммы размеров ^8тй) отличается от многогранника задачи о рюкзаке лишь тем, что неравенство агх < Ь заменено равенством.

662

МАКСИМЕНКО

Двойное покрытие

^Покрытие) С Числовое разбиение) \ Г Кубический подграф)

/

^Рюкзак) Ç 3-выполнимость)

\

Ç Назначения с ограничением )

( Простой путь ^-

Ç Частичное упорядочение )

Асимметричный коммивояжер

^-Коммивояжер)

Рис. 1. Иерархия многогранников.

Многогранник задачи числового разбиения (РЯТта) является частным случаем многогранни-

> Т1

ка суммы размеров при Ь = аТ - .

Многогранник задачи 3-выполнимость (35АТтй). Задан набор троек {а,, Ь,, с}, I = 1, 2, ..., т, где {а¡, Ь¡, с} с {х1, х2, ..., х^, 1 — х1, ..., 1 — ха}. Вершины многогранника определяются векторами х = (х1, х2, ..., ха), координаты которых удовлетворяют неравенствам аI + ЬI + с 1 > 1, I = 1, 2, ..., т.

Вершинами многогранника коммивояжера

(БТБРп) служат вектора х е {0, 1}"^/2, ассоциированные графы О(х) которых являются гамиль-тоновыми циклами в полном графе на п вершинах.

Аналогично, вершинами многогранника асимметричной задачи коммивояжера (ЛТБРп) служат характеристические вектора всех гамильтоновых контуров орграфа на п вершинах.

Многогранник простых путей (SWn). В полном орграфе Б = (V,Л) с вершинами V = { уь у2, ..., уп,

^ рассмотрим множество простых путей, ведущих из вершины « в вершину Множество характеристических векторов всех таких путей образует вершины многогранника ^Жп.

Многогранник кубических подграфов (0Бп) есть множество характеристических векторов кубических подграфов полного графа на п вершинах (степень каждой вершины кубического графа равна трем).

Многогранник частичных порядков (РОп). Подграф Б' полного орграфа Б = (V, Л) на п вершинах будем называть частичным порядком, если он не содержит контуров и для любой пары его дуг (у, у-), (у, V/) выполняется свойство транзитивности:

(( У* V]) е П) & ((ур Ук) е П) ^ (у, ук) е П.

Соответственно, вершины многогранника РОп задаются характеристическими векторами всех частичных порядков графа Б.

Многогранник задачи о назначениях с ограничением (CASn). Дан полный двудольный граф G = (V, W, E), где V = {vb v2, ..., vn}, W = {w1, w2, ..., wn} — множества вершин долей; каждому его ребру (v, w) e E приписан некоторый вес Cj е e [, 1 < i, j < n; выбрано число-ограничение b. Вершинам многогранника CASn соответствуют такие совершенные паросочетания в графе G, суммарный вес ребер каждого из которых равен b.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ

Заметим, что каждая комбинаторная задача оказывается источником целого семейства многогранников. Выше для типичного представителя такого семейства использовалось обозначение вида Pn или Pmd, где n, m и d — некоторые ключевые параметры, характеризующие размер входных данных задачи, далее будем называть их размерами многогранника. Если же речь идет о семействе многогранников, будем использовать обозначение без индексов: P = {Pn} или P = {Pmd}.

Определение 1. Будем говорить, что семейство многогранников P аффинно сводится к семейству Q, если для каждого многогранника p e P найдется q e Q, такой что p аффинно эквивалентен либо самому многограннику q, либо некоторой его грани. При этом размеры (и в частности размерность) многогранника q ограничены сверху некоторым полиномом от размеров (размерности) многогранника p. Обозначение аффинной сводимости: P xA Q. Заметим, что аффинная сводимость обладает свойством транзитивности.

Теорема 1. Семейство многогранников двойных покрытий аффинно сводится к каждому из се-мействмногогранников из приведенного выше списка.

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

Эта теорема позволяет систематизировать наши знания относительно некоторых важных свойств описанных многогранников. Так, например, из работы Мацуи [4] известно, что задача распознавания несмежности вершин для многогранников двойных покрытий NP-полна. Из теоремы 1 следует, что это свойство наследуется всеми семействами приведенного выше списка.

Другой пример связан с поиском кликового числа графа многогранника. Известно, что эта характеристика является нижней оценкой сложности ассоциированной с многогранником задачи в классе алгоритмов прямого типа (см. [8]). Для упомянутых выше семейств многогранников теорема 1 позволяет относительно легко получить

ДОКЛАДЫ АКАДЕМИИ НАУК том 443 № 6 2012

ОБ АФФИННОЙ СВОДИМОСТИ

663

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

Пусть G = (V, E) — полный граф на n вершинах. Для каждого подмножества V' с V (в том числе и пустого) рассмотрим индуцированный им полный подграф G' графа G. Многогранником клик (CLn) назовем множество характеристических векторов всех таких подграфов. Хорошо известно (см., например, [8]), что граф этого многогранника полон. Соответственно, его кликовое число равно 2n.

Теорем а 2. Семейство многогранников клик аффинно сводится к семейству многогранников двойных покрытий:

CL <xA DSC.

С учетом теоремы 1 получаем следующее утверждение.

Теорем а 3. Кликовое число графа многогранника для каждого из перечисленных выше семейств

суперполиномиально относительно наименьшего из размеров многогранника.

СПИСОК ЛИТЕРАТУРЫ

1. Hausmann D. In: Mathematical Systems in Economics. Meisenheim am Glan, Hain, 1980. V . 49. 237 p.

2. Емеличев В.А., Ковалев М.М., Кравцов М.К. Многогранники, графы, оптимизация. М.: Наука, 1981. 344 с.

3. Papadimitriou C.H. // Math. Programming. 1978. V. 14. № 1. P. 312-324.

4. Matsui T. // Lecture Notes Operat. Res. 1995. V. 1. P. 249-258.

5. Bondarenko V.A., Yurov S.V. // Fundam. Informaticae. 1996. P. 28-35.

6. Alfakih A.Y., Murty K.G. // Discrete Appl. Math. 1998. V. 87. № 1. P. 269-274.

7. Fiorini S. // Europ. J. Combinatorics. 2003. V. 24. № 2. P. 149-159.

8. Бондаренко В.А., Максименко А.Н. Геометрические конструкции и сложность в комбинаторной оптимизации. M.: ЛКИ, 2008. 184 с.

ДОКЛАДЫ АКАДЕМИИ НАУК том 443 № 6 2012

Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.

Показать целиком