Author name cluster

Sanjukta Roy

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

15 papers

1 author row

TCS Journal 2026 Journal Article

Exact and Parameterized Algorithms for Window Width Minimization in Bipartite Arrangement

Shashank Chauhan
Tanmay Inamdar
Lawqueen Kanesh
Sanjukta Roy

We study 2-layer Window Width Minimization in Bipartite arrangements, where given a bipartite arrangement G with bipartition A⊎B, and fixed and distinct integer positions for vertices in A, the goal is to determine distinct integer positions for vertices in B such that the window width parameter b is minimized. The window width b ensures that each vertex v ∈ B maintains a horizontal distance at most b from its neighbors in A and from its sibling vertices in B that share a common neighbor in A. In this paper, we design two exact exponential algorithms for Window Width Minimization: (1) an O * ( 4. 36 n · 2 p + n + b ) time and polynomial space algorithm and (2) O * ( 4. 899 n ) time and O * ( 2 n ) space algorithm, where | A | = p, | B | = n. We also initiate the study of the problem from the perspective of parameterized complexity and design a fixed-parameter tractable algorithm parameterized by the window size, which stands in stark contrast with the closely related Bandwidth Minimization problem. Specifically, our algorithm runs in O * ( b O ( b ) ) time and space, either finds an ordering of children with window width b, or correctly determines that no such ordering exists.

Details DOI

AAAI Conference 2026 Conference Paper

Fair Societies: Algorithms for House Allocations

Hadi Hosseini
Sanjukta Roy
Aditi Sethia

House allocations concern with matchings involving one-sided preferences, where houses serve as a proxy encoding valuable indivisible resources (e.g. organs, course seats, subsidized public housing units) to be allocated among the agents. Every agent must receive exactly one resource. We study algorithmic approaches towards ensuring fairness in such settings. Minimizing the number of envious agents is known to be computationally hard. We present two tractable approaches to deal with the hardness. When the agents are presented with an initial allocation of houses, we aim to refine this allocation by reallocating a bounded number of houses to reduce the number of envious agents. We show an efficient algorithm when the agents express preference for a bounded number of houses and houses are accepted by a bounded number of agents. Next, we consider single peaked preference domain and present a polynomial time algorithm for finding an allocation that minimize the number of envious agents. We further extend it to satisfy Pareto efficiency. Our former algorithm works for other measures of envy such as total envy, or maximum envy, with suitable modifications. Finally, we present an empirical analysis recording the fairness-welfare trade-off of our algorithms.

PDF Details DOI

AAAI Conference 2025 Conference Paper

Eliminating Majority Illusion Is Easy

Jack Dippel
Max Dupré la Tour
April Niu
Sanjukta Roy
Adrian Vetta

Majority illusion is a phenomenon in social networks wherein the decision by the majority of the network is not the same as one's personal social circle's majority, leading to an incorrect perception of the majority in a large network. We present polynomial-time algorithms which completely eliminate majority illusion by altering as few connections in the network as possible. Eliminating majority illusion ensures each neighbourhood in the network has at least a 1/2-fraction of the majority winner. This result is surprising as partially eliminating majority illusion is NP-hard. We generalize the majority illusion problem to an arbitrary fraction p and show that the problem of ensuring all neighbourhoods in the network contain at least a p-fraction of nodes consistent with a given preference is NP-hard, for nearly all values of p.

PDF Details DOI

AAAI Conference 2025 Conference Paper

Strategyproof Matching of Roommates and Rooms

Hadi Hosseini
Shivika Narang
Sanjukta Roy

We initiate the study of matching roommates and rooms wherein the preferences of agents over other agents and rooms are complementary and represented by Leontief utilities. In this setting, 2n agents must be paired up and assigned to n rooms. Each agent has cardinal valuations over the rooms as well as compatibility values over all other agents. Under Leontief preferences, an agent’s utility for a matching is the minimum of the two values. We focus on the tradeoff between maximizing utilitarian social welfare and strategyproofness. Our main result shows that—in a stark contrast to the additive case— under binary Leontief utilities, there exist strategyproof mechanisms that maximize the social welfare. We further devise a strategyproof mechanism that implements such a welfare maximizing algorithm and is parameterized by the number of agents. Along the way, we highlight several possibility and impossibility results, and give upper bounds and lower bounds for welfare with or without strategyproofness.

PDF Details DOI

AAMAS Conference 2024 Conference Paper

Gerrymandering Planar Graphs

Jack Dippel
Max Dupré la Tour
April Niu
Sanjukta Roy
Adrian Vetta

