Xref: utzoo comp.theory:1792 sci.math:16534 Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!zaphod.mps.ohio-state.edu!wuarchive!uunet!mcsun!corton!irisa!jeron From: jeron@irisa.fr (jeron) Newsgroups: comp.theory,sci.math Subject: Some questions about circuits in graphs Message-ID: <1991Apr9.161805.6764@irisa.fr> Date: 9 Apr 91 16:18:05 GMT Sender: news@irisa.fr Organization: IRISA, Rennes (Fr) Lines: 78 I am looking for an algorithm (and not a naive one) of graph theory which deals with circuits in directed graphs. I know a naive algorithm but I am looking for an efficient one but that seems to be more difficult. The question is: Given a directed graph G=(V,E) and a subset W of V, find an algorithm which tells whether every circuit of G contains at least one vertice w in W. Now this problem is equivalent to: Given a directed graph G=(V,E) and a subset W of V, find an algorithm which tells whether every elementary circuit of G contains at least one vertice w in W. I can simplify this problem if I first build the strongly connected components by Tarjan's algorithm. The problem is now: Given a strongly connected directed graph G=(V,E) and a subset W of V, find an algorithm which tells whether every circuit of G contains at least one vertice w in W. I know that a depth first algorithm in which you only detect circuits can perform this. But you can travel some circuits several time. Example: G : 0->1, 0->4 1->2, 1->4 2->3, 2->5 3->6 4->5 5->6, 5->0 6->1 0 The depth first algorithm travels / \ the following tree where (v) means that / \ a loop is detected. / \ 1 4 We can see that there are 9 detected circuits: / \ | 1236 0125 1256 0145 1456 / \ | 045 6123 5612 4561 2 4 5 / | | / \ But there are only 6 different ones: / | | / \ 1236 0125 1256 0145 1456 045 3 5 5 (0) 6 / / \ / \ | / / \ / \ | 6 (0) 6 (0) 6 1 / | | / \ / | | / \ (1) (1) (1) 2 (4) / \ / \ 3 (5) | | (6) Thus I would like to find an algorithm which detects every elementary circuit once and only once. I found no pointer to this in the literature but I think that it is possible. An other interesting question is whether there exists and how can I find a subset S of (elementary) circuits such that every elementary circuit has a vertice in W if and only if every circuit of S has one. In the example above, it is not necessary to test the circuit 0145 if 045 has already been tested: if there is a v in W in 045 then it is also in 0145. If you have any idea about those questions or pointers to articles or books, please contact me by e-mail to: jeron@irisa.irisa.fr ------------------------------------------------------------------------------ Jeron Thierry IRISA Campus de Beaulieu 35000 RENNES, FRANCE e-mail: jeron@irisa.irisa.fr ------------------------------------------------------------------------------