A perfect clone in an ordinal election (i.e., an election where the voters rank the candidates in a strict linear order) is a set of candidates that each voter ranks consecutively. We consider different relaxations of this notion: *independent* or *subelection clones* are sets of candidates that only some of the voters recognize as a perfect clone, whereas *approximate clones* are sets of candidates such that every voter ranks their members close to each other, but not necessarily consecutively. We establish the complexity of identifying such imperfect clones, and of partitioning the candidates into families of imperfect clones. We also study the parameterized complexity of these problems with respect to a set of natural parameters such as the number of voters, the size or the number of imperfect clones we are searching for, or their level of imperfection.

We study strategic candidate nomination by parties in elections decided by Plurality voting. Each party selects a nominee before the election, and the winner is chosen from the nominated candidates based on the voters' preferences. We introduce a new restriction on these preferences, which we call party-aligned single-peakedness: all voters agree on a common ordering of the parties along an ideological axis, but may differ in their perceptions of the positions of individual candidates within each party. The preferences of each voter are single-peaked with respect to their own axis over the candidates, which is consistent with the global ordering of the parties. We present a polynomial-time algorithm for recognizing whether a preference profile satisfies party-aligned single-peakedness. In this domain, we give polynomial-time algorithms for deciding whether a given party can become the winner under some (or all) nominations, and whether this can occur in some pure Nash equilibrium. We also prove a tight result about the guaranteed existence of pure strategy Nash equilibria for elections with up to three parties for single-peaked and party-aligned single-peaked preference profiles.

Abstract We consider the following problem that we call the Shortest Two Disjoint Paths problem: given an undirected graph $$G=(V,E)$$ G = ( V , E ) with edge weight function $${w:E\rightarrow \mathbb {R}}$$ w : E → R , two terminals s and t in G , find two internally vertex-disjoint paths between s and t with minimum total weight. As shown recently by Schlotter and Sebő (2022), this problem becomes $$\textsf{NP}$$ NP -hard if edges can have negative weights, even if the weight function is conservative, i.e., there are no cycles in G with negative total weight. We propose a polynomial-time algorithm that solves the Shortest Two Disjoint Paths problem for conservative weights in the case when the negative-weight edges form a constant number of trees in G .

We survey the notion of control in various areas of computational social choice (COMSOC) such as voting, fair allocation, cooperative game theory, matching under preferences, and group identification. In all these scenarios, control can be exerted, for instance, by adding or deleting agents with the goal of influencing the outcome. We conclude by briefly covering control in some other COMSOC areas including participatory budgeting, judgment aggregation, and opinion diffusion.

We study fundamental connections between coalition formation games and clustering, illustrating the cross-disciplinary relevance of these concepts. We focus on graphical hedonic games where agents' preferences are compactly represented by a friendship graph and an enemy graph. In the context of clustering, friendship relations naturally align with data point similarities, whereas enmity corresponds to dissimilarities. We consider two stability notions based on single-agent deviations: local popularity and local stability. Exploring these concepts from an algorithmic viewpoint, we design efficient mechanisms for finding locally stable or locally popular partitions. Besides gaining theoretical insight into the computational complexity of these problems, we perform simulations that demonstrate how our algorithms can be successfully applied in clustering and community detection. Our findings highlight the interplay between coalition formation games and data-driven clustering techniques, offering fresh perspectives and applications in both areas.

Abstract. Minimizing the weight of an edge set satisfying parity constraints is a challenging branch of combinatorial optimization as witnessed by the binary hypergraph chapter of Alexander Schrijver’s book [ Combinatorial Optimization, Springer-Verlag, 2003, Chapter 80]. This area contains relevant graph theory problems including open cases of the Max Cut problem and some multiflow problems. We clarify the interconnections between some of these problems and establish three levels of difficulty. On the one hand, we prove that the Shortest Odd Path problem in undirected graphs without cycles of negative total weight and several related problems are NP-hard, settling a long-standing open question asked by Lovász (Open Problem 27 in Schrijver’s book [ Combinatorial Optimization, Springer-Verlag, 2003]). On the other hand, we provide an algorithm for the closely related and well-studied Minimum-weight Odd [Formula: see text]-Join problem for nonnegative weights: our algorithm runs in FPT time parameterized by [Formula: see text], where [Formula: see text] is the number of connected components in some efficiently computed minimum-weight [Formula: see text]-join. If negative weights are also allowed, then finding a minimum-weight odd [Formula: see text]-join is equivalent to the Minimum-weight Odd [Formula: see text]-Join problem for arbitrary weights, whose complexity is still only conjectured to be polynomially solvable. The analogous problems for digraphs are also considered.

