A complexidade do problema do conjunto dominante em subclasses específicas de gráficos de acordes

Estou interessado na complexidade do problema do conjunto dominante (DSP) em algumas classes gráficas específicas que são subclasses de gráficos cordais .

Um gráfico é um gráfico de caminho não direcionado se for o gráfico de interseção de vértices de uma família de caminhos em alguma árvore não direcionada. Seja UP a classe dos gráficos de caminho não direcionado.

Um gráfico é um gráfico EPT se for o gráfico de interseção de arestas de uma família de caminhos em alguma árvore não direcionada. Um gráfico EPT pode não ser cordal, mas permita que a CEPT seja a classe dos gráficos cordiais EPT.

Um gráfico é um gráfico de caminho direcionado (enraizado) se for o gráfico de interseção de vértices de uma família de caminhos direcionados em alguma árvore direcionada enraizada (ou seja, todos os arcos direcionados para longe da raiz). Deixe o RDP ser a classe dos gráficos de caminho direcionado (com raiz).

Temos $RDP\subseteq CEPT \subseteq UP\subseteq chordal$

Sabe-se que o DSP é solucionável em tempo linear para gráficos em RDP, mas NP-completo para gráficos de UP [ Booth e Johnson, 1981 ]

Estou interessado em gráficos especiais que correspondem a gráficos de interseção de vértices de famílias de caminhos não direcionados em árvores de tipo lagarta de grau máximo 3. Mais precisamente, essas "lagartas" são construídas a partir de um caminho no qual cada segundo vértice tem um grau de pendente. um vértice anexado a. Vamos chamar essa classe de cat-UP.

Além disso, meus gráficos especiais também podem ser construídos como gráficos de interseção de arestas de algumas famílias de caminhos não direcionados em árvores específicas de grau máximo 3.

Então, minhas perguntas são:

1) A complexidade do DSP para gráficos de cat-UP é conhecida? (observe que a redução em [ Booth e Johnson, 1981 ] produz uma árvore hospedeira que é de grau máximo 3, mas muito longe de uma lagarta)

2) Qual é a complexidade do DSP para gráficos da CEPT? E para gráficos da CEPT que surgem formam uma árvore hospedeira de grau máximo 3? ( isso não é conhecido pelo ISGCI )

3) Existe algum resultado de complexidade para o DSP em uma família de gráficos intimamente relacionados?

Pena que você está esperando há tanto tempo sem obter qualquer resposta. Não conheço as aulas solicitadas, mas conheço algumas classes de gráficos relacionadas e novas técnicas que você pode experimentar.

Primeiro, mencionarei que Steven Chaplick trabalhou em aulas de gráfico relacionadas; ele terminou sua tese no início deste ano; talvez você ache sua pesquisa interessante.

Sei que alguns resultados nessa direção seguem do meu próprio trabalho Classes de gráfico com vizinhanças estruturadas e aplicações algorítmicas Isso fornece uma técnica geral para resolver vários problemas, incluindo o DSP em determinadas classes de gráfico. Fazemos isso introduzindo novas decomposições de gráficos (veja minha tese ).

$(d-1)^{3(s-1)}poly(n)$

$0$$k \times n$

A mesma técnica pode funcionar para a CEPT resultante de uma árvore hospedeira de grau máximo 3, mas preciso de mais tempo para entender esta classe. Se você tiver um link para algumas caracterizações dessa classe, isso ajudaria.