Сложность реоптимизации задачи вычисления хроматического числа графа с заданным множеством оптимальных решений
Используются сведения, вводящие и сохраняющие разрыв. Показано, что для множественной реоптимизации задачи о вычислении хроматического числа графа с заданным экспоненциальным множеством оптимальных решений при вставке произвольной вершины с не более чем двумя ребрами, ей инцидентными, а также при уд...
Збережено в:
| Опубліковано в: : | Кибернетика и системный анализ |
|---|---|
| Дата: | 2016 |
| Автор: | |
| Формат: | Стаття |
| Мова: | Russian |
| Опубліковано: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2016
|
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/133680 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Сложность реоптимизации задачи вычисления хроматического числа графа с заданным множеством оптимальных решений / В.А. Михайлюк // Кибернетика и системный анализ. — 2016. — Т. 52, № 3. — С. 39-48. — Бібліогр.: 14 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-133680 |
|---|---|
| record_format |
dspace |
| spelling |
Михайлюк, В.А. 2018-06-05T05:40:55Z 2018-06-05T05:40:55Z 2016 Сложность реоптимизации задачи вычисления хроматического числа графа с заданным множеством оптимальных решений / В.А. Михайлюк // Кибернетика и системный анализ. — 2016. — Т. 52, № 3. — С. 39-48. — Бібліогр.: 14 назв. — рос. 0023-1274 https://nasplib.isofts.kiev.ua/handle/123456789/133680 519.854 Используются сведения, вводящие и сохраняющие разрыв. Показано, что для множественной реоптимизации задачи о вычислении хроматического числа графа с заданным экспоненциальным множеством оптимальных решений при вставке произвольной вершины с не более чем двумя ребрами, ей инцидентными, а также при удалении произвольной вершины со всеми инцидентными ей ребрами не существует полиномиально приближенной схемы (PTAS). Такой же результат имеет место для обычной реоптимизации. Використано зведення, що вводять і зберігають розрив. Показано, що для множинної реоптимізаціі задачі про обчислення хроматичного числа графа із заданою експоненціальною множиною оптимальних розв’язків при уставленні довільної вершини з не більш ніж двома ребрами, їй інцидентними, а також при видаленні довільної вершини з усіма інцидентними їй ребрами не існує поліноміально наближеної схеми (PTAS). Такий же результат має місце для звичайної реоптимізаціі. The author uses gap-introducing and gap-preserving reductions and shows that for multiple reoptimization of the problem of calculating the chromatic number of a graph with a given exponential set of optimal solutions, when an arbitrary vertex with no more than two edges incident to it is inserted as well as when any vertex with all incident edges is deleted, polynomial time approximation scheme (PTAS) does not exist. The same result holds for ordinary reoptimization. ru Інститут кібернетики ім. В.М. Глушкова НАН України Кибернетика и системный анализ Кибернетика Сложность реоптимизации задачи вычисления хроматического числа графа с заданным множеством оптимальных решений Складність реоптимізації задачі обчислення хроматичного числа графа із заданою множиною оптимальних розв’язків Hardness of reoptimization of the problem of calculating the chromatic number of a graph with a given set of optimal solutions Article published earlier |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| title |
Сложность реоптимизации задачи вычисления хроматического числа графа с заданным множеством оптимальных решений |
| spellingShingle |
Сложность реоптимизации задачи вычисления хроматического числа графа с заданным множеством оптимальных решений Михайлюк, В.А. Кибернетика |
| title_short |
Сложность реоптимизации задачи вычисления хроматического числа графа с заданным множеством оптимальных решений |
| title_full |
Сложность реоптимизации задачи вычисления хроматического числа графа с заданным множеством оптимальных решений |
| title_fullStr |
Сложность реоптимизации задачи вычисления хроматического числа графа с заданным множеством оптимальных решений |
| title_full_unstemmed |
Сложность реоптимизации задачи вычисления хроматического числа графа с заданным множеством оптимальных решений |
| title_sort |
сложность реоптимизации задачи вычисления хроматического числа графа с заданным множеством оптимальных решений |
| author |
Михайлюк, В.А. |
| author_facet |
Михайлюк, В.А. |
| topic |
Кибернетика |
| topic_facet |
Кибернетика |
| publishDate |
2016 |
| language |
Russian |
| container_title |
Кибернетика и системный анализ |
| publisher |
Інститут кібернетики ім. В.М. Глушкова НАН України |
| format |
Article |
| title_alt |
Складність реоптимізації задачі обчислення хроматичного числа графа із заданою множиною оптимальних розв’язків Hardness of reoptimization of the problem of calculating the chromatic number of a graph with a given set of optimal solutions |
| description |
Используются сведения, вводящие и сохраняющие разрыв. Показано, что для множественной реоптимизации задачи о вычислении хроматического числа графа с заданным экспоненциальным множеством оптимальных решений при вставке произвольной вершины с не более чем двумя ребрами, ей инцидентными, а также при удалении произвольной вершины со всеми инцидентными ей ребрами не существует полиномиально приближенной схемы (PTAS). Такой же результат имеет место для обычной реоптимизации.
Використано зведення, що вводять і зберігають розрив. Показано, що для множинної реоптимізаціі задачі про обчислення хроматичного числа графа із заданою експоненціальною множиною оптимальних розв’язків при уставленні довільної вершини з не більш ніж двома ребрами, їй інцидентними, а також при видаленні довільної вершини з усіма інцидентними їй ребрами не існує поліноміально наближеної схеми (PTAS). Такий же результат має місце для звичайної реоптимізаціі.
The author uses gap-introducing and gap-preserving reductions and shows that for multiple reoptimization of the problem of calculating the chromatic number of a graph with a given exponential set of optimal solutions, when an arbitrary vertex with no more than two edges incident to it is inserted as well as when any vertex with all incident edges is deleted, polynomial time approximation scheme (PTAS) does not exist. The same result holds for ordinary reoptimization.
|
| issn |
0023-1274 |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/133680 |
| citation_txt |
Сложность реоптимизации задачи вычисления хроматического числа графа с заданным множеством оптимальных решений / В.А. Михайлюк // Кибернетика и системный анализ. — 2016. — Т. 52, № 3. — С. 39-48. — Бібліогр.: 14 назв. — рос. |
| work_keys_str_mv |
AT mihailûkva složnostʹreoptimizaciizadačivyčisleniâhromatičeskogočislagrafaszadannymmnožestvomoptimalʹnyhrešenii AT mihailûkva skladnístʹreoptimízacíízadačíobčislennâhromatičnogočislagrafaízzadanoûmnožinoûoptimalʹnihrozvâzkív AT mihailûkva hardnessofreoptimizationoftheproblemofcalculatingthechromaticnumberofagraphwithagivensetofoptimalsolutions |
| first_indexed |
2025-11-26T02:06:00Z |
| last_indexed |
2025-11-26T02:06:00Z |
| _version_ |
1850607961731235840 |
| fulltext |
ÓÄÊ 519.854
Â.À. ÌÈÕÀÉËÞÊ
ÑËÎÆÍÎÑÒÜ ÐÅÎÏÒÈÌÈÇÀÖÈÈ ÇÀÄÀ×È ÂÛ×ÈÑËÅÍÈß
ÕÐÎÌÀÒÈ×ÅÑÊÎÃÎ ×ÈÑËÀ ÃÐÀÔÀ Ñ ÇÀÄÀÍÍÛÌ
ÌÍÎÆÅÑÒÂÎÌ ÎÏÒÈÌÀËÜÍÛÕ ÐÅØÅÍÈÉ
Àííîòàöèÿ. Èñïîëüçóþòñÿ ñâåäåíèÿ, ââîäÿùèå è ñîõðàíÿþùèå ðàçðûâ. Ïîêà-
çàíî, ÷òî äëÿ ìíîæåñòâåííîé ðåîïòèìèçàöèè çàäà÷è î âû÷èñëåíèè õðîìàòè-
÷åñêîãî ÷èñëà ãðàôà ñ çàäàííûì ýêñïîíåíöèàëüíûì ìíîæåñòâîì îïòèìàëü-
íûõ ðåøåíèé ïðè âñòàâêå ïðîèçâîëüíîé âåðøèíû ñ íå áîëåå ÷åì äâóìÿ ðåá-
ðàìè, åé èíöèäåíòíûìè, à òàêæå ïðè óäàëåíèè ïðîèçâîëüíîé âåðøèíû ñî
âñåìè èíöèäåíòíûìè åé ðåáðàìè íå ñóùåñòâóåò ïîëèíîìèàëüíî ïðèáëèæåí-
íîé ñõåìû (PTAS). Òàêîé æå ðåçóëüòàò èìååò ìåñòî äëÿ îáû÷íîé ðåîïòèìè-
çàöèè.
Êëþ÷åâûå ñëîâà: ìíîæåñòâåííàÿ ðåîïòèìèçàöèÿ, ñâåäåíèÿ çàäà÷, ââîäÿùèõ
è ñîõðàíÿþùèõ ðàçðûâ, APX-òðóäíîñòü, ïîëèíîìèàëüíî ïðèáëèæåííûå ñõå-
ìû (PTAS).
ÏÎÑÒÀÍÎÂÊÀ ÇÀÄÀ×È
Êàê èçâåñòíî, íàõîæäåíèå îïòèìàëüíûõ ðåøåíèé NP-òðóäíûõ çàäà÷ êîìáèíàòîð-
íîé îïòèìèçàöèè ÿâëÿåòñÿ âû÷èñëèòåëüíî ñëîæíîé çàäà÷åé, è ïðåäëàãàþòñÿ ðàç-
ëè÷íûå ïîäõîäû (ýâðèñòèêè è äðóãèå ïðèáëèæåííûå àëãîðèòìû) äëÿ âû÷èñëåíèÿ
«õîðîøèõ» (íå îáÿçàòåëüíî îïòèìàëüíûõ) ðåøåíèé. Îäíàêî äàæå íàõîæäåíèå
ïðèáëèæåííûõ ðåøåíèé ìîæåò îêàçàòüñÿ òðóäíîðåøàåìîé (NP-òðóäíîé) çàäà÷åé.
Îäèí èç ïîäõîäîâ, èçâåñòíûõ äëÿ ðåøåíèÿ NP-òðóäíûõ çàäà÷, çàêëþ÷àåòñÿ
â ðàññìîòðåíèè ýêçåìïëÿðîâ çàäà÷ (çàäà÷ ñ çàäàííûìè çíà÷åíèÿìè âõîäíûõ ïà-
ðàìåòðîâ) íå òîëüêî êàê èçîëèðîâàííûõ çàäà÷, íî è â èñïîëüçîâàíèè äîáàâî÷íûõ
çíàíèé î ïîäîáíûõ ýêçåìïëÿðàõ (ïîëó÷åííûõ ïðè ïîïûòêàõ ðåøåíèé ïîäîáíûõ
ýêçåìïëÿðîâ).  äàííîì ñëó÷àå âîçíèêàåò òàêàÿ èäåÿ: èñõîäÿ èç îïòèìàëüíîãî
(èëè áëèçêîãî ê íåìó) ðåøåíèÿ ýêçåìïëÿðà çàäà÷è èñïîëüçîâàòü ýòó èíôîðìàöèþ
äëÿ íàõîæäåíèÿ ðåøåíèé (ýêçåìïëÿðîâ çàäà÷), ïîëó÷åííûõ â ðåçóëüòàòå íåçíà÷è-
òåëüíûõ ëîêàëüíûõ ìîäèôèêàöèé èñõîäíîãî ýêçåìïëÿðà.
Êîíöåïöèÿ ðåîïòèìèçàöèè ôîðìàëüíî îïèñûâàåò ýòîò ïîäõîä.
Ðàññìîòðèì íåêîòîðóþ çàäà÷ó äèñêðåòíîé îïòèìèçàöèè Q ñ çàäàííûìè çíà-
÷åíèÿìè âõîäíûõ ïàðàìåòðîâ (ïóñòü çàäàí ýêçåìïëÿð I çàäà÷è Q ). Åñëè çíà÷åíèå
âõîäíûõ ïàðàìåòðîâ îïðåäåëåííûì îáðàçîì èçìåíåíî, ïîëó÷àåì ýêçåìïëÿð �I çà-
äà÷è Q . Âîçíèêàåò âîïðîñ: êàêèì îáðàçîì, çíàÿ îïòèìàëüíîå ðåøåíèå x� ýêçåì-
ïëÿðà I çàäà÷è Q , íàéòè îïòèìàëüíîå ðåøåíèå ýêçåìïëÿðà �I ? Ïîíÿòèå ðåîïòèìè-
çàöèè çàêëþ÷àåòñÿ â ñëåäóþùåì: êàê ýôôåêòèâíî èñïîëüçîâàòü çíàíèÿ îá îïòè-
ìàëüíîì ðåøåíèè x� ýêçåìïëÿðà I äëÿ íàõîæäåíèÿ òî÷íîãî èëè ïðèáëèæåííîãî
ðåøåíèÿ ýêçåìïëÿðà �I ? Öåëü ðåîïòèìèçàöèè ïðè èñïîëüçîâàíèè ïðèáëèæåííûõ
ìåòîäîâ — ïðèìåíåíèå çíàíèé î ðåøåíèè íà÷àëüíîãî ýêçåìïëÿðà I äëÿ âûïîëíå-
íèè îäíîãî èç óñëîâèé: ïîâûøåíèÿ êà÷åñòâà ïðèáëèæåíèÿ (àïïðîêñèìàöèîííîãî
îòíîøåíèÿ) �I , ñîçäàíèÿ áîëåå ýôôåêòèâíîãî (ïî áûñòðîäåéñòâèþ) àëãîðèòìà
îïðåäåëåíèÿ îïòèìàëüíîãî ëèáî áëèçêîãî ê íåìó ðåøåíèÿ �I èëè âûïîëíåíèÿ
ïðåäûäóùèõ äâóõ óñëîâèé. Åñëè â ðåçóëüòàòå ðåîïòèìèçàöèè óäàåòñÿ óëó÷øèòü
êà÷åñòâî ïðèáëèæåíèÿ (àïïðîêñèìàöèîííîãî îòíîøåíèÿ), òî áóäåò ëè îíî óëó÷-
øàåìûì (ïîðîãîâûì) â êëàññå ïàðàìåòðè÷åñêèõ ïðèáëèæåííûõ àëãîðèòìîâ íå-
êîòîðîãî êëàññà (íàïðèìåð, ïîëèíîìèàëüíûõ)?
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2016, òîì 52, ¹ 3 39
© Â.À. Ìèõàéëþê, 2016
 ýòîì êîíòåêñòå êà÷åñòâî ïðèáëèæåíèÿ èçìåðÿåòñÿ êàê îòíîøåíèå çíà÷åíèÿ
