Ist die Sprache in den Details in NP-C oder P definiert?

Question

Es ist bekannt, dass: $$ \ textrm {clique}={(g, k): \ mbox {g hat eine Clique der Größe} k \} $$ ist $ \ textrm {NP-C} $ , aber was ist, wenn jeder Vertex 2 Nachbarn (wie in $ \ textrm definiert ist){2d-Clique} $ )? $$ \ textrm {2d-clique}={(g, k): \ mbox {Jeder Scheitelpunkt in G hat genau 2 $ Nachbarn und $ G $ hat eine Clique of Size} k \}. $$

Answer 1

Angenommen, jeder Scheitelpunkt von $ g $ hat Grad $ 2 $ , keine Clique von $ g $ kann mehr als $ 3 $ -Ger-Scheitelpunkte haben. Dann $ \ textrm {2d-clique} $ ist trivial in $ \ textrm {p} $ und, Wenn $ \ textrm {p} \ neq \ textrm {p} \ neq \ textrm {np} $ , kann es nicht $ \ textrm {NP} $ sein -complete.

unter der obigen Annahme (was trivial zur Überprüfung ist), $ (g, k) \ in \ textrm {2d-clique} $ iFF eines der folgenden Bedingungen hält:

• $ k= 0 $ oder
• $ k \ in \ {1,2 \} $ und $ g $ ist nicht leer oder
• $ k= 3 $ und $ g $ hat ein Dreieck, das in $ o (n) $ Zeit.