# Inversion number of an oriented graph and related parameters

3 COATI - Combinatorics, Optimization and Algorithms for Telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , Laboratoire I3S - COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
Abstract : 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(L → R) = inv(L) + inv(R) where L → R 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.
Keywords :
Document type :
Conference papers

https://hal.inria.fr/hal-03035419
Contributor : Frederic Havet <>
Submitted on : Wednesday, December 2, 2020 - 10:56:03 AM
Last modification on : Thursday, January 21, 2021 - 1:34:13 PM

### File

inversion-ALGOS.pdf
Files produced by the author(s)

### Identifiers

• HAL Id : hal-03035419, version 1

### Citation

Jørgen Bang-Jensen, Jonas Ferreira da Silva, Frédéric Havet. Inversion number of an oriented graph and related parameters. ALGOS 2020 - 1st International Conference on Algebras, Graphs and Ordered Sets, Aug 2020, Nancy / Virtual, France. ⟨hal-03035419⟩

Record views