Parameterization Above Guaranteed Values

You are reading version 1 of this direction, frozen 2026-10-04. The latest version is version 2.

Version 1 of 221 papers46 conceptsfrozen 2026-10-04

In classical complexity theory, many optimization problems are NP-hard, suggesting they are intractable for large inputs. However, many of these problems have "trivial" solutions or guaranteed lower bounds that can be found easily. For instance, in any graph with $m$ edges, a Max-Cut of size at least $m/2$ is guaranteed to exist. The real computational difficulty lies not in finding any solution, but in finding one that is slightly better than what is guaranteed. Parameterization above guaranteed value is a technique in parameterized complexity that measures the difficulty of a problem by the surplus required over these baseline guarantees.

Shifting the Complexity Parameter

Standard parameterized complexity often uses the size of the solution $k$ as the parameter. This is uninformative for problems like Max-Cut or Max-SAT, where $k$ is naturally very large (e.g., half the number of edges or clauses). As noted by Arash Rafiey, Anders Yeo, and Gregory Z. Gutin in The Linear Arrangement Problem Parameterized Above Guaranteed Value, using the difference between the solution cost and a known lower bound allows algorithms to ignore trivial components and focus on the structural features that contribute to the "excess" cost.

This approach transforms the question from "Can we find a solution of size $k$?" to "Can we find a solution of size $L + k$?", where $L$ is the guaranteed minimum. This shift often reveals that problems previously thought to be hard are actually Fixed-Parameter Tractable (FPT) relative to the surplus $k$.

Identifying Tight Lower Bounds

The success of this method depends on identifying a "tight" lower bound—a baseline that is mathematically guaranteed for all instances but cannot be improved without further computation. Stefan Szeider and colleagues demonstrated in Solving MAX-2-SAT Above a Tight Lower Bound that parameterizing by the margin of improvement over such bounds renders constraint satisfaction problems tractable.

Researchers use various structural guarantees as baselines:

Why It Works: Kernelization and Structural Surplus

The intuition behind why these problems become tractable is often rooted in kernelization. When we ask for a solution only slightly better than the guarantee, large portions of the input that satisfy the guarantee "for free" can be reduced or simplified. This leaves behind a small "core" or kernel whose size depends only on the surplus $k$, not the total input size.

For example, in A Fast Algorithm for MaxSAT above Half Number of Clauses, Junqiang Peng and Mingyu Xiao achieved a significant algorithmic breakthrough by targeting the above-guarantee parameter directly, slashing the complexity bounds for instances that are close to the trivial $m/2$ threshold.

Boundaries of Tractability

Not all problems are FPT when parameterized above a guarantee. The choice of the lower bound is critical. As shown by Shaohua Li and Marcin Pilipczuk in Cluster Editing parameterized above the size of a modification-disjoint P3 packing, even if a lower bound is strong, the problem can remain NP-hard (para-NP-hard) if the structural gap between the bound and the optimal solution is too complex to bridge. This highlights that the "above guarantee" framework is not just a tool for solving problems, but a way to map the exact boundary between what is trivial and what is computationally essential.

Papers in this version

History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 17 papers
  2. Version 1 · 2026-10-04 · 21 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_above_guarantee_parameterization_9444af55,
  title = {above-guarantee parameterization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/above-guarantee-parameterization/rdr_9444af555f5c4e1684c29dc04bfa724c},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-21},
}

This exact version (version 1, frozen text):

@misc{lacuna_parameterization_above_guaranteed_values_9444af55_v1,
  title = {Parameterization Above Guaranteed Values},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/parameterization-above-guaranteed-values/rdr_9444af555f5c4e1684c29dc04bfa724c/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-21},
}