Multiwinner Elections have emerged as a prominent area of research with numerous practical applications. Given a set of candidates, C, a set of voters, V, approving a subset of candidates (called approval set of a voter), and an integer k, we consider the problem of selecting a ``good'' committee using Thiele rules. This problem is computationally challenging for most Thiele rules with monotone submodular satisfaction functions, as there is no (1-1/e- epsilon) approximation algorithm in f(k)(|C| + |V|)^(o(k)) time for any fixed epsilon > 0 and any computable function f, and no PTAS even when the length of approval set is two. Skowron designed an approximation scheme running in FPT time parameterized by the combined parameter, size of the approval set, and k. In this paper, we consider a parameter d+k (no d voters approve the same set of d candidates), where d is upper bounded by the size of the approval set (thus, can be much smaller). With respect to this parameter, we design parameterized approximation schemes, a lossy polynomial-time preprocessing method, and show that an extra committee member suffices to achieve the desired score (i.e., 1-additive approximation). Additionally, we resolve an open question by Yang and Wang regarding the fixed-parameter tractability of the problem under the PAV rule with the total score as the parameter, demonstrating that it admits an FPT algorithm.

Allocating conflicting jobs among individuals while respecting a budget constraint for each individual is an optimization problem that arises in various real-world scenarios. In this paper, we consider the situation where each individual derives some satisfaction from each job. We focus on finding a feasible allocation of conflicting jobs that maximize egalitarian cost, i.e., the satisfaction of the individual who is worst-off. To the best of our knowledge, this is the first paper to combine egalitarianism, budget-feasibility, and conflict-freeness in allocations. We provide a systematic study of the computational complexity of finding budget-feasible conflict-free egalitarian allocation and show that our problem generalizes a large number of classical optimization problems. Therefore, unsurprisingly, our problem is NP-hard even for two individuals and when there is no conflict between any jobs. We show that the problem admits algorithms when studied in the realm of approximation algorithms and parameterized algorithms with a host of natural parameters that match and in some cases improve upon the running time of known algorithms.

Single-elimination (SE) tournaments are a popular format used in competitive environments and decision making. Algorithms for SE tournament manipulation have been an active topic of research in recent years. In this paper, we initiate the algorithmic study of a novel variant of SE tournament manipulation that aims to model the fact that certain matchups are highly desired in a sporting context, incentivizing an organizer to manipulate the bracket to make such matchups take place. We obtain both hardness and tractability results. We show that while the problem of computing a bracket enforcing a given set of matches in an SE tournament is NP-hard, there are natural restrictions that lead to polynomial-time solvability. In particular, we show polynomial-time solvability if there is a linear ordering on the ability of players with only a constant number of exceptions where a player with lower ability beats a player with higher ability.

Classical work on metric space based committee selection problem interprets distance as ``near is better''. In this work, motivated by real-life situations, we interpret distance as ``far is better''. Formally stated, we initiate the study of ``obnoxious'' committee scoring rules when the voters' preferences are expressed via a metric space. To this end, we propose a model where large distances imply high satisfaction and study the egalitarian avatar of the well-known Chamberlin-Courant voting rule and some of its generalizations. For a given integer value $1 \le λ\le k$, the committee size k, a voter derives satisfaction from only the $λ$-th favorite committee member; the goal is to maximize the satisfaction of the least satisfied voter. For the special case of $λ= 1$, this yields the egalitarian Chamberlin-Courant rule. In this paper, we consider general metric space and the special case of a $d$-dimensional Euclidean space. We show that when $λ$ is $1$ and $k$, the problem is polynomial-time solvable in $\mathbb{R}^2$ and general metric space, respectively. However, for $λ= k-1$, it is NP-hard even in $\mathbb{R}^2$. Thus, we have ``double-dichotomy'' in $\mathbb{R}^2$ with respect to the value of λ, where the extreme cases are solvable in polynomial time but an intermediate case is NP-hard. Furthermore, this phenomenon appears to be ``tight'' for $\mathbb{R}^2$ because the problem is NP-hard for general metric space, even for $λ=1$. Consequently, we are motivated to explore the problem in the realm of (parameterized) approximation algorithms and obtain positive results. Interestingly, we note that this generalization of Chamberlin-Courant rules encodes practical constraints that are relevant to solutions for certain facility locations.

