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

Zusammenfassung

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)<log n + 4k - 3 for all n E Z > 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.