Paper Info
Title
DAG-width and circumference of digraphs.
Abstract
We prove that every digraph of circumference l has DAG-width at most l. This is best possible and solves a recent conjecture from S. Kintali (ArXiv:1401.2662v1 [math.CO], January 2014).(1) As a consequence of this result we deduce that the k-linkage problem is polynomially solvable for every fixed k in the class of digraphs with bounded circumference. This answers a question posed in J. Bang-Jensen, F. Havet, and A. K. Maia (Theor Comput Sci 562 (2014), 283-303). We also prove that the weak k-linkage problem (where we ask for arc-disjoint paths) is polynomially solvable for every fixed k in the class of digraphs with circumference 2 as well as for digraphs with a bounded number of disjoint cycles each of length at least 3. The case of bounded circumference digraphs is still open. Finally, we prove that the minimum spanning strong subdigraph problem is NP-hard on digraphs of DAG-width at most 5.
Year
DOI
Venue
2015
10.1002/jgt.21894
JOURNAL OF GRAPH THEORY
Keywords
Field
DocType
DAG-width,k-linkage problem,bounded cycle length,polynomial algorithm,cops-and-robbers game
Circumference 2,Discrete mathematics,Circumference,Combinatorics,Disjoint sets,Mathematics,Digraph,Bounded function
Journal
Volume
Issue
ISSN
82.0
2.0
0364-9024
Citations 
PageRank 
References 
0
0.34
10
Authors
2
Name
Order
Citations
PageRank
Jørgen Bang-Jensen192.01
Tilde My Larsen200.34