Consider a directed, rooted graph \(G=(V\cup\{r\},E)\) where each vertex in \(V\) has a partial order preference over its incoming edges. The preferences of a vertex naturally extend to preferences over arborescences rooted at \(r\) . We present a polynomial-time algorithm that decides whether a given input instance admits a popular arborescence, i.e., one for which there is no “more popular” arborescence. In fact, our algorithm solves the more general popular common base problem in the intersection of two matroids: we are given an arbitrary matroid \(M=(E,\mathcal{I})\) and a partition matroid \(M_{\text{part}}\) over \(E\) , where partition classes correspond to a set \(V\) of agents with \(|V|={\rm rank}(M)\) and each agent has a partial order preference over its associated partition class; the problem asks for a common base of \(M\) and \(M_{\text{part}}\) such that there is no “more popular” common base. Our algorithm is combinatorial, and can be regarded as a primal–dual algorithm. It searches for a solution along with its dual certificate, a chain of subsets of \(E\) , witnessing its popularity. Our generalized results, expressed in terms of matroids, demonstrate that the identification of agents with vertices of the graph in the popular arborescence problem is not essential. We also study the related popular common independent set problem. For the case with weak rankings, we formulate the popular common independent set polytope, and thus show that a minimum-cost popular common independent set can be computed efficiently. By contrast, we prove that it is \(\mathsf{NP}\) -hard to compute a minimum-cost popular arborescence, even when rankings are strict.

We study variants of the Optimal Refugee Resettlement problem where a set F of refugee families need to be allocated to a set P of possible places of resettlement in a feasible and optimal way. Feasibility issues emerge from the assumption that each family requires certain services (such as accommodation, school seats, or medical assistance), while there is an upper and, possibly, a lower quota on the number of service units provided at a given place. Besides studying the problem of finding a feasible assignment, we also investigate two natural optimization variants. In the first one, we allow families to express preferences over P, and we aim for a Pareto-optimal assignment. In a more general setting, families can attribute utilities to each place in P, and the task is to find a feasible assignment with maximum total utilities. We study the computational complexity of all three variants in a multivariate fashion using the framework of parameterized complexity. We provide fixed-parameter algorithms for a handful of natural parameterizations, and complement these tractable cases with tight intractability results.

Our input is a directed, rooted graph G = (V ∪ {r}, E) where each vertex in V has a partial order preference over its incoming edges. The preferences of a vertex extend naturally to preferences over arborescences rooted at r. We seek a popular arborescence in G, i.e., one for which there is no “more popular” arborescence. Popular arborescences have applications in liquid democracy or collective decision making; however, they need not exist in every input instance. The popular arborescence problem is to decide if a given input instance admits a popular arborescence or not. We show a polynomial-time algorithm for this problem, whose computational complexity was not known previously.

We consider the following problem that we call the Shortest Two Disjoint Paths problem: given an undirected graph $G=(V,E)$ with edge weights $w:E \rightarrow \mathbb{R}$, two terminals $s$ and $t$ in $G$, find two internally vertex-disjoint paths between $s$ and $t$ with minimum total weight. As shown recently by Schlotter and Sebő (2022), this problem becomes NP-hard if edges can have negative weights, even if the weight function is conservative, there are no cycles in $G$ with negative total weight. We propose a polynomial-time algorithm that solves the Shortest Two Disjoint Paths problem for conservative weights in the case when the negative-weight edges form a constant number of trees in $G$.

Abstract Consider elections where the set of candidates is partitioned into parties, and each party must nominate exactly one candidate. The Possible President problem asks whether some candidate of a given party can become the unique winner of the election for some nominations from other parties. We perform a multivariate computational complexity analysis of Possible President for several classes of elections based on positional scoring rules. We consider the following parameters: the size of the largest party, the number of parties, the number of voters and the number of voter types. We provide a complete computational map of Possible President in the sense that for each choice of the four possible parameters as (i) constant, (ii) parameter, or (iii) unbounded, we classify the computational complexity of the resulting problem as either polynomial-time solvable or -complete, and for parameterized versions as either fixed-parameter tractable or [1]-hard with respect to the parameters considered.

