Skip to Main content Skip to Navigation
New interface
Reports (Research report)

Finding a subdivision of a prescribed digraph of order 4

Abstract : The problem of when a given digraph contains a subdivision of a fixed digraph F is considered. Bang-Jensen et al. [2] 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 NPcomplete. 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.
Document type :
Reports (Research report)
Complete list of metadata

Cited literature [15 references]  Display  Hide  Download
Contributor : Frederic Havet Connect in order to contact the contributor
Submitted on : Monday, September 21, 2015 - 3:06:01 PM
Last modification on : Wednesday, October 26, 2022 - 8:14:15 AM
Long-term archiving on: : Tuesday, December 29, 2015 - 9:00:14 AM


Files produced by the author(s)


  • HAL Id : hal-01202650, version 1



Frédéric Havet, Ana Karolinna Maia de Oliveira, Bojan Mohar. Finding a subdivision of a prescribed digraph of order 4. [Research Report] RR-8773, INRIA. 2015. ⟨hal-01202650⟩



Record views


Files downloads