Diversity in Kemeny Rank Aggregation: A Parameterized Approach

1 Introduction

Traditionally, in optimization theory, when given an instance of a computational problem, one is interested in computing some optimal solution for the instance in question. For certain problems of practical relevance, this framework may not be satisfactory because it precludes the user from the possibility of choosing among optimal solutions in case more than one exists, or from choosing a slightly less optimal solution that may be a better fit for the intended application, due to subjective factors. A recent upcoming trend of research in artificial intelligence, called diversity of solutions [Petit and Trapp, 2019; Baste et al., 2020; Ingmar et al., 2020; Baste et al., 2019; Fomin et al., 2020], has focused on the development of notions of optimality that may be more appropriate in settings where subjectivity is essential. The idea is that instead of aiming at the development of algorithms that output a single optimal solution, the goal is to investigate algorithms that output a small set of sufficiently good solutions that are sufficiently diverse from one another. In this way, the user has the opportunity to choose the solution that is most appropriate to the context at hand. The intuition is that the criteria employed by the user to decide what an appropriate solution is may be subjective, and therefore, impractical or even impossible to be formalized at the level of the problem specification. Examples of such criteria are aesthetic, economic, political, or environmental criteria. Another motivation comes from the problem of finding several good committees such that each committee member is not overloaded with commitments, as described in [Bredereck et al., 2020]; again, some diversity could be helpful.

One source of difficulty when trying to develop efficient algorithms for diverse variants of computational problems is the fact that these problems may be computationally hard. In particular, many interesting computational problems that are suitable for being studied from the perspective of diversity of solutions are already NP-hard in the usual variant in which one asks for a single solution. Additionally, it may be the case that even problems that are polynomial-time solvable in the single-solution version become NP-hard when considering diverse sets of solutions. One way to circumvent this difficulty is to combine the framework of diversity of solutions with the framework of fixed-parameter tractability theory [Downey and Fellows, 1999]. A central notion in this framework is the one of fixed-parameter tractability. An algorithm for a given computational problem is said to be fixedparameter tractable with respect to parameters k1, . . . , kr if it runs in time f(k1, . . . , kr) · nO(1) , where n is the size of the input and f is a computable function that depends only on the parameters. The intuition is that if the range of the parameters is small on instances of practical relevance, then even if the function f grows relatively fast, the algorithm can be considered to be fast enough for practical purposes.

When studying a given computational problem from the point of view of solution diversity, it is crucial to have in hands a notion of distance between solutions for that problem. The diversity of a set of solutions S is then defined as the sum of distances between pairs of solutions in S. We denote this measure by d. Intuitively, diversity is a global measure for how representative a set of solutions is among the space of solutions. Three natural parameters can be used to quantify how good a diverse set of solutions is: the number r of solutions in the set, the maximum distance δ between the cost of a solution in the set and the cost of an optimal solution (we call this parameter the solution imperfection of the set), and the minimum required distance s between any two solutions in the set. This last parameter is also known in the literature as the scatteredness of S [Galle, 1989].

In this work, we investigate the impact of the notions of diversity of solutions and of fixed parameter tractability theory in the context of social choice theory. In particular, we focus on the framework of preference list aggregation introduced by Kemeny in the late fifties [Kemeny, 1959]. Intuitively, preference lists are a formalism used in social choice theory to capture information about choice in applications involving the selection of candidates, products, etc. by a group of voters. The task is then to find a ranking of the candidates that maximizes the overall satisfaction among the voters. This problem is commonly referred to in modern terminology as the Kemeny rank aggregation (KRA) problem. In its most general setting, the ranking cast by each voter is a partial order on the set of candidates. The distance measure we use to define our diverse version for KRA is the Kendall-Tau distance which is widely used in the context of preference aggregation. Its popularity is underlined by articles describing these issues for the interested public audience; see [Farkas and Timotity, 2019].

