FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups 
 ProfileProfile   PreferencesPreferences   Log in to check your private messagesLog in to check your private messages   Log inLog in 
Forum index » Science and Technology » Math » Combinatorics
finding maximal directed cycles
Post new topic   Reply to topic Page 1 of 1 [4 Posts] View previous topic :: View next topic
Author Message
Athanassios Avramidis
science forum beginner


Joined: 29 Mar 2006
Posts: 2

PostPosted: Wed Mar 29, 2006 1:26 am    Post subject: finding maximal directed cycles Reply with 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?

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)343-6111 ext 3511 Fax (514)343-5834
http://www.iro.umontreal.ca/~avramidi
Back to top
Proginoskes
science forum Guru


Joined: 29 Apr 2005
Posts: 2593

PostPosted: Wed Mar 29, 2006 11:12 pm    Post subject: Re: finding maximal directed cycles Reply with quote

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 NP-complete, 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 strongly-connected 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

PostPosted: Sun Apr 02, 2006 3:36 am    Post subject: Re: finding maximal directed cycles Reply with quote

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 NP-complete, 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 strongly-connected 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 189-195) 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)343-6111 ext 3511 Fax (514)343-5834
http://www.iro.umontreal.ca/~avramidi
Back to top
Proginoskes
science forum Guru


Joined: 29 Apr 2005
Posts: 2593

PostPosted: Sun Apr 02, 2006 5:59 am    Post subject: Re: finding maximal directed cycles Reply with quote

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

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

--- Christopher Heckman

Quote:
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)343-6111 ext 3511 Fax (514)343-5834
http://www.iro.umontreal.ca/~avramidi
Back to top
Google

Back to top
Display posts from previous:   
Post new topic   Reply to topic Page 1 of 1 [4 Posts] View previous topic :: View next topic
The time now is Thu Dec 14, 2017 4:54 pm | All times are GMT
Forum index » Science and Technology » Math » Combinatorics
Jump to:  

Similar Topics
Topic Author Forum Replies Last Post
No new posts Finding a Web Design Development with a Good Results lbardagol@gmail.com Math 0 Mon Jul 17, 2006 10:21 am
No new posts Maximal dimension + subspace of invertible matrices eugene Math 3 Thu Jul 13, 2006 8:04 pm
No new posts Request for help finding a 1/4-32 or 1/4-40 screw, or thr... John2005 Mechanics 3 Sun Jul 02, 2006 2:15 am
No new posts Maximal entropy from Bayes' law? John Baez Research 9 Thu Jun 29, 2006 9:05 pm
No new posts Help Finding Lab Supply: Fussy about Bench Paper Peggy.Dunlop@ec.gc.ca Chem 4 Sun Jun 18, 2006 10:06 pm

Copyright © 2004-2005 DeniX Solutions SRL
Other DeniX Solutions sites: Electronics forum |  Medicine forum |  Unix/Linux blog |  Unix/Linux documentation |  Unix/Linux forums  |  send newsletters
 


Powered by phpBB © 2001, 2005 phpBB Group
[ Time: 0.0964s ][ Queries: 16 (0.0793s) ][ GZIP on - Debug on ]