The complexity of deciding whether a graph admits an orientation with fixed weak diameter
Résumé
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.