Our main result is a multi-parametric algorithm for DIVERSE KRA over partially ordered votes that runs in time f(w, r, δ, s) · d · n · log(n2 · m), where n is the number of candidates, m is the number of votes, r, δ, s and d are the parameters discussed above, and w is the unanimity width of the votes. That is to say, the pathwidth of the cocomparability graph of the unanimity order of the input votes (Corollary 11). Intuitively, this width measure is a quantification of the amount of disagreement between votes. Note that pathwidth and treewidth coincide for the class of cocomparability graphs [Habib and M¨ohring, 1994].

On the path towards obtaining our results for Kemeny Rank Aggregation, we also make contributions to problems of independent interest arising in the theory of cocomparability graphs. First, by leveraging on classic results from [Habib and M¨ohring, 1994], we show that the problem of constructing a ρ-consistent path decomposition of approximately minimum width for the cocomparability graph Gρ of a given partial-order ρ is fixed-parameter tractable with respect to the pathwidth of Gρ. While it was known that the pathwidth and the ρ-consistent pathwidth of Gρ are always the same [Arrighi et al., 2020], and fixed-parameter tractable algorithms for computing path decompositions of approximately minimum width exists due to structural properties of cocomparability graphs [Bouchitt´e et al., 2004], the problem of computing such a decomposition satisfying the additional ρ-consistent requirement was open [Arrighi et al., 2020].

Second, we note that the notion of Kendall-Tau distance between partial orders (formally defined in Section 3), which is used to define our notion of diversity, can be applied equally well in the more general context of the COMPLETION OF AN ORDERING problem (CO), a problem of fundamental importance in order theory that unifies several problems of relevance for artificial intelligence, such as KRA, ONE-SIDED CROSSING MINIMIZATION (an important subroutine used in the search for good hierarchical representations of graphs), and GROUPING BY SWAPPING (a relevant problem in the field of memory management) [Wong and Reingold, 1991]. For a matter of generality, we first develop a f(w, r, δ, s)·d·n·log(n2 ·m) time algorithm for DIVERSE CO (Theorem 10) and then obtain our main result for DIVERSE KRA as a corollary. In the more general context of CO, the parameter w is the width of the cocomparability graph of the partial order given at the input.

Finally, building on recent advances in the theory of Ckfree graphs [Chudnovsky et al., 2020] we establish an upper bound for the pathwidth of a cocomparability graph in terms of the number of edges of the graph. As a by-product of this result, we obtain the first algorithm running in time O∗ (2O(√k) ) (Theorem 12) for the positive completion of an ordering problem (PCO), a special case of CO which still generalizes KRA and other important combinatorial problems. Previous to our work, the best algorithm for this problem parameterized by cost had asymptotic time complexity O∗ (kO(√k) ) = O∗ (2√k log k ). We remove the log-factor in the exponent; according to Thm. 18 in [Arrighi et al., 2020] this is optimal under ETH (Exponential Time Hypothesis).

2 Preliminaries

If n is a positive integer, [n] = {1, . . . , n} denotes the discrete interval of the first n positive integers, and [n]0 = [n] ∪ {0}. N denotes the non-negative integers.

Let C be a set. A partial order over C is a reflexive, antisymmetric and transitive binary relation ρ ⊆ C × C. We say that ρ is a linear order if additionally, for each (x, y) ∈ C×C, either (x, y) ∈ ρ or (y, x) ∈ ρ. The comparability relation sc(ρ) of ρ is the symmetric closure of ρ, i.e., (x, y) ∈ sc(ρ) iff (x, y) ∈ ρ or (y, x) ∈ ρ. For instance, sc(ρ) = C × C iff ρ is a linear order. If ρ ⊆ C×C is a partial order, then <ρ denotes the corresponding strict order, which is irreflexive and transitive. Linear orders over C can be given by bijections π : [|C|] → C. Hence, <π (or ≤π) is used to denote the corresponding strict (or partial) linear order. Given a binary relation α, we denote by tc(α) the transitive closure of α.

Definition 1 (Cocomparability graph (F1)). Given a partial order ρ ⊆ C × C, we let Gρ ˙= (C,C × C \ sc(ρ)) be the cocomparability graph of ρ.

Given an undirected graph G = (V, E) and a vertex v ∈ V , we let N(v) ˙= {u | u ∈ V, (v, u) ∈ E} be the neighborhood of v. A path decomposition of a graph G = (V,E) is a sequence P = (B1,B2, . . . ,Bl) of subsets of V , such that the following conditions are satisfied.

