Gutin, Gregory Z.Gregory Z.GutinMnich, MatthiasMatthiasMnich2025-08-202025-08-202025-11Computer Science Review 58: 100795 (2025)https://hdl.handle.net/11420/57012Abstract: 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.en1876-77452025Elsevierhttps://creativecommons.org/licenses/by/4.0/Parameterized problemsGraphsParametrization above guaranteeParametrization below guaranteeFixed parameter tractableComputer Science, Information and General Works::004: Computer SciencesComputer Science, Information and General Works::005: Computer Programming, Programs, Data and SecurityNatural Sciences and Mathematics::510: MathematicsReview Articlehttps://doi.org/10.15480/882.1577910.1016/j.cosrev.2025.10079510.15480/882.15779Review Article