On the Minimum Number of Inversions to Make a Digraph k‐(Arc‐)Strong

ABSTRACT The inversion of a set of vertices in a digraph consists of reversing the direction of all arcs of . We study (resp., ) which is (for some positive integer ) the minimum number of inversions needed to transform into a ‐arc‐strong (resp., ‐strong) digraph or if no such transformation exists. Note that . We set . We show the following results where is a fixed integer for : for every ; for any fixed positive integer , deciding whether a given oriented graph with satisfies is NP‐complete; for any fixed positive integer , deciding whether a given oriented graph with satisfies is NP‐complete; if is a tournament of order at least , then , and ; for some tournament of order ; if is a tournament of order at least (resp., ), then (resp., ); for every , there exists such that for every positive integer and every tournament on at least vertices, we have .