• ⋃1≤i≤l Bi = V .
• For each edge (u, v) ∈ E, there is an i ∈ [l] such that u, v ∈ Bi.
• For each i, j, k ∈ [l] with i < j < k, Bi ⋂ Bk ⊆ Bj .

For each position p ∈ {2, . . . , l}, for each vertex v ∈ Bp \ Bp-1, we say that Bp introduces v (v is introduced by Bp) and for each vertex v ∈ Bp-1 \ Bp, we say that Bp forgets v (v is forgotten by Bp). For a position p ∈ {1, . . . , l}, we write intro(p) (resp. forg(p)) for the set of all vertices introduced (resp. forgotten) by Bp, and we let Lp = ⋃1≤i≤p forg(p) be the set of vertices that have been forgotten up to position p. The width of P is defined as w(P) = maxi∈[l] |Bi| - 1. The pathwidth, pw(G), of G is the minimum width of a path decomposition of G.

The pathwidth of the cocomparability graph of a partial order may be regarded as a measure of how close the order is from being a linear order. The cocomparability graph of a linear order τ on n elements is the graph with n vertices and no edges. This graph has pathwidth 0. On the other hand, if τ is a partial order where all n elements are unrelated, then the cocomparability graph of τ is the n-clique, which has pathwidth n - 1 (the highest possible pathwidth in an n-vertex graph).

3 The Kemeny Rank Aggregation Problem

Let C be a finite set, which in this paper will denote a set of candidates, or alternatives. A partial vote over C is a partial order over C. The KT-distance between two partial votes π1 and π2, denoted by KT-dist(π1, π2), is the number of pairs of candidates that are ordered differently in the two partial votes: KT-dist(π1, π2) = |{(c, c′ ) ∈ C×C | c <π1 c′ ∧c′ <π2 c}| .

Observe that when the votes are totally ordered, the Kendall-Tau distance can be seen as the 'bubble sort' distance, i.e., the number of pairwise adjacent transpositions needed to transform one linear order into the other. Given a linear order π over a set of candidates C and a set Π of votes over C, the Kemeny score of π with respect to Π is defined as the sum of the Kendall-Tau distances between π and each vote in Π. In this work, we consider the following problem.

Problem name: KEMENY RANK AGGREGATION (KRA) Given: A list of partial votes Π over a set of candidates C, a non-negative integer k.

Output: Is there a linear order π on C such that the sum of the KT-distances of π from all the partial votes is ≤ k?

Hence, given partial votes π1, . . . , πm of C and a nonnegative integer k, the question is if there exists a linear order π ⊆ C × C such that ∑mi=1 KT-dist(π, πi) ≤ k .

Definition 2. Given a set Π of partial votes, the unanimity order of Π is simply the partial order ρ obtained as the intersection of all partial orders in Π. In other words, a candidate c1 has higher precedence than a candidate c2 in ρ if and only if c1 precedes c2 in each vote in Π.

As a consequence, the more disagreements there are among the voters with respect to the relative orders of pairs of candidates, the denser the cocomparability graph of ρ will be and therefore the greater its pathwidth will be. Therefore, the pathwidth of the cocomparability graph of the unanimity order of Π may be seen as a quantification of the amount of disagreement among the votes in Π.

The notion of diversity of solutions for computationally hard problems has been considered under a variety of frameworks. In this work, we define a notion of diversity for the KEMENY RANK AGGREGATION problem which is analogous to the notion of diversity of vertex sets used in [Baste et al., 2020]. More precisely, if R is a set of partial orders, then we define the Kendall-Tau diversity of R as the sum of Kendall-Tau distances between votes in the set R. KT-Div(R) = ∑π1,π2∈R KT-dist(π1, π2).