âû÷èñëÿåìîãî ðåøåíèÿ ê çíà÷åíèþ îïòèìàëüíîãî. Èíûìè ñëîâàìè, äëÿ ìèíèìèçà-
öèîííûõ çàäà÷ U è àëãîðèòìà A äëÿ U àïïðîêñèìàöèîííîå îòíîøåíèå � A n( )
äëÿ ââåäåííûõ äàííûõ ðàçìåðà n îïðåäåëÿåòñÿ êàê max {
I
A I Opt I I( ) / ( ) : — ýêçåìï-
ëÿð U ðàçìåðà n}. Åñëè � A n( ) ìîæíî îöåíèòü ñâåðõó êàê êîíñòàíòó, òî ñ÷èòàþò,
÷òî A — êîíñòàíòíûé ïðèáëèæåííûé àëãîðèòì äëÿ U . Êëàññ APX ñîäåðæèò âñå
çàäà÷è, äëÿ êîòîðûõ ñóùåñòâóåò êîíñòàíòíûé ïðèáëèæåííûé àëãîðèòì. Ïîëèíî-
ìèàëüíî ïðèáëèæåííîé ñõåìîé (Polinomial Time Approximation Scheme — PTAS)
ÿâëÿåòñÿ àëãîðèòì, êîòîðûé äëÿ çàäàííîãî � � 0 âû÷èñëÿåò ( )1� � -ïðèáëèæåííîå
ðåøåíèå çà ïîëèíîìèàëüíîå âðåìÿ îòíîñèòåëüíî n (íî, âîçìîæíî, ýêñïîíåíöèàëü-
íîå ïî1/ �). Çàäà÷è, êîòîðûå APX -òðóäíû, ÿâëÿþòñÿ íàèáîëåå ñëîæíûìè çàäà÷àìè
â êëàññå APX . Äëÿ òàêèõ çàäà÷ íå ñóùåñòâóåò PTAS, åñëè P NP� .
Âïåðâûå ïîíÿòèå ðåîïòèìèçàöèè ïîÿâèëîñü â ñåðåäèíå 1980-õ ãîäîâ ïðè ðå-
øåíèè òàêèõ ïîëèíîìèàëüíûõ çàäà÷ îïòèìèçàöèè, êàê ìèíèìàëüíîå îñòîâíîå
äåðåâî [1] è êðàò÷àéøèé ïóòü â ãðàôå [2]. Ñóòü ñîñòîÿëà â ïîääåðæêå è èñïîëüçî-
âàíèè îïòèìàëüíîãî ðåøåíèÿ çàäà÷è ïðè ìîäèôèêàöèè âõîäíûõ äàííûõ (âñòàâêà
èëè óäàëåíèå ðåáðà, èçìåíåíèå âåñà ðåáðà) äëÿ äîñòèæåíèÿ ðåçóëüòàòà (îïòè-
ìàëüíîãî ðåøåíèÿ) ñ ìåíüøèìè âû÷èñëèòåëüíûìè çàòðàòàìè. Çàòåì èññëåäîâà-
ëèñü ìíîãèå êëàññè÷åñêèå NP-ïîëíûå (NP-òðóäíûå) çàäà÷è äèñêðåòíîé îïòèìè-
çàöèè (çàäà÷à êîììèâîÿæåðà, çàäà÷à î ìèíèìàëüíîì äåðåâå Øòåéíåðà, çàäà÷à
î ïîêðûòèè, çàäà÷à î ðàíöå è ò.ä.). (Îáçîð èçâåñòíûõ ðåçóëüòàòîâ ïî ðåîïòèìèçà-
öèè ìîæíî íàéòè â [3–5].)
 ðàáîòàõ [6, 7] ïðåäëàãàåòñÿ îáîáùåíèå ðåîïòèìèçàöèîííîãî ïîäõîäà. Ñ÷è-
òàåòñÿ, ÷òî çàäàíî íå åäèíñòâåííîå îïòèìàëüíîå ðåøåíèå èñõîäíîé çàäà÷è, à äàæå
íåêîòîðîå èõ ìíîæåñòâî (èëè ìíîæåñòâî ðåøåíèé, áëèçêèõ ê îïòèìàëüíûì). Âîç-
íèêàåò âîïðîñ: ìîæåò ëè ýòî ñïîñîáñòâîâàòü óëó÷øåíèþ êà÷åñòâà ðåîïòèìèçàöèè?
 ðàáîòàõ [6, 7] äàåòñÿ îòðèöàòåëüíûé îòâåò îòíîñèòåëüíî çàäà÷è î ìèíèìàëüíîì
