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

Description

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-arcstrong (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) ≤ sinv ′ k (n) ≤ log n + 4k-3 ; (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 sinv ′ k (T) ≤ 4 3 k + o(k); (iv) 1 2 log(2k + 1) ≤ sinv ′ k (T) ≤ sinv k (T) for some tournament T of order 2k + 1; (v) if T is a tournament of order at least 19k-2 (resp. 11k-2), then sinv ′ k (T) ≤ sinv k (T) ≤ 1 (resp. sinv k (T) ≤ 3); (vi) for every ϵ > 0, there exists C such that sinv ′ k (T) ≤ sinv k (T) ≤ C for every tournament T on at least 2k + 1 + ϵk vertices.

Abstract

International audience

Additional details