W [1] -твердые задачи на ограниченных графах степеней

11

Знаете ли вы задачи, которые являются W [1] -твердыми даже для ограниченных графов степеней?

Метрическое измерение сложно на графах со степенью не более 3, но это W [2] -твердый. Красно-синий неблокатор был W [1] -твердым на ограниченных графах степеней, но в доказательстве была ошибка (книга Downey Fellows 2013), и это трудно, только если синие вершины имеют ограниченную степень.

Olf
источник

Ответы:

7

Ball и Trap I остаются -твердыми, когда ограничены бинарными деревьямиW[1]

Теорема 5 гласит:

Теорема 5. Шар и ловушка I остаются -твердыми, ограниченными бинарными деревьями, максимальное количество ловушек на вершину - одна на цвет, и шары не размещаются ни на листьях, ни на родителях листьев.W[1]

Мухаммед Аль-Туркистани
источник
5

Указанные графы и максимальной степени , то -Жесткие , чтобы решить , следует ли содержит подграф , изоморфного параметризованного числа компонента связности . Это теорема N.1 на странице 46 этой работы Даниэля Маркса и Михаила Пилипчука.граммЧАС2W[1]граммЧАСграмм

Раду Куртиканский
источник
Благодаря! Но меня больше интересуют результаты с естественным параметром.
Ольф