We note that the restricted version of the KRA problem where all votes are linear orders, the requirements that a set of solutions is at the same time diverse and only contains rankings with small Kemeny score are clashing. The problem is that the very existence of two distinct rankings with small Kemeny score is an impossible task. If two candidates c1 and c2 occur with the order (c1, c2) in one of the solutions and in the order (c2, c1) in the other solution, then at least one of these solutions will have a Kemeny score of at least half the number of votes. However this opposition between diversity and small Kemeny score is not present in the setting where votes are allowed to be partial. The generalization to partial votes is one possible way to circumvent this conflict of desiderata. Another way we will be looking at is not to consider the cost of the solutions directly but the difference between the cost of solutions and the cost of an optimal solution. In this case, we can have diversity and a small difference between the cost and the cost of an optimal solution.

Problem name: DIVERSE KEMENY RANK AGGREGATION (DIVERSE-KRA)

Given: A list of partial votes Π over a set of candidates C, and k, r, d ∈ N.

Output: Is there a set R = {π1, . . . , πr} of linear orders on C such that the Kemeny score for each order πi is at most k and KT-Div(R) ≥ d?

The problem KEMENY RANK AGGREGATION is known to be NP-complete [Bartholdi et al., 1989], even if only four votes are given at the input [Dwork et al., 2001]. For this reason, KRA has been studied from the perspective of parameterized complexity theory under a variety of parameterizations. Below, we consider two prominent parameterizations for this problem.

The first parameter we consider is the cost of a solution. Simjour [2009] obtained an algorithm for the problem that runs in time O∗ (1.403k ). There are also subexponential algorithms for KEMENY RANK AGGREGATION under this parameterization: Karpinski and Schudy [Karpinski and Schudy, 2010] obtained an algorithm for KEMENY RANK AGGREGATION that runs in O∗ (2O(√k) ) time, while the algorithm of Fernau et al. [Fernau et al., 2011; Fernau et al., 2014], based on a different methodology, runs in O∗ (kO(√k) ) time. Recently, in [Arrighi et al., 2020], it was shown that KRA on instances with only m = 4 votes on some candidate set C and some integer k bounding the sum of the Kendall-Tau distances to a solution cannot be solved neither in time O∗ (2o(|C|) ) nor in time O∗ (2o(√k)), unless ETH fails. The mentioned NP-hardness of KRA immediately translates to NP-hardness results of KRA and of DIVERSE-KRA, in the latter case by setting r = 1 and d = 0.

The second parameter we consider is the unanimity width of the set of votes, which is based on the notion of unanimity order of a set of votes [Charon and Hudry, 2007]. The unanimity width of Π is defined as the pathwidth of the cocomparability graph of ρ.

4 Completion of an Ordering

In this section, we will introduce the COMPLETION OF AN ORDERING problem, a generalization of the POSITIVE COMPLETION OF AN ORDERING (PCO) problem originally considered in [Dujmovic et al., 2003, Sec. 8] and [Fernau, 2005, Sec. 6.4].

Problem name: COMPLETION OF AN ORDERING (CO) Given: A partial order ρ ⊆ C × C over a set C, a cost function c : C × C → N, and some k ∈ N.

Output: Is there a linear order τ ⊇ ρ with c(τ \ ρ) = ∑(x,y)∈τ\ρ c(x, y) ≤ k?

Intuitively, given a partial order ρ and a cost function c, the goal is to find a linear extension of ρ incurring a cost of at most k. The only difference between CO and the original PCO problem introduced in [Dujmovic et al., 2003; Fernau, 2005] is that, in the latter, for every pair (x, y) ∈ C × C such that x and y are incomparable in ρ, the cost of (x, y) is strictly positive (c(x, y) > 0) whereas in CO, the cost can be zero (c(x, y) = 0).

We note that the notion of Kendall-Tau diversity introduced in Section 3 can also be used as a notion of diversity for CO, i.e., given a set R of (not necessarily optimal) solutions for a given instance (ρ, c) of CO, we let KT-Div(R) be the diversity of this set.

Problem name: DIVERSE COMPLETION OF AN ORDERING (DIVERSE-CO)

Given: A partial order ρ ⊆ C×C over a set C, a cost function c : C × C → N, and non-negative integers k, r, d ∈ N.

Output: Is there a set R = {τ1, . . . , τr} of linear extensions of ρ such that c(τi \ ρ) ≤ k for each i ∈ [r], and KT-Div(R) ≥ d ?

