Selected Talks

The practice of partitioning a region into areas to favor a particular candidate or a party in an election has been known to exist for the last two centuries. This practice is commonly known as gerrymandering. Recently, the problem has also attracted a lot of attention from complexity theory perspective. In particular, Cohen-Zemach et al. [AAMAS 2018] proposed a graph theoretic version of gerrymandering problem and initiated an algorithmic study around this, which was continued by Ito et al. [AAMAS 2019]. In this paper we continue this line of investigation and resolve an open problem in the literature, as well as move the algorithmic frontier forward by studying this problem in the realm of parameterized complexity.

Our contributions in this article are two-fold, conceptual and computational. We first resolve the open question posed by Ito et al. [AAMAS 2019] about the computational complexity of gerryman- dering when the input graph is a path. Next, we propose a generalization of the model studied in [AAMAS 2019], where the input consists of a graph on n vertices representing the set of voters, a set of m candidates C, a weight function wv : C → Z+ for each voter v ∈ V (G) representing the preference of the voter over the candidates, a distinguished candidate p ∈ C, and a positive integer k. The objective is to decide if it is possible to partition the vertex set into k districts (i.e., pair- wise disjoint connected sets) such that the candidate p wins more districts than any other candidate. There are several natural parameters associated with the problem: the number of districts the vertex set needs to be partitioned (k), the number of voters (n), and the number of candidates (m). The problem is known to be NP-complete even if k = 2, m = 2, and G is either a complete bipartite graph (in fact K2,n, a complete bipartite graphs with one side of size 2 and the other of size n) or a complete graph. This hardness result implies that we cannot hope to have an algorithm with running time (n + m)^{f(k,m)} let alone f(k,m)(n + m)^{O(1)}, where f is a function depending only on k and m, as this would imply that P=NP. This means that in search for FPT algorithms we need to either focus on the parameter n, or subclasses of forest (as the problem is NP-complete on K2,n, a family of graphs that can be transformed into a forest by deleting one vertex). Circumventing these intractable results, we successfully obtain the following algorithmic results.

• We design a parameterized algorithm with respect to the parameter k (an algorithm with run- ning time 2O(k)nO(1)) in both deterministic and randomized settings, even for arbitrary weight functions. Whether the problem is FPT parameterized by k on trees remains an interesting open problem.

• We show that the problem admits a 2^n (n + m)^{O(1)} time algorithm on general graphs.
  Our algorithmic results use sophisticated technical tools such as representative set family and Fast Fourier transform based polynomial multiplication, and their (possibly first) application to problems arising in social choice theory and/or algebraic game theory may be of independent interest to the community.

In computational social choice, shift bribery is the procedure of paying voters to shift the briber’s preferred candidate forward in their preferences so as to make this candidate an election winner; the more general swap bribery procedure also allows one to pay voters to swap other candidates in their preferences. The complexity of swap and shift bribery is well-understood for many voting rules; typically, finding a minimum-cost bribery is computationally hard. In this paper we initiate the study of swap and shift bribery in the setting where voters’ preferences are known to be single-peaked or single-crossing. We obtain polynomial-time algorithms for several variants of these problems for classic voting rules, such as Plurality, Borda and Condorcet-consistent rules.

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 manipula- tors. 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 ma- nipulation is to bribe players to alter the outcome of matches. Kim and Williams [IJCAI 2015] inte- grated such deceit into TF, and showed that the re- sulting problem is NP-hard when l < (1 − ε) log n alterations are possible (for any fixed ε > 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 in- cident 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 paameterized 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 58:151–169, 2010) proved this problem is NP-complete. In this article, we give an exact-exponential algorithm for SEOPM running in time 2^{O(𝑛)}, where ndenotes 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^{𝑜(𝑛)}. 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 all possible non-isomorphic out-branchings. Our results cover both the cases when the preference lists are strict and complete, and when they are strict but possibly incomplete.