6
$\begingroup$

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 3

4

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.

2

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

  • 0
    Isn't a 2-factorization about the edges of a graph and not the vertices?2010-11-16
  • 0
    2-factorization is partitioning of the (edges of the) graph into 2-factors.2010-11-16
  • 0
    You are correct, I didn't read your answer properly. Is this (existence of 2-factor) valid for directed graphs too?2010-11-16
  • 0
    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.2010-11-16
1

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.