5 papers
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…
Circuits and Backdoors: Five Shades of the SETH
Michael Lampis
The Strong Exponential Time Hypothesis (SETH) is a standard assumption in (fine-grained) parameterized complexity and many tight lower bounds are based on it. We consider a number…
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…
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.…
Satisfactory Budget Division
Laurent Gourvès, Laurent Gourvès, Michael Lampis +2
A divisible budget must be allocated to several projects, and agents are asked for their opinion on how much they would give to each project. We consider that an agent is satisfied…