The inversion of a set X of vertices in a digraph D consists of reversing the direction of all arcs of D(X). 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) | D is a 2k-edge-connected digraph of order n}. We show : (i) 1/2 log (n-k+1) o;; (ii) for any fixed positive integers k and t, deciding whether a given oriented graph G satisfies sinv k (G) < t (resp. sinv k (G) < t) is NP-complete ; (iii) if T is a tournament of order at least 2k + 1 , then sinv k (T) < sinv k (T) < 2k, and 1/2 log (2k+1) < sinv k (T) < 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) < 1 (resp. sinv k (T) < 6); (v) for every e > 0, there exists C such that sinv k (T) < C for every tournament T on at least 2k + 1 + Ek vertices.
History
Primary Research Area
Algorithmic Foundations and Cryptography
Name of Conference
European Conference on Combinatorics Graph Theory and Applications (EUROCOMB)
Journal
European Conference on Combinatorics Graph Theory and Applications
Volume
abs/2303.11719
Page Range
386-392
Publisher
Masaryk University Press
Open Access Type
Hybrid
BibTeX
@inproceedings{Duron:Havet:Hörsch:Rambaud:2023,
title = "On the minimum number of inversions to make a digraph k-(arc-)strong",
author = "Duron, Julien" AND "Havet, Frédéric" AND "Hörsch, Florian" AND "Rambaud, Clément",
year = 2023,
month = 8,
journal = "European Conference on Combinatorics Graph Theory and Applications",
number = "12",
pages = "386--392",
publisher = "Masaryk University Press",
issn = "2788-3116",
doi = "10.5817/cz.muni.eurocomb23-054"
}