Можете ли вы уменьшить K-независимый набор на 2-SAT

Question

Это вопрос о домашнем задании, чтобы начать. Перед тем, как начать, у меня есть несколько вопросов.

Наша проблема:

«Сокращение от к-независимого набора на 2-SAT следующим образом Учитывая граф с п вершины образуют п предложения, одна для каждой вершины Каждого предложения XI для вершины я установлен в положении.. true, если вершина i принадлежит незанятому множеству. Теперь для каждого ребра (u, v) напишем предложение, в котором говорится, что u и v не могут принадлежать к независимому множеству ».

Мой вопрос в том, что все, что я читаю, говорит, что 2-SAT не является проблемой NP-Complete. Как мы можем уменьшить из проблемы Независимого набора?

Answer 1

Существует важное различие между поиском любого независимого набора и выбором максимального независимого набора (независимого набора максимального размера).

Поиск любого независимого набора красиво сводится к 2-SAT, используя сокращение, которое вы описали в своем вопросе. Ни одна из проблем не является NP-полной. Обратите внимание, что сокращение, которое вы описали в своем вопросе, никак не ограничивает количество узлов в независимом наборе. Даже пустое множество удовлетворяет задаче 2-SAT, создаваемой этой редукцией, потому что пустое множество также является независимым множеством!

Поиск максимального независимого набора (или k-независимого набора), однако, является NP-полной проблемой. Он не уменьшает до 2-SAT.

Или другими словами: K в «к -независимой Набор» является дополнительным ограничением, которое не является частью этого сокращения 2-SAT (именно поэтому к даже не упоминается в описании сокращения). Вы могли бы добавить дополнительные предложения к проблеме SAT, чтобы подсчитать количество включенных узлов и обеспечить, чтобы это число было не менее k, но вы не можете этого сделать, добавив только 2-предложения. Таким образом, добавление k - это шаг, на котором ваша проблема с двумя SAT становится NP-полной общей проблемой SAT.

MAX-2-SAT является NP-полным расширением 2-SAT, которое также может использоваться для решения проблемы с максимальной независимой установкой с использованием сокращенного сообщения. (Вам понадобится две тривиальные модификации для сокращения: (1) Добавить 1-оговорки для каждого предложения и (2) дублировать 2-положения для взвешивания.)