Finding a subdivision of a prescribed digraph of order 4 - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 2015

Finding a subdivision of a prescribed digraph of order 4

Résumé

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.
Fichier principal
Vignette du fichier
RR-8773.pdf (902.47 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-01202650 , version 1 (21-09-2015)

Identifiants

  • HAL Id : hal-01202650 , version 1

Citer

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⟩
188 Consultations
196 Téléchargements

Partager

Gmail Facebook X LinkedIn More