Threshold dimension is NP-complete; Extended threshold dimension is NP-hard and co-NP-hard; both, plus ladder/semi-ladder indices, resist |X|^o(1) and FPT o(k) approximation under Gap-ETH.
Tight Hardness Results for Minimizing Discrepancy , booktitle =
1 Pith paper cite this work, alongside 50 external citations. Polarity classification is still indexing.
1
Pith paper citing it
50
external citations · OpenAlex
fields
cs.CC 1years
2026 1verdicts
ACCEPT 1representative citing papers
citing papers explorer
-
On the Computational Complexity of (Extended) Threshold Dimension and (Semi-)Ladder Index
Threshold dimension is NP-complete; Extended threshold dimension is NP-hard and co-NP-hard; both, plus ladder/semi-ladder indices, resist |X|^o(1) and FPT o(k) approximation under Gap-ETH.