In my opinion, this is actually one of the main questions in parameterized algorithms. There is a number of articles that discuss the "art" of problem parameterization, I list a few of them below.
In a nutshell, an ideal parameter $k$ for a problem should give you two things:
- The problem is fixed-parameter tracable for parameter $k$ with a good running time dependence on $k$. That is, it can be solved in $f(k)\cdot n^{O(1)}$ time for some moderately exponential function $f$.
- The value of $k$ is small in typical instances of this problem.
Most of research in parameterized algorithms focuses on the first issue. The second issue is not really treated in a systematic empirical fashion I'd say. That is, there are no comprehensive studies measuring the value of parameters in real-world instances. What people do to justify the study of particular parameters is to systematically compare parameter values. For example, one may say that a fixed-parameter algorithm for a parameter $k$ is more useful than a fixed-parameter algorithm for parameter $\ell$ if $\ell>k$ in many instances and $\ell\ge k$ in all instances. Using these relations between parameter values one may navigate through parameter space to obtain useful fixed-parameter algorithms.
For example, if you have shown that a graph problem with input graph $G$ is fixed-parameter tractable for the parameter vertex cover number $\mathrm{vc}(G)$ you may want to show that it is fixed-parameter tractable for the parameter feedback vertex set number $\mathrm{fvs}(G)$ because $\mathrm{fvs}(G)\le \mathrm{vc}(G)$ in all graphs. If this is the case, then you may want to show that the problem is fixed-parameter tractable for the treewidth $\mathrm{tw}(G)$ of the graph since $\mathrm{tw}(G)\le \mathrm{fvs}(G)+1$ in all graphs and so on.
Some references:
- Michael R. Fellows, Bart M. P. Jansen, Frances A. Rosamond:
Towards fully multivariate algorithmics: Parameter ecology and the deconstruction of computational complexity. Eur. J. Comb. 34(3): 541-566 (2013)
- Rolf Niedermeier:
Reflections on Multivariate Algorithmics and Problem Parameterization. STACS 2010: 17-32
- Christian Komusiewicz, Rolf Niedermeier:
New Races in Parameterized Algorithmics. MFCS 2012: 19-30