On the minimum number of inversions to make a digraph k-(arc-)strong

EUROCOMB’23

Julien Duron Frédéric Havet Florian Hörsch Clément Rambaud

https://doi.org/10.5817/CZ.MUNI.EUROCOMB23-054

PDF
Abstract
The inversion of a set $X$ of vertices in a digraph $D$ consists of reversing the direction of all arcs of $D\langle X\rangle$. We study $sinv‘_k(D)$ (resp. $sinv_k(D)$) which is the minimum number of inversions needed to transform $D$ into a $k$-arc-strong (resp. $k$-strong) digraph and $sinv‘_k(n) = \max\{sinv‘_k(D) \mid D~\mbox{is a $2k$-edge-connected digraph of order $n$}\}$. We show : (i) $\frac{1}{2} \log (n - k+1) \leq sinv‘_k(n) \leq \log n + 4k -3$ for all $n \in \mathbb{Z}_{\geq 0}$; (ii) for any fixed positive integers $k$ and $t$, deciding whether a given oriented graph $\vec{G}$ satisfies $sinv‘_k(\vec{G}) \leq t$ (resp. $sinv_k(\vec{G}) \leq t$) is NP-complete ; (iii) if $T$ is a tournament of order at least $2k+1$, then $sinv‘_k(T) \leq sinv_k(T) \leq 2k$, and $\frac{1}{2}\log(2k+1) \leq sinv‘_k(T) \leq sinv_k(T)$ for some $T$; (iv) if $T$ is a tournament of order at least $28k-5$ (resp. $14k-3$), then $sinv_k(T) \leq 1$ (resp. $sinv_k(T) \leq 6$); (v) for every $ε>0$, there exists $C$ such that $sinv_k(T) \leq C$ for every tournament $T$ on at least $2k+1 + ε k$ vertices.

Pages:
386–392
References

Nir Ailon, Moses Charikar, and Alantha Newman. Aggregating inconsistent information: Ranking and clustering. Journal of the ACM, 55(5), 2008.
https://doi.org/10.1145/1411509.1411513

Noga Alon. Ranking tournaments. SIAM Journal on Discrete Mathematics, 20:137-142, 2006.
https://doi.org/10.1137/050623905

Noga Alon, Emil Powierski, Michael Savery, Alex Scott, and Elizabeth Wilmer. Invertibility of digraphs and tournaments, 2022.

Guillaume Aubian, Frédéric Havet, Florian Hörsch, Felix Klingelhoefer, Nicolas Nisse, Clément Rambaud, and Quentin Vermande. Problems, proofs, and disproofs on the inversion number, 2022.

Jœrgen Bang-Jensen and Anders Yeo. Making a tournament k-arc-strong by reversing or deorienting arcs. Discrete Applied Mathematics, 136(2):161-171, 2004. The 1st Cologne-Twente Workshop on Graphs and Combinatorial Optimization.
https://doi.org/10.1016/S0166-218X(03)00438-4

Jørgen Bang-Jensen, Jonas Costa Ferreira da Silva, and Frédéric Havet. On the inversion number of oriented graphs. Discrete Mathematics & Theoretical Computer Science, 23(2):# 8, 2022.
https://doi.org/10.46298/dmtcs.7474

Jørgen Bang-Jensen and Gregory Z. Gutin. Digraphs: theory, algorithms and applications. Springer-Verlag, London, 2009.
https://doi.org/10.1007/978-1-84800-998-1

Jørgen Bang-Jensen, Florian Hörsch, and Matthias Kriesell. Complexity of (arc)-connectivity problems involving arc-reversals or deorientations, 2023.
https://doi.org/10.2139/ssrn.4399506

Jørgen Bang-Jensen, Kasper S. Johansen, and Anders Yeo. Making a tournament k-strong. Journal of Graph Theory, 103(1):5-11, 2023.
https://doi.org/10.1002/jgt.22900

Houmem Belkhechine, Moncef Bouaziz, Imed Boudabbous, and Maurice Pouzet. Inversion dans les tournois. Comptes Rendus Mathematique, 348(13-14):703-707, 2010.
https://doi.org/10.1016/j.crma.2010.06.022

Pierre Charbit, Stéphan Thomassé, and Anders Yeo. The minimum feedback arc set problem is NP-hard for tournaments. Combinatorics, Probability and Computing, 16:1-4, 2007.
https://doi.org/10.1017/S0963548306007887

Irit Dinur and Samuel Safra. On the hardness of approximating minimum vertex cover. Annals of Mathematics, Second Series, 162(1):439-485, 2005.
https://doi.org/10.4007/annals.2005.162.439

Olivier Durand de Gevigney. On Frank's conjecture on k-connected orientations. Journal of Combinatorial Theory, Series B, 141:105-114, 2020.
https://doi.org/10.1016/j.jctb.2019.07.001

Julien Duron, Frédéric Havet, Florian Hörsch, and Clément Rambaud. On the minimum number of inversions to make a digraph k-(arc-)-strong, 2023.
https://doi.org/10.5817/CZ.MUNI.EUROCOMB23-054

Frédéric Havet and Stéphan Thomassé. Median orders of tournaments: A tool for the second neighborhood problem and sumner's conjecture. Journal of Graph Theory, 35(4):244-256, 2000.
https://doi.org/10.1002/1097-0118(200012)35:4<244::AID-JGT2>3.0.CO;2-H

ANR Digraph Inversion Working Group. On the diameter of the inversion graph. Unpublished.

Vido Kann. On the Approximability of NP-complete Optimization Problems. PhD thesis, Department of Numerical Analysis and Computing Science, Royal Institute of Technology, Stockholm, 1992.

Richard M. Karp. Reducibility among combinatorial problems. In Complexity of Computer Computations, The IBM Research Symposia Series, pages 85-103. Plenum Press, New York, 1972.
https://doi.org/10.1007/978-1-4684-2001-2_9

Claire Kenyon-Mathieu and Warren Schudy. How to rank with few errors. In Proceedings of the Thirty-Ninth Annual ACM Symposium on Theory of Computing, STOC '07, page 95-103, 2007.
https://doi.org/10.1145/1250790.1250806

Brendan D. McKay. The asymptotic numbers of regular tournaments, eulerian digraphs and eulerian oriented graphs. Combinatorica, 10(4):367-377, 1990.
https://doi.org/10.1007/BF02128671

Crispin St J.A. Nash-Williams. On orientations, connectivity and odd-vertex-pairings in finite graphs. Canadian Journal of Mathematics, 12:555-567, 1960.
https://doi.org/10.4153/CJM-1960-049-6

Herbert E. Robbins. A theorem on graphs, with an application to a problem on traffic control. American Mathematical Monthly, 46(5):281-283, 1939.
https://doi.org/10.2307/2303897

Bhalchandra Thatte, Hamza Si Kaddour, and Maurice Pouzet. On the boolean dimension of a graph and other related parameters. Discrete Mathematics & Theoretical Computer Science, 23, 2022.
https://doi.org/10.46298/dmtcs.7437

Carsten Thomassen. Strongly 2-connected orientations of graphs. Journal of Combinatorial Theory, Series B, 110:67-78, 2015.
https://doi.org/10.1016/j.jctb.2014.07.004

Metrics

0

Views

0

PDF views

Creative Commons License

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Copyright © 2023 Julien Duron, Frédéric Havet, Florian Hörsch, Clément Rambaud

PDF