A multivariate complexity analysis of lobbying in multiple referenda

R. Bredereck, J. Chen, S. Hartung, S. Kratsch, R. Niedermeier, O. Suchy, G.J. Woeginger

Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademicpeer review

21 Citaten (Scopus)
218 Downloads (Pure)


Assume that each of n voters may or may not approve each of m issues. If an agent (the lobby) may influence up to k voters, then the central question of the NP-hard Lobbying problem is whether the lobby can choose the voters to be influenced so that as a result each issue gets a majority of approvals. This problem can be modeled as a simple matrix modification problem: Can one replace k rows of a binary n x m-matrix by k all-1 rows such that each column in the resulting matrix has a majority of 1s? Significantly extending on previous work that showed parameterized intractability (W[2]-completeness) with respect to the number k of modified rows, we study how natural parameters such as n, m, k, or the "maximum number of 1s missing for any column to have a majority of 1s" (referred to as "gap value g") govern the computational complexity of Lobbying. Among other results, we prove that Lobbying is fixed-parameter tractable for parameter m and provide a greedy logarithmic-factor approximation algorithm which solves Lobbying even optimally if m <5. We also show empirically that this greedy algorithm performs well on general instances. As a further key result, we prove that Lobbying is LOGSNP-complete for constant values g>0, thus providing a first natural complete problem from voting for this complexity class of limited nondeterminism.
Originele taal-2Engels
Pagina's (van-tot)409-446
Aantal pagina's38
TijdschriftJournal of Artificial Intelligence Research
StatusGepubliceerd - 2014


Duik in de onderzoeksthema's van 'A multivariate complexity analysis of lobbying in multiple referenda'. Samen vormen ze een unieke vingerafdruk.

Citeer dit