Problema de decisión de descomposición de Hamilton

Deje ser un gráfico no dirigido. Una descomposición de V en subconjuntos disjuntos V i se llama descomposición de Hamilton de G si el subgrafo inducido por cada conjunto V i es un gráfico de Hamilton o consiste en un solo borde con | V i | = 2 .$G=(V,E)$$V$$V_i$$G$$V_i$$|V_i|=2$

Ejemplo : El gráfico bipartito completo posee una descomposición de Hamilton si y solo si m = n .$K_{m,n}$$m=n$

Estoy buscando un algoritmo que decida si un gráfico dado posee una descomposición de Hamilton. ¿Es este problema de decisión NP-completo? Si no, ¿cómo podemos encontrar tal descomposición?

Nota : En la literatura, una descomposición de Hamilton a menudo denota una descomposición de los bordes de G, de modo que las subgrafías inducidas son Hamilton. Por el contrario, estoy interesado en una descomposición de los vértices.$E$$G$

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