Existence of circuit passing through each vertex in a directed graph 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?
 A: 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

Given a directed graph $G=(V,A)$, can
  the vertices be partitioned into
  disjoint sets $V_1, V_2, \dots, V_k$
  for some $k$, such that each $V_i$
  contains at least three vertices and
  induces a subgraph of $G$ that
  contains a Hamiltonian Circuit.

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: 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).
A: 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.
