The complexity of deciding whether a graph admits an orientation with fixed weak diameter
Julien Bensmail, Romaric Duvignau, Sergey Kirgizov
Abstract
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