We consider the Shortest Odd Path problem, where given an undirected graph G , a weight function on its edges, and two vertices s and t in G , the aim is to find an ( s , t ) -path with odd length and, among all such paths, of minimum weight. For the case when the weight function is conservative, i.e., when every cycle has non-negative total weight, the complexity of the Shortest Odd Path problem had been open for 20 years, and was recently shown to be NP -hard. We give a polynomial-time algorithm for the special case when the weight function is conservative and the set E − of negative-weight edges forms a single tree. Our algorithm exploits the strong connection between Shortest Odd Path and the problem of finding two internally vertex-disjoint paths between two terminals in an undirected edge-weighted graph. It also relies on solving an intermediary problem variant called Shortest Parity-Constrained Odd Path where for certain edges we have parity constraints on their position along the path. Also, we exhibit two FPT algorithms for solving Shortest Odd Path . The first FPT algorithm is parameterized by | E − | , the number of negative edges, or more generally, by the maximum size of a matching in the subgraph of G spanned by E − , when the weight function is conservative. Our second FPT algorithm is parameterized by the treewidth of G , and the algorithm does not rely on conservativeness.

A preference system I is an undirected graph where vertices have preferences over their neighbors, and I admits a master list if all preferences can be derived from a single ordering over all vertices. We study the problem of deciding whether a given preference system I is close to admitting a master list based on three different distance measures. We determine the computational complexity of the following questions: can I be modified by (i) k swaps in the preferences, (ii) k edge deletions, or (iii) k vertex deletions so that the resulting instance admits a master list? We investigate these problems in detail from the viewpoint of parameterized complexity and of approximation. We also present two applications related to stable and popular matchings.

We consider a matching problem in a bipartite graph G = (A∪B, E) where each node in A is an agent having preferences in partial order over her neighbors, while nodes in B are objects with no preferences. The size of our matching is more important than node preferences–thus, we are interested in maximum matchings only. Any pair of maximum matchings in G (equivalently, perfect matchings or assignments) can be compared by holding a head-to-head election between them where agents are voters. The goal is to compute an assignment such that there is no better or “more popular” assignment. This is the popular assignment problem and it generalizes the well-studied popular matching problem (Abraham et al., 2007). Popular assignments need not exist in every input instance. We show a polynomial-time algorithm that decides if the given instance admits one or not, and computes one, if so. In instances with no popular assignment, we consider the problem of finding an almost popular assignment, i.e., an assignment with minimum unpopularity margin. We show an O∗ (|E|k) time algorithm for deciding if there exists an assignment with unpopularity margin at most k. We then show that this algorithm is essentially optimal by proving that the problem is NP-complete and Wl[1]-hard with parameter k. We also consider the minimum-cost popular assignment problem when there are edge costs, and show this problem to be NP-hard. This hardness holds even when all edge costs are in {0,1} and agents have strict preferences. By contrast, we propose a polynomial-time algorithm to the problem of deciding if there exists a popular assignment with a given set of forced/forbidden edges (this tractability holds even for partially ordered preferences). Our algorithms are combinatorial and based on LP duality. They search for an appropriate witness or dual certificate, and when a certificate cannot be found, we prove that the desired assignment does not exist in G.

Abstract We consider the following control problem on fair allocation of indivisible goods. Given a set I of items and a set of agents, each having strict linear preferences over the items, we ask for a minimum subset of the items whose deletion guarantees the existence of a proportional allocation in the remaining instance; we call this problem Proportionality by Item Deletion (PID). Our main result is a polynomial-time algorithm that solves PID for three agents. By contrast, we prove that PID is computationally intractable when the number of agents is unbounded, even if the number k of item deletions allowed is small—we show that the problem is $${\mathsf {W}}[3]$$ W [ 3 ] -hard with respect to the parameter k. Additionally, we provide some tight lower and upper bounds on the complexity of PID when regarded as a function of |I| and k. Considering the possibilities for approximation, we prove a strong inapproximability result for PID. Finally, we also study a variant of the problem where we are given an allocation $$\pi $$ π in advance as part of the input, and our aim is to delete a minimum number of items such that $$\pi $$ π is proportional in the remainder; this variant turns out to be $${{\mathsf {N}}}{{\mathsf {P}}}$$ N P -hard for six agents, but polynomial-time solvable for two agents, and we show that it is $$\mathsf {W[2]}$$ W [ 2 ] -hard when parameterized by the number k of

