Jørgen Bang-Jensen ; Jonas Costa Ferreira da Silva ; Frédéric Havet - On the inversion number of oriented graphs

dmtcs:7474 - Discrete Mathematics & Theoretical Computer Science, December 21, 2022, vol. 23 no. 2, special issue in honour of Maurice Pouzet - https://doi.org/10.46298/dmtcs.7474
On the inversion number of oriented graphsArticle

Authors: Jørgen Bang-Jensen ; Jonas Costa Ferreira da Silva ; Frédéric Havet

    Let $D$ be an oriented graph. The inversion of a set $X$ of vertices in $D$ consists in reversing the direction of all arcs with both ends in $X$. The inversion number of $D$, denoted by ${\rm inv}(D)$, is the minimum number of inversions needed to make $D$ acyclic. Denoting by $\tau(D)$, $\tau' (D)$, and $\nu(D)$ the cycle transversal number, the cycle arc-transversal number and the cycle packing number of $D$ respectively, one shows that ${\rm inv}(D) \leq \tau' (D)$, ${\rm inv}(D) \leq 2\tau(D)$ and there exists a function $g$ such that ${\rm inv}(D)\leq g(\nu(D))$. We conjecture that for any two oriented graphs $L$ and $R$, ${\rm inv}(L\rightarrow R) ={\rm inv}(L) +{\rm inv}(R)$ where $L\rightarrow R$ is the dijoin of $L$ and $R$. This would imply that the first two inequalities are tight. We prove this conjecture when ${\rm inv}(L)\leq 1$ and ${\rm inv}(R)\leq 2$ and when ${\rm inv}(L) ={\rm inv}(R)=2$ and $L$ and $R$ are strongly connected. We also show that the function $g$ of the third inequality satisfies $g(1)\leq 4$. We then consider the complexity of deciding whether ${\rm inv}(D)\leq k$ for a given oriented graph $D$. We show that it is NP-complete for $k=1$, which together with the above conjecture would imply that it is NP-complete for every $k$. This contrasts with a result of Belkhechine et al. which states that deciding whether ${\rm inv}(T)\leq k$ for a given tournament $T$ is polynomial-time solvable.


    Volume: vol. 23 no. 2, special issue in honour of Maurice Pouzet
    Section: Special issues
    Published on: December 21, 2022
    Accepted on: October 30, 2022
    Submitted on: May 11, 2021
    Keywords: Mathematics - Combinatorics,Computer Science - Discrete Mathematics
    Funding:
      Source : OpenAIRE Graph
    • Digraphs; Funder: French National Research Agency (ANR); Code: ANR-19-CE48-0013

    1 Document citing this article

    Consultation statistics

    This page has been seen 5221 times.
    This article's PDF has been downloaded 292 times.