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 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.
Type de document :
Article dans une revue
Journal of Graph Theory, Wiley, 2018, 87 (4), pp.536-560. 〈10.1002/jgt.22174〉
Liste complète des métadonnées

Littérature citée [24 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01711403
Contributeur : Frederic Havet <>
Soumis le : samedi 17 février 2018 - 17:51:04
Dernière modification le : vendredi 23 février 2018 - 15:42:02
Document(s) archivé(s) le : lundi 7 mai 2018 - 04:46:53

Fichier

revised1_JGT.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

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〉

Partager

Métriques

Consultations de la notice

88

Téléchargements de fichiers

30