Предположим, вам дан связный простой неориентированный граф H.
Проблема H-свободного среза определяется следующим образом:
Для простого неориентированного графа G существует ли разрез (разбиение вершин на два непустых множества L, R) такой, что графы, индуцированные множествами разрезов (L и R), не содержат подграфа, изоморфного H ,
Например, когда H является графом с двумя вершинами, соединенными одним ребром, проблема та же, что и определение, является ли граф двудольным и находится ли в P.
В случае, когда H является треугольником, это похоже на вершинную версию задачи Монохроматического треугольника .
Я думаю, что мне удалось показать, что, когда H 2-связен по крайней мере с тремя вершинами, проблема H-свободного разреза является NP-полной.
Я не смог найти никаких ссылок на эту проблему (и, следовательно, каких-либо результатов).
Можем ли мы отбросить условие 2-связности и все же доказать NP-полноту?
Кто-нибудь знает какие-либо известные результаты, которые подразумевали бы вышеупомянутый или более сильный результат (или вы думаете, что это может быть актуально)?
Ответы:
Вы можете искать термин «двунаправленное» или «разбиение вершины» или «раскраска», а не «вырезать». Различные обобщения хроматического числа вдоль линий, на которые вы намекаете, рассматривались с середины 80-х годов (или, возможно, ранее). На канадских конференциях по комбинаторике есть некоторые ранние труднодоступные ссылки, но вы можете проверить Коуэн, Годдард и Йезурум (JGT или SODA 1997) и соответствующие ссылки / цитаты.
Отредактировано 15/02/2011
А. Фарругия. Разбиение вершин на фиксированные аддитивно-наследственные свойства является NP-трудным. Электрон. Дж. Комбин. 11 (2004) # R46 (9 стр.).
источник
Я понимаю, что это может не дать прямого ответа на ваш вопрос (о ссылках), но я хотел бы наметить возможный подход к показу твердости NP без условия 2-связности. Есть две вещи, которые отсутствуют: одна является доказательством NP-твердости, так сказать, «проблемы с источником», а другая - то, что я сокращаю до «цветной» версии H-cut, которая может или может не быть полезным. Что касается первого узкого места, я думаю, у меня есть доказательство того, что мне лень формализоваться, поэтому я надеюсь, что скоро вернусь к этому. Однако я немного подумал о том, чтобы свести цветную версию к той, которую вы представляете, но пока без особой удачи. Мне также очень любопытно ваше доказательство в случае, если H 2-связен, не могли бы вы предоставить некоторые детали?
Таким образом, цветная версия выглядит следующим образом: каждая вершина графа снабжена списком цветов из палитры P (фиксированный, конечный набор). Нам нужно найти разрез, чтобы ни одно разбиение не индуцировало монохроматическую копию H, то есть не было подмножества | H | вершины, индуцирующие копию H, и соответствующий список цветов имеют непустое пересечение.
Вот сокращение от ограниченного варианта d-SAT, где d равно | H |. (Обратите внимание, что это очевидно не будет работать, когда d = 2).
Ограниченный вариант d-SAT следующий:
Каждое предложение имеет только положительные или только отрицательные литералы, позвольте мне упомянуть такие предложения как P-предложения и N-предложения соответственно,
Каждое P-предложение может быть спарено с N-предложением, так что два предложения включают в себя один и тот же набор переменных.
(У меня есть некоторое представление о том, почему эта, казалось бы, ограниченная версия может быть сложной - очень тесно связанное ограничение является жестким, и я могу представить сокращение оттуда, хотя я могу легко ошибиться!)
Учитывая эту проблему, сокращение, возможно, напрашивается само собой. Граф имеет вершину для каждой переменной формулы. Для каждого предложения C_i индуцируйте копию H на множестве переменных, участвующих в предложении, и добавьте цвет i к этому набору вершин. Это завершает строительство.
Любое назначение естественно соответствует разрезу:
L = набор всех переменных, которые были установлены в 0, R = набор всех переменных, которые были установлены в 1.
Утверждение состоит в том, что удовлетворительное назначение соответствует монохроматическому без H-среза.
Другими словами, (L, R), когда оно дается удовлетворительным присваиванием, будет таким, что ни L, ни R не будут индуцировать монохроматическую копию H. Если L имеет такую копию, то обратите внимание, что соответствующее P-предложение должно было иметь все его переменные установлены в 0, что противоречит тому, что присваивание было удовлетворительным. И наоборот, если R имеет такую копию, то в соответствующем N-предложении все переменные должны быть равны 1, опять же противоречие.
И наоборот, рассмотрите любое сокращение и установите переменные на одной стороне равными 1, а другой - 0 (обратите внимание, что не имеет значения, каким образом вы это делаете - учитывая тип формулы, с которой мы работаем, присваивание, и оно переворачивается версия эквивалентна, насколько удовлетворяемость идет). Если предложение не удовлетворяется этим назначением, то мы можем проследить его обратно до монохроматической копии H на одной из сторон, что противоречит монохроматической H-свободе разреза.
Причина, по которой нужно заниматься раскрашиванием, заключается в том, что копии H могут мешать создавать поддельные копии H, которые не соответствуют пунктам, в попытке прямого сокращения. В самом деле, он терпит неудачу - плохо - даже когда H является чем-то простым, как путь.
Мне не повезло в избавлении от цветов, и я не уверен, что облегчил проблему. Тем не менее, я надеюсь, что - если правильно - это может быть началом.
источник