DAG-width and circumference of digraphs

DOI10.1002/JGT.21894MaRDI QIDQ2811203zbMATH OpenOpenAlexFDO

Authors Tilde My Larsen, Jørgen Bang-Jensen

Publication date 10 June 2016

Published in Journal of Graph Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1502.03241

zbMATH Keywords

\(k\)-linkage problembounded cycle lengthcops-and-robbers gameDAG-widthpolynomial algorithm

Mathematics Subject Classification ID

Distance in graphs (05C12) Directed graphs (digraphs), tournaments (05C20) Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Abstract: We prove that every digraph of circumference $l$ has DAG-width at most $l$ and this is best possible. As a consequence of our 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 cite{bangTCS562}. 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 open. Finally we prove that the minimum spanning strong subdigraph problem is NP-hard on digraphs of DAG-width at most 5.

Recommendations

• Disjoint paths in decomposable digraphs
• The 2-linkage problem for acyclic digraphs
• Arc-disjoint paths in decomposable digraphs
• The directed 2-linkage problem with length constraints
• Directed tree-width

Cites work

• A Polynomial Algorithm for the 2-Path Problem for Semicomplete Digraphs
• Are there any good digraph width measures?
• Digraph measures: Kelly decompositions, games, and orderings
• Digraphs
• Directed tree-width
• Disjoint paths in tournaments
• Finding a subdivision of a digraph
• Graph minors. XIII: The disjoint paths problem
• Graph searching and a min-max theorem for tree-width
• On strongly connected digraphs with bounded cycle length
• The dag-width of directed graphs
• The directed subgraph homeomorphism problem
• Tree-width and circumference of graphs

Cited in

(8)

• On the girth of digraphs
• Digraphs of bounded width
• DAG-width is PSPACE-complete
• The Linkage of a Graph
• Parameterized algorithms for generalizations of directed feedback vertex set
• Hitting long directed cycles is fixed-parameter tractable
• Hunting a rabbit is hard
• Hunting a rabbit: complexity, approximability and some characterizations

This page was built for publication: DAG-width and circumference of digraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2811203)