Эквивалентность между мин uncut и min-csp_xor

Question

В этой статье

agarwal, amit et al. «O (√ log n) алгоритмы аппроксимации для мин неразрезаны, мин 2CNF удаление и направленные проблемы с разрезами". Материалы тридцати седьмого ежегодного симпозиума ACM по теории вычислений. 2005.

agarwal et al. утверждают, что следующие две проблемы эквивалентны.

Рассмотрим логические переменные $ b_1, \ dots, b_n $ и набор ограничений формы $ b_i \ oplus b_j= 0 $ и $ b_i \ oplus b_j= 1 $ . Цель состоит в том, чтобы минимизировать количество неудовлетворенных ограничений.

и

Учитывая график $ g= (v, e) $ Найти разреза, который минимизирует количество неразрешенных краев.

Если ограничения были только из формы $ b_i \ oplus b_j= 1 $ , эквивалентность простой. Однако, если мы также рассмотрим ограничения формы $ B_i \ Oplus b_j= 0 $ , первая формулировка кажется мне более общем.

Как эти эквивалентные?

Answer 1

Предположим, нам дают набор ограничений формы $ b_i \ oplus b_j= c $ . Мы строим график с одной вершиной, соответствующей каждому $ b_i $ . Для каждого ограничения формы $ b_i \ oplus b_j= 1 $ , мы добавляем край $ \ {i, j \ } $ . Для каждого ограничения формы $ B_i \ Oplus b_j= 0 $ , мы добавляем новую вершину $ x $ , И два края $ \ {i, x \}, \ {j, x \} $ .

Мы можем думать о вырезах как раздел вершин на две части. Для ограничения формы $ b_i \ oplus b_j= 1 $ , ограничение неудовлетворена iff $ i, j $ < / span> относятся к той же части iff $ \ {i, j \} $ unsut. Для ограничения формы $ b_i \ oplus b_j= 0 $ , есть два случая:

.

• Если ограничение неудовлетворена, то $ i, j $ принадлежат к разным частям, и так же, как именно один из ребер $ \ {i, x \}, \ {j, x \} $ нерешит.

• Если ограничение не неудовлетворена, то $ i, j $ принадлежат к той же части, и поэтому (в зависимости от расположения <класса Span= «Математический контейнер»> $ x $ ) либо ноль или два края $ \ {i, x \}, \ {j, x \} $ < / span> нерехие. Поскольку мы стремимся к минимуму минимизировать количество неразрешенных краев, мы можем предположить, что ноль неисправна.

Всего количества неудовлетворенных ограничений совпадает с количеством неразрешенных ребер.