-hierarchy представляет собой иерархию классов полностью в параметризованном сложности, см Сложности Зоопарк определений. Альтернативное определение определяет используя взвешенную определимость для логики первого порядка, см. Учебник Флума и Гроэ .
Для низших классов и W [ 2 ] известно много естественных полных задач, например, Клика и Независимый Набор завершены для W [ 1 ] , а Доминирующий Набор и Набор Ударов завершены для W [ 2 ] , где каждая из этих задач определяется как соответствующая известная N P -полная задача с размером требуемого решения, установленного в качестве параметра.
Существуют ли известные естественные полные проблемы для классов выше в иерархии, в частности для W [ 3 ] и W [ 4 ] ?
cc.complexity-theory
parameterized-complexity
Ян Йоханнсен
источник
источник
Ответы:
Из комментария выше:
ГИПЕРГРАФ- (НЕ) -DOMINATING-SETp является W [3] -полным при fpt-сокращениях:
Гиперграф состоит из множества V вершин и множества Х гиперреберов. Каждый гиперребро как подмножество V . В 3-гиперграфе все ребра имеют размер 3. Если H = ( V , E ) является 3-гиперграфом, то каждый a ∈ V индуцирует граф H a = ( V a , E a ), определяемый как:H=(V,E) V E V H=(V,E) a∈V Ha=(Va,Ea)
и E a = { { u , v } ∣ { a , u , v } ∈ E }Va={v∈V∣v≠a and there is e∈E with a,v∈e} Ea={{u,v}∣{a,u,v}∈E}
Вход : 3-гиперграф , множество M ⊆ V и k ≥ 1 . Параметр : к . Проблема : Решите, существует ли множество D ⊆ V мощности k такое, что:H=(V,E) M⊆V k≥1
k
D⊆V k
см. Йиджи Чен, Йорг Флум и Мартин Гроэ. Анализ W * -иерархии. Журнал символической логики, Vol. 72, № 2 (Jun., 2007), с. 513-534
источник
Я полагаю, что название этой статьи не требует пояснений и отвечает на ваш вопрос: Об охвате продукта в трехуровневых моделях цепочки поставок: естественные полные проблемы для W [3] и W [4]
источник