Particionar un gráfico en ciclos de nodos separados

Problema relacionado: el teorema de Veblen establece que "un gráfico admite una descomposición del ciclo si y solo si es par". Los ciclos son de borde disjunto, pero no necesariamente de nodo disjunto. Dicho de otra manera, "El conjunto de bordes de un gráfico se puede dividir en ciclos si y solo si cada vértice tiene un grado par".

Mi problema: Me pregunto si alguien ha estudiado la partición de un gráfico en ciclos de nodos separados. Es decir, divida los vértices de un gráfico G en V 1 , V 2 , ⋯ , V k , y cada subgráfico inducido por V i es hamiltoniano.$V$$G$$V_1, V_2, \cdots, V_k$$V_i$

¿Es NP-duro o fácil?

Problema más relacionado: la partición en triángulo es NP-completa. (Página 68 de "Ordenadores e intractabilidad")

Gracias por su consejo de antemano. ^^

Una partición en ciclos vértice-disjuntos es lo mismo que un subgrafo de 2-regular, más comúnmente conocido como factor 2. Se puede encontrar (si existe) en tiempo polinómico mediante un algoritmo basado en la coincidencia. Por ejemplo, vea este enlace .

ETA, noviembre de 2013: según los comentarios a continuación, parece que la reducción de la fuente vinculada anteriormente es incorrecta. Sin embargo, la afirmación de que el problema puede reducirse a una coincidencia perfecta sigue siendo correcta. La reducción correcta está en WT Tutte (1954), "Una breve prueba del teorema del factor para gráficos finitos", Canadian J. Math. 6: 347–352 .

Reemplace cada vértice con grado d por un gráfico bipartito completo G v = K d $v$$d$ , y represente cada bordeuvdel gráfico original por un borde desde un vértice de G u a un vértice de G v (en el lado de la bipartición convérticesd) de tal manera que cada vértice de G v en ese lado de la bipartición tiene exactamente uno de esos incidentes de borde.$G_v=K_{d,\,d-2}$$uv$$G_u$$G_v$$d$$G_v$

Luego, una coincidencia perfecta en el gráfico modificado debe coincidir con los vértices en su lado de la bipartición de G v con d - 2 fuera de los vértices d en el otro lado, dejando exactamente dos vértices libres que deben coincidir con sus vecinos en otros subgrafos G u . De esta manera, las coincidencias perfectas del gráfico modificado corresponden 1 por 1 con las cubiertas del ciclo del gráfico original.$d-2$$G_v$$d-2$$d$$G_u$