Name
Abstract | ||
|---|---|---|
The dicycle transversal number t(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) boolean AND V (C) = empty set. It turns out that the problem is polynomially solvable for digraphs with a constantly bounded number of transversal vertices (including cases where tau(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. (C) 2015 Wiley Periodicals, Inc. |
Year | DOI | Venue |
|---|---|---|
2016 | 10.1002/jgt.22006 | JOURNAL OF GRAPH THEORY |
Keywords | DocType | Volume |
cycle,dicycle,disjoint cycle problem,arc-disjoint cycle problem,mixed problem,cycle transversal number,transversal arc | Journal | 83.0 |
Issue | ISSN | Citations |
4.0 | 0364-9024 | 0 |
PageRank | References | Authors |
0.34 | 6 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Jorgen Bang-Jensen | 1 | 132 | 16.95 |
| Matthias Kriesell | 2 | 349 | 43.73 |
| alessandro maddaloni | 3 | 0 | 0.34 |
| Sven Simonsen | 4 | 9 | 2.09 |