{
  "id": "2105.04137",
  "version": "v1",
  "published": "2021-05-10T06:37:38.000Z",
  "updated": "2021-05-10T06:37:38.000Z",
  "title": "On the inversion number of oriented graphs",
  "authors": [
    "Jørgen Bang-Jensen",
    "Jonas Costa Ferreira da Silva",
    "Frédéric Havet"
  ],
  "categories": [
    "math.CO",
    "cs.DM"
  ],
  "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 ${\\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.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2021-05-10T06:37:38.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "oriented graph",
      "inversion number",
      "third inequality satisfies",
      "conjecture",
      "cycle transversal number"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}