Julien Bensmail ; Romaric Duvignau ; Sergey Kirgizov - 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 - https://doi.org/10.46298/dmtcs.2161
The complexity of deciding whether a graph admits an orientation with fixed weak diameter

Authors: Julien Bensmail ; Romaric Duvignau ORCID-iD; Sergey Kirgizov

    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.


    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]
    Fundings :
      Source : OpenAIRE Research Graph
    • Graph Theory: Colourings, flows, and decompositions.; Funder: European Commission; Code: 320812

    Share

    Consultation statistics

    This page has been seen 288 times.
    This article's PDF has been downloaded 205 times.