¿Se define el idioma en los detalles en NP-C o P?

Question

Se sabe que: $$ \ textrm {clique}=\ \ {(g, k): \ mbox {g tiene una clama de tamaño} k \} $$ es $ \ textrm {np-c} $ , pero ¿qué pasa si cada vértice tiene 2 vecinos (según se define en $ \ textrm{2d-clique} $ )? $$ \ textrm {2d-clique}={(g, k): \ mbox {Cada vértice en G tiene exactamente $ 2 $ vecinos y $ G $ tiene una clama de tamaño} K \}. $$

Answer 1

Suponiendo que cada vértice de $ g $ tiene grado $ 2 $ , no hay clique de $ g $ puede tener más de $ 3 $ vértices. Luego, $ \ textrm {2d-clique} $ es trivialmente en $ \ textrm {p} $ y, Si $ \ textrm {p} \ neq \ textrm {np} $ , no puede ser $ \ textrm {np} $ -clete.

bajo el supuesto anterior (que es trivial para comprobar), $ (g, k) \ in \ textrm {2d-clique} $ iff uno de los siguientes Condiciones Sostiene:

• $ k= 0 $ , o
• $ k \ in \ {1,2 \} $ y $ g $ no está vacío , o
• $ k= 3 $ y $ g $ tiene un triángulo, que se puede registrar < Span Class="Math-contenedor"> $ o (n) $ tiempo.