Discrete Mathematics & Theoretical Computer Science, Vol 17, No 3 (2016)

Font Size:  Small  Medium  Large

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

Julien Bensmail, Romaric Duvignau, Sergey Kirgizov


An oriented graph G is said weak (resp. strong) if, for every pair {u,v} of vertices of 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 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 ≥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.

Full Text: PDF