HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Why researchers don't study the parameterizations of the problems unlikely to be NP-Hard?

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
whythestudyresearchersunlikelyhardparameterizationsproblemsdon

Problem

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?

Solution

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.

[1] Korenwein, Viatcheslav, André Nichterlein, Rolf Niedermeier, and Philipp Zschoche. "Data Reduction for Maximum Matching on Real-World Graphs: Theory and Experiments." In 26th Annual European Symposium on Algorithms (ESA 2018). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2018.

[2] Mertzios, George B., André Nichterlein, and Rolf Niedermeier. "The power of linear-time data reduction for matching." Schloss Dagstuhl–Leibniz-Zentrum für Informatik, 2017.

[3] Giannopoulou, Archontia C., George B. Mertzios, and Rolf Niedermeier. "Polynomial fixed-parameter algorithms: A case study for longest path on interval graphs." Theoretical Computer Science 689 (2017): 67-95.

Context

StackExchange Computer Science Q#102612, answer score: 7

Revisions (0)

No revisions yet.