91 citations · 118 across the 8 of their papers we have counts for
9 papers
An even simpler hard variant of Not-All-Equal 3-SAT
Andreas Darmann, Janosch Döcker, Britta Dorn
We show that Not-All-Equal 3-Sat remains NP-complete when restricted to instances that simultaneously satisfy the following properties: (i) The clauses are given as the disjoint un…
Placing quantified variants of 3-SAT and Not-All-Equal 3-SAT in the polynomial hierarchy
Janosch Döcker, Britta Dorn, Simone Linz +1
The complexity of variants of 3-SAT and Not-All-Equal 3-SAT is well studied. However, in contrast, very little is known about the complexity of the problems' quantified counterpart…
Obtaining a Proportional Allocation by Deleting Items
Britta Dorn, Ronald de Haan, Ildikó Schlotter
We consider the following control problem on fair allocation of indivisible goods. Given a set of items and a set of agents, each having strict linear preference over the items…
On planar variants of the monotone satisfiability problem with bounded variable appearances
Andreas Darmann, Janosch Döcker, Britta Dorn
We show NP-completeness for several planar variants of the monotone satisfiability problem with bounded variable appearances. With one exception the presented variants have an asso…
Often harder than in the Constructive Case: Destructive Bribery in CP-nets
Britta Dorn, Dominikus Krüger, Patrick Scharpfenecker
We study the complexity of the destructive bribery problem---an external agent tries to prevent a disliked candidate from winning by bribery actions---in voting over combinatorial…
On the Hardness of Bribery Variants in Voting with CP-Nets
Britta Dorn, Dominikus Krüger
We continue previous work by Mattei et al. (Mattei, N., Pini, M., Rossi, F., Venable, K.: Bribery in voting with CP-nets. Ann. of Math. and Artif. Intell. pp. 1--26 (2013)) in whic…