The minimum spanning strong subdigraph problem is fixed parameter tractable

A digraph DD is strong if it contains a directed path from xx to yy for every choice of vertices x,yx,y in DD. 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 DD on nn vertices contains a spanning strong subdigraph on at most 2n−22n−2 arcs. By reformulating the MSSS problem into the equivalent problem of finding the largest positive integer k≤n−2k≤n−2 so that DD contains a spanning strong subdigraph with at most 2n−2−k2n−2−k arcs, we obtain a problem which we prove is fixed parameter tractable. Namely, we prove that there exists an O(f(k)nc)O(f(k)nc) algorithm for deciding whether a given strong digraph DD on nn vertices contains a spanning strong subdigraph with at most 2n−2−k2n−2−k arcs.We furthermore prove that if k≥1k≥1 and DD has no cut vertex then it has a kernel of order at most (2k−1)2(2k−1)2. We finally discuss related problems and conjectures.