Полиномиальное ядро ​​для

10

Параметризованная задача k-FLIP SAT определяется как:

Вход: формула 3-CNFφ с n переменные и присвоение правды σ:[n]{0,1}
Параметр: k
Вопрос: можем ли мы преобразовать заданиеσ в удовлетворяющее назначение σ за φ перевернуть значение истины самое большееk переменные?

Проблема явно в FPT ( Stefan Szeider: Параметризованная сложность локального поиска k-Flip для SAT и MAX SAT. Дискретная оптимизация 8 (1): 139-145 (2011) )

Допускает ли оно полиномиальное ядро? (при разумных допущениях сложности)

Недавние методы кросс-композиции (см. Ханс Л. Бодлаендер, Барт М.П. Янсен, Стефан Крач, «Нижние границы кернелизации с помощью кросс-композиции» ) кажутся бесполезными для этой проблемы. И они также кажутся бесполезными для подобных проблем, которые спрашивают, может ли данное решение NP-трудной проблемы быть найдено из данного экземпляра локальным поиском (ограничивая поиск соседями данного экземпляра, по некоторой естественной мере расстояния).

Марцио де Биаси
источник
Круто, но почему эта проблема явно FPT? Если вы сделаете это 2-CNF с ровно k переменными сальто вместо не более, то я считаю, что проблема fpt-эквивалентна k-клике. Я работал над документом, который включает в себя некоторые результаты по задачам точного к-флип.
Майкл Вехар
Я думаю, что сказать, что это в FPT означает, что это разрешимо в е(К)NО(1)время.
Майкл Вехар
Я думаю, что сказать, что это в XP означает, что это разрешимо в nf(k)время.
Майкл Вехар
Я не знаю взаимосвязи между проблемой точного k-flip и проблемой atmost-k-flip. Сначала я думал, что вы говорите, что проблема atmost-k-flip проще в том смысле, что atmost-k-flip - это FPT. Я говорю проще, потому что точный k-flip не может быть FPT, если ETH не ложно. Причина этого в том, что она эквивалентна k-клике, и известно, чтое(К)NО(1)Время алгоритмов для k-клики подразумевает ETH ложно.
Майкл Вехар
1
@MichaelWehar: ops, вы правы (я удаляю неправильный комментарий дурака), вопрос должен быть отполирован (я определил проблему как «самое большее k FLIPS»). КАК МОЖНО СКОРЕЕ Я взгляну на документ (ы) (одним из них должен быть Стефан Сайдер, «Параметризованная сложность локального поиска k-Flip для SAT и MAX SAT»), в котором говорится, что k-FLIP SAT FPT для предложений с ограниченным размером.
Марцио Де Биаси

Ответы:

12

Проблема не имеет ядра полинома, если NP не находится в coNP / poly. Техника кросс-композиции из нашей статьи применяется нетривиальным образом.

Позвольте мне показать, как классическая задача покрытия вершин ИЛИ пересекается с задачей k-FLIP-SAT; по результатам цитируемой статьи этого достаточно. Конкретно, мы строим алгоритм за полиномиальное время, вход которого представляет собой последовательность экземпляров Vertex Cover(г1,К),(г2,К),...,(гT,К) что все имеют одинаковую ценность К и у всех точно NВершины. Вывод является экземпляромК-FLIP SAT со значением параметра О(К+журналT)который достаточно мал для перекрестного состава, так что К-FLIP SAT экземпляр имеет ответ да, если один из входных графов имеет размер вершины К, Дублируя один вход (который не меняет значение ИЛИ), мы можем гарантировать, что количество входовT это сила двух.

