caa a22 4500 44535853X CHVBK 20180317142908.0 cr unu---uuuuu 170323e20111201xx s 000 0 eng 10.1007/s00493-011-2670-z doi (NATIONALLICENCE)springer-10.1007/s00493-011-2670-z On the problem of finding disjoint cycles and dicycles in a digraph [Elektronische Daten] [Jørgen Bang-Jensen, Matthias Kriesell] We study the following problem: Given a digraph D, decide if there is a cycle B in D and a cycle C in its underlying undirected graph UG(D) such that V (B)∩V (C)=ø. Whereas the problem is NP-complete if, as additional part of the input, a vertex x is prescribed to be contained in C, we prove that one can decide the existence of B,C in polynomial time under the (mild) additional assumption that D is strongly connected. Our methods actually find B,C in polynomial time if they exist. The behaviour of the problem as well as our solution depend on the cycle transversal number τ (D) of D, i.e. the smallest cardinality of a set T of vertices in D such that D-T is acyclic: If τ (D)≥3 then we employ McCuaig's framework on intercyclic digraphs to (always) find these cycles. If τ (D) = 2 then we can characterize the digraphs for which the answer is "yes” by using topological methods relying on Thomassen's theorem on 2-linkages in acyclic digraphs. For the case τ (D)≤1 we provide an algorithm independent from any earlier work. János Bolyai Mathematical Society and Springer Verlag, 2011 Bang-Jensen Jørgen IMADA, University of Southern Denmark, DK-5230, Odense M, Denmark aut Kriesell Matthias IMADA, University of Southern Denmark, DK-5230, Odense M, Denmark aut Combinatorica Springer-Verlag 31/6(2011-12-01), 639-668 0209-9683 31:6<639 2011 31 493 https://doi.org/10.1007/s00493-011-2670-z text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s00493-011-2670-z text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Bang-Jensen Jørgen IMADA, University of Southern Denmark, DK-5230, Odense M, Denmark aut NATIONALLICENCE 700 1- Kriesell Matthias IMADA, University of Southern Denmark, DK-5230, Odense M, Denmark aut NATIONALLICENCE 773 0- Combinatorica Springer-Verlag 31/6(2011-12-01), 639-668 0209-9683 31:6<639 2011 31 493 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer