алгоритмы для параметризованных задач, в которых время выполнения полиномиально от входного размера, но произвольно зависит от параметра
В параметризованной сложности, . Предполагается, что каждое из условий является правильным.⊆ W [ 2 ] ⊆ … ⊆ W [ P ]FPT⊆W[1]FPT⊆W[1]\mathsf{FPT} \subseteq \mathsf{W}[1] ⊆W[2]⊆W[2]\subseteq \mathsf{W}[2] ⊆…⊆W[P]⊆…⊆W[P]\subseteq \ldots \subseteq \mathsf{W}[P] Если то .P = W [ P...
Я хотел бы узнать о параметризованной сложности (как на алгоритмической стороне, так и на жесткости). Какие книги / конспекты лекций я могу прочитать на эту...
В настоящее время я делаю обзор литературы по проблеме изоморфизма графов (GI). Я хотел бы знать некоторые открытые вопросы, связанные со следующим Каковы параметры графика, для которых фиксированная возможность отслеживания GI является открытой проблемой. Каковы параметры графа, фиксируя их...
Когда нам дается древовидная декомпозиция графа с шириной w , есть несколько способов сделать его «красивым». В частности, известно, что его можно преобразовать в разложение дерева, где дерево является двоичным, а его высота равна O ( log n ) . Это может быть достигнуто при сохранении ширины...
Проблема цикла заключается в следующем:Кkk Экземпляр: неориентированный граф с n вершинами и до ( nграммGGNnn края.( н2)(n2)n \choose 2 Вопрос: существует ли (правильный) цикл в G ?КkkграммGG Предыстория: для любого фиксированного мы можем решить цикл за времени.2 k O ( n 2 )Кkk2 к2k2kO (...
Учитывая график, , я хочу , чтобы найти оптимальный г -domination для G . То есть, я хочу подмножество S из V таким образом, что все вершины в G находятся на расстоянии не более чем г от некоторой вершины в S , при сведении к минимуму размера S .G=(V,E)G=(V,E)G = (V, E)rrrGGGSSSVVVGGGrrrSSSSSS Из...
Покрытие Vertex может быть легко уменьшено до Независимого набора и наоборот. Однако в контексте параметризованной сложности Независимый набор сложнее, чем Vertex Cover. Ядро с вершин существует для Vertex Cover, но независимое множество W 1 жестких.2k2k2k Как меняется характер Независимого...
Фиксированный параметр и аппроксимация - это совершенно разные подходы для решения сложных задач. У них разная мотивация. Приближение ищет более быстрый результат с приближенным решением. Фиксированный параметр ищет точное решение с временной сложностью в терминах экспоненциальной или некоторой...
В определении (сильной) управляемости с фиксированными параметрами временная граница является выражением вида где входной экземпляр - ( x , k ) с параметром k , p - многочлен, а f - вычислимая функция.е( к ) . р ( | х | ) ,е(К),п(|Икс|),f(k).p(|x|),( х , к )(Икс,К)(x,k)ККkппpееf Можно заменить...
Пусть - формула 2CNF, а k - неотрицательное целое число. В этой статье доказано, что проблема принятия решения о том, можно ли удалить не более k предложений, чтобы сделать φ выполнимой, задается с фиксированным параметром, где k - параметр. Мой вопрос заключается в том, есть ли какие-либо работы,...
В статье Стивена Кука о проблеме P против NP [1] он утверждает следующее [2]: Тезис осуществимости: естественная задача имеет выполнимый алгоритм, если он имеет алгоритм полиномиального времени. У меня вопрос, что именно он (или вообще, на самом деле, что один) подразумевает под « естественной...
Википедия пишет: FPT содержит задачи с фиксированными параметрами, которые можно решить за время для некоторой вычислимой функции . Как правило, эта функция рассматривается как единая экспонента, такая как но определение допускает функции, которые растут еще быстрее. Это важно для большой части...
После эквивалентных вопросов относительно NP-полноты (см. Вопрос о весе и заданный вопрос ) мне стало интересно, как эти атрибуты влияют на параметризованные проблемы. Какие задачи жесткого графа являются -твердыми на ориентированных графах, но фиксированными параметрами, которые можно отследить на...
Гипотеза Бермана – Хартманиса: все NP-полные языки выглядят одинаково в том смысле, что они могут быть связаны друг с другом полиномиальными изоморфизмами времени [1]. Меня интересует более мелкозернистая версия «полиномиального времени», то есть, если мы используем параметризованные сокращения....
Параметризованная задача k-FLIP SAT определяется как: Вход: формула 3-CNFφφ\varphi с nnn переменные и присвоение правды σ:[n]→{0,1}σ:[n]→{0,1}\sigma : [n] \to \{0,1\} Параметр: kkk Вопрос: можем ли мы преобразовать заданиеσσ\sigma в удовлетворяющее назначение σ′σ′\sigma' за φφ\varphi перевернуть...