Hamilton Decomposition Decision Problem

Question

Let $G=(V,E)$ be an undirected graph. A decomposition of $V$ into disjoint subsets $V_i$ is called a Hamilton decomposition of $G$ if the subgraph induced by each set $V_i$ is either a Hamilton graph or consists of a single edge with $|V_i|=2$.

Example: The complete bipartite graph $K_{m,n}$ possesses a Hamilton decomposition if and only if $m=n$.

I am looking for an algorithm that decides whether a given graph possesses a Hamilton decomposition. Is this decision problem NP-complete? If not, how can we find such a decomposition?

Note: In the literature a Hamilton decomposition often denotes a decomposition of the edges $E$ of $G$ such that the induced subgraphs are Hamilton. In contrast I am interested in a decomposition of the vertices.

Answer 1

If we request that each $|V_i| \ge 3$, then this is the 2-factor problem, see the book Combinatorial Optimization by Schrijver. If you allow $|V_i| = 2$, then we can solve this by replacing each undirected edge by two directed ones and compute what is called a cycle-cover. This can be done in polynomial time by reduction to bipartite matching.