Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question

3 Answers 3

up vote 4 down vote accepted

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.

share|improve this answer

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.

share|improve this answer

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

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.