TY - JOUR

T1 - Arc-disjoint directed and undirected cycles in digraphs

AU - Bang-Jensen, Jørgen

AU - Kriesell, Matthias

AU - Maddaloni, Alessandro

AU - Simonsen, Sven

PY - 2016

Y1 - 2016

N2 - The dicycle transversal number τ(D) 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 D-a 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 UG(D) such that V(B)∩V(C)=Ø. It turns out that the problem is polynomially solvable for digraphs with a constantly bounded number of transversal vertices (including cases where τ(D)≥2). 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.

AB - The dicycle transversal number τ(D) 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 D-a 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 UG(D) such that V(B)∩V(C)=Ø. It turns out that the problem is polynomially solvable for digraphs with a constantly bounded number of transversal vertices (including cases where τ(D)≥2). 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.

KW - arc-disjoint cycle problem

KW - cycle

KW - cycle transversal number

KW - dicycle

KW - disjoint cycle problem

KW - mixed problem

KW - transversal arc

U2 - 10.1002/jgt.22006

DO - 10.1002/jgt.22006

M3 - Journal article

SN - 0364-9024

VL - 83

SP - 406

EP - 420

JO - Journal of Graph Theory

JF - Journal of Graph Theory

IS - 4

ER -