On the inversion number of oriented graphs
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'...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Discrete Mathematics & Theoretical Computer Science
2022-12-01
|
| Series: | Discrete Mathematics & Theoretical Computer Science |
| Subjects: | |
| Online Access: | https://dmtcs.episciences.org/7474/pdf |
| _version_ | 1797270039651418112 |
|---|---|
| author | Jørgen Bang-Jensen Jonas Costa Ferreira da Silva Frédéric Havet |
| author_facet | Jørgen Bang-Jensen Jonas Costa Ferreira da Silva Frédéric Havet |
| author_sort | Jørgen Bang-Jensen |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-03-11T21:32:12Z |
| format | Article |
| id | doaj.art-dbaca9b369f14138ae0a93b3ebda0361 |
| institution | Directory Open Access Journal |
| issn | 1365-8050 |
| language | English |
| last_indexed | 2024-04-25T01:57:56Z |
| publishDate | 2022-12-01 |
| publisher | Discrete Mathematics & Theoretical Computer Science |
| record_format | Article |
| series | Discrete Mathematics & Theoretical Computer Science |
| spelling | doaj.art-dbaca9b369f14138ae0a93b3ebda03612024-03-07T15:44:44ZengDiscrete Mathematics & Theoretical Computer ScienceDiscrete Mathematics & Theoretical Computer Science1365-80502022-12-01vol. 23 no. 2, special issue...Special issues10.46298/dmtcs.74747474On the inversion number of oriented graphsJørgen Bang-JensenJonas Costa Ferreira da SilvaFrédéric HavetLet $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.https://dmtcs.episciences.org/7474/pdfmathematics - combinatoricscomputer science - discrete mathematics |
| spellingShingle | Jørgen Bang-Jensen Jonas Costa Ferreira da Silva Frédéric Havet On the inversion number of oriented graphs Discrete Mathematics & Theoretical Computer Science mathematics - combinatorics computer science - discrete mathematics |
| title | On the inversion number of oriented graphs |
| title_full | On the inversion number of oriented graphs |
| title_fullStr | On the inversion number of oriented graphs |
| title_full_unstemmed | On the inversion number of oriented graphs |
| title_short | On the inversion number of oriented graphs |
| title_sort | on the inversion number of oriented graphs |
| topic | mathematics - combinatorics computer science - discrete mathematics |
| url | https://dmtcs.episciences.org/7474/pdf |
| work_keys_str_mv | AT jørgenbangjensen ontheinversionnumberoforientedgraphs AT jonascostaferreiradasilva ontheinversionnumberoforientedgraphs AT frederichavet ontheinversionnumberoforientedgraphs |