Знаете ли вы задачи, которые являются W [1] -твердыми даже для ограниченных графов степеней? Метрическое измерение сложно на графах со степенью не более 3, но это W [2] -твердый. Красно-синий неблокатор был W [1] -твердым на ограниченных графах степеней, но в доказательстве была ошибка (книга...
В параметризованной сложности люди используют сокращение с фиксированным параметром (FPT), чтобы доказать W [t] -твердость. Теоретически FPT-редукция не является редукцией за полиномиальное время, поскольку она может экспоненциально выполняться по параметру k. Но на практике все сокращения FPT,...
После эквивалентных вопросов относительно NP-полноты (см. Вопрос о весе и заданный вопрос ) мне стало интересно, как эти атрибуты влияют на параметризованные проблемы. Какие задачи жесткого графа являются -твердыми на ориентированных графах, но фиксированными параметрами, которые можно отследить на...
Параметризованная задача k-FLIP SAT определяется как: Вход: формула 3-CNFφφ\varphi с nnn переменные и присвоение правды σ:[n]→{0,1}σ:[n]→{0,1}\sigma : [n] \to \{0,1\} Параметр: kkk Вопрос: можем ли мы преобразовать заданиеσσ\sigma в удовлетворяющее назначение σ′σ′\sigma' за φφ\varphi перевернуть...
Предположим, что - параметризованный язык относительно некоторого алфавита Σ . К -slice из L является L K = L ∩ { ( х , к ) | х ∈ Е * } , множество экземпляров в L , которые имеют параметр K . Класс сложности X P содержит параметризованные языки L такие, что L k ∈ P для каждого...
Я научный сотрудник, работающий в области теории алгоритмов и сложности, в некоторой степени я использую параметризованную сложность. Мне кажется, что исследователи в параметризованной сложности очень активны (я не имею в виду, что другие не) с точки зрения количества исследовательских работ. Я...
Позволять FFF быть семьей dddподмножества конечной вселенной UUUобъектов. СемьяHHH из kkkподмножества UUU, с 1≤k<d1≤k<d1 \le k < d, это (k,d)(k,d)(k,d)- наезд набора изFFF если для каждого V∈FV∈FV \in F существует хотя бы один набор W∈HW∈HW \in H такой, что W⊂VW⊂VW \subset V, Учитывая...
В предыдущем вопросе « Параметризованный алгоритм поиска бикликов» я поинтересовался, существуют ли быстрые параметризованные алгоритмы для нахождения -биклика в графе вершин, и узнал, что он открыт, если он равен FPT относительно . То же самое верно и для подсчета в -bicliques, или известно , что...