Next, we give a rather straightforward reduction from KRA to CO. Given an instance (Π, C) of KRA with partial votes Π = (π1, . . . , πm) and candidates C = {c1, . . . , cn}, we construct an instance (ρ, c) of CO by letting ρ be the unanimity order of Π, and by defining the cost function c : C × C → N as follows. For every pair of candidates (c, c′ ), we define its cost, c(c, c′ ), as the number of votes that order c′ before c. More formally, c(c, c′ ) = |{i ∈ [m] | c′ <πi c}|. With this reduction, it is straightforward to check that a given linear order π of the candidates has Kemeny score ∑mi=1 KT-dist(π, πi) = ∑nj=1 ∑nk=1 c(ck, cj )[ck <π cj ].

Here, for a logical proposition p, we use the bracket notation [p] to denote the integer 1 if p is true the integer 0 if p is false. In other words, ∑mi=1 KT-dist(π, πi) is the cost of π as a linear extension of the ordering ρ.

It is important to note that if all votes in Π are linear orders then (ρ, c) is actually an instance of PCO. In other words, if two candidates c and c′ are incomparable in the unanimity order, then the cost assigned by c to both pairs (c, c′ ) and (c′ , c) are strictly positive. This property will be used crucially in the development of our sub-exponential time algorithm for KRA parameterized by cost.

We also note that since our reduction is solution preserving, it is also immediate that it is diversity preserving. In other words, R is a set of solutions of diversity d for an instance of KRA if and only if it is also a set of solutions of diversity d for the corresponding instance of CO.

5 Diverse CO Parameterized by Pathwidth

In this section, we devise a fixed parameter tractable algorithm for DIVERSE CO parameterized by solution imperfection, number of solutions, scatteredness, and pathwidth of the cocomparability graph of the input instance. Given our reduction that preserves solution and parameters from KRA to CO introduced in Section 4, this algorithm immediately implies that DIVERSE KRA is fixed parameter tractable when parameterized by solution imperfection, number of solutions, scatteredness, and unanimity width.

We start by defining a suitable notion of consistency between a path decomposition and a given partial order. Let G = (C,E) be a graph and ρ ⊆ C × C be a partial order on the vertices of G. We say that a path decomposition D = (B1, . . . ,Bl) is ρ-consistent if there is no pair of vertices (x, y) ∈ ρ such that

In other words, if x is smaller than y in ρ, then y cannot be forgotten in D before x is introduced in D. The ρ-consistent pathwidth of G, denoted by cpw(G, ρ), is the minimum width of a ρ-consistent path decomposition of G.

It has been shown recently that for any partial order ρ ⊆ C × C, the pathwidth of the cocomparability graph Gρ is equal to the consistent pathwidth of Gρ [Arrighi et al., 2020]. The proof of this result was based on the fact that the consistent pathwidth of a cocomparability graph of a partial order is equal to the interval width of the order [Habib and M¨ohring, 1994]. Nevertheless, the problem of constructing, or even approximating, a minimum-width consistent path decomposition in FPT time was left open in [Arrighi et al., 2020].

By taking a closer look at the theory of cocomparability graphs, we solve this open problem in a constructive way. More precisely, in Lemma 3 we show that for any partial order ρ, one can construct a ρ-consistent path decomposition of the cocomparability graph Gρ in fixed-parameter tractable time parameterized by the pathwidth of the graph Gρ.

Lemma 3. Let ρ ⊆ C × C be a partial order and Gρ be the cocomparability graph of ρ. Then one can construct a nice ρconsistent path decomposition P of Gρ of width O(pw(Gρ)) in time 2O(pw(Gρ)) · |C|.

Let ρ be a partial order and P = (B1,B2, . . . ,Bl) be a ρ-consistent path decomposition of Gρ of width w. For each p ∈ [l], let Pp be the set of pairs of the form (S, τ) where S is a subset of Bp that contains vertices introduced by Bp (intro(p) ⊆ S ⊆ Bp), τ ⊇ ρ|S is a linear extension of the restriction ρ|S ˙= S ×S ∩ ρ of ρ to S.