äåðåâå Øòåéíåðà è çàäà÷è î êîììèâîÿæåðå.
Äàííàÿ ñòàòüÿ ïîñâÿùåíà èññëåäîâàíèþ ýòîãî âîïðîñà äëÿ çàäà÷è î ìèíè-
ìàëüíîé ðàñêðàñêå ãðàôà.
ÏÐÅÄÂÀÐÈÒÅËÜÍÛÅ ÎÏÐÅÄÅËÅÍÈß È ÎÁÎÇÍÀ×ÅÍÈß
Ïðèâåäåì íåêîòîðûå ïîíÿòèÿ, íåîáõîäèìûå äëÿ äàëüíåéøåãî èçëîæåíèÿ [3, 8].
Îïðåäåëåíèå 1. NP-îïòèìèçàöèîííàÿ (êëàññ NPO) çàäà÷à � îïðåäåëÿåòñÿ
êàê ÷åòâåðêà ( , , , )E Sol m opt òàêàÿ, ÷òî:
1) E — ìíîæåñòâî ýêçåìïëÿðîâ çàäà÷è �, ðàñïîçíàâàåìîå çà ïîëèíîìèàëüíîå
âðåìÿ;
2) äëÿ äàííîãî I E� èìååì Sol I( ) — ìíîæåñòâî äîïóñòèìûõ ðåøåíèé I ;
äëÿ êàæäîãî S Sol I� ( ) | |S (ðàçìåð S ) ïîëèíîìèàëåí ïî | |I (ðàçìåð I ); äëÿ ëþáî-
ãî äàííîãî I è ëþáîãî S (ïîëèíîìèàëüíîãî ïî | |I ) çà ïîëèíîìèàëüíîå âðåìÿ
ìîæíî îïðåäåëèòü S Sol I� ( );
3) äëÿ äàííûõ I E� è S Sol I� ( ) èìååì m I S( , ) — çíà÷åíèå (÷èñëîâîå) S ;
m — ïîëèíîìèàëüíî âû÷èñëèìàÿ öåëåâàÿ ôóíêöèÿ;
4) opt �{ }min, max — òèï îïòèìèçàöèîííîé çàäà÷è.
Äëÿ äàííîé NPO-çàäà÷è � { }E Sol m opt, , , îïòèìàëüíîå ðåøåíèå ýêçåìïëÿ-
ðà I çàäà÷è � áóäåì îáîçíà÷àòü S I� ( ), à åãî âåëè÷èíó m I S I( , ( ))� — îïòèìàëü-
íûì ðåøåíèåì opt I( ).
Îïðåäåëåíèå 2. Äëÿ äàííîé NPO-çàäà÷è � ( , , , )E Sol m opt ïðèáëèæåííûé
(àïïðîêñèìàöèîííûé) àëãîðèòì A äëÿ äàííîãî ýêçåìïëÿðà I çàäà÷è � âûäàåò äî-
ïóñòèìîå ðåøåíèå S Sol I� ( ).
40 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2016, òîì 52, ¹ 3
Åñëè A âûïîëíÿåòñÿ çà ïîëèíîìèàëüíîå âðåìÿ îòíîñèòåëüíî | |I , òî ýòîò
àëãîðèòì íàçûâàåòñÿ ïîëèíîìèàëüíûì ïðèáëèæåííûì àëãîðèòìîì äëÿ �.
Êà÷åñòâî ïðèáëèæåííîãî àëãîðèòìà îáû÷íî îöåíèâàåòñÿ êàê îòíîøåíèå
� A I( ) (àïïðîêñèìàöèîííîå îòíîøåíèå) ìåæäó çíà÷åíèåì ïðèáëèæåííîãî ðåøåíèÿ
m I A I( , ( )) è çíà÷åíèåì îïòèìàëüíîãî ðåøåíèÿ opt I( ). Òàêèì îáðàçîì, äëÿ ìèíè-
ìèçàöèîííûõ çàäà÷ àïïðîêñèìàöèîííîå îòíîøåíèå íàõîäèòñÿ â ïðåäåëå [ , )1
, äëÿ
ìàêñèìèçàöèîííûõ — â ïðåäåëå [ , ]0 1 .
Îòíîñèòåëüíî êà÷åñòâà ïðèáëèæåííûõ àëãîðèòìîâ NPO-çàäà÷è êëàññèôèöè-
ðóþò ñëåäóþùèì îáðàçîì.
Îïðåäåëåíèå 3. NPO-çàäà÷à � ïðèíàäëåæèò êëàññó APX, åñëè ñóùåñòâóþò
ïîëèíîìèàëüíî ïðèáëèæåííûé àëãîðèòì A è ðàöèîíàëüíîå ÷èñëî r òàêèå, ÷òî
äëÿ äàííîãî I �� èìååì � A I r( ) � (ñîîòâåòñòâåííî � A I r( ) � ), ïðè ýòîì � —
ìèíèìèçàöèîííàÿ (ñîîòâåòñòâåííî ìàêñèìèçàöèîííàÿ) çàäà÷à.  ýòîì ñëó÷àå A
íàçûâàåòñÿ r-ïðèáëèæåííûì (àïïðîêñèìàöèîííûì) àëãîðèòìîì (à çàäà÷à � —
r-àïïðîêñèìèðóåìà àëãîðèòìîì A).
Äëÿ îòäåëüíûõ çàäà÷ èç êëàññà APX ìîæíî ââåñòè áîëåå ñèëüíóþ ôîðìó àï-
ïðîêñèìàöèîííîñòè. Äëÿ òàêèõ çàäà÷ è ëþáîãî ðàöèîíàëüíîãî r �1 (èëè r �( , )0 1
äëÿ ìàêñèìèçàöèîííûõ çàäà÷) ñóùåñòâóþò àëãîðèòì Ar è ïîäõîäÿùèé ïîëèíîì
p òàêîé, ÷òî Ar — r-àïïðîêñèìàöèîííûé (ïðèáëèæåííûé) àëãîðèòì ñî âðåìå-
íåì, èçìåðÿåìûì êàê p îò | |I . Ñåìåéñòâî àëãîðèòìîâ Ar (ïàðàìåòðèçîâàííîå ñ
ïîìîùüþ r) íàçûâàåòñÿ ïîëèíîìèàëüíî ïðèáëèæåííîé ñõåìîé (PTAS).
Îïðåäåëåíèå 4. NPO-çàäà÷à � ïðèíàäëåæèò êëàññó PTAS, åñëè äëÿ ëþáîãî
ðàöèîíàëüíîãî � � 0 è ëþáîãî ýêçåìïëÿðà I çàäà÷è � ñóùåñòâóåò ïîëèíîìèàëüíî
ïðèáëèæåííàÿ ñõåìà A� òàêàÿ, ÷òî � �
�A I( ) � �1 (ñîîòâåòñòâåííî � �
�A I( ) �
1 )
äëÿ �-ìèíèìèçàöèîííîé (ñîîòâåòñòâåííî ìàêñèìèçàöèîííîé) çàäà÷è.
Åñëè P NP� , òî èìååò ìåñòî âêëþ÷åíèå PTAS NPO� �APX .
Äëÿ ýêçåìïëÿðà I �� îáîçíà÷èì c I( ) çíà÷åíèå öåëåâîé ôóíêöèè, êîòîðîå
íàõîäèò àëãîðèòì (èëè îæèäàåìîå çíà÷åíèå, åñëè àëãîðèòì ñëó÷àéíûé), OPT I( )
— çíà÷åíèå îïòèìàëüíîãî ðåøåíèÿ.
Îïðåäåëåíèå 5 (îòíîøåíèå àïïðîêñèìàöèè). Ïîëàãàþò, ÷òî àëãîðèòì A äîñòè-
ãàåò îòíîøåíèÿ àïïðîêñèìàöèè C-ïðèáëèæåííîãî àëãîðèòìà, åñëè äëÿ êàæäîãî ýê-
çåìïëÿðà I �� èìååì c I C OPT I( ) ( )� � , ãäå � — ìèíèìèçàöèîííàÿ çàäà÷à.
Ïîä ýôôåêòèâíûì àëãîðèòìîì äëÿ çàäà÷è � ïîíèìàþò àëãîðèòì ñî âðåìå-
íåì ðàáîòû íå áîëåå ÷åì ïîëèíîì îò ðàçìåðíîñòè âõîäà. Äëÿ çàäà÷è � óñòàíîâ-
ëåíà âåðõíÿÿ îöåíêà îòíîøåíèÿ àïïðîêñèìàöèè C , åñëè ñóùåñòâóåò ïîëèíîìè-
àëüíûé C-ïðèáëèæåííûé àëãîðèòì äëÿ ðåøåíèÿ �. Äëÿ çàäà÷è � óñòàíîâëåíà
íèæíÿÿ îöåíêà îòíîøåíèÿ àïïðîêñèìàöèè d , åñëè äëÿ ïðîèçâîëüíîãî � � 0 íå ñó-
ùåñòâóåò ïîëèíîìèàëüíîãî ïðèáëèæåííîãî àëãîðèòìà äëÿ �, íà êîòîðîì äîñòè-
ãàåòñÿ îòíîøåíèå àïïðîêñèìàöèè d
�. Åñëè çàäà÷à � ÿâëÿåòñÿ NP-òðóäíîé èëè
NP-ïîëíîé, òî, åñòåñòâåííî, äîáàâëÿåòñÿ óñëîâèå P NP� . Åñëè C d , òî äëÿ çà-
äà÷è � óñòàíîâëåí ïîðîã îòíîøåíèÿ àïïðîêñèìàöèè. Ñîîòâåòñòâóþùèé àëãî-
ðèòì íàçûâàåòñÿ îïòèìàëüíûì èëè ïîðîãîâûì (è îòíîøåíèå àïïðîêñèìàöèè —
îïòèìàëüíîå èëè ïîðîãîâîå).
×òîáû îõàðàêòåðèçîâàòü íèæíèå îöåíêè îòíîøåíèÿ àïïðîêñèìàöèè ïðèáëè-
æåííûõ àëãîðèòìîâ, ââîäèòñÿ ïîíÿòèå ñëîæíîñòè îòíîøåíèÿ àïïðîêñèìàöèè.
Îïðåäåëåíèå 6 (ñëîæíîñòü, òðóäíîñòü àïïðîêñèìàöèè). Íàçîâåì çàäà÷ó
�-ñëîæíîé (�-òðóäíîé) äëÿ àïïðîêñèìàöèè (ïðèáëèæåíèÿ), åñëè íå ñóùåñòâóåò
ïðèáëèæåííîãî ïîëèíîìèàëüíîãî àëãîðèòìà ñ îòíîøåíèåì àïïðîêñèìàöèè
ìåíüøå � ïðè P NP� .
Òàêèì îáðàçîì, åñëè çàäà÷à � ÿâëÿåòñÿ NP-òðóäíîé èëè NP-ïîëíîé, òî óñòà-
íîâëåíèå äëÿ íåå íèæíåé îöåíêè îòíîøåíèÿ àïïðîêñèìàöèè c îçíà÷àåò, ÷òî ýòà
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2016, òîì 52, ¹ 3 41
çàäà÷à åñòü c-ñëîæíîé (c-òðóäíîé) äëÿ ïðèáëèæåíèÿ (àïïðîêñèìàöèè). Ïîýòîìó
óñòàíîâëåíèå íèæíèõ îöåíîê îòíîøåíèÿ àïïðîêñèìàöèè íàçûâàþò òàêæå ñëîæ-
íîñòüþ (òðóäíîñòüþ) àïïðîêñèìàöèè (hardness of approximation) èëè íåàïïðîêñè-
ìèðîâàííîñòüþ (innapproximability).
ÑÂÅÄÅÍÈß ÇÀÄÀ×, ÂÂÎÄßÙÈÕ È ÑÎÕÐÀÍßÞÙÈÕ ÐÀÇÐÛÂ.
ÂËÈßÍÈÅ ÍÀ ÑËÎÆÍÎÑÒÜ ÀÏÏÐÎÊÑÈÌÀÖÈÈ
Ââåäåì ïîíÿòèÿ ñâåäåíèé çàäà÷, ââîäÿùèõ è ñîõðàíÿþùèõ ðàçðûâ [9]. Äëÿ
îïðåäåëåííîñòè áóäåì ðàññìàòðèâàòü çàäà÷è ìèíèìèçàöèè.
Îïðåäåëåíèå 7. Ïðåäïîëîæèì, ÷òî L ÿâëÿåòñÿ NP-òðóäíîé çàäà÷åé ðàñïîçíàâà-
íèÿ ñâîéñòâ, à � — ìèíèìèçàöèîííàÿ çàäà÷à. Ïóñòü g — ôóíêöèÿ, âû÷èñëèìàÿ çà
ïîëèíîìèàëüíîå âðåìÿ, êîòîðàÿ îòîáðàæàåò äà-ýêçåìïëÿðû L â ìíîæåñòâî S1 ýêçåì-
ïëÿðîâ çàäà÷è � è íåò-ýêçåìïëÿðû L â ìíîæåñòâî S 2 ýêçåìïëÿðîâ çàäà÷è �. Ïðåä-
ïîëîæèì, ÷òî ñóùåñòâóåò ïîëèíîìèàëüíî âû÷èñëèìàÿ ôóíêöèÿ h òàêàÿ, ÷òî
� äëÿ ïðîèçâîëüíîãî äà-ýêçåìïëÿðà L : OPT g x h g x( ( )) ( ( ))� ;
� äëÿ ïðîèçâîëüíîãî íåò-ýêçåìïëÿðà L : OPT g x x h g x( ( )) (| | ) ( ( ))� �� ,
ãäå OPT y( ) — çíà÷åíèå îïòèìàëüíîãî ðåøåíèÿ y çàäà÷è �, à | |x — äëèíà
(ðàçìåð) x. Òîãäà g íàçîâåì ñâåäåíèåì, ââîäÿùèì ðàçðûâ îò L ê �, à � —
ðàçìåðîì ðàçðûâà.
Ëåììà 1. Åñëè P NP� è äëÿ çàäà÷è � ñóùåñòâóåò ñâåäåíèå g, ââîäÿùåå ðàç-
ðûâ îò L ê � (� — ðàçìåð ðàçðûâà), òî äëÿ � íå ñóùåñòâóåò ïîëèíîìèàëüíîãî àë-
ãîðèòìà ñ îòíîøåíèåì àïïðîêñèìàöèè, íå áîëüøèì �.
Äîêàçàòåëüñòâî. Ïðåäïîëîæèì, ÷òî äëÿ çàäà÷è � ñóùåñòâóåò ïîëèíîìèàëüíûé
�-ïðèáëèæåííûé àëãîðèòì Alg ñ îòíîøåíèåì àïïðîêñèìàöèè � �� , Alg y( ) — çíà-
÷åíèå àëãîðèòìà Alg íà ýêçåìïëÿðå y ��. Ïðåäïîëîæèì, ÷òî x åñòü äà-ýêçåìïëÿð L,
òîãäà Alg y Alg g x OPT y OPT y h y( ) ( ( )) ( ) ( ) ( ) � � � � � �� � � . Äëÿ íåò-ýêçåìïëÿ-
ðà L ïîëó÷èì Alg y Alg g x OPT g x h g x h y( ) ( ( )) ( ( )) ( ( )) ( ) � � � �� � . Òàêèì îáðà-
çîì, ñóùåñòâóåò âîçìîæíîñòü çà ïîëèíîìèàëüíîå âðåìÿ (ñ ïîìîùüþ àëãîðèò-
ìà Alg) îòëè÷èòü äà-ýêçåìïëÿðû îò íåò-ýêçåìïëÿðîâ NP-òðóäíîé çàäà÷è L; ñëå-
äîâàòåëüíî, P NP . Ëåììà äîêàçàíà.
Ðàññìîòðèì çàäà÷ó ðàñêðàñêè ãðàôà (CG).
Óñëîâèå. Äàíû ãðàô G V E ( , ) è öåëîå ïîëîæèòåëüíîå ÷èñëî K K V( | | )� .
Âîçíèêàåò âîïðîñ: äåéñòâèòåëüíî ëè ãðàô G ìîæíî ðàñêðàñèòü K öâåòàìè?
(Ãðàô íàçûâàåòñÿ ðàñêðàøèâàåìûì K öâåòàìè, åñëè ñóùåñòâóåò íåêîòîðàÿ ôóíê-
öèÿ f V K: , , ,� { }1 2 � , êîãäà ïðè ( , )u E� � èìååì f u f( ) ( )� � .)
Èçâåñòíî, ÷òî çàäà÷à CG ÿâëÿåòñÿ NP-ïîëíîé (à çíà÷èò, è NP-òðóäíîé) äëÿ
K � 3 öåëîãî [14]. Ñ çàäà÷åé CG ñîïîñòàâèì NPO-çàäà÷ó î ìèíèìàëüíîé ðàñêðàñ-
êå ãðàôà ( _ )Min CG : íàõîæäåíèå ìèíèìàëüíîãî K, êîãäà ãðàô G V E ( , ) åñòü
K-ðàñêðàøèâàåìûì. Çàäà÷ó Min CG_ çàïèøåì â âèäå G V E w ( , , ), ãäå w — öå-
ëåâàÿ ôóíêöèÿ (÷èñëî öâåòîâ), w � min.
Õðîìàòè÷åñêîå ÷èñëî ãðàôà G V E ( , ), îáîçíà÷àåìîå �( )G , åñòü ðåøåíèå
îïòèìèçàöèîííîé çàäà÷è Min CG_ . Èñïîëüçóÿ ëåììó 1, à òàêæå òî, ÷òî çàäà÷à CG
äëÿ K 3 ÿâëÿåòñÿ NP-ïîëíîé (ñëåäîâàòåëüíî, NP-òðóäíîé), ïîëó÷àåì ñëåäóþ-
ùèé ðåçóëüòàò ïî ñëîæíîñòè (òðóäíîñòè) àïïðîêñèìàöèè îïòèìèçàöèîííîé çàäà-
÷è âû÷èñëåíèÿ õðîìàòè÷åñêîãî ÷èñëà çàäàííîãî ãðàôà G .
Ëåììà 2. Åñëè P NP� , òî äëÿ ëþáîãî � � 0 íå ñóùåñòâóåò ( / )4 3
� -ïðèáëè-
æåííîãî ïîëèíîìèàëüíîãî àëãîðèòìà äëÿ âû÷èñëåíèÿ õðîìàòè÷åñêîãî ÷èñëà ãðàôà.
Äîêàçàòåëüñòâî. Ïîñòðîèì ñâåäåíèå, ââîäÿùåå ðàçðûâ îò çàäà÷è CG ïðè
K 3 ê çàäà÷å âû÷èñëåíèÿ õðîìàòè÷åñêîãî ÷èñëà ( Min CG_ ). Ïóñòü S1 — ìíî-
æåñòâî ãðàôîâ ñ õðîìàòè÷åñêèì ÷èñëîì, íå ïðåâîñõîäÿùèì òðåõ, à S 2 — ñ õðî-
42 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2016, òîì 52, ¹ 3
ìàòè÷åñêèì ÷èñëîì, íå ìåíüøèì, ÷åì 4. Òîãäà äà-ýêçåìïëÿðû îòîáðàæàþòñÿ íà
S1, à íåò-ýêçåìïëÿðû — íà S 2 . Ñîãëàñíî ëåììå 1 äëÿ Min CG_ íå ñóùåñòâóåò ïî-
ëèíîìèàëüíîãî àëãîðèòìà ñ îòíîøåíèåì àïïðîêñèìàöèè, íå áîëüøèì 4/3.
Åñëè ñóùåñòâóåò ñâåäåíèå, ââîäÿùåå ðàçðûâ îò L ê çàäà÷å �1, òî ìîæíî
îïðåäåëèòü ñëîæíîñòü (òðóäíîñòü) àïïðîêñèìàöèè äëÿ äðóãîé çàäà÷è �2 ââåäå-
íèåì ñâåäåíèÿ, ñîõðàíÿþùåãî ðàçðûâ îò �1 ê �2 .
Îïðåäåëåíèå 8. Ñâåäåíèå, ñîõðàíÿþùåå ðàçðûâ (ôóíêöèÿ F ) îò �1 ê �2 ,
çàäàåòñÿ ÷åòûðüìÿ ïàðàìåòðàìè (ôóíêöèÿìè): f f1 2, , ,� � . Äëÿ çàäàííîãî ýêçåì-
ïëÿðà x ��1 ñâåäåíèå âû÷èñëÿåò çà ïîëèíîìèàëüíîå âðåìÿ ýêçåìïëÿð y ��2
( ( ))y F x òàêîé, ÷òî
OPT x f x OPT y f y( ) ( ) ( ) ( )� � �1 2 ,
OPT x x f x OPT y y f y( ) (| | ) ( ) ( ) (| | ) ( )� � � � �� �1 2 .
Ëåììà 3. Ïóñòü g — ñâåäåíèå, ââîäÿùåå ðàçðûâ îò L ê �1 (�(| | )x — ðàçìåð
ðàçðûâà), à F — ñâåäåíèå, ñîõðàíÿþùåå ðàçðûâ îò �1 ê �2 ñ ïàðàìåòðàìè
f f1 2, , ,� � . Òîãäà åñëè P NP� , òî äëÿ çàäà÷è �2 íå ñóùåñòâóåò ïîëèíîìèàëü-
íîãî àëãîðèòìà ñ îòíîøåíèåì àïïðîêñèìàöèè, íå áîëüøèì � .
Äîêàçàòåëüñòâî. Ðàññìîòðèì êîìïîçèöèþ ñâåäåíèÿ, ââîäÿùåãî ðàçðûâ äëÿ
�1 ( )g , è ñâåäåíèÿ, ñîõðàíÿþùåãî ðàçðûâ äëÿ �2(F ): g F F g x� ( ( )). Êîìïîçè-
öèÿ g F� çàäàåò ñâåäåíèå, ââîäÿùåå ðàçðûâ îò L ê �2 (�-ðàçðûâ). Îñòàëîñü ïðè-
ìåíèòü ëåììó 1 ê çàäà÷å �2 .
ÎÁ ÎÏÒÈÌÀËÜÍÎÉ ÐÀÑÊÐÀÑÊÅ ÎÄÍÎÃÎ ÃÐÀÔÀ
Ïîñòðîèì ãðàô H i , ïðåäñòàâëÿþùèé öåïü-( , )K i3 , ãäå K3 — ïîëíûé 3-âåð-
øèííûé ãðàô; i — íàòóðàëüíîå ÷èñëî. Ãðàô H i ñîñòîèò èç i çâåíüåâ è ñòðî-
èòñÿ èíäóêòèâíî. Ãðàô H1, ïðåäñòàâëÿþùèé öåïü-( , )K3 1 , — ýòî ãðàô
K V EK K3 3 3
( , ), ãäå âåðøèíû V a b cK i i i3
{ }, , íàçîâåì ñîîòâåòñòâåííî âåð-
øèíàìè òèïà a , òèïà b, òèïà c (â êàæäîì ïîñëåäóþùåì çâåíå); ðåáðà EK3
= { }( , ); ( , ); ( , )a b b c c ai i i i i i . Ïóñòü çàäàí ãðàô H i , ïðåäñòàâëÿþùèé öåïü-( , )K i3
è èìåþùèé i çâåíüåâ (K3). Ãðàô H i� 1 öåïü-( , )K i3 1� îáðàçóåòñÿ èç ãðàôà
H i öåïü-( , )K i3 , ê êîòîðîìó äîáàâëÿåòñÿ ãðàô K3 (( )i �1 -å çâåíî) âìåñòå
ñ òðåìÿ ðåáðàìè (îíè ñîåäèíÿþò âåðøèíû òèïà a, òèïà b, òèïà c ( )i �1 -ãî
çâåíà K3 ñ ñîîòâåòñòâóþùèìè âåðøèíàìè òèïà a , òèïà b, òèïà c ïîñëåäíåãî
çâåíà ãðàôà H i öåïü-( , )K i3 ). Áóäåì ñòðîèòü îïòèìàëüíûå ðàñêðàñêè ãðàôà
H i öåïü-( , )K i3 .
Ëåììà 4. Ãðàô H i öåïü-( , )K i3 ìîæíî ðàñêðàñèòü òðåìÿ öâåòàìè, è ñóùåñò-
âóåò 2 i îïòèìàëüíûõ ðàñêðàñîê òðåìÿ öâåòàìè (îïòèìàëüíûõ ðåøåíèé Min CG_ )
ýòîãî ãðàôà.
Äîêàçàòåëüñòâî. Ïîñêîëüêó ãðàô H i öåïü-( , )K i3 ñîäåðæèò â êà÷åñòâå ïîä-
ãðàôà õîòÿ áû îäèí ãðàô K3 , ðàñêðàñèòü ýòîò ãðàô, ìåíüøå, ÷åì òðåìÿ öâåòàìè,
íåâîçìîæíî. Ïîýòîìó îïòèìàëüíàÿ ðàñêðàñêà èñïîëüçóåò íå ìåíåå òðåõ öâåòîâ.
Ãðàô H i áóäåì ðàñêðàøèâàòü òðåìÿ öâåòàìè, ïåðåíóìåðîâàâ èõ êàê 1, 2, 3. Ðàñ-
êðàñêó ãðàôà K3 áóäåì çàäàâàòü öâåòàìè â ïîðÿäêå ñëåäîâàíèÿ âåðøèí òèïà b,
òèïà c, òèïà a . Íàïðèìåð, ðàñêðàñêà ãðàôà K3 êàê 123 îçíà÷àåò, ÷òî âåðøèíà òèïà
b èìååò öâåò 1, òèïà c — öâåò 2, òèïà a — öâåò 3. Áóäåì ñ÷èòàòü, ÷òî äëÿ ðàñêðàñ-
êè ãðàôà H1 öâåò âåðøèíû òèïà b — ôèêñèðîâàííûé (è çàðàíåå çàäàííûé). Ðàñ-
êðàñêó ãðàôà H i öåïü-( , )K i3 ïðîâåäåì èíäóêòèâíî. Ãðàô H1 ìîæíî ðàñêðàñèòü
äâóìÿ ñïîñîáàìè ïðè ôèêñèðîâàííîì öâåòå âåðøèíû òèïà b. Òàêèì îáðàçîì,
åñëè öâåò b åñòü 1, òî ïðàâèëüíàÿ ðàñêðàñêà èìååò âèä { }123 132, ; åñëè öâåò b åñòü
2, òî ïðàâèëüíàÿ ðàñêðàñêà — { }213 231, ; åñëè öâåò b åñòü 3, òî ïðàâèëüíàÿ ðàñ-
êðàñêà — { }312 321, . Ïóñòü ãðàô H i ìîæíî ðàñêðàñèòü 2 i ñïîñîáàìè ( i 1 2, ,�).
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2016, òîì 52, ¹ 3 43
Ïîêàæåì, ÷òî ãðàô H i�1 ìîæíî ïðàâèëüíî ðàñêðàñèòü
2 2 2 1
�
�i i ñïîñîáàìè. Ïðîñòûì ïåðåáîðîì ìîæíî
ïîêàçàòü, ÷òî åñëè i-å çâåíî ãðàôà H i ïðàâèëüíî ðàñ-
êðàøåíî êàê bca (ãäå a b c, , , ,�{ }1 2 3 ), òî ïðè äîáàâëå-
íèè ( )i �1 -ãî çâåíà K3 åãî ìîæíî ïðàâèëüíî ðàñêðàñèòü
äâóìÿ ñïîñîáàìè: cab abc, è çàïèñàòü êàê
bca cab abc� , . (1)
Ðàñêðàñêè (1) ñîñòàâëÿþò òàêîå ìíîæåñòâî ðàñ-
êðàñîê:
{123 231 312 132 321 213 213 132 321� � �, ; , ; , ;
231 312 123 312 123 231 321 213 132� � �, ; , ; , }. (2)
Òàêèì îáðàçîì, ïðè äîáàâëåíèè ( )i �1 -ãî çâåíà
÷èñëî ïðàâèëüíûõ ðàñêðàñîê óâåëè÷èòñÿ ðîâíî âäâîå:
2 2 2 1
�
�i i . Ëåììà äîêàçàíà.
Íà ðèñ. 1 ïîêàçàíà îïòèìàëüíàÿ ðàñêðàñêà ãðàôà
H 3 öåïü-( , )K3 3 èç âîçìîæíûõ âîñüìè îïòèìàëüíûõ
ðàñêðàñîê. Äàííàÿ ðàñêðàñêà ñîîòâåòñòâóåò ïîäìíî-
æåñòâó ðàñêðàñîê { }132 321 213 321 213 132� �, ; , èç (2).
ÏÎÍßÒÈÅ ÌÍÎÆÅÑÒÂÅÍÍÎÉ ÐÅÎÏÒÈÌÈÇÀÖÈÈ
Èçâåñòíî, ÷òî çàäà÷à î êîììèâîÿæåðå TSP (Travelling Salesman Problem) ÿâëÿåòñÿ
çàäà÷åé íàõîæäåíèÿ êðàò÷àéøåãî ãàìèëüòîíîâà ïóòè â ðåáåðíî-âçâåøåííîì ïîë-
íîì ãðàôå. Åñëè P NP� , òî äëÿ ýòîé çàäà÷è íå ñóùåñòâóåò ïîëèíîìèàëüíîãî
ïðèáëèæåííîãî àëãîðèòìà ñ àïïðîêñèìàöèîííûì îòíîøåíèåì 2n â n-âåðøèííîì
ãðàôå ñ ïðîèçâîëüíûìè âåñàìè ðåáåð [10]. Ïóñòü Inc -Edge-Reopt -TSP — ðåîï-
òèìèçàöèîííàÿ âåðñèÿ çàäà÷è TSP, â êîòîðîé óâåëè÷èëñÿ âåñ îäíîãî ðåáðà. Êàê è
â ñëó÷àå TSP, èìååò ìåñòî ðåçóëüòàò.
Òåîðåìà 1 [11, 12]. ßâëÿåòñÿ NP-òðóäíûì àïïðîêñèìèðîâàòü çàäà÷ó
Inc -Edge-Reopt -TSP ñ àïïðîêñèìàöèîííûì îòíîøåíèåì, êîòîðîå ïðåäñòàâëÿåò
ïîëèíîì îò ðàçìåðíîñòè çàäà÷è.
Îáîáùåíèå ðåîïòèìèçàöèè (êîòîðóþ áóäåì íàçûâàòü ìíîæåñòâåííîé ðå-
îïòèìèçàöèåé) ñîñòîèò â òîì, ÷òî èçâåñòíûì ÿâëÿåòñÿ íå åäèíñòâåííîå îïòè-
ìàëüíîå ðåøåíèå «ñòàðîãî» ýêçåìïëÿðà, à ìíîæåñòâî îïòèìàëüíûõ ðåøåíèé
èëè áëèçêèõ ê íèì (âîçìîæíî, ñ ýêñïîíåíöèàëüíûì ÷èñëîì), äîñòóï ê êîòîðûì
íå îãðàíè÷åí [6, 7].
Îïðåäåëåíèå 9. Ïðåäñòàâèì çàäà÷ó Inc -Edge-ReoptALL -TSP êàê çàäà÷ó, çà-
äàííóþ ïîëíûì ãðàôîì G V E ( , ), ñ äâóìÿ çàäàííûìè âåñîâûìè ôóíêöèÿìè:
cold è cnew òàêèìè, ÷òî ( , )G cold è ( , )G cnew ÿâëÿþòñÿ äîïóñòèìûìè ýêçåìïëÿðàìè
äëÿ TSP, è òàêèìè, ÷òî cold è cnew ñîâïàäàþò âñåìè ðåáðàìè, êðîìå ðåáðà
e Echange � , ãäå c e c eold change new change( ) ( )� . Áîëåå òîãî, èçâåñòíû âñå îïòèìàëü-
íûå TSP-ðåøåíèÿ ( , )G cold . Íåîáõîäèìî âû÷èñëèòü îïòèìàëüíîå TSP-ðåøåíèå
äëÿ ( , )G cnew .
Òåîðåìà 2 [7]. Â ïðåäïîëîæåíèè P NP� íå ñóùåñòâóåò ïîëèíîìèàëüíîãî
ïðèáëèæåííîãî àëãîðèòìà ñ îòíîøåíèåì àïïðîêñèìàöèè 2n äëÿ çàäà÷è
Inc -Edge-ReoptALL -TSP , ãäå n — ÷èñëî âåðøèí ýêçåìïëÿðà.
Òàêèì îáðàçîì, ïðè ñðàâíåíèè òåîðåì 1 è 2 ïðèõîäèì ê âûâîäó, ÷òî â äàí-
íîì ñëó÷àå ìíîæåñòâåííàÿ ðåîïòèìèçàöèÿ íå ñïîñîáñòâóåò óëó÷øåíèþ êà÷åñòâà
ïðèáëèæåíèÿ.
44 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2016, òîì 52, ¹ 3
1
1
3
3
2
1 2
2
3 ñkak
bk
cj
aj
bj
ciai
bi
Ðèñ. 1. Îïòèìàëüíàÿ ðàñêðàñ-
êà ãðàôà H3 öåïü-( , )K3 3
(èç âîñüìè âîçìîæíûõ)
Çàäà÷à î ìèíèìàëüíîì äåðåâå Øòåéíåðà (STP) ïðåäñòàâëÿåòñÿ ñëåäóþùåé
îïòèìèçàöèîííîé çàäà÷åé: äëÿ çàäàííîãî íåîðèåíòèðîâàííîãî ïîëíîãî ãðàôà
G V E ( , ), ìåòðè÷åñêîé âåñîâîé ôóíêöèè ðåáåð c E Q: �
� (Q � — ìíîæåñòâî
ïîëîæèòåëüíûõ ðàöèîíàëüíûõ ÷èñåë) è ìíîæåñòâà S V� òåðìèíàëîâ íåîáõîäè-
ìî íàéòè ìèíèìàëüíîå ïî âåñó ïîääåðåâî G , êîòîðîå ñîäåðæèò âñå òåðìèíàëû
(è, âîçìîæíî, íåêîòîðûå íå òåðìèíàëû). Òàêîå ïîääåðåâî, ñîäåðæàùåå âñå òåð-
ìèíàëû, íàçûâàåòñÿ ìèíèìàëüíûì äåðåâîì Øòåéíåðà äëÿ G .
Îïðåäåëåíèå 10. Ðåîïòèìèçàöèîííàÿ çàäà÷à äëÿ ìèíèìàëüíîãî äåðåâà
Øòåéíåðà ñ ëîêàëüíîé ìîäèôèêàöèåé lm, íàïðèìåð äîáàâëåíèåì òåðìèíàëüíîé
âåðøèíû ñ ðåáðàìè ê ãðàôó (ñîêðàùåííî Reopt -STP - lm), ÿâëÿåòñÿ òàêîé îïòè-
ìèçàöèîííîé çàäà÷åé. Ââîä ñîñòîèò èç STP-ýêçåìïëÿðà ( , , )G S c , îïòèìàëüíîãî
äåðåâà Øòåéíåðà Told äëÿ íåãî è ëîêàëüíî ìîäèôèöèðîâàííîãî STP-ýêçåìïëÿðà
( , , )� � �G S c ïî îòíîøåíèþ ê lm . Íåîáõîäèìî íàéòè ìèíèìàëüíîå äåðåâî Øòåéíå-
ðà äëÿ ýêçåìïëÿðà ( , , )� � �G S c .
Ðàññìîòðèì ìîäèôèêàöèþ lm AddTerm (äîáàâëåíèå òåðìèíàëüíîé âåðøè-
íû). Ïîêàçàíî [13], ÷òî Reopt - STP -AddTerm ÿâëÿåòñÿ APX-òðóäíîé çàäà÷åé. Ýòî
îçíà÷àåò, ÷òî íå ñóùåñòâóåò PTAS äëÿ çàäà÷è ïðè P NP� .
Îïðåäåëåíèå 11. Ìèíèìàëüíàÿ ðåîïòèìèçàöèîííàÿ çàäà÷à äåðåâà Øòåéíåðà
ñ k ðåøåíèÿìè (ñîêðàùåííî k - Sol-Reopt -STP - lm) ïðåäñòàâëÿåò ñëåäóþùóþ
çàäà÷ó. Ââîä ñîñòîèò èç STP-ýêçåìïëÿðà ( , , )G S c , ïîñëåäîâàòåëüíîñòè k íàèëó÷-
øèõ äåðåâüåâ Øòåéíåðà T T k
old old
( ) ( ), ,1
� äëÿ íåãî è ëîêàëüíî ìîäèôèöèðîâàííîãî
ýêçåìïëÿðà ( , , )� � �G S c ïî îòíîøåíèþ ê lm. Çàäà÷à ñîñòîèò â íàõîæäåíèè ìèíè-
ìàëüíîãî äåðåâà Øòåéíåðà äëÿ ( , , )� � �G S c .
Ñ ïîìîùüþ AP-ñâåäåíèé, ñîõðàíÿþùèõ àïïðîêñèìàöèîííîå îòíîøåíèå,
óñòàíîâëåí ñëåäóþùèé ôàêò.
Òåîðåìà 3 [6]. Çàäà÷à nn
2- Sol-Reopt -AddTerm ÿâëÿåòñÿ APX-òðóäíîé.
Òàêèì îáðàçîì, è â ýòîì ñëó÷àå ìíîæåñòâåííàÿ ðåîïòèìèçàöèÿ íå
ñïîñîáñòâóåò óëó÷øåíèþ êà÷åñòâà ïðèáëèæåíèÿ.
ÌÍÎÆÅÑÒÂÅÍÍÀß ÐÅÎÏÒÈÌÈÇÀÖÈß ÇÀÄÀ×È
Î ÌÈÍÈÌÀËÜÍÎÉ ÐÀÑÊÐÀÑÊÅ ÃÐÀÔÀ
Îïðåäåëåíèå 12. k-ìíîæåñòâåííàÿ ðåîïòèìèçàöèÿ Min CG_ ñ ëîêàëüíîé ìîäè-
ôèêàöèåé lm (ñîêðàùåííî k -Set -Reopt - Min CG_ - lm) ïðåäñòàâëÿåò ñëåäóþùóþ
îïòèìèçàöèîííóþ çàäà÷ó. Ââîä ñîñòîèò èç ýêçåìïëÿðà G V E w ( , , )old old old çà-
äà÷è Min CG_ ñ k îïòèìàëüíûìè ðåøåíèÿìè è ëîêàëüíî ìîäèôèöèðîâàííîãî
ýêçåìïëÿðà G V E w ( , , )new new ïî îòíîøåíèþ ê lm. Íåîáõîäèìî íàéòè ìèíè-
ìàëüíîå ÷èñëî êðàñîê wnew äëÿ G V E w ( , , )new new .
Âîçìîæåí âàðèàíò k k n ( ), ãäå n — ÷èñëî âåðøèí ãðàôà.  êà÷åñòâå ìîäè-
ôèêàöèè lm áóäåì ðàññìàòðèâàòü âàðèàíòû: a) lm AddVer (âñòàâêà ïðîèçâîëü-
íîé âåðøèíû ñ íå áîëåå ÷åì äâóìÿ ðåáðàìè, èíöèäåíòíûìè åé); á) lm DelVer
(óäàëåíèå ëþáîé âåðøèíû ñî âñåìè èíöèäåíòíûìè åé ðåáðàìè).
Áóäåì ñ÷èòàòü, ÷òîV V nold old(| | ) ñîäåðæèò õîòÿ áû îäèí ãðàô K3 â êà÷åñò-
âå ïîäãðàôà (äëÿ êîððåêòíîé ðåàëèçàöèè ïðåäëàãàåìîé êîíñòðóêöèè).
Ðàññìîòðèì ñëåäóþùóþ ðåîïòèìèçàöèîííóþ çàäà÷ó. Ïóñòü ãðàô
G V E w1 1 1 ( , , ) ïîëó÷åí èç ãðàôà G V E w ( , , ) ñ èñïîëüçîâàíèåì âñòàâêè ïðîèç-
âîëüíîé âåðøèíû ñ íå áîëåå ÷åì äâóìÿ ðåáðàìè, èíöèäåíòíûìè åé. Çàäà÷à ðåîï-
òèìèçàöèè G1 çàêëþ÷àåòñÿ â íàõîæäåíèè åå ðåøåíèÿ (ïðèáëèæåííîãî) â ïðåäïî-
ëîæåíèè, ÷òî îïòèìàëüíîå ðåøåíèå G ñî çíà÷åíèåì wmin èçâåñòíî.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2016, òîì 52, ¹ 3 45
Òåîðåìà 4 [8]. Åñëè P NP� , òî äëÿ ðåîïòèìèçàöèè çàäà÷è G V E w1 1 1 ( , , ) íå
ñóùåñòâóåò PTAS.
Ïóñòü G V E w2 2 2 ( , , ) ïîëó÷àåòñÿ èç ãðàôà G V E w ( , , ) óäàëåíèåì ïðîèç-
âîëüíîé âåðøèíû ñî âñåìè èíöèäåíòíûìè åé ðåáðàìè.
Òåîðåìà 5 [8]. Åñëè P NP� , òî äëÿ ðåîïòèìèçàöèè çàäà÷è G V E w2 2 2 ( , , )
íå ñóùåñòâóåò PTAS.
Òåîðåìà 6. Åñëè P NP� , òî äëÿ çàäà÷è 2n -Set - Reopt - Min CG_ - AddVer íå
ñóùåñòâóåò PTAS.
Äîêàçàòåëüñòâî. Ïóñòü L — çàäà÷à CG ïðè K 3, à �1 — ðåîïòèìèçàöèÿ
G V E w1 1 1 ( , , ). Ïîñòðîèì ñâåäåíèå g , ââîäÿùåå ðàçðûâ îò L ê �1 (ôàêòè÷åñêè
ýòî ñâåäåíèå ðàññìàòðèâàëîñü â [8, äîêàçàòåëüñòâî òåîðåìû 4]). Ïóñòü x L� —
ýêçåìïëÿð çàäà÷è L, g x( ) — ïðåîáðàçîâàíèå (ïîëèíîìèàëüíîå), ñîñòîÿùåå â îòîá-
ðàæåíèè V íà V1 è E íà E1, êîòîðîå çàäàåòñÿ äîáàâëåíèåì âåðøèíû � ê V (ïîëó-
÷èì V1) ñ íå áîëåå ÷åì äâóìÿ ðåáðàìè, èíöèäåíòíûìè åé (ïîëó÷èì E1). Åñëè
x L� åñòü äà-ýêçåìïëÿð, òî ýòî ÿâëÿåòñÿ 3-ðàñêðàñêîé ãðàôà G . Ïîêàæåì, ÷òî îíà
áóäåò 3-ðàñêðàñêîé ãðàôà G1. Äåéñòâèòåëüíî, èñõîäÿ èç 3-ðàñêðàñêè G, ìîæíî
ðàñêðàñèòü âåðøèíó � ãðàôà G1 (äîáàâëåíû íå áîëåå ÷åì äâà èíöèäåíòíûõ åé
ðåáðà) öâåòîì, îòëè÷íûì îò äâóõ öâåòîâ (åñëè äîáàâëåíû ðîâíî äâà ðåáðà), êîòî-
ðûìè ðàñêðàøåíû â G ñîîòâåòñòâóþùèå âåðøèíû (ñîåäèíåííûå ðåáðîì).
Ïðè äîáàâëåíèè îäíîãî ðåáðà âåðøèíà � ðàñêðàøèâàåòñÿ öâåòîì, îòëè÷íûì îò
öâåòà ñîñåäíåé ê � âåðøèíû. Òàêèì îáðàçîì, ïîëó÷èì 3-ðàñêðàñêó ãðàôà G1,
ò.å. ýêçåìïëÿð y g x G �( ) 1 ñî çíà÷åíèåì w h y� ( ) 3. Íåò-ýêçåìïëÿð çàäà÷è L —
ýòî ðàñêðàñêà ãðàôà G íå ìåíåå ÷åòûðüìÿ öâåòàìè, ÷òî ñîãëàñíî ñêàçàííîìó
âûøå äàåò âîçìîæíîñòü ðàñêðàñèòü G1 òàêæå íå ìåíåå ÷åì ÷åòûðüìÿ öâåòàìè,
ò.å. ïîëó÷èì ýêçåìïëÿð y g x �( ) �1 ñî çíà÷åíèåì w x h y� � �(| | ) ( ) 4, îòêóäà
�(| | ) /x 4 3. Òàêèì îáðàçîì, ïîëó÷èì ñâåäåíèå, ââîäÿùåå ðàçðûâ g x( ) îò L ê �1;
�(| | ) /x 4 3 — ðàçìåð ðàçðûâà.
Ïîñòðîèì ñâåäåíèå F , êîòîðå ñîõðàíÿåò ðàçðûâ îò �1 ê çàäà÷å �2
2n -Set - Reopt -Min CG_ -AddVer.
Ñóòü êîíñòðóêöèè ñîñòîèò â çàìåíå ïðîèçâîëüíîé âåðøèíû u (òîëüêî íå íî-
âîé äîáàâëåííîé) ýêçåìïëÿðà x ��1 ãðàôîì H n öåïü-( , )K n3 , êîòîðûé èìååò
3n âåðøèí. Âåðøèíà òèïà b ïåðâîãî çâåíà H n ïîëó÷èò òàêîé æå öâåò, êîòîðûé
îíà èìåëà â îïòèìàëüíîì ðåøåíèè ñî çíà÷åíèåì wmin . Îñòàëüíûå äâà öâåòà ðàñ-
êðàñêè äëÿ H n âûáèðàþòñÿ îòëè÷íûìè îò öâåòà u , ïðè ýòîì îíè ïðèñóòñòâóþò
â ðàñêðàñêå G1. Òàêèì îáðàçîì, äëÿ x ��1 F x( ) — ïîëèíîìèàëüíîå ïðåîáðàçîâà-
íèå, ñîñòîÿùåå â îòîáðàæåíèèV1 íàV3 (äîáàâëåíà 3 1n
âåðøèíà êV1 ñîîòâåòñòâó-
þùèì îáðàçîì) è E1 íà E3 (äîáàâëåíèåì ñîîòâåòñòâóþùåãî ÷èñëà ðåáåð ê E1).
Òîãäà ìíîæåñòâî îïòèìàëüíûõ ðåøåíèé äëÿ G V E w3 3 3 ( , , ) ìîæåò áûòü âû÷èñ-
ëåíî ïðè çàìåíå ðàñêðàñêè u ìíîæåñòâîì îïòèìàëüíûõ ðàñêðàñîê ãðàôà H n (÷èñ-
ëî êîòîðûõ ñîñòàâëÿåò 2n ). Òàêèì îáðàçîì, îáùàÿ ñòðóêòóðà ãðàôà íå èçìåíÿåòñÿ
îïèñàííûì ïðåîáðàçîâàíèåì è çíàíèå âñåãî ýêñïîíåíöèàëüíîãî ÷èñëà ðàñêðàñîê
(2n ) íå ñïîñîáñòâóåò ðåøåíèþ íîâîãî ýêçåìïëÿðà. Ñîãëàñíî îïðåäåëåíèþ 8 äëÿ
x ��1 èìååì y F x �( ) �2 , ò.å. f x f y1 2 3( ) ( )� � , � �(| | ) (| | ) /x y� � 4 3,
íà îñíîâàíèè ñâîéñòâ ïîñòðîåííîãî ïðåîáðàçîâàíèÿ F x( ), êîòîðûå àíàëîãè÷íû
ñâîéñòâàì g x( ).
Ïðèìåíÿÿ ê ñâåäåíèÿì g è F ëåììó 3, ïîëó÷àåì ñëåäóþùåå: åñëè P NP� , òî
äëÿ çàäà÷è �2 íå ñóùåñòâóåò ïîëèíîìèàëüíîãî àëãîðèòìà ñ îòíîøåíèåì àïïðîê-
ñèìàöèè, íå áîëüøèì �(| | ) /y 4 3, èëè íå ñóùåñòâóåò PTAS.
Òåîðåìà 7. Åñëè P NP� , òî äëÿ çàäà÷è 2n -Set -Reopt -Min CG_ -DelVer íå ñó-
ùåñòâóåò PTAS.
46 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2016, òîì 52, ¹ 3
Äîêàçàòåëüñòâî àíàëîãè÷íî ïðåäûäóùåìó è ñëåäóåò èç òîãî ôàêòà, ÷òî èç
3-ðàñêðàñêè ãðàôà G V E w ( , , ) âûòåêàåò 3-ðàñêðàñêà ãðàôà G V E w3 3 3 ( , , ) è èç
íå ìåíåå ÷åì 4-ðàñêðàñêè G ñëåäóåò íå ìåíåå ÷åì 4-ðàñêðàñêà ãðàôà G3 .
ÇÀÊËÞ×ÅÍÈÅ
 íàñòîÿùåé ñòàòüå ïîêàçàíî, ÷òî äëÿ ìíîæåñòâåííîé ðåîïòèìèçàöèè çàäà÷è
