В задаче Макс-Кута ищется подмножество S вершин данного простого неориентированного графа так, чтобы число ребер между S и дополнением к S было как можно большим.
Max-Cut является APX-полным на графах с ограниченной степенью [PY91] и фактически APX-полным на кубических графах (т.е. графах степени 3) [AK00].
Max-Cut является NP-полным на графах без треугольников степени не более 3 [LY80] (без треугольников означает, что входной граф не содержит K_3, полный граф на 3 вершинах в качестве подграфа).
Вопрос: Является ли Max-Cut APX-полным на графиках без треугольников? (Примечание: разрешены произвольные степени)
Спасибо.
ОБНОВЛЕНИЕ: Ответ найден, но мне все равно будет интересна ссылка на этот результат, если таковой имеется.
Ссылки:
[AK00] П. Алимонти и В. Канн: Некоторые результаты APX-полноты для кубических графов. Теор. Вычи. Sci. 237 (1-2): 123-134, 2000. doi: 10.1016 / S0304-3975 (98) 00158-3
[LY80] Дж. М. Льюис и М. Яннакакис: Задача удаления узлов для наследственных свойств является NP-полной. J. Comput. Сист. Sci. 20 (2): 219-230, 1980. doi: 10.1016 / 0022-0000 (80) 90060-4
[PY91] CH Papadimitriou и M. Yannakakis: классы оптимизации, аппроксимации и сложности, J. Comput. System Sci., 43 (3): 425-440, 1991. doi: 10.1016 / 0022-0000 (91) 90023-X
Ответы:
Да, путем сокращения от MaxCut до MaxCut без треугольников. Вот что Википедия называет L-сокращением
Учитывая экземплярг Max-Cut, построить 3-х полосный г' путем разделения каждого края на три края. Тогда порядок максимального срезаг' порядок максимального среза г плюс вдвое больше ребер в г , Поскольку размер максимального среза всегда равен по крайней мере половине количества ребер, коэффициент ошибок только ухудшается постоянным фактором.
источник