Сложность проблемы доминирующего множества в конкретных подклассах хордовых графов

Меня интересует сложность задачи о доминирующем множестве (DSP) в некоторых конкретных классах графов, которые являются подклассами хордовых графов .

Граф является неориентированным графом путей, если он является графом пересечения вершин семейства путей в некотором неориентированном дереве. Пусть UP будет классом неориентированных графов путей.

Граф - это граф EPT, если он является графом пересечения ребер семейства путей в некотором неориентированном дереве. Граф EPT может не быть хордовым, но пусть CEPT будет классом хордовых графов EPT.

Граф является (корневым) направленным графом путей, если он является графом пересечения вершин семейства направленных путей в некотором корневом ориентированном дереве (т.е. все дуги направлены от корня). Пусть RDP - класс (корневых) ориентированных графов путей.

У нас есть$RDP\subseteq CEPT \subseteq UP\subseteq chordal$

Известно, что DSP является линейно-разрешаемым для графов в RDP, но NP-полным для графов UP [ Booth and Johnson, 1981 ]

Меня интересуют специальные графы, которые соответствуют графам пересечения вершин семейств ненаправленных путей в гусеничных деревьях максимальной степени 3. Точнее, эти «гусеницы» строятся из пути, в котором каждая вторая вершина имеет подвесную степень - одна вершина прикреплена к. Давайте назовем этот класс cat-UP.

Кроме того, мои специальные графы также могут быть построены как графы пересечения ребер некоторых семейств ненаправленных путей в конкретных деревьях максимальной степени 3.

Итак, мои вопросы:

1) Известна ли сложность DSP для графиков cat-UP? (обратите внимание, что сокращение в [ Booth and Johnson, 1981 ] дает дерево хозяев, которое имеет максимальную степень 3, но довольно далеко от гусеницы)

2) Какова сложность DSP для графов CEPT? А для графов CEPT возникающих образуют дерево хостов максимальной степени 3? ( это не известно ISGCI )

3) Есть ли какой-либо результат сложности для DSP в тесно связанном семействе графов?

Жаль, что вы так долго ждали, не получив ответа. Я не знаю для классов, которые вы просили, но я знаю некоторые связанные классы графов и новые методы, которые вы можете попробовать.

Сначала я упомяну, что Стивен Чаплик провел работу над связанными классами графов, он закончил свою диссертацию в начале этого года, его исследование может показаться вам интересным.

Я знаю, что некоторые результаты в этом направлении следуют из моей собственной работы Классы графов со структурированными окрестностями и алгоритмическими приложениями. Это дает общую технику для решения различных задач, включая DSP в определенных классах графов. Мы делаем это путем введения новых разложений графов (см. Мой тезис ).

Например, если нам дана модель пересечения UP, где дерево имеет максимальную степень d, а пути имеют максимальную длину s, мы можем решить доминирующий набор в .$(d-1)^{3(s-1)}poly(n)$

Аналогично, если у нас есть граф с моделью пересечения, состоящей из изгибных путей в сетке (для константы k).$0$$k \times n$

Тот же метод может работать для CEPT, возникающего из дерева хостов максимальной степени 3, но мне нужно больше времени, чтобы понять этот класс. Если у вас есть ссылка на некоторые характеристики этого класса, это поможет.