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.
Type de document :
Rapport
[Research Report] RR-8773, INRIA. 2015
Liste complète des métadonnées


https://hal.inria.fr/hal-01202650
Contributeur : Frederic Havet <>
Soumis le : lundi 21 septembre 2015 - 15:06:01
Dernière modification le : vendredi 16 septembre 2016 - 15:13:51
Document(s) archivé(s) le : mardi 29 décembre 2015 - 09:00:14

Fichier

RR-8773.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01202650, version 1

Collections

Citation

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

Partager

Métriques

Consultations de
la notice

169

Téléchargements du document

76