A linguagem definida nos detalhes no NP-C ou P?

Question

Sabe-se que: $$ \ Textrm {clique}={(g, k): \ mbox {g tem um clique de tamanho} k} $$ é $ \ textrm {np-c} $ , mas e se cada vértice tiver 2 vizinhos (conforme definido na $ \ Textrm{2d-clique} $ )? $$ \ Textrm {2d-clique}={(g, k): \ mbox {cada vértice em g tem exatamente $ 2 $ vizinhos e $ g $ tem um clique de tamanho} k}. $$

Answer 1

Supondo que cada vértice de $ g $ tem grau $ 2 $ , sem clique de $ g $ pode ter mais do que $ 3 $ vértices. Em seguida, $ \ textrm {2d-clique} $ é trivialmente na $ \ textrm {p} $ e, Se $ \ TEXTRM {p} \ neq \ textrm {np} $ , não pode ser $ \ TEXTRM {np} $ -complete.

sob a suposição acima (que é trivial para verificar), $ (g, k) \ in \ textrm {2d-clique} $ se um dos seguintes Condições detém:

• $ k= 0 $ , ou
• $ k \ in \ {1,2 \} $ e $ g $ não está vazio , ou
• $ k= 3 $ e $ g $ tem um triângulo, que pode ser verificado em < span class="contêiner matemática"> $ O (n) $ tempo.