# 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?

-

## 3 Answers

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

-
Isn't a 2-factorization about the edges of a graph and not the vertices? –  Aryabhata Nov 16 '10 at 17:19
2-factorization is partitioning of the (edges of the) graph into 2-factors. –  Yuval Filmus Nov 16 '10 at 17:32
You are correct, I didn't read your answer properly. Is this (existence of 2-factor) valid for directed graphs too? –  Aryabhata Nov 16 '10 at 17:41
In general, k-factors only make sense for undirected graphs (unless $k=2$), so probably not, but it's best to consult Tutte's paper. –  Yuval Filmus Nov 16 '10 at 17:57

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.

-