Options
A survey on graph problems parameterized above and below guaranteed values
Citation Link: https://doi.org/10.15480/882.15779
Publikationstyp
Review Article
Date Issued
2025-11
Sprache
English
TORE-DOI
Journal
Volume
58
Article Number
100795
Citation
Computer Science Review 58: 100795 (2025)
Publisher Link
Publisher
Elsevier
Peer Reviewed
true
Abstract: We survey the field of algorithms and complexity for graph problems parameterized above or below guaranteed values. Those problems seek, for a given graph G, a solution whose value is at least g(G)+k or at most g(G)−k, where g(G) is a guarantee on the value that any solution on G takes. The goal is to design algorithms which find such solution in time whose complexity in k is decoupled from that in the guarantee, or to rule out the existence of such algorithms by means of intractability results. We discuss a large number of algorithms and intractability results, and complement them by several open problems.
Subjects
Parameterized problems
Graphs
Parametrization above guarantee
Parametrization below guarantee
Fixed parameter tractable
DDC Class
004: Computer Sciences
005: Computer Programming, Programs, Data and Security
510: Mathematics
Publication version
publishedVersion
Loading...
Name
1-s2.0-S1574013725000711-main.pdf
Size
1023.41 KB
Format
Adobe PDF