Finding a subdivision of a prescribed digraph of order 4

Frédéric Havet 1 A. Karolinna Maia 2 Bojan Mohar 3
1 COATI - Combinatorics, Optimization and Algorithms for Telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , Laboratoire I3S - COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
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 algorith-mic 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.
Document type :
Journal articles
Complete list of metadatas

Cited literature [12 references]  Display  Hide  Download

https://hal.inria.fr/hal-01711403
Contributor : Frederic Havet <>
Submitted on : Saturday, February 17, 2018 - 5:51:04 PM
Last modification on : Wednesday, June 26, 2019 - 4:28:05 PM
Long-term archiving on : Monday, May 7, 2018 - 4:46:53 AM

File

revised1_JGT.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

Frédéric Havet, A. Karolinna Maia, Bojan Mohar. Finding a subdivision of a prescribed digraph of order 4. Journal of Graph Theory, Wiley, 2018, 87 (4), pp.536-560. ⟨10.1002/jgt.22174⟩. ⟨hal-01711403⟩

Share

Metrics

Record views

363

Files downloads

101