Bensmail, Julien and Duvignau, Romaric and Kirgizov, Sergey - The complexity of deciding whether a graph admits an orientation with fixed weak diameter

dmtcs:2161 - Discrete Mathematics & Theoretical Computer Science, February 17, 2016, Vol. 17 no. 3
The complexity of deciding whether a graph admits an orientation with fixed weak diameter

Authors: Bensmail, Julien and Duvignau, Romaric and Kirgizov, Sergey

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.


Source : oai:HAL:hal-00824250v6
Volume: Vol. 17 no. 3
Section: Graph Theory
Published on: February 17, 2016
Submitted on: September 18, 2014
Keywords: complexity, weak diameter, strong diameter,oriented graph,[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]


Share

Browsing statistics

This page has been seen 29 times.
This article's PDF has been downloaded 34 times.