Are there necessary and sufficient conditions for the existence of a circuit, or a disjoint set of circuits, that passes through each vertex once in a directed graph?
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
According to the classic text, "Computers and Intractability, A Guide to the Theory of NP-Completeness" by Garey and Johnson, the following problem:
Partition into Hamiltonian Subgraphs
is NP-Complete, by a reduction from 3SAT.
The book also mentions that if we allow each $V_i$ to contain at least two vertices, then this is solvable in polynomial time using Matching techniques.
A collection of disjoint cycles that cover all vertices of an (undirected) graph is known as a 2-factor. This paper references some criterion of Tutte for the existence of these, which, paraphrasing the authors, in some sense completely solves the problem. It's Theorem 1 on page 2, which points to "The factors of graphs" by Tutte (1952).
I don't think any are known. A quick search on the web gave a paper by Gutin and Yeo, which also directs to Chapter 1 of Digraphs - Theory, Algorithms, and Applications by Bang-Jensen and Gutin (Springer Monographs, ISBN: 978-1-84800-997-4).
In any case, if there were necessary and sufficient conditions, then taking any graph and replacing each edge by a pair of directed edges going back-and-forth would give you a characterization of Hamiltonian graphs, if I'm not very confused, which is not known.