Abstract LetGbe a digraph where every node has preferences over its incoming edges. The preferences of a node extend naturally to preferences overbranchings, i.e., directed forests; a branchingBispopularifBdoes not lose a head-to-head election (where nodes cast votes) against any branching. Such popular branchings have a natural application in liquid democracy. The popular branching problem is to decide ifGadmits a popular branching or not. We give a characterization of popular branchings in terms ofdual certificatesand use this characterization to design an efficient combinatorial algorithm for the popular branching problem. When preferences are weak rankings, we use our characterization to formulate thepopular branching polytopein the original space and also show that our algorithm can be modified to compute a branching withleast unpopularity margin. When preferences are strict rankings, we show that “approximately popular” branchings always exist.

Abstract Stable matching problems with lower quotas are fundamental in academic hiring and ensuring operability of rural hospitals. Only few tractable (polynomial-time solvable) cases of stable matching with lower quotas have been identified; most such problems are $$\mathsf {NP}$$ NP -hard and also hard to approximate (Hamada et al. in Algorithmica 74(1):440–465, 2016). We therefore consider stable matching problems with lower quotas under a relaxed notion of tractability, namely fixed-parameter tractability. By cloning hospitals we focus on the case when all hospitals have upper quota equal to 1, which generalizes the setting of “arranged marriages” first considered by Knuth (Mariages stables et leurs relations avec d’autres problèmes combinatoires, Les Presses de l’Université de Montréal, Montreal, 1976). We investigate how a set of natural parameters, namely the maximum length of preference lists for men and women, the number of distinguished men and women, and the number of blocking pairs allowed determine the computational tractability of this problem. Our main result is a complete complexity trichotomy: for each choice of parameters we either provide a polynomial-time algorithm, or an $$\mathsf {NP}$$ NP -hardness proof and fixed-parameter algorithm, or $$\mathsf {NP}$$ NP -hardness proof and $$\mathsf {W}[1]$$ W[1] -hardness proof. As corollary, we negatively answer a question by Hamada et al. (Algorithmica 74(1):440–465, 2016) by showing fixed-parameter intractability parameterized by optimal solution size. We also classify all cases of one-sided constraints where only women may be distinguished.

We study a family of problems where the goal is to make a graph Eulerian, i.e., connected and with all the vertices having even degrees, by a minimum number of deletions. We completely classify the parameterized complexity of various versions: undirected or directed graphs, vertex or edge deletions, with or without the requirement of connectivity, etc. The collection of results shows an interesting contrast: while the node-deletion variants remain intractable, i.e., W[1]-hard for all the studied cases, edge-deletion problems are either fixed-parameter tractable or polynomial-time solvable. Of particular interest is a randomized FPT algorithm for making an undirected graph Eulerian by deleting the minimum number of edges, based on a novel application of the color coding technique. For versions that remain NP-complete but fixed-parameter tractable we consider also possibilities of polynomial kernelization; unfortunately, we prove that this is not possible unless NP⊆coNP/poly.

Approval-like voting rules, such as Sincere-Strategy Preference-Based Approval voting (SP-AV), the Bucklin rule (an adaptive variant of k-Approval voting), and the Fallback rule (an adaptive variant of SP-AV) have many desirable properties: for example, they are easy to understand and encourage the candidates to choose electoral platforms that have a broad appeal. In this paper, we investigate both classic and parameterized computational complexity of electoral campaign management under such rules. We focus on two methods that can be used to promote a given candidate: asking voters to move this candidate upwards in their preference order or asking them to change the number of candidates they approve of. We show that finding an optimal campaign management strategy of the first type is easy for both Bucklin and Fallback. In contrast, the second method is computationally hard even if the degree to which we need to affect the votes is small. Nevertheless, we identify a large class of scenarios that admit a fixed-parameter tractable algorithm.