One can consider the parameterized version of these problems, asking for a solution of size \(k\) —they are then denoted by \(k\) -DS, \(k\) -FVS.
A problem parameterized by \(k\)  is fixed parameter tractable (\(\textrm {FPT}\) )
if it admits an algorithm running in time \(O(f(k)n^c)\)  where \(n\)  is the size of the input.
For instance \(k\) -FVS is well-known to be \(\textrm {FPT}\)  for tournaments (see Kumar and Lokshtanov [1]}),
whereas \(k\) -DS is probably not \(\textrm {FPT}\) .
However general tournaments may not be representative of usual instances,
for example, majority voting tournaments involving \(2r+1\)  referees form a very restricted class.
A cornerstone paper by Alon et al. [2]}, based on Vapnik-Cervonenkis dimension,
shows that \(k\) -DS is trivially \(\textrm {FPT}\)  on \((2r+1)\) -majority tournaments because the minimum size of a dominating set is bounded by \(f(r)\) .
This exemplifies how difficult problems can become easy on restricted classes, and, further,
how complexity parameters (here bounded VC-dimension) can help to define classes of tournaments.