î âû÷èñëåíèè õðîìàòè÷åñêîãî ÷èñëà ãðàôà íå ñóùåñòâóåò PTAS ïðè âñòàâêå
ïðîèçâîëüíîé âåðøèíû ñ íå áîëåå ÷åì äâóìÿ ðåáðàìè, åé èíöèäåíòíûìè,
à òàêæå ïðè óäàëåíèè ïðîèçâîëüíîé âåðøèíû ñî âñåìè ðåáðàìè, åé èíöèäåíò-
íûìè, åñëè çàäàíî ìíîæåñòâî èç 2n îïòèìàëüíûõ ðàñêðàñîê èñõîäíîé çàäà÷è,
ãäå n — ÷èñëî âåðøèí â ãðàôå.
Ïîäîáíûå ðåçóëüòàòû èìåþò ìåñòî (íå óëó÷øàåòñÿ êà÷åñòâî ïðèáëèæåíèÿ —
àïïðîêñèìàöèîííîå îòíîøåíèå â ñðàâíåíèè ñ îáû÷íîé ðåîïòèìèçàöèåé) äëÿ ìíî-
æåñòâåííîé ðåîïòèìèçàöèè çàäà÷è î ìèíèìàëüíîì äåðåâå Øòåéíåðà ñ äîáàâëåíè-
åì òåðìèíàëüíîé âåðøèíû [6] è äëÿ çàäà÷è î êîììèâîÿæåðå ïðè óâåëè÷åíèè âåñà
îäíîãî ðåáðà [7]. Ïðåäñòàâëÿþò èíòåðåñ ïîäîáíûå è îòëè÷àþùèåñÿ îò íèõ ðåçóëü-
òàòû, ïîëó÷åííûå ñ èñïîëüçîâàíèåì ìíîæåñòâåííîé ðåîïòèìèçàöèè ïðè ëîêàëü-
íûõ èçìåíåíèÿõ äàííûõ äëÿ äðóãèõ êëàññîâ äèñêðåòíûõ îïòèìèçàöèîííûõ çàäà÷.
 ÷àñòíîñòè, àâòîðó íåèçâåñòíû ðåçóëüòàòû ìíîæåñòâåííîé ðåîïòèìèçàöèè, êîòî-
