Ashlesha Hota

Ashlesha Hota, Shashwat Kumar, Daman Deep Singh et al.

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 this, the National Payments Corporation of India (NPCI) has mandated that no single UPI app should exceed 30 percent of total transaction volume. Enforcing this cap, however, poses a significant computational challenge: how to redistribute user transactions across apps without causing widespread user inconvenience while maintaining capacity limits? In this paper, we formalize this problem as the Minimum Edge Activation Flow (MEAF) problem on a bipartite network of users and apps, where activating an edge corresponds to a new app installation. The objective is to ensure a feasible flow respecting app capacities while minimizing additional activations. We further prove that Minimum Edge Activation Flow is NP-Complete. To address the computational challenge, we propose scalable heuristics, named Decoupled Two-Stage Allocation Strategy (DTAS), that exploit flow structure and capacity reuse. Experiments on large semi-synthetic transaction network data show that DTAS finds solutions close to the optimal ILP within seconds, offering a fast and practical way to enforce transaction caps fairly and efficiently.

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, overlooking the role of social influence. However, in reality, individuals are social beings and are often represented as part of a social network, where bribed voters may influence their neighbors, thereby amplifying the effect of persuasion. We study Shift bribery over Networks, where voters are modeled as nodes in a directed weighted graph, and arcs represent social influence between them. In this setting, bribery is not confined to directly targeted voters its effects can propagate through the network, influencing neighbors and amplifying persuasion. Given a budget and individual cost functions for shifting each voter's preference toward a designated candidate, the goal is to determine whether a shift strategy exists within budget that ensures the preferred candidate wins after both direct and network-propagated influence takes effect. We show that the problem is NP-Complete even with two candidates and unit costs, and W[2]-hard when parameterized by budget or maximum degree. On the positive side, we design polynomial-time algorithms for complete graphs under plurality and majority rules and path graphs for uniform edge weights, linear-time algorithms for transitive tournaments for two candidates, linear cost functions and uniform arc weights, and pseudo-polynomial algorithms for cluster graphs. We further prove the existence of fixed-parameter tractable algorithms with treewidth as parameter for two candidates, linear cost functions and uniform arc weights and pseudo-FPT with cluster vertex deletion number for two candidates and uniform arc weights. Together, these results give a detailed complexity landscape for shift bribery in social networks.

Palash Dey, Anubhav Dhar, Ashlesha Hota et al.

In this paper, we study the Maximum Common Vertex Subgraph problem: Given two input graphs $G_1,G_2$ and a non-negative integer $h$, is there a common subgraph $H$ on at least $h$ vertices such that there is no isolated vertex in $H$. In other words, each connected component of $H$ has at least $2$ vertices. This problem naturally arises in graph theory along with other variants of the well-studied Maximum Common Subgraph problem and also has applications in computational social choice. We show that this problem is NP-hard and provide an FPT algorithm when parameterized by $h$. Next, we conduct a study of the problem on common structural parameters like vertex cover number, maximum degree, treedepth, pathwidth and treewidth of one or both input graphs. We derive a complete dichotomy of parameterized results for our problem with respect to individual parameterizations as well as combinations of parameterizations from the above structural parameters. This provides us with a deep insight into the complexity theoretic and parameterized landscape of this problem.