We study the computational complexity of the map redistricting problem (gerrymandering). Mathematically, the electoral district designer (gerrymanderer) attempts to partition a weighted graph into 𝑘 connected components (districts) such that its candidate (party) wins as many districts as possible. Prior work has principally concerned the special cases where the graph is a path or a tree. Our focus concerns the realistic case where the graph is planar. We prove that the gerrymandering problem is solvable in polynomial time in 𝜆-outerplanar graphs, when the number of candidates and 𝜆 are constants and the vertex weights (voting weights) are polynomially bounded. In contrast, the problem is NP-complete in general planar graphs even with just two candidates. This motivates the study of approximation algorithms for gerrymandering planar graphs. However, when the number of candidates is large, we prove it is hard to distinguish between instances where the gerrymanderer cannot win a single district and instances where the gerrymanderer can win at least one district. This immediately implies that the redistricting problem is inapproximable in polynomial time in planar graphs, unless P=NP. This conclusion appears terminal for the design of good approximation algorithms – but it is not. The inapproximability bound can be circumvented as it only applies when the maximum number of districts the gerrymanderer can win is extremely small, say one. Indeed, for a fixed number of candidates, our main result is that there is a constant factor approximation algorithm for redistricting unweighted planar graphs, provided the optimal value is a large enough constant.

PDF

NeurIPS Conference 2024 Conference Paper

Putting Gale & Shapley to Work: Guaranteeing Stability Through Learning

Hadi Hosseini
Sanjukta Roy
Duohan Zhang

Two-sided matching markets describe a large class of problems wherein participants from one side of the market must be matched to those from the other side according to their preferences. In many real-world applications (e. g. content matching or online labor markets), the knowledge about preferences may not be readily available and must be learned, i. e. , one side of the market (aka agents) may not know their preferences over the other side (aka arms). Recent research on online settings has focused primarily on welfare optimization aspects (i. e. minimizing the overall regret) while paying little attention to the game-theoretic properties such as the stability of the final matching. In this paper, we exploit the structure of stable solutions to devise algorithms that improve the likelihood of finding stable solutions. We initiate the study of the sample complexity of finding a stable matching, and provide theoretical bounds on the number of samples needed to reach a stable matching with high probability. Finally, our empirical results demonstrate intriguing tradeoffs between stability and optimality of the proposed algorithms, further complementing our theoretical findings.

PDF Details DOI

AAMAS Conference 2023 Conference Paper

Hedonic Games With Friends, Enemies, and Neutrals: Resolving Open Questions and Fine-Grained Complexity

Jiehua Chen
Gergely Csáji
Sanjukta Roy
Sofia Simola

We investigate verification and existence problems for prominent stability concepts in hedonic games with friends, enemies, and optionally with neutrals [8, 15]. We resolve several (long-standing) open questions [4, 15, 19, 22] and show that for friend-oriented preferences, under the friends and enemies model, it is coNP-complete to verify whether a given agent partition is (strictly) core stable, while under the friends, enemies, and neutrals model, it is NP-complete to determine whether an individual stable partition exists. We further look into natural restricted cases from the literature, such as when the friends and enemies relationships are symmetric, when the initial coalitions have bounded size, when the vertex degree in the friendship graph (resp. the union of friendship and enemy graph) is bounded, or when such graph is acyclic or close to being acyclic. We obtain a complete (parameterized) complexity picture regarding these cases.

PDF

IJCAI Conference 2023 Conference Paper

Optimal Seat Arrangement: What Are the Hard and Easy Cases?

Esra Ceylan
Jiehua Chen
Sanjukta Roy

We study four NP-hard optimal seat arrangement problems which each have as input a set of n agents, where each agent has cardinal preferences over other agents, and an n-vertex undirected graph (called the seat graph). The task is to assign each agent to a distinct vertex in the seat graph such that either the sum of utilities or the minimum utility is maximized, or it is envy-free or exchange-stable. Aiming at identifying hard and easy cases, we extensively study the algorithmic complexity of the four problems by looking into natural graph classes for the seat graph (e. g. , paths, cycles, stars, or matchings), problem-specific parameters (e. g. , the number of non-isolated vertices in the seat graph or the maximum number of agents towards whom an agent has non-zero preferences), and preference structures (e. g. , non-negative or symmetric preferences). For strict preferences and seat graphs with disjoint edges and isolated vertices, we correct an error in the literature and show that finding an envy-free arrangement remains NP-hard in this case.

PDF Details DOI

TCS Journal 2022 Journal Article

Resolute control: Forbidding candidates from winning an election is hard

Sushmita Gupta
Sanjukta Roy
Saket Saurabh
Meirav Zehavi

