3 papers
cs.CC2026
d-QBF with Few Existential Variables Revisited
Andreas Grigorjew, Michael Lampis
Quantified Boolean Formula (QBF) is a notoriously hard generalization of \textsc{SAT}, especially from the point of view of parameterized complexity, where the problem remains intr…
cs.DS2025
Structural Parameters for Steiner Orientation
Tesshu Hanaka, Michael Lampis, Nikolaos Melissinos +3
We consider the \textsc{Steiner Orientation} problem, where we are given as input a mixed graph and a set of demand pairs , . The goal is to ori…
cs.GT2024
On the Tractability Landscape of the Conditional Minisum Approval Voting Rule
Georgios Amanatidis, Michael Lampis, Evangelos Markakis +1
This work examines the Conditional Approval Framework for elections involving multiple interdependent issues, specifically focusing on the Conditional Minisum Approval Voting Rule.…