I have seen the parameterization of the very well known problems like vertex cover, hitting set etc which are NP-hard (NP-complete precisely). Many researchers in the past have been studied the parameterization of these problems. My question is why researcher's don't study the parameterizations of the problems unlikely to be NP-Hard?
$\begingroup$
$\endgroup$
2
-
$\begingroup$ Do you mean with the fixed parameter tractability approach? Considering other parameters like the optimal solution size or maximum degree in the running times of algorithms, instead of just the problem size $n$? $\endgroup$– j_random_hackerCommented Jan 9, 2019 at 12:01
-
$\begingroup$ yes fixed parameter tractability approach. $\endgroup$– user94342Commented Jan 9, 2019 at 12:09
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
0
This is not true, there is a program known as "FPT inside P" where we look for interesting parameterizations for problems inside P. The results are perhaps indeed more scattered as opposed to FPT for hard problems which you tend to see much more.
For example, look at the work of Niedermeier and others [1,2] for graph matchings. There is also work for longest path on interval graphs [3]. You will find more by looking at papers that reference the ones mentioned.
$\begingroup$
$\endgroup$
3
Most problems that aren't NP-hard are in P, so they're trivially fixed-parameter tractable.
That only leaves NP-intermediate problems such as graph isomorphism and integer factoring, or the possibility of using tighter notions of FPT, such as fixed-parameter linearity.
answered Jan 9, 2019 at 14:32
-
2$\begingroup$ I thought the OP was looking for cases where the fastest known algorithm is, say, $O(n^2)$, but this drops to $O(kn)$ where $k$ is some parameter like maximum degree of a graph. E.g. the usual algorithm for computing the edit distance between two strings of lengths $n$ and $m$ takes $O(nm)$ time, but there's also an $O(dn)$-time algorithm, where $d$ is that (initially unknown) edit distance. $\endgroup$ Commented Jan 9, 2019 at 20:19
-
2$\begingroup$ @j_random_hacker That's what I meant by "fixed-parameter linearity": the running time for parameter $k$ is $O(f(k)\,n)$ for some function $f$ (the identity function, in your example). $\endgroup$ Commented Jan 9, 2019 at 20:22
-