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.
Document type :
Journal articles
Complete list of metadatas

Cited literature [10 references]  Display  Hide  Download

https://hal.inria.fr/hal-00824250
Contributor : Coordination Episciences Iam <>
Submitted on : Tuesday, August 16, 2016 - 3:49:05 PM
Last modification on : Wednesday, September 12, 2018 - 1:27:26 AM

File

2704-9863-1-PB.pdf
Explicit agreement for this submission

Identifiers

  • HAL Id : hal-00824250, version 6

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

Share

Metrics

Record views

681

Files downloads

337