Композиция происходит следующим образом. Пронумеруйте вершины в графе каждого входного графагя в виде vi,1,vi,2,,vi,n, Создайте соответствующую переменную в экземпляре FLIP-SAT для каждой вершины каждого входного графа. Дополнительно сделайте переменную селектораui для каждого входного номера экземпляра i[t], Для каждого входного графикаGiМы добавим несколько пунктов в формулу. Для каждого края{vi,Икс,vi,Y} графика гядобавить пункт (vя,Иксvя,Y¬Uя) в формулу, которая будет кодировать "либо одна из конечных точек этого ребра установлена ​​в true, либо экземпляр я не активен ". В начальном присваивании все вершинные переменные установлены в false и все переменные селектора Uяустанавливаются в ложь, так что все эти пункты выполняются. Чтобы встроить OR-поведение в композицию, мы расширим формулу, чтобы убедиться, что удовлетворяющее присваивание устанавливает хотя бы один селектор в true, а затем должно также сформировать покрытие вершин выбранного графа.

Чтобы убедиться, что мы можем сделать этот выбор, сохраняя маленькое расстояние переворачивания по сравнению с количеством входов Tмы используем структуру полного бинарного дерева с T листья, которые имеют высоту журналT, Номер листьев от1 в T и связать ялист с переменной Uя это контролирует, если вход яактивен или нет. Создайте новую переменную для каждого внутреннего узла двоичного дерева. Для каждого внутреннего узла пусть его соответствующая переменная будетИкс и переменные его двух детей будут Y а также Z, Добавить пункт(¬ИксYZ) к формуле, которая отражает значение (Икс(YZ)), обеспечивая это Иксможет быть правдой, только если один из его детей правдив. Чтобы завершить формулу, добавьте одноэлементное предложение о том, что переменная корневого узла двоичного дерева должна быть истинной. В начальном назначении истинности значения всех переменных для внутренних узлов устанавливаются в false, что удовлетворяет всем пунктам формулы, за исключением предложения singleton, требующего, чтобы корневой узел дерева имел свою переменную true.

Это завершает описание формулы и присвоения правды. Установите параметрК' задачи ПЕРЕКЛЮЧЕНИЕ ДИСТАНЦИИ, чтобы быть равным (К+журналT+1), который соответствующим образом ограничен для кросс-композиции. Осталось показать, что мы можем перевернутьК' переменные, чтобы сделать формулу истинной, если некоторый входной граф гя имеет размер вершины К,

В обратном направлении предположим, что гя имеет размер-Кпокрытие вершины. УстановитьК переменные, соответствующие Квершины в покрытии к истине, переворачивая их. Установите переменную селектораUя в true, чтобы закодировать этот вход я активируется и переворачивает переменные журналT внутренние двоичные узлы дерева на пути листа яв корень к истине. Нетрудно убедиться, что это удовлетворительное назначение: все значения в двоичном дереве удовлетворены, значение корневого узла установлено в true, пункты, которые проверяют ребрагя' за я'я оставайтесь довольны, потому что Uя' остается ложным, в то время как предложения для графа гя удовлетворены, потому что для каждого ребра мы устанавливаем по крайней мере одну конечную точку в true.

Для прямого направления, предположим, что формула может быть удовлетворена, перевернув самое большее К+журналT+1переменные. Затем мы должны перевернуть переменную корневого узла в true. Последствия в двоичном дереве приводят к тому, что, по крайней мере, одна переменная селектора листа имеет значение true, скажем,Uя, Чтобы удовлетворить последствия, закодированные в двоичном дереве, все внутренние узлы на пути отUя в корне были установлены в true, с учетом 1+журналTпереворачивается. посколькуUя установлен в true, пункты сделаны для графа гя не удовлетворены буквально ¬Uя, поэтому они удовлетворены, потому что одна из конечных точек каждого края гяустановлен в true. Так как по крайней мере1+журналT переменные двоичного дерева были перевернуты, самое большее Кпеременные вершины перевернуты в true в этом решении. Это кодирует покрытие вершины размераК в гяи доказывает, что один из входных данных является экземпляром YES. Это завершает доказательство.

Барт Янсен
источник
1
Эта статья дает более сильные последствия от такого сжатия.
Спасибо!!! (Я сразу удалил «и др.» Из ссылки ;-). Хорошее доказательство (IMO, вы должны опубликовать его в газете).
Марцио Де Биаси