<p>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.</p>

CC BY-SA 3.0
2012-02-28T19:17:27.693Z
2012-02-28T19:17:27.693Z
Markus Bläser
<p>Let $G=(V,E)$ be an undirected graph. A decomposition of $V$ into disjoint subsets $V_i$ is called a <strong>Hamilton decomposition</strong> 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$. </p>

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

<p>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?</p>

<p><strong>Note</strong>: 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.</p>

<cc.complexity-theory><ds.algorithms><graph-theory><np-hardness><hamiltonian-paths>
Hamilton Decomposition Decision Problem
Volker Turau
# Hamilton Decomposition Decision Problem

(Asked by: username_0 on 2012-02-28)

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.

**Tags:** cc.complexity-theory, ds.algorithms, graph-theory, np-hardness, hamiltonian-paths


---

## 1 answers

### Answer by username_1 on 2012-02-28. Score: 17 | Accepted answer

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.


---

