-
Chapter and Conference Paper
Parameterized Aspects of Distinct Kemeny Rank Aggregation
The Kemeny method is one of the popular tools for rank aggregation. However, computing an optimal Kemeny ranking is \(\textsf{NP}\) ...
-
Chapter and Conference Paper
Finding Perfect Matching Cuts Faster
A cut (X, Y) is a perfect matching cut if and only if each vertex in X has exactly one neighbor in Y and each vertex in Y has exactly one neighbor in X. The computational problem of determining if a graph admits ...
-
Chapter and Conference Paper
The Price of Equity with Binary Valuations and Few Agent Types
In fair division problems, the notion of price of fairness measures the loss in welfare due to a fairness constraint. Prior work on the price of fairness has focused primarily on envy-freeness up to one good (...
-
Article
Exact Multi-Covering Problems with Geometric Sets
The b-Exact Multicover problem takes a universe U of n elements, a family F \(\mathcal {F}\)
-
Chapter and Conference Paper
Eternal Vertex Cover on Bipartite Graphs
The Eternal Vertex Cover problem is a dynamic variant of the vertex cover problem. We have a two player game in which guards are placed on some vertices of a graph. In every move, one player (the attacker) attack...
-
Chapter and Conference Paper
On Fair Division with Binary Valuations Respecting Social Networks
We study the computational complexity of finding fair allocations of indivisible goods in the setting where a social network on the agents is given. Notions of fairness in this context are “localized”, that is...
-
Chapter and Conference Paper
Fair Division Is Hard Even for Amicable Agents
We consider the problem of distributing a collection of indivisible objects among agents in a manner that satisfies some desirable notions of fairness and efficiency. We allow agents to “share” goods in order ...
-
Chapter and Conference Paper
On the Parameterized Complexity of Spanning Trees with Small Vertex Covers
We consider the minimum power spanning tree (MPST) problem with general and unit demands from a parameterized perspective. The case of unit demands is equivalent to the problem of finding a spanning tree with ...
-
Chapter and Conference Paper
Imbalance Parameterized by Twin Cover Revisited
We study the problem of Imbalance parameterized by the twin cover of a graph. We show that Imbalance is XP parameterized by twin cover, and FPT when parameterized by the twin cover and the size of the largest cli...
-
Chapter and Conference Paper
A Parameterized Perspective on Attacking and Defending Elections
We consider the problem of protecting and manipulating elections by recounting and changing ballots, respectively. Our setting involves a plurality-based election held across multiple districts, and the probl...
-
Chapter and Conference Paper
Deleting to Structured Trees
We consider a natural variant of the well-known Feedback Vertex Set problem, namely the problem of deleting a small subset of vertices or edges to a full binary tree. This version of the problem is motivated by r...
-
Chapter and Conference Paper
Robustness Radius for Chamberlin-Courant on Restricted Domains
The notion of robustness in the context of committee elections was introduced by Bredereck et al. [SAGT 2018] [2] to capture the impact of small changes in the input preference orders, depending on the voting rul...
-
Chapter and Conference Paper
On the Parameterized Complexity of Edge-Linked Paths
An edge Hamiltonian path of a graph is a permutation of its edge set where every pair of consecutive edges have a vertex in common. Unlike the seemingly related problem of finding an Eulerian walk, the edge Ha...
-
Chapter and Conference Paper
On the Complexity of Optimal Matching Reconfiguration
We consider the problem of matching reconfiguration, where we are given two matchings \(M_s\) and
-
Chapter and Conference Paper
On the Parameterized Complexity of Party Nominations
Consider a fixed voting rule . In the Possible President problem, we are given an election where the candidates are partitioned into parties, an...
-
Chapter and Conference Paper
The Parameterized Complexity of Dominating Set and Friends Revisited for Structured Graphs
We consider variants and generalizations of the dominating set problem on special classes of graphs, specifically, graphs that are a small distance from a tractable class. Here, our focus is mainly on the prob...
-
Article
Parameterized Algorithms for Max Colorable Induced Subgraph Problem on Perfect Graphs
We address the parameterized complexity of Max Colorable Induced Subgraph on perfect graphs. The problem asks for a maximum sized q-colorable induced subgraph of an input graph G. Yannakakis and Gavril (Inf Proce...
-
Chapter and Conference Paper
The Parameterized Complexity of Happy Colorings
Consider a graph \(G = (V,E)\) and a coloring c of vertices with colors from
-
Chapter and Conference Paper
On the Parameterized Complexity of Colorful Components and Related Problems
The colorful components framework is motivated by applications emerging from computational biology. A vertex-colored graph G is said to be colorful if every color appears exactly once. The general goal is to remo...
-
Chapter and Conference Paper
On Structural Parameterizations of Firefighting
The Firefighting problem is defined as follows. At time , a fire breaks out at a vertex of a graph. At each time step ...
