Loading [MathJax]/jax/output/HTML-CSS/jax.js

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 inv(D), is the minimum number of inversions needed to make D acyclic. Denoting by τ(D), τ(D), and ν(D) the cycle transversal number, the cycle arc-transversal number and the cycle packing number of D respectively, one shows that inv(D)τ(D), inv(D)2τ(D) and there exists a function g such that inv(D)g(ν(D)). We conjecture that for any two oriented graphs L and R, inv(LR)=inv(L)+inv(R) where LR is the dijoin of L and R. This would imply that the first two inequalities are tight. We prove this conjecture when inv(L)1 and inv(R)2 and when inv(L)=inv(R)=2 and L and R are strongly connected. We also show that the function g of the third inequality satisfies g(1)4. We then consider the complexity of deciding whether inv(D)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 inv(T)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 5362 times.
    This article's PDF has been downloaded 383 times.