首页 | 本学科首页   官方微博 | 高级检索  
     检索      


On the problem of finding disjoint cycles and dicycles in a digraph
Authors:J?rgen Bang-Jensen  Matthias Kriesell
Institution:1. IMADA, University of Southern Denmark, DK-5230, Odense M, Denmark
Abstract: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.
Keywords:
本文献已被 SpringerLink 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号