Stable Marriage is a fundamental problem to both computer science and economics. Four well-known NP-hard optimization versions of this problem are the Sex-Equal Stable Marriage (SESMI), Balanced Stable Marriage (BSMI), max-Stable Marriage with Ties (max-SMTI), and min-Stable Marriage with Ties (min-SMTI) problems. In this paper, we analyze these problems from the viewpoint of parameterized complexity. We conduct the first study of these problems in particular, and of problems related to Stable Marriage in general, with respect to the parameter treewidth. The motivation behind the choice of treewidth is threefold. First, several problems in social choice theory have already been studied with respect to treewidth. The networks relevant to these problems (say, social networks) are clearly also relevant to Stable Marriage. Thus, the motivation underlying these studies directly extends to our study. Second, empirical studies of the treewidth of several types of networks relevant to Stable Marriage have also already been undertaken, identifying that some of these networks indeed have a treelike structure. Third, treewidth is the most well studied structural parameter in parameterized complexity. We design optimal parameterized algorithms for all four problems under the treewidth of both their primal graphs and rotation digraphs. First, we study the treewidth ${\mathtt{tw}}$ of the primal graph. We establish that all four problems are W[1]-hard. In particular, while it is easy to show that all four problems admit algorithms that run in time $n^{{\mathcal{O}}({\mathtt{tw}})}$, we prove that unless the exponential-time hypothesis is false, all of these algorithms are optimal. Next, we study the treewidth ${\mathtt{tw}}$ of the rotation digraph. In this context, max-SMTI and min-SMTI are not defined. For both SESMI and BSMI, we design (highly nontrivial) algorithms that run in time $2^{{\mathtt{tw}}}n^{{\mathcal{O}}(1)}$. Then, for both SESMI and BSMI, we prove that unless the strong exponential-time hypothesis is false, algorithms that run in time $(2-\epsilon)^{{\mathtt{tw}}}n^{{\mathcal{O}}(1)}$ do not exist for any fixed $\epsilon>0$. We thus present a comprehensive, complete picture of the behavior of Stable Marriage with respect to treewidth.

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.

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 complexity of computing good committees. More formally, given a set of candidates C, a set of voters V, each ranking the candidates according to their preferences, and an integer k; a multiwinner voting rule identifies a committee of size k, based on these given voter preferences. In this paper we consider several utilitarian and egailitarian OWA (ordered weighted average) scoring rules, which are an extensively researched family of rules (and a subfamily of the family of committee scoring rules). First, we improve the result of Betzler et al. [JAIR, 2013], which gave a O(n^n) algorithm for computing winner under the Chamberlin Courant rule (CC), where n is the number of voters; to a running time of O(2^n), which is optimal. Furthermore, we study the parameterized complexity of the Pessimist voting rule and describe a few tractable and intractable cases. Apart from such utilitarian voting rules, we extend our study and consider egalitarian median and egalitarian mean (both committee scoring rules), showing some tractable and intractable results, based on nontrivial structural observations.

In the Stable Marriage problem, when the preference lists are complete, all agents of the smaller side can be matched. However, this need not be true when preference lists are incomplete. In most real-life situations, where agents participate in the matching market voluntarily and submit their preferences, it is natural to assume that each agent wants to be matched to someone in his/her preference list as opposed to being unmatched. In light of the Rural Hospital Theorem, we have to relax the "no blocking pair" condition for stable matchings in order to match more agents. In this paper, we study the question of matching more agents with fewest possible blocking edges. In particular, the goal is to find a matching whose size exceeds that of a stable matching in the graph by at least t and has at most k blocking edges. We study this question in the realm of parameterized complexity with respect to several natural parameters, k,t,d, where d is the maximum length of a preference list. Unfortunately, the problem remains intractable even for the combined parameter k+t+d. Thus, we extend our study to the local search variant of this problem, in which we search for a matching that not only fulfills each of the above conditions but is "closest", in terms of its symmetric difference to the given stable matching, and obtain an FPT algorithm.

In the standard model of committee selection, we are given a set of ordinal votes over a set of candidates and a desired committee size, and the task is to select a committee that relates to the given votes. Motivated by possible interactions and dependencies between candidates, we study a generalization of committee selection in which the candidates are connected via a network and the task is to select a committee that relates to the given votes while also satisfy certain properties with respect to this candidate network. To accommodate certain correspondences to the voter preferences, we consider three standard voting rules (in particular, $k$-Borda, Chamberlin-Courant, and Gehrlein stability); to model different aspects of interactions and dependencies between candidates, we consider two graph properties (in particular, Independent Set and Connectivity). We study the parameterized complexity of the corresponding combinatorial problems and discuss certain implications of our algorithmic results.

Single-elimination tournaments are a popular format in competitive environments. The Tournament Fixing Problem (TFP), which is the problem of finding a seeding of the players such that a certain player wins the resulting tournament, is known to be NP-hard in general and fixed-parameter tractable when parameterized by the feedback arc set number of the input tournament (an oriented complete graph) of expected wins/loses. However, the existence of polynomial kernelizations (efficient preprocessing) for TFP has remained open. In this paper, we present the first polynomial kernelization for TFP parameterized by the feedback arc set number of the input tournament. We achieve this by providing a polynomial-time routine that computes a SAT encoding where the number of clauses is bounded polynomially in the feedback arc set number.

