La complejidad del problema del conjunto dominante en subclases específicas de gráficos cordales

Estoy interesado en la complejidad del problema de conjunto dominante (DSP) en algunas clases de gráficos específicos que son subclases de gráficos cordales .

Un gráfico es un gráfico de ruta no dirigida si es el gráfico de intersección de vértices de una familia de rutas en algún árbol no dirigido. Deje que UP sea la clase de gráficos de ruta no dirigidos.

Un gráfico es un gráfico EPT si es el gráfico de intersección de bordes de una familia de caminos en algún árbol no dirigido. Un gráfico EPT puede no ser cordal, pero permita que CEPT sea la clase de gráficos EPT cordal.

Un gráfico es un gráfico de ruta dirigida (enraizada) si es el gráfico de intersección de vértices de una familia de rutas dirigidas en algún árbol dirigido enraizado (es decir, todos los arcos dirigidos fuera de la raíz). Deje que RDP sea la clase de gráficos de ruta dirigida (enraizada).

Tenemos $RDP\subseteq CEPT \subseteq UP\subseteq chordal$

Se sabe que el DSP es solucionable en tiempo lineal para gráficos en RDP pero NP-completo para gráficos de UP [ Booth y Johnson, 1981 ]

Estoy interesado en gráficos especiales que corresponden a gráficos de intersección de vértices de familias de caminos no dirigidos en árboles con forma de oruga de grado máximo 3. Más precisamente, estas "orugas" se construyen a partir de un camino en el que cada segundo vértice tiene un grado pendiente. un vértice unido a. Llamemos a esta clase cat-UP.

Además, mis gráficos especiales también se pueden construir como gráficos de intersección de bordes de algunas familias de caminos no dirigidos en árboles específicos de grado máximo 3.

Entonces mis preguntas son:

1) ¿Se conoce la complejidad del DSP para gráficos de cat-UP? (tenga en cuenta que la reducción en [ Booth y Johnson, 1981 ] produce un árbol huésped que es de grado máximo 3, pero bastante lejos de una oruga)

2) ¿Cuál es la complejidad de DSP para gráficos de CEPT? ¿Y para los gráficos de CEPT que surgen forman un árbol host de grado máximo 3? ( esto no es conocido por ISGCI )

3) ¿Hay algún resultado complejo para el DSP en una familia de gráficos estrechamente relacionada?

Lástima que hayas esperado tanto tiempo sin obtener ninguna respuesta. No sé para las clases que solicitaste, pero conozco algunas clases gráficas relacionadas y nuevas técnicas que puedes probar.

Primero mencionaré que Steven Chaplick ha trabajado en clases gráficas relacionadas, terminó su tesis a principios de este año, puede encontrar interesante su investigación.

Sé que algunos resultados en esta dirección se derivan de mi propio trabajo Clases de gráficos con vecindarios estructurados y aplicaciones algorítmicas Esto proporciona una técnica general para resolver diversos problemas, incluido DSP en ciertas clases de gráficos. Hacemos esto mediante la introducción de nuevas descomposiciones de gráficos (ver mi tesis ).

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

$0$$k \times n$

La misma técnica podría funcionar para que el CEPT surja de un árbol host de grado máximo 3, pero necesito más tiempo para comprender esta clase. Si tiene un enlace a algunas caracterizaciones de esta clase, eso ayudaría.