1
$\begingroup$

I am studying parameterized complexity. I have seen few parameterized algorithm for problems like vertex cover, feedback vertex set etc. I have difficulty in determining when a parameter is said to be a " good parameter ". My definition of good parameter is not clear although, but it simply means if I can come up with an FPT algorithm for that problem using that parameter then it will solve some non-trivial set of instances.

For an example: If we talk about the parameterization of some graph problem using independent set (I) and vertex cover (V) and some how we get an FPT algorithm of type $g(k)^{f(I)}\text{Poly}(n)$. Will it a good parameterization of the problem.

Question : When we say a parameter is good for a problem? I can define many parameters for a problem, but the question here is to how to decide it is a good parameter.

Improve this question
$\endgroup$
  • $\begingroup$ I would modify the example above because if $I$ is the maximum independent set of the graph and $V$ is the minum vertex cover, then $V+I=n$ where $n$ is the number of vertices in the graph. Hence, parameterizing by $V$ and $I$ simultaneously is never a good parameterization. $\endgroup$ – Christian Komusiewicz Apr 10 '18 at 7:22
6
$\begingroup$

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:

  1. 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$.
  2. 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
Improve this answer
$\endgroup$
  • 2
    $\begingroup$ While your two guiding points for qualifying a parameterization as «good» are probably the most important ones for applications, there are others that also have strong bearing on research into parameterized problems: namely, (a) does designing a parameterized algorithm for this problem force you to do something new and interesting?, and (b) would such an algorithm have any other cool results as corollaries? $\endgroup$ – daniello Apr 10 '18 at 8:21
  • $\begingroup$ I fully agree with these two additional motivations. My answer considers the narrow viewpoint of studying one specific problem. I would say your motivations are more advanced whereas my answer is more like a rule of thumb for people that start doing research in parameterized algorithms? Is there any literature discussing the points raised by you that I could add to the reference list? $\endgroup$ – Christian Komusiewicz Apr 10 '18 at 8:36
  • $\begingroup$ Thanks for the answer but there may some problems where choice of parameters is not that much natural as problems have in graph theory. On your last paragraph of answer, if parameterization of the problem is not yet known than it may be challenging to find whether FPT algorithm is which is interseting. $\endgroup$ – abaa Apr 10 '18 at 9:17
  • $\begingroup$ @daniello " does designing a parameterized algorithm for this problem force you to do something new and interesting?" I did not get the meaning of interesting. did you mean after designing a fpt algorithm try to design kernel etc or something else. $\endgroup$ – abaa Apr 10 '18 at 9:34
  • $\begingroup$ @abaa Of course the parameter depends on the domain of your inputs. If you are looking at graph problems then there is a vast amount of literature discussing different parameters of graphs but I would argue that every domain has some natural parameters. In string problems, one may consider for example the alphabet size as a parameter. In hypergraph problems, the size of the largest hyperedge is a natural parameter. If you are looking at a particular type of inputs, and you would like to know what natural parameters are for these inputs, then the question needs to be rephrased. $\endgroup$ – Christian Komusiewicz Apr 10 '18 at 9:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.