🛠

Parameterized Approaches to COMSOC Problems - I

Status
Working
Title
Parameterized Approaches to COMSOC Problems - I
Date
Excerpt
Published
Tags
Feature on homepage
Background
Voting
 
Illustrative Example: Multi-Issue Elections and Lobbying
Voters → Electorate and Alternatives → Issues Preferences → Approval Ballots (accept/reject) an issue Lobbying → Change a few votes to get all issues accepted...
 
📝
and .
🤔
Can we change at most k rows of A such that each column has more 1's than 0's?
Parameter: number of voters
📜
[Christian/Fellows/Rosamond/Slinko, Review of Economic Design 2007]
An easy solution: brute-force
Also ETH-hardness (no algorithm) via a reduction from Vertex Cover
Reduction overview
💡
Based on the incidence matrix of the graph and some dummy entities
Description
Start from an instance of Vertex Cover given by
Begin by setting to the incidence matrix ( columns, rows)
Add dummy rows + columns [total number of rows = ]
Add 1's in the dummy region so that each dummy column has exactly one 1 and each dummy row has exactly one 1.
Set
Schematic - 1
notion image
 
Schematic - 2
notion image
Dummy columns need at least rows to be coverted
Example
notion image
Parameter: size of solution
📜
[Christian/Fellows/Rosamond/Slinko, Review of Economic Design 2007]
An easy solution: brute-force
Also W[2]-hard via a reduction from Dominating Set
💡
Based on the incidence matrix of the graph and some dummy entities
Description
Start from an instance of Dominating Set given by
Start with rows and columns
Add dummy rows (total number of rows = )
A column indexed by a vertex , in the top row positions, has 0’s in those rows that are indexed by vertices .
Set the dummy rows so that the total number of 0’s is one more than the total number of 1’s.
Use the extra column to "force" the solution to avoid dummy rows.
The parameter stays the same
Schematic
notion image
The only zeroes in the column corresponding to are in the rows corresponding to .
Parameter: number of candidates
📜
[Bredereck/Chen/Hartung/Kratsch/Niedermeier/Suchy/Woeginger, JAIR 2014]
ILP-based FPT result for number of candidates
🤔
Desirable: variables
No polynomial kernel with respect to m + k
ILP-based solution
Let be the number of rows of type that are affected. Note that number of types .
Let be the number of rows that ARE type .
Let be the target number of ones needed in column .
Let if and only if row i has a zero in column j
Objective function
notion image
Row constraints
notion image
Column constraints
notion image
Conclusion
FPT follows by Lenstra
[Lenstra, Mathematics of Operations Research, 1983]
Running time:
[Frank and Tardos, Combinatorica, 1987] [Kannan, Mathematics of Operations Research, 1987]
Combinatorial methods? Better running time?