Showing 2026Show all
3 papers · 1 filter
cs.DM2026
Structural Parameterizations for Eternal Vertex Cover
Neeldhara Misra, Sebastian Ordyniak, Giacomo Paesani +1
Eternal Vertex Cover (EVC) is a turn-based attacker-defender game on an undirected graph . To begin with, the defender places guards on vertices of . The attacker, on the…
cs.CC2026
Clausal Deletion Backdoors for QBF: a Parameterized Complexity Approach
Leif Eriksson, Victor Lagerkvist, Sebastian Ordyniak +3
Determining the validity of a quantified Boolean formula (QBF) is a PSPACE-complete problem with rich expressive power. Despite interest in efficient solvers, there is, compared to…
cs.DS2026
Backdoors for Quantified Boolean Formulas
Leif Eriksson, Victor Lagerkvist, Sebastian Ordyniak +3
The quantified Boolean formula problem (QBF) is a well-known PSpace-complete problem with rich expressive power, and is generally viewed as the SAT analogue for PSpace. Given that…