5
$\begingroup$

@user777 suggested the introduction of a tag for parameterized algorithms in a question:

We should have tag about "Parameterized Algorithm" that covers the technique of this subject like: bounded search, kernelization, iterative compression, etc. I found only "Parameterized Complexity" which is another topic in this topic.

Although this is a rather niche topic on CS.SE, I agree that the current tag doesn't cover all questions related to parameterized algorithms.

Therefore, I suggest the creation of the tag to either replace the tag or accompany it.

Please cast your votes on one of the answers below, or create a new answer if your opinion isn't represented in any of the existing answers.

Any further comments or suggestions are welcome.

Some brief stats: there are currently 40 questions with the of which 19 are also tagged as .

$\endgroup$
1
  • 1
    $\begingroup$ Some remarks as to why (I guess) the current tag name was chosen: 1. Historically, parameterized complexity gave rise to the study of parameterized algorithms (you can't even define the notion of parameterized algorithms without the language of parameterized complexity!) 2. This site has more complexity theorists than algorithm designers, so there is a bias towards the complexity perspective. Also, the reason this tag is rather niche here is probably because it is relatively 'new'. New enough to be mostly excluded from bachelor programs, at least. $\endgroup$
    – Discrete lizard Mod
    Jan 22, 2018 at 13:27

5 Answers 5

Reset to default
2
$\begingroup$

No, there's no need for a new tag

We have enough tags already, so there's no need to create one for a niche topic.

[feel free to add additional reasons]

$\endgroup$
1
$\begingroup$

Yes, create the tag

There is a significant number of questions that are tagged that aren't about complexity at all, but are good questions about parameterized algorithms, so we should create a tag to properly represent these questions.

[feel free to add additional reasons]

Don't forget to set the synonym and perhaps .

$\endgroup$
6
  • $\begingroup$ I agree in this opinion. Because "Parameterized complexity" is big topic in its own (e.g. parameterized reduction, W[t]-heirarchy, lower bound of kernelization, etc.) while "Parameterized algorithm" covers the designing and analysing of techniques. $\endgroup$
    – user777
    Jan 22, 2018 at 13:18
  • $\begingroup$ To me, "parameterized algorithm" sounds like a pleonasm. Every meaningful algorithm is parameterized. $\endgroup$
    – Raphael Mod
    Jan 22, 2018 at 19:14
  • $\begingroup$ (Good call on the spelling-fixing synonyms!) $\endgroup$
    – Raphael Mod
    Jan 22, 2018 at 19:18
  • $\begingroup$ @Raphael While I would agree with your statement on philosophical grounds, I disagree on practical grounds: the term 'parameterized algorithms' is a standard term in CS, while 'parameterized analysis' is not. $\endgroup$
    – Discrete lizard Mod
    Jan 22, 2018 at 19:24
  • 2
    $\begingroup$ Hmpf. That's what happens if you let complexity theorists (ab)use terminology. </skip> I for one prefer the tagging system that makes sense to newcomers as well, and that does not reflect views that make me have to answer questions like "why is this algorithm with two parameters "parameterized" but this other one isn't"? (Believe me, people will use the tag for any algorithm that has a parameter.) $\endgroup$
    – Raphael Mod
    Jan 22, 2018 at 20:22
  • $\begingroup$ @Raphael Alright, you have a point. I can see that this tag name would have a decent change to be misused by new users. $\endgroup$
    – Discrete lizard Mod
    Jan 22, 2018 at 20:34
0
$\begingroup$

Create a new tag , but keep

  1. Almost all of the question that are tagged parameterized complexity but not complexity theory are either a) about complexity theory anyway or b) a question about a fixed parameter tractable algorithm

  2. A tag with the same name exists on cstheory.

  3. When thinking about it more thoroughly, I cannot think of a question regarding parameterized algorithms that would neither be related to fixed parameter tractable algorithms or parameterized complexity.

$\endgroup$
7
  • $\begingroup$ Similar criticism: How is an algorithm "tractable"? $\endgroup$
    – Raphael Mod
    Jan 22, 2018 at 20:20
  • $\begingroup$ There is parameterized complexity theory outside of FPT, so there should be questions (out there, maybe not on the site) tagged parameterized-complexity for which fixed-parameter-tractable is not appropriate. $\endgroup$
    – Raphael Mod
    Jan 22, 2018 at 20:21
  • $\begingroup$ @Raphael Yes, but this suggestion would leave parameterized complexity alone, so that wouldn't be a problem. Although, that was my intention. Should I clarify that? $\endgroup$
    – Discrete lizard Mod
    Jan 22, 2018 at 20:24
  • $\begingroup$ @Raphael As for your literary criticism, how is an algorithm "polynomial"? Clearly, we mean an algorithm with polynomial (time) complexity. Similarly, a fixed parameter tractable algorithm is an algorithm for which the complexity is tractable when a certain parameter is fixed. I see no problem here. $\endgroup$
    – Discrete lizard Mod
    Jan 22, 2018 at 20:31
  • $\begingroup$ @Raphael Additionally, even with the addition of 'complexity', I still see nothing wrong with this usage. An FPT algorithm, or perhaps we should say its execution, is 'easily handled or managed' (=tractable according to Merriam Webster) when we fix the parameter, in contrast to e.g. exponential algorithms. I can see that one might relate 'tractable' to the complexity of understanding the algorithm, but this definition is technical enough that I doubt many people would think to know what it means while they actually don't. $\endgroup$
    – Discrete lizard Mod
    Jan 22, 2018 at 20:39
  • $\begingroup$ Yes, your post currently seems to me as if you proposed FPT = PC. $\endgroup$
    – Raphael Mod
    Jan 22, 2018 at 21:13
  • $\begingroup$ Indeed, a "tractable algorithm" is, to me, not the same as "(an efficient) algorithm as witness of the tractability of a problem". $\endgroup$
    – Raphael Mod
    Jan 22, 2018 at 21:14
-1
$\begingroup$

Create a new tag .

When studying "parametrized algorithms", the algorithm indeed remains the same; the way to analyse is changes (we add more parameters to the cost function). Therefore, if we create a new tag, it should reflect that.

$\endgroup$
1
  • $\begingroup$ I don't think we need a new tag, but if we want one then this. $\endgroup$
    – Raphael Mod
    Jan 22, 2018 at 19:16
-3
$\begingroup$

Yes, create , but remove

The tag doesn't represent all tagged questions well, but there is no need for a new tag. We can simply rename the tag into . The questions that are about complexity are already indicated by the tag.

[feel free to add additional reasons]

$\endgroup$
1
  • $\begingroup$ parameterized-algorithms would not represent well questions that are mainly about parameterized complexity of problems but do not deal immediately with algorithms. $\endgroup$
    – Raphael Mod
    Jan 22, 2018 at 19:17

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .