Есть ли какие-либо результаты на двоичном логическом CSP помимо возможности фиксированного параметра почти 2SAT проблемы?

Пусть - формула 2CNF, а k - неотрицательное целое число. В этой статье доказано, что проблема принятия решения о том, можно ли удалить не более k предложений, чтобы сделать φ выполнимой, задается с фиксированным параметром, где k - параметр. Мой вопрос заключается в том, есть ли какие-либо работы, которые обобщают этот результат на другой двоичный логический CSP? (То есть, чтобы решить, можно ли удалить не более k ограничений, чтобы сделать некоторый экземпляр CSP удовлетворительным, параметризованным k ) Или какие-либо отрицательные результаты?$\varphi$$k$$k$$\varphi$$k$$k$$k$

Насколько мне известно, классификация этого варианта CSP широко открыта. Вы можете выразить несколько проблем с фиксированными параметрами в настройке (например, d-Hitting Set примерно соответствует случаю, когда у вас есть положительные предложения размера не более d плюс отрицательные назначения; примерно означает, что проблема CSP является несколько более общей, но легко решаемой вернуться к d-HS или, по крайней мере, взвешенному d-HS). Даже для ограничений, которые можно реализовать с помощью количественно-количественных формул 2-CNF, понятно, в чем сложность. Проблема в том, что при реализации ограничений таким способом, в то время как они являются 2-CNF, вы платите только один, чтобы удалить все это. Следовательно, даже простые ограничения, которые являются просто соединением двух других, могут быть трудными (у меня может быть пример + ссылка позже).