An input to the Popular Matching problem, in the roommates setting, consists of a graph G where each vertex ranks its neighbors in strict order, known as its preference. In the Popular Matching problem the objective is to test whether there exists a matching M* such that there is no matching M where more people (vertices) are happier (in terms of the preferences) with M than with M*. In this paper we settle the computational complexity of the Popular Matching problem in the roommates setting by showing that the problem is NP-complete. Thus, we resolve an open question that has been repeatedly and explicitly asked over the last decade.

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.

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<(1-\epsilon)\log n$ alterations are possible (for any fixed $\epsilon>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.

In this paper we consider a problem that arises from a strategic issue in the stable matching model (with complete preference lists) from the viewpoint of exact-exponential time algorithms. Specifically, we study the Stable Extension of Partial Matching (SEOPM) problem, where the input consists of the complete preference lists of men, and a partial matching. The objective is to find (if one exists) a set of preference lists of women, such that the men-optimal Gale Shapley algorithm outputs a perfect matching that contains the given partial matching. Kobayashi and Matsui [Algorithmica, 2010] proved this problem is NP-complete. In this article, we give an exact-exponential algorithm for SEOPM running in time 2^{O(n)}, where n denotes the number of men/women. We complement our algorithmic finding by showing that unless Exponential Time Hypothesis (ETH) fails, our algorithm is asymptotically optimal. That is, unless ETH fails, there is no algorithm for SEOPM running in time 2^{o(n)}. Our algorithm is a non-trivial combination of a parameterized algorithm for Subgraph Isomorphism, a relationship between stable matching and finding an out-branching in an appropriate graph and enumerating non-isomorphic out-branchings.

In this paper we study the "independent" version of the classic Feedback Vertex Set problem in the realm of parameterized algorithms and moderately exponential time algorithms. More precisely, we study the Independent Feedback Vertex Set problem, where we are given an undirected graph G on n vertices and a positive integer k, and the objective is to check if there is an independent feedback vertex set of size at most k. A set S subseteq V(G) is called an independent feedback vertex set (ifvs) if S is an independent set and G\S is a forest. In this paper we design two deterministic exact algorithms for Independent Feedback Vertex Set with running times O*(4.1481^k) and O*(1.5981^n). In fact, the algorithm with O*(1.5981^n) running time finds the smallest sized ifvs, if an ifvs exists. Both the algorithms are based on interesting measures and improve the best known algorithms for the problem in their respective domains. In particular, the algorithm with running time O*(4.1481^k) is an improvement over the previous algorithm that ran in time O*(5^k). On the other hand, the algorithm with running time O*(1.5981^n) is the first moderately exponential time algorithm that improves over the naive algorithm that enumerates all the subsets of V(G). Additionally, we show that the number of minimal ifvses in any graph on n vertices is upper bounded by 1.7485^n.

We show that for a fixed $r$, the number of maximal $r$-regular induced subgraphs in any graph with $n$ vertices is upper bounded by $\mathcal{O}(c^n)$, where $c$ is a positive constant strictly less than $2$. This bound generalizes the well-known result of Moon and Moser, who showed an upper bound of $3^{n/3}$ on the number of maximal independent sets of a graph on $n$ vertices. We complement this upper bound result by obtaining an almost tight lower bound on the number of (possible) maximal $r$-regular induced subgraphs possible in a graph on $n$ vertices. Our upper bound results are algorithmic. That is, we can enumerate all the maximal $r$-regular induced subgraphs in time $\mathcal{O}(c^n n^{\mathcal{O}(1)})$. A related question is that of finding a maximum-sized $r$-regular induced subgraph. Given a graph $G=(V,E)$ on $n$ vertices, the Maximum $r$-Regular Induced Subgraph (M-$r$-RIS) problem asks for a maximum-sized subset of vertices, $R \subseteq V$, such that the induced subgraph on $R$ is $r$-regular. As a by-product of the enumeration algorithm, we get a $\mathcal{O}(c^n)$ time algorithm for this problem for any fixed constant $r$, where $c$ is a positive constant strictly less than $2$. Furthermore, we use the techniques and results obtained in the paper to obtain improved exact algorithms for a special case of the Induced Subgraph Isomorphism problem, namely, the Induced $r$-Regular Subgraph Isomorphism problem, where $r$ is a constant, the $\delta$-Separating Maximum Matching problem and the Efficient Edge Dominating Set problem.