8 papers
Fair, Efficient and Connected Allocations on Graphs
Susobhan Bandopadhyay, Anish Datta, Palash Dey +2
We study the classical and parameterized complexity of efficient connected allocation problems on graphs, where efficiency is measured by egalitarian and utilitarian welfare maximi…
Fair Distribution of Digital Payments: Balancing Transaction Flows for Regulatory Compliance
Ashlesha Hota, Shashwat Kumar, Daman Deep Singh +3
The concentration of digital payment transactions in just two UPI apps like PhonePe and Google Pay has raised concerns of duopoly in India s digital financial ecosystem. To address…
Shift Bribery over Social Networks
Ashlesha Hota, Susobhan Bandopadhyay, Palash Dey
In shift bribery, a briber seeks to promote his preferred candidate by paying voters to raise their ranking. Classical models of shift bribery assume voters act independently, over…
Parameterized Complexity of Finding a Maximum Common Vertex Subgraph Without Isolated Vertices
Palash Dey, Anubhav Dhar, Ashlesha Hota +2
In this paper, we study the Maximum Common Vertex Subgraph problem: Given two input graphs and a non-negative integer , is there a common subgraph on at least …
Universal Solvability for Robot Motion Planning on Graphs
Anubhav Dhar, Pranav Nyati, Tanishq Prasad +2
We study the Universal Solvability of Robot Motion Planning on Graphs (USolR) problem: given an undirected graph and robots, determine whether any arbitrary config…
Minimizing Envy and Maximizing Happiness in Graphical House Allocation
Anubhav Dhar, Ashlesha Hota, Palash Dey +1
We study the house allocation problem in a setting where agents are connected by a graph representing friendships. In this model, two agents can only envy each other if they are ne…