Arc‐Disjoint Directed and Undirected Cycles in Digraphs |
| |
Authors: | Jørgen Bang‐Jensen Matthias Kriesell Alessandro Maddaloni Sven Simonsen |
| |
Institution: | 1. DEPARTMENT OF MATHEMATICS AND COMPUTER SCIENCE, UNIVERSITY OF SOUTHERN DENMARK, ODENSE M, DENMARKContract grant sponsor: Danish council for independent research;2. contract grant number: 1323‐00178B.;3. INSTITUT FüR MATHEMATIK, TECHNISCHE UNIVERSIT?T ILMENAU, ILMENAU, GERMANY;4. TECIP INSTITUTE SCUOLA SUPERIORE SANT' ANNA, PISA, ITALYContract grant sponsor: Danish council for independent research;5. DEPARTMENT OF MATHEMATICS AND COMPUTER SCIENCE, UNIVERSITY OF SOUTHERN DENMARK, ODENSE M, DENMARK |
| |
Abstract: | The dicycle transversal number of a digraph D is the minimum size of a dicycle transversal of D, that is a set of vertices of D, whose removal from D makes it acyclic. An arc a of a digraph D with at least one cycle is a transversal arc if a is in every directed cycle of D (making acyclic). In 3] and 4], we completely characterized the complexity of following problem: Given a digraph D, decide if there is a dicycle B in D and a cycle C in its underlying undirected graph such that . It turns out that the problem is polynomially solvable for digraphs with a constantly bounded number of transversal vertices (including cases where ). In the remaining case (allowing arbitrarily many transversal vertices) the problem is NP‐complete. In this article, we classify the complexity of the arc‐analog of this problem, where we ask for a dicycle B and a cycle C that are arc‐disjoint, but not necessarily vertex‐disjoint. We prove that the problem is polynomially solvable for strong digraphs and for digraphs with a constantly bounded number of transversal arcs (but possibly an unbounded number of transversal vertices). In the remaining case (allowing arbitrarily many transversal arcs) the problem is NP‐complete. |
| |
Keywords: | cycle dicycle disjoint cycle problem arc‐disjoint cycle problem mixed problem cycle transversal number transversal arc 05c38 05c20 05c85 |
|
|