Hacker News Reader

Comment by DoctorOetker | Hacker News Reader

Your last comment indicates you do understand my question! so I upvote it :)

Not sure what you mean with pl and sng in "you (pl)" and "you (sng)"

Most fantastic would of course be a general method so that given as inputs the transforms between problem types, and the known fixed parameter, and fixed parameter tractable algorithm, gives as output the new fixed parameter, and a new fixed parameter tractable algorithm for the new fixed parameter.

I assume we do not have such a general method, so similarily interesting would be data points for constructing such a method: examples of deducing the fixed parameter for a problem domain, given the fixed parameter (and tractable algorithm) from those of a different problem type.

With enough examples perhaps a general method can be guessed.

View on HN

> Your last comment indicates you do understand my question! so I upvote it :)
OK, cool, thanks!

> Not sure what you mean with pl and sng in "you (pl)" and "you (sng)"*

"Plural" and "Singular" - in English I can't make it clear that in some cases I'm talking about you and previous speakers, and in other cases I'm talking only about you. Other languages make it easier to make the distinction, in English it must be inferred, or made explicit.

> Most fantastic would of course be a general method so that given as inputs the transforms between problem types, and the known fixed parameter, and fixed parameter tractable algorithm, gives as output the new fixed parameter, and a new fixed parameter tractable algorithm for the new fixed parameter.

I feel like that's a lot to ask, but we are beyond my expertise.

> I assume we do not have such a general method ... With enough examples perhaps a general method can be guessed.

I have no intuition about this at all, so I'll stand aside and let others with greater knowledge comment, if they're around.

Okay let (P,k) be a parameterized problem which admits a fixed-parameter algorithm with respect to k. That means you have an algorithm which runs in f(k)n time, where n is the input size and f is a function only depending on k (for example (2^k)*n). Hence, if your real-world instances have always a small k then you can solve arbitrary large instances. Note that one problem can have a lot of different parameters and not all admitting such an algorithm (unless the world is very different than we believe). Now let (P’,h) be another parameterized problem and you have a polynomial time reduction from P’ to P. Then, this reduction gives you a fixed-parameter algorithm for P’ with respect to h if the value of k in the reductions depends only on h and nothing else.

The relevant term might be fpt-reduction.

Also some NP-COMPLETE problems are not fixed parameter tractable as far as we know, but some are.

Reply on news.ycombinator.com