Problem decyzyjny rozkładu Hamiltona

Niech będzie wykresem niekierowanym. Rozkładem V na podzbiory rozłączne V i nazywa się Hamilton rozkładu z G jeśli subgraph wywołanych przez każdy zestaw V i jest albo wykres Hamiltona lub składa się z jednej krawędzi z | V i | = 2 .$G=(V,E)$$V$$V_i$$G$$V_i$$|V_i|=2$

Przykład : Pełny dwudzielny wykres ma rozkład Hamiltona wtedy i tylko wtedy, gdy m = n .$K_{m,n}$$m=n$

Szukam algorytmu, który decyduje, czy dany wykres ma rozkład Hamiltona. Czy problem decyzyjny NP jest kompletny? Jeśli nie, to jak możemy znaleźć taki rozkład?

Uwaga : W literaturze często rozkładowi Hamilton oznacza rozkład krawędzie z G taki sposób, że są indukowane subgraphs Hamiltona. Natomiast interesuje mnie rozkład wierzchołków.$E$$G$

$|V_i| \ge 3$$|V_i| = 2$