We study a set of voting problems where given an election E = ( C, Π V ) (where C is the set of candidates and Π V is a set of votes), and a non-empty subset of candidates J, the question under consideration is: Can we modify the election in a way so that none of the candidates in J wins the election? The modification operations allowed are that of either adding or deleting some candidates. Yang and Wang (2017) [44] introduced these problems as the Resolute Control problem, a generalization of the destructive control problem where J is a singleton. They studied parameterized complexity of Resolute Control for voting rules Borda (both addition and deletion), Maximin (addition), and Copeland (both addition and deletion). They primarily consider | J | as parameter. In this paper we study Resolute Control parameterized by the other natural parameters viz. , the number of candidates added or deleted. We show that the Resolute Control for Borda (both addition and deletion), Maximin (addition) and Copeland (deletion) are W[2]-hard. We complement this by showing that when the number of voters is odd, Copeland (deletion) is FPT parameterized by the sum of the number of deleted candidates and the size of the feedback arc set of the majority graph of the election.

Details DOI

TCS Journal 2021 Journal Article

Balanced stable marriage: How close is close enough?

Sushmita Gupta
Sanjukta Roy
Saket Saurabh
Meirav Zehavi

Balanced Stable Marriage (BSM) is a central optimization version of the classic Stable Marriage (SM) problem. We study BSM from the viewpoint of Parameterized Complexity. Informally, the input of BSM consists of n men, n women, and an integer k. Each person a has a (sub)set of acceptable partners, A ( a ), whom a ranks strictly; we use p a ( b ) to denote the position of b ∈ A ( a ) in a's preference list. The objective is to decide whether there exists a stable matching μ such that balance ( μ ) ≜ max ⁡ { ∑ ( m, w ) ∈ μ p m ( w ), ∑ ( m, w ) ∈ μ p w ( m ) } ≤ k. In SM, all stable matchings match the same set of agents, A ⋆ which can be computed in polynomial time. As balance ( μ ) ≥ | A ⋆ | 2 for any stable matching μ, BSM is trivially fixed-parameter tractable (FPT) with respect to k. Thus, a natural question is whether BSM is FPT with respect to k − | A ⋆ | 2. With this viewpoint in mind, we draw a line between tractability and intractability in relation to the target value. This line separates additional natural parameterizations higher/lower than ours (e. g. , we automatically resolve the parameterization k − | A ⋆ | 2 ). The two extreme stable matchings are the man-optimal μ M and the woman-optimal μ W. Let O M = ∑ ( m, w ) ∈ μ M p m ( w ), and O W = ∑ ( m, w ) ∈ μ W p w ( m ). In this work, we prove that • BSM parameterized by t = k − min ⁡ { O M, O W } admits (1) a kernel where the number of people is linear in t, and (2) a parameterized algorithm whose running time is single exponential in t. • BSM parameterized by t = k − max ⁡ { O M, O W } is W[1]-hard.

Details DOI

IJCAI Conference 2021 Conference Paper

Fractional Matchings under Preferences: Stability and Optimality

Jiehua Chen
Sanjukta Roy
Manuel Sorge

We study generalizations of stable matching in which agents may be matched fractionally; this models time-sharing assignments. We focus on the so-called ordinal stability and cardinal stability, and investigate the computational complexity of finding an ordinally stable or cardinally stable fractional matching which either maximizes the social welfare (i. e. , the overall utilities of the agents) or the number of fully matched agents (i. e. , agents whose matching values sum up to one). We complete the complexity classification of both optimization problems for both ordinal stability and cardinal stability, distinguishing between the marriage (bipartite) and roommates (non-bipartite) cases and the presence or absence of ties in the preferences. In particular, we prove a surprising result that finding a cardinally stable fractional matching with maximum social welfare is NP-hard even for the marriage case without ties. This answers an open question and exemplifies a rare variant of stable marriage that remains hard for preferences without ties. We also complete the picture of the relations of the stability notions and derive structural properties.

PDF Details DOI

AAMAS Conference 2019 Conference Paper

Gehrlein Stability in Committee Selection: Parameterized Hardness and Algorithms

Sushmita Gupta
Pallavi Jain
Sanjukta Roy
Saket Saurabh
Meirav Zehavi

