6 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…
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…
Faster algorithms for k-Orthogonal Vectors in low dimension
Anita Dürr, Evangelos Kipouridis, Michael Lampis +1
In the Orthogonal Vectors problem (OV), we are given two families of subsets of , each of size , and the task is to decide whether there exists a pair $a…
Satisfactory Budget Division
Laurent Gourvès, Michael Lampis, Nikolaos Melissinos +1
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…
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.…
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…