On the problem of finding disjoint cycles and dicycles in a digraph (Q2428634): Difference between revisions

Given a digraph \(D\), the purpose of the paper is to determine whether or not there exist a cycle \(B\) in \(D\) and a cycle \(C\) in its underlying undirected graph \(UG(D)\) such that \(B\) and \(C\) are vertex-disjoint. It is known that the problem is NP-complete if a vertex \(x\) is required to be in \(C\). In the paper under review it is shown that one can decide the existence of \(B\) and \(C\) in polynomial time if \(D\) is strongly connected. The proposed methods, based on cycle transversal number \(\tau(D)\), actually find \(B\) and \(C\) in polynomial time if they exist. For \(\tau(D)\) more than 2, the paper uses McCuaig's framework on intercyclic digraphs to find these cycles. For \(\tau(D) = 2\) by using topological methods relying on Thomassen's theorem on 2-linkages in acyclic digraphs, the paper can characterize the digraphs for which the answer is ``yes''. For \(\tau(D)\) less than 2, the paper gives another independent algorithm for its solution.