Finding a subdivision of a prescribed digraph of order 4

DOI10.1002/JGT.22174MaRDI QIDQ4638646zbMATH OpenOpenAlexFDO

Authors Frédéric Havet, A. Karolinna Maia, Bojan Mohar

Publication date 27 April 2018

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

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

zbMATH Keywords

digraphslinkagessubdivisions

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Analysis of algorithms and problem complexity (68Q25)

Abstract: The problem of when a given digraph contains a subdivision of a fixed digraph $F$ is considered. Bang-Jensen et al. laid out foundations for approaching this problem from the algorithmic point of view. In this paper we give further support to several open conjectures and speculations about algorithmic complexity of finding $F$-subdivisions. In particular, up to 5 exceptions, we completely classify for which 4-vertex digraphs $F$, the $F$-subdivision problem is polynomial-time solvable and for which it is NP-complete. While all NP-hardness proofs are made by reduction from some version of the 2-linkage problem in digraphs, some of the polynomial-time solvable cases involve relatively complicated algorithms.

Recommendations

• Finding a subdivision of a digraph
• A note on complete subdivisions in digraphs of large outdegree
• Dichromatic number and forced subdivisions

Cited in

(2)

• Dichromatic number and forced subdivisions
• Finding a subdivision of a digraph

This page was built for publication: Finding a subdivision of a prescribed digraph of order 4

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