In a multiwinner election based on the Condorcet criterion, we are given a set of candidates, and a set of voters with strict preference ranking over the candidates. A committee is weakly Gehrlein stable (WGS) if each committee member is preferred to each non-member by at least half of the voters. Recently, Aziz et al. [IJCAI 2017] studied the computational complexity of finding a WGS committee of size k. They show that this problem is NP-hard in general and polynomial time solvable when the number of voters is odd. In this article, we initiate a systematic study of the problem in the realm of parameterized complexity. We first show that the problem is W[1]-hard when parameterized by the size of the committee. To overcome this intractability result, we use a known reformulation of WGS as a problem on directed graphs and then use parameters that measure the “structure” of these directed graphs. In particular, we consider the majority graph, defined as follows: there is a vertex corresponding to each candidate, and there is a directed arc from a candidate c to c′ if the number of voters that prefer c over c′ is more than those that prefer c′ over c. The problem of finding WGS committee of size k corresponds to finding a vertex subset X of size k in the majority graph with the following property: the set X contains no vertex outside the committee that has an in-neighbor in X. Observe that the polynomial time algorithm of Aziz et al. [IJCAI 2017] corresponds to solving the problem on a tournament (a complete graph with orientation on edges). Thus, natural parameters to study our problem are “closeness” to being a tournament. We define closeness as the number of missing arcs in the given directed graph and the number of vertices we need to delete from the given directed graph such that the resulting graph is a tournament. We show that the problem is fixed parameter tractable (FPT) and admits linear kernels with respect to closeness parameters. Finally, we also design an exact exponential time algorithm running in time O(1. 2207nnO(1)). Here, n denotes the number of candidates. Proc. of the 18th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2019), N. Agmon, M. E. Taylor, E. Elkind, M. Veloso (eds.), May 13–17, 2019, Montreal, Canada. © 2019 International Foundation for Autonomous Agents and Multiagent Systems (www. ifaamas. org). All rights reserved.

PDF

TCS Journal 2018 Journal Article

Parameterized algorithms for stable matching with ties and incomplete lists

Deeksha Adil
Sushmita Gupta
Sanjukta Roy
Saket Saurabh
Meirav Zehavi

We study the parameterized complexity of NP-hard optimization versions of Stable Matching and Stable Roommates in the presence of ties and incomplete lists. These problems model many real-life situations where solutions have to satisfy certain predefined criterion of suitability and compatibility. Specifically, our objective is to maximize/minimize the size of the stable matching. Our main theorems state that Stable Matching and Stable Roommates admit small kernels. Consequently, we also conclude that Stable Matching is fixed-parameter tractable (FPT) with respect to solution size, and that Stable Roommates is FPT with respect to a structural parameter. Finally, we analyze the special case where the input graph is planar.

Details DOI

IJCAI Conference 2018 Conference Paper

When Rigging a Tournament, Let Greediness Blind You

Sushmita Gupta
Sanjukta Roy
Saket Saurabh
Meirav Zehavi

A knockout tournament is a standard format of competition, ubiquitous in sports, elections and decision making. Such a competition consists of several rounds. In each round, all players that have not yet been eliminated are paired up into matches. Losers are eliminated, and winners are raised to the next round, until only one winner exists. Given that we can correctly predict the outcome of each potential match (modelled by a tournament D), a seeding of the tournament deterministically determines its winner. Having a favorite player v in mind, the Tournament Fixing Problem (TFP) asks whether there exists a seeding that makes v the winner. Aziz et al. [AAAI’14] showed that TFP is NP-hard. They initiated the study of the parameterized complexity of TFP with respect to the feedback arc set number k of D, and gave an XP-algorithm (which is highly inefficient). Recently, Ramanujan and Szeider [AAAI’17] showed that TFP admits an FPT algorithm, running in time 2^{ O(k^2 log k)} n ^{O(1)}. At the heart of this algorithm is a translation of TFP into an algebraic system of equations, solved in a black box fashion (by an ILP solver). We present a fresh, purely combinatorial greedy solution. We rely on new insights into TFP itself, which also results in the better running time bound of 2^{ O(k log k)} n^{ O(1)}. While our analysis is intricate, the algorithm itself is surprisingly simple.

PDF Details

IJCAI Conference 2018 Conference Paper

Winning a Tournament by Any Means Necessary

Sushmita Gupta
Sanjukta Roy
Saket Saurabh
Meirav Zehavi

In a tournament, $n$ players enter the competition. In each round, they are paired-up to compete against each other. Losers are thrown, while winners proceed to the next round, until only one player (the winner) is left. Given a prediction of the outcome, for every pair of players, of a match between them (modeled by a digraph $D$), the competitive nature of a tournament makes it attractive for manipulators. In the Tournament Fixing (TF) problem, the goal is to decide if we can conduct the competition (by controlling how players are paired-up) so that our favorite player $w$ wins. A common form of manipulation is to bribe players to alter the outcome of matches. Kim and Williams [IJCAI 2015] integrated such deceit into TF, and showed that the resulting problem is NP-hard when $\ell 0$). For this problem, our contribution is fourfold. First, we present two operations that ``obfuscate deceit'': given one solution, they produce another solution. Second, we present a combinatorial result, stating that there is always a solution with all reversals incident to $w$ and ``elite players''. Third, we give a closed formula for the case where $D$ is a DAG. Finally, we present exact exponential-time and parameterized algorithms for the general case.

PDF Details