Везде, где я читаю о проблеме разреженного разреза, это говорит только о том, что проблема, как известно, является NP- трудной. Где я могу найти подтверждение этому? Какая известная NP- трудная проблема сводится к проблеме разреженного разреза?
Я не смог найти никаких доказательств в книге Вазирани «Алгоритмы аппроксимации», в которой представлен алгоритм Лейтона Рао, или в книге «Компьютеры и неразрешимость», в которой обобщены многие NP- полные проблемы. Я не смог найти его с помощью поиска (с очевидными поисковыми строками) в Google. Есть одна статья Чавлы и др., Которая предполагает гипотезу Хота по UGC и доказывает твердость аппроксимации самого разреженного разреза. Я надеялся увидеть доказательства, которые не предполагают никаких предположений.
Доказательство должно просто уменьшить известную NP- трудную проблему до разреженного разреза.
Спасибо,
Арпита Корвар.
источник
Ответы:
[Перемещено из комментария]
В статье Дэвида В. Матула « Редкие разрезы и узкие места на графиках » Фархад Шахрохи дает решение проблемы максимального сокращения. Доказательство твердости Max-cut можно найти в Garey Johnson.
источник