Author 
Message 
Athanassios Avramidis science forum beginner
Joined: 29 Mar 2006
Posts: 2

Posted: Wed Mar 29, 2006 1:26 am Post subject:
finding maximal directed cycles



We are given a directed graph (V,E), and, by convention, let
any single node induce a directed cycle containing itself.
We want to find a partition of the vertex set V
(ie sets S_1,...S_k such that
\cup_i S_i = V and S_i \cap S_j = \empty whenever i \ne j)
corresponding to maximal independent cycles, i.e:
1. for each i=1,...,k, there exists a directed cycle over
the members of S_i ,
and
2. there exists no directed cycle spanning nodes across more
than one of the S_i
Can anyone point to algorithms and complexity for this?
Neither of the books by
 Aho, Hopcroft and Ulmann
 Bondy and Murty (Graph theory and Applications)
seems to provide an answer.

Thanos Avramidis
Researcher, Dept. of Computer Science & Operations Research,
Pav. Andre Eisenstadt, Room 3357, Univ. of Montreal, Montreal, H3C 3J7,
CANADA
avramidi@iro.umontreal.ca Tel (514)3436111 ext 3511 Fax (514)3435834
http://www.iro.umontreal.ca/~avramidi 

Back to top 


Proginoskes science forum Guru
Joined: 29 Apr 2005
Posts: 2593

Posted: Wed Mar 29, 2006 11:12 pm Post subject:
Re: finding maximal directed cycles



Athanassios Avramidis wrote:
Quote:  We are given a directed graph (V,E), and, by convention, let
any single node induce a directed cycle containing itself.
We want to find a partition of the vertex set V
(ie sets S_1,...S_k such that
\cup_i S_i = V and S_i \cap S_j = \empty whenever i \ne j)
corresponding to maximal independent cycles, i.e:
1. for each i=1,...,k, there exists a directed cycle over
the members of S_i ,
and
2. there exists no directed cycle spanning nodes across more
than one of the S_i
Can anyone point to algorithms and complexity for this?

If k is part of the input, then the problem is NPcomplete, because any
algorithm can solve the directed Hamiltonian cycle problem just by
letting k=1.
There are some digraphs such that no such partition exists. For
instance, if you have a stronglyconnected digraph which is not
(directed) Hamiltonian, you can't have k=1. If k>1, then you should end
up with at least two directed cycles; now choose two vertices (u and
v), one in S_1 and one in S_2. Since the digraph is strongly connected,
there is a directed cycle containing u and v, but this directed cycle
violates condition (2).
So I think you'll end up partitioning the digraph into strongly
connected components, and k will be the number of these. There _is_ an
algorithm for this, which I think runs in linear time (linear in the
number of vertices + number of edges): It's a DFS algorithm.
 Christopher Heckman
P.S. I hope this wasn't homework. 

Back to top 


Athanassios Avramidis science forum beginner
Joined: 29 Mar 2006
Posts: 2

Posted: Sun Apr 02, 2006 3:36 am Post subject:
Re: finding maximal directed cycles



Proginoskes wrote:
Quote:  Athanassios Avramidis wrote:
We are given a directed graph (V,E), and, by convention, let
any single node induce a directed cycle containing itself.
We want to find a partition of the vertex set V
(ie sets S_1,...S_k such that
\cup_i S_i = V and S_i \cap S_j = \empty whenever i \ne j)
corresponding to maximal independent cycles, i.e:
1. for each i=1,...,k, there exists a directed cycle over
the members of S_i ,
and
2. there exists no directed cycle spanning nodes across more
than one of the S_i
Can anyone point to algorithms and complexity for this?
If k is part of the input, then the problem is NPcomplete, because any
algorithm can solve the directed Hamiltonian cycle problem just by
letting k=1.
There are some digraphs such that no such partition exists. For
instance, if you have a stronglyconnected digraph which is not
(directed) Hamiltonian, you can't have k=1. If k>1, then you should end
up with at least two directed cycles; now choose two vertices (u and
v), one in S_1 and one in S_2. Since the digraph is strongly connected,
there is a directed cycle containing u and v, but this directed cycle
violates condition (2).
So I think you'll end up partitioning the digraph into strongly
connected components, and k will be the number of these. There _is_ an
algorithm for this, which I think runs in linear time (linear in the
number of vertices + number of edges): It's a DFS algorithm.
 Christopher Heckman
P.S. I hope this wasn't homework.

After looking at the issue more carefully, I found that what
I meant to ask was "find the strongly connected components of a
digraph", for which problem Aho et al (pp 189195) give an
O(max(#nodes,#edges)) algorithm (probably what you had in mind).
Thanks, that helped! And it was not homework :)

Thanos Avramidis
Researcher, Dept. of Computer Science & Operations Research,
Pav. Andre Eisenstadt, Room 3357, Univ. of Montreal, Montreal, H3C 3J7,
CANADA
avramidi@iro.umontreal.ca Tel (514)3436111 ext 3511 Fax (514)3435834
http://www.iro.umontreal.ca/~avramidi 

Back to top 


Proginoskes science forum Guru
Joined: 29 Apr 2005
Posts: 2593

Posted: Sun Apr 02, 2006 5:59 am Post subject:
Re: finding maximal directed cycles



Athanassios Avramidis wrote:
Quote:  [...]
Thanks, that helped! And it was not homework

I would have found it out wasn't homework, if I had checked your .sig!
8)
 Christopher Heckman


Back to top 


Google


Back to top 



The time now is Fri Nov 17, 2017 10:54 pm  All times are GMT

