17 Result(s)
within
Pallavi Jain
Computer Science
-
Chapter and Conference Paper
Sparsity in Covering Solutions
In the classical covering problems, the goal is to find a subset of vertices/edges that “covers” a specific structure of the graph. In this work, we initiate the study of the covering problems where given a gr...
-
Chapter and Conference Paper
Max-SAT with Cardinality Constraint Parameterized by the Number of Clauses
Max-SAT with cardinality constraint (CC-Max-SAT) is one of the classical NP-complete problems. In this problem, given a CNF-formula $$\varPhi ...
-
Article
Even More Effort Towards Improved Bounds and Fixed-Parameter Tractability for Multiwinner Rules
Multiwinner elections have proven to be a fruitful research topic with many real-world applications. We contribute to this line of research by improving the state of the art regarding the computational complex...
-
Chapter and Conference Paper
More Effort Towards Multiagent Knapsack
In this paper, we study two multiagent variants of the knapsack problem. Fluschnik et al. [AAAI 2019] studied the model in which each agent expresses its preference by assigning a utility to every item. They s...
-
Chapter and Conference Paper
Preserving Consistency for Liquid Knapsack Voting
Liquid Democracy (LD) uses transitive delegations to facilitate joint decision making. In its simplest form, it is used for binary decisions, however its promise holds also for more advanced voting settings. H...
-
Chapter and Conference Paper
Gehrlein Stable Committee with Multi-modal Preferences
Inspired by Gehrlein stability in multiwinner election, in this paper, we define several notions of stability that are applicable in multiwinner elections with multimodal preferences, a model recently proposed...
-
Chapter and Conference Paper
Gerrymandering on Graphs: Computational Complexity and Parameterized Algorithms
This paper studies gerrymandering on graphs from a computational viewpoint (introduced by Cohen-Zemach et al. [AAMAS 2018] and continued by Ito et al. [AAMAS 2019]). Our contributions are two-fold: conceptual and...
-
Chapter and Conference Paper
Parameterized Complexity of d-Hitting Set with Quotas
In this paper we study a variant of the classic d -Hitting Set problem with lower and upper capacity constraints, say A and B, respectively. The input to the problem consists of a universe U, a set family, ...
-
Chapter and Conference Paper
Circumventing Connectivity for Kernelization
Classical vertex subset problems demanding connectivity are of the following form: given an input graph G on n vertices and an integer k, find a set S of at most k vertices that satisfies a property and G[S] is c...
-
Article
Conflict Free Version of Covering Problems on Graphs: Classical and Parameterized
Let π be a family of graphs. In the classical π-Vertex Deletion problem, given a graph G and a positive integer k, the objective is to check whether there exists a subset S of at most k vertices such that G − S i...
-
Article
Parameterized Complexity of Conflict-Free Matchings and Paths
An input to a conflict-free variant of a classical problem \(\Gamma \)Γ, called Conflict-Free\(\Gamma \)Γ, consists of an instance I of \(\Gamma \)Γ coupled with a graph H, called the conflict graph. A solution t...
-
Article
Gehrlein stability in committee selection: parameterized hardness and algorithms
In a multiwinner election based on the Condorcet criterion, we are given a set of candidates, and a set of voters with strict preference rankings over the candidates. A committee is weakly Gehrlein stable (WGS) i...
-
Chapter and Conference Paper
Vertex Deletion on Split Graphs: Beyond 4-Hitting Set
In vertex deletion problems on graphs, the task is to find a set of minimum number of vertices whose deletion results in a graph with some specific property. The class of vertex deletion problems contains seve...
-
Chapter and Conference Paper
Quadratic Vertex Kernel for Split Vertex Deletion
A graph is called a split graph if its vertex set can be partitioned into a clique and an independent set. Split graphs have rich mathematical structure and interesting algorithmic properties making it one of ...
-
Chapter and Conference Paper
Hitting and Covering Partially
d-Hitting Set and d-Set Cover are among the classical NP-hard problems. In this paper, we study variants of d-Hitting Set and d-Set Cover, which are called Partial d -Hitting Set (Partial
-
Chapter and Conference Paper
Conflict Free Version of Covering Problems on Graphs: Classical and Parameterized
Let \(\mathrm{\Pi }\) be a family of graphs. In the classical
-
Chapter and Conference Paper
Mixed Dominating Set: A Parameterized Perspective
In the mixed dominating set (mds) problem, we are given an n-vertex graph G and a positive integer k, and the objective is to decide whether there exists a set
