Name
Abstract | ||
|---|---|---|
The dicycle transversal number τ(D) of a digraph D is the minimum size of a dicycle transversal of D, i.e. a set T⊆V(D) such that D−T is acyclic. We study the 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 is known that there is a polynomial time algorithm for this problem when restricted to strongly connected graphs, which actually finds B, C if they exist. We generalize this to any class of digraphs D with either τ(D)≠1 or τ(D)=1 and a bounded number of dicycle transversals, and show that the problem is NP-complete for a special class of digraphs D with τ(D)=1 and, hence, in general. |
Year | DOI | Venue |
|---|---|---|
2014 | 10.1016/j.jctb.2013.10.005 | Journal of Combinatorial Theory, Series B |
Keywords | Field | DocType |
Cycle,Dicycle,Disjoint cycle problem,Mixed problem,Cycle transversal number,Intercyclic digraphs | Discrete mathematics,Combinatorics,Dicycle,Disjoint sets,Vertex (geometry),Transversal (geometry),Time complexity,Strongly connected component,Digraph,Mathematics,Bounded function | Journal |
Volume | ISSN | Citations |
106 | 0095-8956 | 5 |
PageRank | References | Authors |
0.61 | 4 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Jørgen Bang-Jensen | 1 | 573 | 68.96 |
| Matthias Kriesell | 2 | 349 | 43.73 |
| Alessandro Maddaloni | 3 | 10 | 2.09 |
| Sven Simonsen | 4 | 9 | 2.09 |