Problemas naturales completos en los niveles superiores de la jerarquía

La jerarquía es una jerarquía de clases de complejidad en complejidad parametrizada, consulte el Zoo de Complejidad para ver las definiciones. Una definición alternativa define usando la definibilidad ponderada de Fagin para las lógica de primer orden, vea el libro de texto de Flum y Grohe .$\mathsf{W}$$\mathsf{W}[t]$$\mathsf{W}[t]$$\Pi_t$

Para las clases más bajas y , se conocen muchos problemas completos naturales, por ejemplo, Clique y Independent Set están completos para , y Dominating Set y El conjunto de golpes está completo para , donde cada uno de estos problemas se define como el correspondiente problema completo conocido de con el tamaño de la solución requerida establecida como parámetro. $\mathsf{W}[1]$$\mathsf{W}[2]$$\mathsf{W}[1]$$\mathsf{W}[2]$$\mathsf{NP}$

¿Existen problemas naturales completos conocidos para las clases superiores en la , en particular para y ?$\mathsf{W}$$\mathsf{W}[3]$$\mathsf{W}[4]$

Del comentario anterior:

-HYPERGRAPH- (NO) -DOMINATING-SET$p$es W [3] -completo bajo fpt-reducciones:

Una hipergrafía consiste en un conjunto V de vértices y un conjunto E de hiperedges. Cada hyperedge es como subconjunto de V . En una hipergrafía 3, todos los bordes tienen un tamaño 3. Si H = ( V , E ) es una hipergrafía 3, cada a ∈ V induce una gráfica H a = ( V a , E a ) dada por:$H = (V,E)$$V$$E$$V$$H = (V,E)$$a \in V$$H^a = (V^a, E^a)$

y E a = { { u , v } ∣ { a , u , v } ∈ E $V^a = \{ v \in V \mid v \neq a \text{ and there is } e \in E \text{ with } a, v \in e \}$$E^a = \{ \{u,v\} \mid \{a,u,v\} \in E \}$

Entrada : A 3-hipergrafía , un conjunto M ⊆ V , y k ≥ 1 . Parámetro : k . Problema : decida si existe un conjunto D ⊆ V de cardinalidad k tal que:$H = (V,E)$$M \subseteq V$$k \geq 1$
$k$
$D \subseteq V$$k$

• si , entonces D es un conjunto dominante de H a ,$a \in M$$D$$H^a$
• si , entonces D no es un conjunto dominante de H a .$a \notin M$$D$$H^a$

ver a Yijia Chen, Jörg Flum y Martin Grohe. Un análisis de la jerarquía W *. El diario de la lógica simbólica, vol. 72, núm. 2 (junio de 2007), págs. 513-534

Creo que el título de este documento se explica por sí mismo y responde a su pregunta: sobre la cobertura de productos en modelos de cadena de suministro de 3 niveles: problemas naturales completos para W [3] y W [4]