Definition 4. Let p ∈ [l], δ ∈ N, and f : Pp → N. Then, we let Tp(f, δ) be the set of all triples of the form (S, τ, γ), where (S, τ) ∈ Pp and f(S, τ) ≤ γ ≤ f(S, τ) + δ.

Intuitively, the function f will be used by our dynamic programming algorithm to record the optimal values of partial solutions at each bag Bp when processing the path decomposition from left to right (see Theorem 8 and Theorem 10) and δ will be the allowed solution imperfection. In the case of a unique solution, this value will be 0 but this parameter will be useful in the diverse case as we allow sub-optimal linear extensions. A partial solution up to the p-th bag is a linear order σ of ⋃j≤p Bj. Vertices that will be introduced in future bags can be inserted in σ, to extend it, only after vertices already forgotten in the p-th bag. If u will be introduced in a future bag and v is in some Bj but not in Bp, then by consistency of the path decomposition with respect to ρ, we have v <ρ u. Therefore, in Bp, we only need to remember the "last" part of σ, which are the vertices that are in Bp and after all forgotten vertices in σ.

Remark 5. For each p ∈ [l], f : Pp → N and δ ∈ N, the size of Tp(f, δ) is bounded by e · (δ + 1) · (w+1)!.

For each p ∈ [l - 1], f : Pp → N and δ ∈ N, we say that a triple (S, τ, γ) ∈ Tp(f, δ) is compatible with a triple (S′ , τ ′ , γ ′ ) ∈ Tp+1(f, δ) if the following conditions hold.

• C1 Let v = maxτ (S ∩ forg(p+1)) be the maximum vertex of S forgotten by Bp+1 according to the linear order τ. Then, we have the following equality S′ = intro(p+1)∪ {u ∈ S | v <τ u}. This means that one can build S′ from S by removing all vertices that are either forgotten by Bp+1 or smaller than some vertex forgotten by Bp+1, and subsequently, by adding all vertices that have been introduced by Bp+1.
• C2 τ|S∩S′ = τ ′ |S∩S′ , i.e., τ and τ ′ agree on S ∩S′ .
• C3 γ ′ = γ + ∑v∈intro(p+1) (∑u∈S′ ,u<τ′v c(u, v) + ∑u∈S∩S′ ,v<τ′u c(v, u) + ∑u∈Bp+1\S′ c(u, v)). To compute γ ′ , we add to γ the cost of adding the introduced vertices in the order. The first two terms compute the cost of each new vertex in τ ′ and the last one computes the cost of placing the new vertices after all vertices in Bp+1 \ S′ .

A compatible sequence for P is a sequence of triples γ = (S1, τ1, γ1) . . . (Sl, τl, γl) such that for each p ∈ [l], (Sp, τp, γp) is compatible with (Sp-1, τp-1, γp-1).

Our interest in compatible sequences stems from the two following lemmas.

Lemma 6. Let ρ ⊆ C × C be a partial order over C, c : C × C → N be a cost function, and P be a ρ-consistent path decomposition of the graph Gρ. Let γ = t1 . . . tl = (S1, τ1, γ1) . . . (Sl, τl, γl) be a compatible sequence for P. Then, the linear order π = tc(ρ ∪ τ1 ∪ · · · ∪ τl) is a linear extension of ρ of cost γl.

Lemma 7. Let ρ ⊆ C × C be a partial order over C, c : C × C → N be a cost function, and P be a ρ-consistent path decomposition of the graph Gρ. Let π be a linear extension of ρ, and γ = (S1, τ1, γ1) . . . (Sl, τl, γl) be a sequence such that for each position p ∈ [l], Sp = {v ∈ Bp | v >π maxπ(Lp)}, τp = π|Sp , and γp = c(π|Lp∪Bp ). Then, γ is a compatible sequence for P.

