The complexity of deciding whether a graph admits an orientation with fixed weak diameter

Abstract : An oriented graph (G) over right arrow is said weak (resp. strong) if, for every pair {u, v} of vertices of (G) over right arrow, there are directed paths joining u and v in either direction (ree. both directions). In case, for every pair of vertices, some of these directed paths have length at most k, we call (G) over right arrow k-weak (resp. k-strong). We consider several problems asking whether an undirected graph G admits orientations satisfying some connectivity and distance properties. As a main result, we show that deciding whether G admits a k-weak orientation is NP-complete for every k >= 2. This notably implies the NP-completeness of several problems asking whether G is an extremal graph (in terms of needed colours) for some vertex-colouring problems.
Type de document :
Article dans une revue
Liste complète des métadonnées

https://hal-univ-bourgogne.archives-ouvertes.fr/hal-01418678
Contributeur : Le2i - Université de Bourgogne <>
Soumis le : vendredi 16 décembre 2016 - 18:38:46
Dernière modification le : mercredi 12 septembre 2018 - 01:26:06

Identifiants

  • HAL Id : hal-01418678, version 1

Citation

Julien Bensmail, Romaric Duvignau, Sergey Kirgizov. The complexity of deciding whether a graph admits an orientation with fixed weak diameter. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2016, ⟨http://search.proquest.com/openview/004e768569aaed69d1f70edc48b08339/1?pq-origsite=gscholar&cbl=946337⟩. ⟨hal-01418678⟩

Partager

Métriques

Consultations de la notice

167