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

Abstract : An oriented graph $\overrightarrow{G}$ is said weak (resp. strong) if, for every pair $\{ u,v \}$ of vertices of $\overrightarrow{G}$, there are directed paths joining $u$ and $v$ in either direction (resp. both directions). In case, for every pair of vertices, some of these directed paths have length at most $k$, we call $\overrightarrow{G}$ $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 \geq 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
Discrete Mathematics and Theoretical Computer Science, DMTCS, 2016, Vol. 17 no. 3 (3), pp.31-42
Liste complète des métadonnées

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

https://hal.inria.fr/hal-00824250
Contributeur : Coordination Episciences Iam <>
Soumis le : mardi 16 août 2016 - 15:49:05
Dernière modification le : mercredi 13 décembre 2017 - 14:20:29

Fichier

2704-9863-1-PB.pdf
Accord explicite pour ce dépôt

Identifiants

  • HAL Id : hal-00824250, version 6

Collections

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, Vol. 17 no. 3 (3), pp.31-42. 〈hal-00824250v6〉

Partager

Métriques

Consultations de la notice

310

Téléchargements de fichiers

80