Lemma 6 and Lemma 7 immediately yield an FPT dynamic programming algorithm for computing a linear extension of ρ. To define the algorithm more precisely, we first need to define the set of functions fp that we will use to define a set of triples with Tp. For each p ∈ [l], we define fp : Pp → N as follows. For each (S, τ) ∈ Pp, we let γ be the minimum cost of a partial solution π up to bag p such that S = {v ∈ Bp | v >π maxπ(Lp)} and τ = π|Sp , then we let fp(S, τ) = γ. Intuitively, fp associates to each linear order τ the cost of an optimal partial solution "ending" by τ. Now, we will describe the algorithm, we process the path decomposition from left to right in l time steps, where at each time step p, we construct the value of fp that we need and a subset Qp ⊆ Tp(fp, 0) of promising triples, which are, intuitively, triples that have a potential to lead to an optimal solution. At time step 1, set Q1 = {(B1, τ, c(τ))}τ is a linear extension of ρ|B1 . At each time step p ≥ 2, Qp is the set of all triples in Tp(fp, 0) that are compatible with some triple in Qp-1. At the end of the process, assuming that Qp is non-empty for each p ∈ [l], we can reconstruct a compatible sequence by backtracking. First, by selecting an arbitrary triple tl in Ql, then by selecting an arbitrary triple tl-1 in Ql-1 compatible with tl, and so on. Once we have constructed a compatible sequence t1 . . . tl, we can extract a linear extension π of cost γl by setting π = tc(ρ ∪ τ1 ∪ . . . τl). This description gives rise to the following theorem.

Theorem 8. Let ρ ⊆ C × C, let n = |C|, let w be the pathwidth of the cocomparability graph of ρ, and c : C×C → [m]0 be a cost function. Then, one can compute an optimal solution in time O (w!O(1) · n · log(n · m)).

Now, leveraging on Lemma 6 and Lemma 7, we will devise a fixed-parameter tractable algorithm for DIVERSECO parameterized by solution imperfection, number of solutions, scatteredness, and pathwidth of the cocomparability graph of the input partial order. Let ρ be a partial order and P = (B1, B2, . . . , Bl) be a ρ-consistent path decomposition of Gρ of width w.

Definition 9. Let p ∈ [l], and f : Pp → N. Then, we let Ip(f, δ) be the set of all tuples of the form

where ∂ ∈ [d+1]0 , for each 1 ≤ i < j ≤ r, ξ{i,j} ∈ [s]0 , and for each i ∈ [r], (Si , τ i , γ i ) is a triple in Tp(f, δ).

Intuitively, ((Si , τ i , γ i ))i∈[r] are r partial linear extensions, ∂ will be the diversity of the r partial linear extensions and ξ will be the distance between all pairs of the r partial linear extensions. A diversity-compatible sequence is a sequence of the form

where for each i ∈ [r], (Si1 , τ i1 , γ i1 ) . . . (Si l , τ i l , γ i l ) is a compatible sequence and for each p ∈ [l - 1], ∂p keeps track of the amount of diversity observed up to position p, ξ p {i,j} keeps track of the distance between partial solutions i and j.

A diversity-compatible sequence is a representation of r solutions for an instance (ρ, c, r, δ, d, s) of DIVERSE-CO. Intuitively, computing such a sequence corresponds to computing r compatible sequences in parallel, by processing the given path decomposition from left to right, while using an additional register to keep track of the overall diversity at each time step and all the pairwise distances.

Theorem 10. Let ρ ⊆ C × C, let n = |C| and w be the pathwidth of the cocomparability graph of ρ, and c : C×C → [m]0 be a cost function. Then, one can determine whether ρ admits r linear extensions π1, . . . , πr at distance at most δ from the optimum, diversity at least d, and scatteredness at least s in time O ((w! · δ)O(r) · sr2 · d · n · log(n2 · m)).

By combining Theorem 8 with our reduction from KRA to CO, we have an FPT algorithm for KRA, parameterized by solution imperfection, number of solutions, scatteredness, and unanimity width (Corollary 11).

Corollary 11. Let Π be a list of m partial votes over a set of n candidates C. Let w be the unanimity width of Π. Given Π and non-negative integers δ, r, s and d, one can determine in time O ((w! · δ)O(r) · sr2 · d · n · log(n2 · m)) whether there is a set R = {π1, . . . , πr} of r linear orders on C such that the Kemeny score for each order πi is at distance at most δ of the optimum, and we find that KT-Div(R) ≥ d and that scatteredness is at least s.

