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, 17 (3), pp.31-42
Liste complète des métadonnées

https://hal.inria.fr/hal-00824250
Contributeur : Coordination Episciences Iam <>
Soumis le : mardi 16 août 2016 - 15:49:05
Dernière modification le : jeudi 18 août 2016 - 11:00:12

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

Partager

Métriques

Consultations de
la notice

181

Téléchargements du document

62