Problema de Decisão de Decomposição de Hamilton

Seja um gráfico não direcionado. Uma decomposição de em subconjuntos separados é chamada de decomposição de Hamilton de se o subgráfico induzido por cada conjunto for um gráfico de Hamilton ou consistir em uma única aresta com .$G=(V,E)$$V$$V_i$$G$$V_i$$|V_i|=2$

Exemplo : O gráfico bipartido completo K_ possui uma decomposição de Hamilton se e somente se .$K_{m,n}$$m=n$

Estou procurando um algoritmo que decida se um determinado gráfico possui uma decomposição de Hamilton. Esse problema de decisão é NP-completo? Caso contrário, como podemos encontrar essa decomposição?

Nota : Na literatura, uma decomposição de Hamilton geralmente denota uma decomposição das arestas de modo que os subgráficos induzidos são Hamilton. Por outro lado, estou interessado em uma decomposição dos vértices.$E$$G$

Se solicitarmos que cada , então este é o problema de 2 fatores, consulte o livro Otimização combinatória de Schrijver. Se você permitir$|V_i| \ge 3$$|V_i| = 2$ , podemos resolver isso substituindo cada aresta não direcionada por duas arestas direcionadas e calculando o que é chamado de cobertura de ciclo. Isso pode ser feito em tempo polinomial, reduzindo a correspondência bipartida.