The minimum spanning strong subdigraph problem is fixed parameter tractable

A digraph D is strong if it contains a directed path from x to y for every choice of vertices x, y in D. We consider the problem (MSSS) of finding the minimum number of arcs in a spanning strong subdigraph of a strong digraph. It is easy to see that every strong digraph D on n vertices contains a spanning strong subdigraph on at most 2 n - 2 arcs. By reformulating the MSSS problem into the equivalent problem of finding the largest positive integer k ≤ n - 2 so that D contains a spanning strong subdigraph with at most 2 n - 2 - k arcs, we obtain a problem which we prove is fixed parameter tractable. Namely, we prove that there exists an O (f (k) n^c) algorithm for deciding whether a given strong digraph D on n vertices contains a spanning strong subdigraph with at most 2 n - 2 - k arcs. We furthermore prove that if k ≥ 1 and D has no cut vertex then it has a kernel of order at most (2 k - 1)². We finally discuss related problems and conjectures.