ðàÿ èìåëà áû ïðåèìóùåñòâî â êà÷åñòâå ïðèáëèæåíèÿ ïî ñðàâíåíèþ ñ îáû÷íîé ðå-
îïòèìèçàöèåé.
ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ
1. F r e d e r i c k s o n G . N . Data structures for on-line updating of minimum spanning trees with
application // SIAM Journal on Computing. — 1985. — 14, N 4. — P. 781–798.
2. R o h n e r t H . A dynamization of the all-pairs least cost problems // Proc. 2nd Symp. on Theoretical
Aspects of Computer Science, 1985. — P. 279–286.
3. A u s i e l l o G . , B o n i f a c i V . , E s c o f f i e r B. Complexity and approximation in
reoptimization // Computability in Context: Computation and Logic in the Real World (S.B. Cooper,
A. Sorbi (Eds.). — London: Imperial College Press, 2011. — P. 101–130.
4. B o c k e n h a u e r H . - J . , H r o m k o v i c J . , M o m k e T . , W i d m a y e r P . On the hardness
of reoptimization / V. Geffert, J. Karhumaki, A. Bertoni, etc. (Eds.) // SOFSEM, Lecture Notes in
Computer Science. — 2008. — 4910. — P. 50–65.
5. B o r i a N . , P a s c h o s V . T h . A survey on combinatorial optimization in dynamic environments
// RAIRO — Operations Research. — 2011. — 45. — P. 241–.294.
6. B o c k e n h a u e r H . - J . , H r o m k o v i c J . , S p r o c k A . On the hardness of reoptimization
with multiple given solutions // Fundamenta Informaticae. — 2011. — 110. — P. 59–76.
7. B o c k e n h a u e r H . - J . , H r o m k o v i c J . , S p r o c k A . Knowing all optimal solutions does
not help for TSP reoptimization / J. Kelemen and A. Kelemenova (Eds.) // Lecture Notes in
Computer Science. — 2011. — 6610. — P. 7–15.
8. Ì è õ à é ë þ ê Â . À . Ê âîïðîñó î ñóùåñòâîâàíèè ïîëèíîìèàëüíî ïðèáëèæåííûõ ñõåì äëÿ ðå-
îïòèìèçàöèè äèñêðåòíûõ çàäà÷ îïòèìèçàöèè // Êèáåðíåòèêà è ñèñòåìíûé àíàëèç. — 2011. —
¹ 3. — Ñ. 42–50.
9. V a z i r a n i V . V . Approximation algorithms. — Berlin: Springer, 2001. — 380 p.
10. S a h n i S . , G o n z a l e s T . F . P-complete approximation problems // Journal of the ACM. —
1976. — 23, N 3. — P. 555–565.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2016, òîì 52, ¹ 3 47
11. B o c k e n h a u e r H . - J . , F o r l i z z i L . , H r o m k o v i c J . , K n e i s J . , K u p k e J . ,
P r o i e t t i G . , W i d m a y e r P . Reusing optimal TSP solutions for locally modified input
instances (extended abstract) // G. Navarro, L.E. Bertissi, Y. Kohayakava (Eds.) // Proc. of the 4th
IFIP International Conference on Theoretical Computer Science (TCS). — 2006. — IFIP, Springer.
— 209. — P. 251–270.
12. B o c k e n h a u e r H . - J . , F o r l i z z i L . , H r o m k o v i c J . , K n e i s J . , K u p k e J . ,
P r o i e t t i G . , W i d m a y e r P . On the approximability of TSP on local modifications of
optimality solved instances // Algorithmic Operations Research. — 2007. — 2, N 2. — P. 83–93.
13. B o c k e n h a u e r H . - J . , F r e i e r m u t h K . , H r o m k o v i c J . , M o m k e T . , S p r o c k A . ,
S t e f f e n B . Steiner tree reoptimization in graphs with sharpened triangle inequality // Journal of
Discrete Algorithms. — 2012. — 11. — P. 73–86.
14. à ý ð è Ì . , Ä æ î í ñ î í Ä . Âû÷èñëèòåëüíûå ìàøèíû è òðóäíîðåøàåìûå çàäà÷è. — Ì.: Ìèð,
1982. — 416 ñ.
Íàä³éøëà äî ðåäàêö³¿ 05.08.2015
Â.Î. Ìèõàéëþê
ÑÊËÀÄͲÑÒÜ ÐÅÎÏÒÈ̲ÇÀÖ²¯ ÇÀÄÀײ ÎÁ×ÈÑËÅÍÍß ÕÐÎÌÀÒÈ×ÍÎÃÎ ×ÈÑËÀ
ÃÐÀÔÀ ²Ç ÇÀÄÀÍÎÞ ÌÍÎÆÈÍÎÞ ÎÏÒÈÌÀËÜÍÈÕ ÐÎÇÂ’ßÇʲÂ
Àíîòàö³ÿ. Âèêîðèñòàíî çâåäåííÿ, ùî ââîäÿòü ³ çáåð³ãàþòü ðîçðèâ. Ïîêàçà-
íî, ùî äëÿ ìíîæèííî¿ ðåîïòèì³çàö³³ çàäà÷³ ïðî îá÷èñëåííÿ õðîìàòè÷íîãî
÷èñëà ãðàôà ³ç çàäàíîþ åêñïîíåíö³àëüíîþ ìíîæèíîþ îïòèìàëüíèõ ðîç-
â’ÿçê³â ïðè óñòàâëåíí³ äîâ³ëüíî¿ âåðøèíè ç íå á³ëüø í³æ äâîìà ðåáðàìè, ¿é
³íöèäåíòíèìè, à òàêîæ ïðè âèäàëåíí³ äîâ³ëüíî¿ âåðøèíè ç óñ³ìà ³íöèäåíò-
íèìè ¿é ðåáðàìè íå ³ñíóº ïîë³íîì³àëüíî íàáëèæåíî¿ ñõåìè (PTAS). Òàêèé
æå ðåçóëüòàò ìຠì³ñöå äëÿ çâè÷àéíî¿ ðåîïòèì³çàö³³.
Êëþ÷îâ³ ñëîâà: ìíîæèííà ðåîïòèì³çàö³ÿ; çâåäåííÿ çàäà÷, ÿê³ ââîäÿòü ³
çáåð³ãàþòü ðîçðèâ; APX-ñêëàäí³ñòü, ïîë³íîì³àëüíî íàáëèæåí³ ñõåìè (PTAS).
V.A. Mikhailyuk
HARDNESS OF REOPTIMIZATION OF THE PROBLEM OF CALCULATING
THE CHROMATIC NUMBER OF A GRAPH WITH A GIVEN SET OF OPTIMAL SOLUTIONS
Abstract. The author uses gap-introducing and gap-preserving reductions and
shows that for multiple reoptimization of the problem of calculating the
chromatic number of a graph with a given exponential set of optimal solutions,
when an arbitrary vertex with no more than two edges incident to it is inserted
as well as when any vertex with all incident edges is deleted, polynomial time
approximation scheme (PTAS) does not exist. The same result holds for
ordinary reoptimization..
Keywords: multiple reoptimization, gap-introducing (gap-preserving) reductions,
APX-difficulty, polynomial time approximation schemes (PTAS).
Ìèõàéëþê Âèêòîð Àëåêñååâè÷,
äîêòîð ôèç.-ìàò. íàóê, äîöåíò, çàâåäóþùèé êàôåäðîé Âîñòî÷íîåâðîïåéñêîãî íàöèîíàëüíîãî
óíèâåðñèòåòà èìåíè Ëåñè Óêðàèíêè, Ëóöê, e-mail: mikhailyukvictor2@gmail.com.
48 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2016, òîì 52, ¹ 3
|