Является ли Max-Cut APX-полным на графиках без треугольников?

9

В задаче Макс-Кута ищется подмножество 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

Standa Zivny
источник
Если вы не нашли ссылку, и кажется, что это оригинальный аргумент, рассмотрите возможность размещения ее здесь: meta.cstheory.stackexchange.com/questions/784/…
Suresh Venkat

Ответы:

14

Да, путем сокращения от MaxCut до MaxCut без треугольников. Вот что Википедия называет L-сокращением

Учитывая экземпляр г Max-Cut, построить 3-х полосный г'путем разделения каждого края на три края. Тогда порядок максимального срезаг' порядок максимального среза г плюс вдвое больше ребер в г, Поскольку размер максимального среза всегда равен по крайней мере половине количества ребер, коэффициент ошибок только ухудшается постоянным фактором.

Колин Маккуиллан
источник
9
Спасибо, Колин! В поисках ответа я обнаружил тот же трюк, который вы называете «3-стрейч», также известный как 2-подразделение. Из того, что я нашел, это, вероятно, впервые появилось в этой статье: Svatopluk Poljak: заметка о стабильных множествах и раскраске графиков, комментарий. Математика Университет Carolinae 15 (1974) 307-309 (доступно здесь: dml.cz/handle/10338.dmlcz/105554 )
Standa Zivny