The Nesting Bird Box Problem is ER-complete.
Smoothing the gap between NP and ER
3 Pith papers cite this work, alongside 11 external citations. Polarity classification is still indexing.
3
Pith papers citing it
11
external citations · OpenAlex
years
2026 3representative citing papers
Defines TLFPT as O(n) + f(k) algorithms, proves it is strictly contained in Linear FPT via diagonalization, and exhibits several problems (SAT, Vertex Cover, k-Path, etc.) that belong to TLFPT under parameters such as treedepth and BFS-width.
citing papers explorer
-
The Nesting Bird Box Problem is ER-complete: Sharp Hardness Results for the Hidden Set Problem
The Nesting Bird Box Problem is ER-complete.
-
$O(n +f(k))$: Truly Linear FPT
Defines TLFPT as O(n) + f(k) algorithms, proves it is strictly contained in Linear FPT via diagonalization, and exhibits several problems (SAT, Vertex Cover, k-Path, etc.) that belong to TLFPT under parameters such as treedepth and BFS-width.
- On Reconstructing a Convex Polygon from Partial Information