research
∙
09/07/2023
Parameterized Aspects of Distinct Kemeny Rank Aggregation
The Kemeny method is one of the popular tools for rank aggregation. Howe...
share
research
∙
08/08/2023
Spartan Bipartite Graphs are Essentially Elementary
We study a two-player game on a graph between an attacker and a defender...
research
∙
07/13/2023
The Price of Equity with Binary Valuations and Few Agent Types
In fair division problems, the notion of price of fairness measures the ...
research
∙
10/05/2022
Romeo and Juliet Meeting in Forest Like Regions
The game of rendezvous with adversaries is a game on a graph played by t...
research
∙
03/28/2022
Chess is hard even for a single player
We introduce a generalization of "Solo Chess", a single-player variant o...
research
∙
01/11/2022
Eternal Vertex Cover on Bipartite and Co-Bipartite Graphs
Eternal Vertex Cover problem is a dynamic variant of the vertex cover pr...
research
∙
11/22/2021
On Fair Division with Binary Valuations Respecting Social Networks
We study the computational complexity of finding fair allocations of ind...
research
∙
01/24/2021
Equitable Division of a Path
We study fair resource allocation under a connectedness constraint where...
research
∙
05/12/2020
Red-Blue Point Separation for Points on a Circle
Given a set R of red points and a set B of blue points in the plane, the...
research
∙
05/07/2020
Imbalance Parameterized by Twin Cover Revisited
We study the problem of Imbalance parameterized by the twin cover of a g...
research
∙
05/06/2020
A Parameterized Perspective on Attacking and Defending Elections
We consider the problem of protecting and manipulating elections by reco...
research
∙
04/29/2020
On the complexity of Winner Verification and Candidate Winner for Multiwinner Voting Rules
The Chamberlin-Courant and Monroe rules are fundamental and well-studied...
research
∙
12/30/2019
Deleting to Structured Trees
We consider a natural variant of the well-known Feedback Vertex Set prob...
research
∙
05/28/2019
A Parameterized Perspective on Protecting Elections
We study the parameterized complexity of the optimal defense and optimal...
research
∙
11/28/2017
On Structural Parameterizations of Firefighting
The Firefighting problem is defined as follows. At time t=0, a fire brea...
research
∙
11/13/2015
On Choosing Committees Based on Approval Votes in the Presence of Outliers
We study the computational complexity of committee selection problem for...
research
∙
09/18/2015
Backdoors into Heterogeneous Classes of SAT and CSP
In this paper we extend the classical notion of strong and weak backdoor...
research
∙
04/30/2015
Manipulation is Harder with Incomplete Votes
The Coalitional Manipulation (CM) problem has been studied extensively i...
research
∙
04/30/2015