6 Sub-Exponential Time Algorithm for PCO

For special cases of PCO, such as those arising from KRA or the graph-drawing problem OSCM, single-exponential subexponential time algorithms have been known, i.e., algorithms with running times of the form O∗ (2O(√k) ). In contrast, for the more general problem of PCO, only algorithms with running time O∗ (k√k ) were known before, where k is the cost parameter [Fernau et al., 2014]. Here, we prove that PCO also admits algorithms of the formO∗ (2O(√k) ), by making use of several structural insights for cocomparability graphs. More precisely, we prove the following theorem.

Theorem 12. Given a partial order ρ ⊆ C × C and a cost function c : C × C → N, one can solve a PCO instance (ρ, c, k) in time |C| · 2O(√k) +O(|C|2 · log(k)).

Our main technical result of this section is the following.

Lemma 13. Let G be a C≥5-free graph, let mbe the number of edges of G. Then, we have m = Ω(tw(G)2 ).

By combining Lemma 13 with the fact that treewidth equals pathwidth for cocomparability graphs and with the fact that cocomparability graphs are C≥5-free, we get the following lemma.

Lemma 14. Let G be a cocomparability graph and let m be the number of edges of G. Then, m = Ω(pw(G)2 ).

Now, in a PCO instance, each edge contributes at least 1 to the cost of any solution. Therefore, if a solution has cost at most k, then the cocomparability graph of the input partial order can have at most k edges. Therefore, this observation, together with Lemma 14 yields the following lemma.

Lemma 15. Let (ρ, c, k) be an YES-instance of PCO. Then, pw(Gρ) = O(√k).

To get the running time of Theorem 12, we need to either compute a ρ-consistent path decomposition of width at most O(√k), or to trigger an early rejection. For this, we will use the following lemma which is based on Lemma 3.

Lemma 16. There is a polynomial-time algorithm that takes an instance of (ρ, c, k) of PCO as input, and either constructs a ρ-consistent path decomposition of the graph Gρ of width O(√k), or answers that this instance is a NO-instance.

In Section 5, in order to define our algorithm for DIVERSECO, we first devised a simpler algorithm for the singlesolution version of CO, that could be used as a building block for the diverse algorithm. It turns out that if our only goal is to solve the single-solution version of CO, then the basic algorithm developed in Section 5 can be optimized, to become a single-exponential time algorithm parameterized by the pathwidth of the cocomparability graph of the input order. More precisely, we have the following lemma.

Lemma 17 ([Arrighi et al., 2020] (Theorem 1)). Given an instance (ρ, c, k) of CO and a ρ-consistent path decomposition P of the graph Gρ, one can solve this instance in time |C| · 2O(pw(Gρ)) · log(k) +O(|C|2 · log(k)).

Now we are ready to prove the statement of Theorem 12. Given an instance (ρ, c, k) of PCO, we apply the algorithm stated in Lemma 16. This algorithm either determines that the instance is a NO-instance, or constructs a ρ-consistent path decomposition P of Gρ of width O(√k). In the first case, we are done and simply answer NO. Otherwise, we give both the instance (ρ, c, k) and the decomposition P to the algorithm stated in Lemma 17 to determine in time |C| · 2O(√k) +O(|C|2 · log(k)) whether (ρ, c, k) is a YESor a NO-instance of PCO. In case this is a YES-instance, the algorithm also constructs a linear extension of ρ of cost at most k. This concludes the proof of Theorem 12.

Acknowledgements

Emmanuel Arrighi acknowledges support from the Research Council of Norway (Grant no. 274526) and from IS-DAAD (Grant no. 309319)). Henning Fernau acknowledges support from DAAD PPP (Grant no. 57525246)). The research of Daniel Lokshtanov is supported by BSF award 2018302 and NSF award CCF-2008838. Mateus de Oliveira Oliveira acknowledges support from the Research Council of Norway (Grant no. 288761), IS-DAAD (Grant no. 309319) and Sigma2 Network (NN9535K). Petra Wolf acknowledges support from DFG project FE 560/9-1 and DAAD PPP (Grant no. 57525246).