Diversity of Solutions: An Exploration Through the Lens of Fixed-Parameter Tractability Theory

1 Introduction

In a typical combinatorial optimization problem we are given a large space of potential solutions and an objective function. The task is to find a solution which maximizes or minimizes the objective function. In many situations of practical relevance, however, it does not really help to get just one optimal solution; it would be much better to have a small, but sufficiently diverse collection of sufficiently good solutions. Given such a small list of good solutions we can select one which is best for our purpose, perhaps by taking into account external factors-such as aesthetical, political, or environmentalwhich are difficult or even impossible to formalize. An early, illustrative example is the problem of generating floor plans for evaluation by an architect [Galle, 1989].

Solution diversity is already a fundamental concept in many computational tasks. Take for instance a web search. Here, we do not want to find the one website that 'optimally fits' the search term, neither a ranking of a small number of

'best fits', but what is desirable is a diverse set of websites that fit the search term reasonably well.

This notion has also been applied to solution sets of various types of combinatorial problems. For instance, the works [Glover et al., 2000] and [Hebrard et al., 2005; Hebrard et al., 2007] seek to find solution sets to mixed integer programming problems and constraint satisfaction problems, respectively, that are diverse. In other words, the solutions are far apart from each other in some mathematical notion of distance. We refer to [Petit and Trapp, 2019] for a timely overview of the subject.

From a complexity-theoretic perspective, there are two immediate barriers to this approach. The first is that most combinatorial problems are already NP-hard when asking only for a single solution. The second is that the very basic MAXIMUM DIVERSITY problem which given a set of n elements in a metric space and an integer k < n, asks for a size-k subset of the elements such that the sum of the pairwise distances is maximized, is NP-hard as well [Kuo et al., 1993]. The theory of fixed-parameter tractability [Downey and Fellows, 2013] provides a powerful framework to overcome these barriers. The key goal is to identify a secondary numerical measure of the inputs to an (NP-hard) computational problem, called the parameter, and to provide algorithms in whose runtime the combinatorial explosion is restricted to the parameter k. More formally, a problem is fixed-parameter tractable (FPT), if it can be solved in time f(k) · nc , where f is a computable function, n the input size and c a fixed constant. On instances where the parameter value is relatively small, FPT-algorithms are efficient. In an application context, we are naturally concerned with finding small diverse sets of solutions, since the aim is to provide the user with a few alternatives that can then be compared manually. Therefore, the number of requested solutions is an ideal candidate for parameterization.

In this work, we propose to study the notion of solution diversity from the perspective of fixed-parameter tractability theory. We demonstrate the theoretical feasibility of this paradigm by showing that diverse variants of a large class of parameterized problems admit FPT-algorithms. Specifically, we consider vertex-problems on graphs, which are sets of pairs (G, S) of a graph G and a subset S of its vertices that satisfies some property. For instance, in the VERTEX COVER problem, we require the set S to be a vertex cover of G (i.e. S has to contain at least one endpoint of each edge of G). One consequence of our main result which we discuss below in more detail is that the diverse variant of VERTEX COVER, asking for r solutions, is FPT when parameterized by solution size plus r.

Before we proceed, we would like to point out promising future applications of the Diverse FPT paradigm in AI. The VERTEX COVER problem itself naturally models conflictresolution: the entities are the vertices of the graph, and a conflict is represented by an edge. Now, a vertex cover of the resulting graph is a set of entities whose removal makes the model conflict-free. An example of a potential use of DIVERSE VERTEX COVER in a planning scenario is given in [Baste et al., 2019b]. In general, in planning and scheduling problems, a large amount of side information is lost or intentionally omitted in the modelling process. Some side information could make the model too complex to be solved, and other information may even be impossible to model. Offering the user a small number of good solutions to a more easily computable 'base model', among which they can hand pick their favorite solution, is a feasible alternative.

A Formal Notion of Diversity. We choose a very natural and general measure as our notion of diversity among solutions. Given two subsets S and S′ of a set V the Hamming distance between S and S′ is the number

We define the diversity of a list S1, . . . , Sr of subsets of V to be

We can now define the diverse version of vertex-problems:

Definition 1 (Diverse Problem). Let P1, . . . , Pr be vertexproblems, and let d ∈ N. We let

Intuitively, given vertex-problems P1, . . . , Pr and a graph G, we want to find subsets S1, . . . , Sr of vertices of G such that for each i ∈ {1, . . . , r}, Si is a solution for problem Pi on input G, and such that the list S1, . . . , Sr has diversity at least d. If all vertex-problems P1, . . . , Pr are the same problemP, then we write Divdr (P) as a shortcut to Divd (P1, . . . , Pr).

Diversity and Dynamic Programming. The treewidth of a graph is a structural parameter that quantifies how close the graph is to being a forest (i.e., a graph without cycles). The popularity of this parameter stems from the fact that many problems that are NP-complete on general graphs can be solved in polynomial time on graphs of constant treewidth. In particular, a celebrated theorem due to Courcelle [Courcelle, 1990] states that any problem expressible in the monadic second-order logic of graphs can be solved in polynomial time on graphs of constant treewidth. Besides this metatheorem, the notion of treewidth has found applications in several branches of Artificial Intelligence such as Answer Set Programs [Bliem et al., 2017], checking the consistency of certain relational algebras in Qualitative Spacial Reasoning [Bodirsky and W¨olfl, 2011], compiling Bayesian networks [Chavira and Darwiche, 2007], determining the winners of multiwinner voting systems [Yang and Wang, 2018], analyzing the dynamics of stochastic social networks [Barrett et al., 2007], and solving constraint satisfaction problems [J´egou et al., 2007]. A large number of these algorithms are in fact FPT-algorithms when treewidth is the parameter, i.e. they run in time f(t) · nc , where f is a computable function, t the treewidth of the input graph, n the number of its vertices, and c some fixed constant. Typically, such algorithms are dynamic programming algorithms which operate on a tree-decomposition in a bottom-up fashion by computing data from the leaves to the root.

Dynamic Programming Core Model. We introduce a formalism for dynamic programming based on a tree decomposition, which we call the Dynamic Programming Core model. This notion captures a large variety of dynamic programming algorithms on tree decompositions. We use the model to derive our main result (Theorem 10) which is a framework to efficiently-and automatically-transform treewidth-based dynamic programming algorithms for vertex-problems into algorithms for the diverse versions of these problems. More precisely, we show that if P1, . . . , Pr are vertex-problems where for each i ∈ {1, . . . , r}, Pi can be solved in time fi(t) · nO(1) , then Divd (P1, . . . , Pr) can be solved in time (∏ri=1 fi(t)) · nO(1) . In particular, if a vertex-problem P can be solved in time f(t) · nO(1) , then its diverse version Divdr (P) can be solved in time f(t)r · nO(1) . The surprising aspect of this result is that the running time depends only polynomially on d (which is at most r2n), while a na¨ıve dynamic programming algorithm would have a runtime of dO(r2 ) · f(t)r · nO(1) .

Discussion of the DiversityMeasure. Various measures of diversity have been used, studied, and compared in different areas of computer science. We choose the sum of the Hamming distances over all pairs of elements for this work. This measure is commonly used for population diversity in genetic algorithms [Gabor et al., 2018; Wineberg and Oppacher, 2003]. Nonetheless, we would like to point out that it has some weaknesses. For instance, taking many copies of two disjoint solutions yields a relatively high diversity value, and such a solution set is not 'diverse' from an intuitive point of view. We refer to [Baste et al., 2019b] for a more detailed discussion. Another natural measure using the Hamming distance is the minimum Hamming distance over all pairs in a set, as it is done e.g. in [Hebrard et al., 2005; Hebrard et al., 2007]. We would like to point out that a straightforward adaptation of our algorithmic framework would result in a running time of dO(r2 ) ·f (t)r ·nO(1) , where d is the diversity, r the number of solutions, and t the treewidth. This remains FPT only when the diversity d is an additional component of the parameter, or when d is naturally upper bounded by t and r. Consider for instance DIVERSE VERTEX COVER, asking for vertex covers of size at most k. In any nontrivial instance, t is at most k, and the Hamming distance between two solutions is at most 2k, therefore we may assume that d ≤ 2k. This implies that DIVERSE VERTEX COVER can be solved in time 2O(r2 log k)+kr · nO(1) using the minimum Hamming distance as a diversity measure.

Related Work. The above mentioned MAXIMUM DIVERSITY problem has applications in the generation of diverse query results, see e.g. [Gollapudi and Sharma, 2009; Abbassi et al., 2013]. Besides mixed integer programming [Glover et al., 2000; Danna and Woodruff, 2009; Petit and Trapp, 2015], binary integer linear programming [Greistorfer et al., 2008; Trapp and Konrad, 2015] and constraint programming [Hebrard et al., 2005; Hebrard et al., 2007], diverse solution sets have been considered in SAT solving [Nadel, 2011], recommender systems [Adomavicius and Kwon, 2014], routing problems [Schittekat and S¨orensen, 2009], answer set programming [Eiter et al., 2013], and decision support systems [Løkketangen and Woodruff, 2005; Hadˇzi´c et al., 2009].

Several details that have been omitted due to space restrictions can be found in the full version [Baste et al., 2019a].

2 Preliminaries

For positive integers a, b ; a < b we use [a, b] to denote the set {a, a + 1, . . . , b}. We use V (G) and E(G), respectively, to denote the vertex and edge sets of a graph G. For a tree T rooted at q we use Tt to denote the subtree of T rooted at a vertex t ∈ V (T ). A rooted tree decomposition of a graph G is a tuple D = (T, q, X), where T is a tree rooted at q ∈ V (T) and X = {Xt | t ∈ V (T)} is a collection of subsets of V (G) such that:

• ⋃t∈V (T ) Xt = V (G),
• for every edge {u, v} ∈ E(G), there is a t ∈ V (T) such that {u, v} ⊆ Xt, and
• for each {x, y, z} ⊆ V (T) such that z lies on the unique path between x and y in T , Xx ∩ Xy ⊆ Xz .

We say that the vertices of T are the nodes of D and that the sets in X are the bags of D. Given a node t ∈ V (T), we denote by Gt the subgraph of G induced by the set of vertices ⋃s∈V (Tt) Xs. The width of a tree decomposition D = (T, q,X) is defined as maxt∈V (T) |Xt| - 1. The treewidth of a graph G, denoted by tw(G), is the smallest integer w such that there exists a rooted tree decomposition of G of width at most w. The rooted path decomposition of a graph is a rooted tree decomposition D = (T, q, X) such that T is a path and q is a vertex of degree 1. The pathwidth of a graph G, denoted by pw(G), is the smallest integer w such that there exists a rooted path decomposition of G of width at most w. Note that in a rooted path decomposition, every node has at most one child.

For convenience we will always assume that the bag associated to the root of a rooted tree decomposition is empty. For a node t ∈ V (T) we use δD(t), or δ(t) when D is clear from the context, to denote the number of children of t in the tree T. For nodes t and t′ of V (T) where t′ is the parent of t we use forg(t) = Xt \ Xt′ to denote the set of vertices of G which are forgotten at t. By convention, for the root q of T, we let forg(q) = ∅. For t ∈ V (T) we denote by new(t) the set Xt \ ⋃δ(t) i=1 Xti where t1, . . . , tδ(t) are the children of t. Given a rooted tree decomposition D of a graph G one can obtain, in linear time, a tree decomposition (T, q, X) of G of the same width as D such that for each t ∈ V (T), δ(t) ≤ 2 and |new(t)| ≤ 1 [Cygan et al., 2015]. From now on we assume that every rooted tree decomposition is of this kind.

3 A First Example: Diverse Vertex Cover

The main result of this paper is a general framework to automatically translate tree-decomposition-based dynamic programming algorithms for vertex-problems into algorithms for the diverse versions of these problems. We develop this framework in Section 4. In this section we illustrate the main techniques used in this conversion process by showing how to translate a tree-decomposition-based dynamic programming algorithm for the VERTEX COVER problem into an algorithm for its diverse version DIVERSE VERTEX COVER. Given a graph G and three integers k, r, and d, the DIVERSE VERTEX COVER problem asks whether one can find r vertex covers in G, each of size at most k, such that their diversity is at least d. Our algorithm for this problem runs in 2O(kr) |V (G)| time.

3.1 Incremental Computation of Diversity

Recall that we defined the diversity of a list S1, S2, . . . , Sr of subsets of a set V to be

We will now describe a way to compute the diversity Div(S1, . . . , Sr) in an incremental fashion, by incorporating the influence of each element of V in turn. For each element v ∈ V and each pair of subsets S, S′ of V , we define γ(S, S′ , v) to be 1 if v ∈ (S \ S′ ) ∪ (S′ \ S), and to be 0 otherwise. Intuitively, γ(S, S′ , v) is 1 if and only if the element v contributes to the Hamming distance between S and S′ . Given this definition we can rewrite HamDist(S, S′ ) as

and the diversity of a list S1, . . . , Sr of subsets of V as

Now, if we define the influence of v on the list S1, . . . , Sr as I(S1, . . . , Sr, v) = |{ℓ : v ∈ Sℓ}| · |{ℓ : v ̸∈ Sℓ}|, then we have that Div(S1, . . . , Sr) = ∑v∈V I(S1, . . . , Sr, v).

3.2 FromVertex Cover to Diverse Vertex Cover

We now solve DIVERSE VERTEX COVER using dynamic programming over a tree decomposition of the input graph.

Let (G, k, r, d) be an instance of DIVERSE VERTEX COVER and let D = (T, q,X) be a rooted tree decomposition of G. For each node t ∈ V (T ), we define the set

This set It, t ∈ V (T), is such that the partial solutions we will construct for the node t will always be a subset of It. Note that for each t ∈ V (T), |It| ≤ (2|Xt| ·(k+1))r ·(d+1). Now, our dynamic programming algorithm for DIVERSE VERTEX COVER consists in constructing for each t ∈ V (T) a subset Rt ⊆ It as follows. Let t be a node in V (T) with children t1, . . . , tδ(t). We recall that, by convention, this set of children is of size 0, 1, or 2. We let Rt be the set of all tuples ((S1, s1), . . . , (Sr, sr), ℓ) ∈ It satisfying the following additional properties:

1. For each j ∈ [1, r], E(G[Xt \ Sj]) = ∅.
2. For each i ∈ [1, δ(t)] there exists a tuple ((Si1 , si1 ), . . . , (Sir , sir ), ℓi) in Rti such that
3. (a) Sj ∩Xti = Si j ∩Xt for each i ∈ [1, δ(t)] and each j ∈ [1, r],
4. (b) For each j ∈ [1, r], sj = |forg(t)∩Sj|+ ∑δ(t) i=1 sij ,
5. (c) and ℓ = min(d,m) where m = ∑v∈forg(t) I(S1, . . . , Sr, v) + ∑δ(t) i=1 ℓi.

Lemma 2. (G, k, r, d) is a YES-instance of DIVERSE VERTEX COVER if and only if there is a tuple ((S1, s1), . . . , (Sr, sr), ℓ) in Rq such that ℓ = d.

Proof. Using induction, one can see that for each t ∈ V (T), Rt is the set of every element of It such that, with Yt = Xt \ forg(t), there exists (̂ S1, . . . , ̂ Sr) ∈ V (Gt)r , that satisfies:

• for each i ∈ [1, r], ̂ Si is a vertex cover of Gt,
• for each i ∈ [1, r], ̂ Si ∩Xt = Si,
• for each i ∈ [1, r], |̂ Si \ Yt| = si, and
• min(d,Div(̂ S1 \ Yt, . . . , ̂ Sr \ Yt)) = ℓ.

As the root q of the tree decomposition D is such that Xq = ∅, we obtain that the elements in Rq are the elements ((∅, s1), . . . , (∅, sr), ℓ) of Iq such that there exists ( ̂ S1, . . . , ̂ Sr) ∈ V (G)r , that satisfy,

• for each i ∈ [1, r], ̂ Si is a vertex cover of Gt,
• for each i ∈ [1, r], |̂ Si| = si ≤ k, and
• min(d,Div(̂ S1, . . . , ̂ Sr)) = ℓ.

As such, a tuple (̂ S1, . . . , ̂ Sr) of subsets of V (G) is a solution of DIVERSE VERTEX COVER if and only if ℓ ≥ d, the lemma follows.

Theorem 3. Given a graph G, integers k, r, d, and a rooted tree decomposition D = (T, q, X) of G of width w, one can determine whether (G, k, r, d) is a YES-instance of DIVERSE VERTEX COVER in time

Proof. Let us analyze the time needed to compute Rq. We have that, for each t ∈ V (D), |It| ≤ (2·|Xt| ·(k+1))r ·(d+1). Note that given I1, . . . , Iδ(t) be elements of Rt1 , . . . ,Rtδ(t) , there are at most 2|new(t)|·r ≤ 2r ways to create an element I of Rt by selecting, or not the (potential) new element of Xt for each set Si, i ∈ [1, r]. The remaining is indeed fixed by I1, . . . , Iδ(t). Thus, Rt can be computed in time O(r·|Xt|·2r · ∏δ(t) i=1 |Rti |), where the factor r · |Xt| appears when verifying that the element we construct satisfy ∀j ∈ [1, r] ,E(G[Xj \ Sj ]) = ∅. As we need to compute Rt for each t ∈ V (D) and that |V (D)| = O(n) and we can assume that δ(t) ≤ 2 for each t ∈ V (D), the theorem follows.

Remark 4. Given a graph G and a vertex cover Z of G of size k, one can find a rooted path decomposition D = (T, q, X) of G of width k, in linear time.

This can be done by considering the bags Z ∪ {v} for each v ∈ V (G) in any fixed order. Thus, from Theorem 3, we get the following corollary, which establishes an upper bound for the running time of our dynamic programming algorithm for DIVERSE VERTEX COVER solely in terms of the size k of the vertex cover, the number r of requested solutions, and the diversity d.

Corollary 5. DIVERSE VERTEX COVER can be solved on an input (G, k, r, d) in time O((2k+2 · (k+1))r ·d·k · r · |V (G)|).

4 Computing Diverse Solutions using the Dynamic Programming Core model

In this section we show that the process illustrated in Section 3, of lifting a dynamic programming algorithm for a combinatorial problem to an algorithm for its diverse version, can be generalized to a much broader context. As a first step, we introduce the notion of dynamic programming core, a suitable formalization of the intuitive notion of tree-width based dynamic programming that satisfies three essential properties. First, this formalization is general enough to be applicable to a large class of combinatorial optimization problems. Second, this formalization is compatible with the notion of diversity, in the sense that the lifting of an algorithm for a problem to an algorithm for the diverse version of this problem can be done automatically, without requiring human ingenuity. Third, the resulting lifted algorithm is fast when compared with the original one. In particular, the running time of the resulting algorithm is polynomial on the diversity parameter. This is a highly desired property, since this allows our framework to be applied in the context where the sizes of the considered solution sets are not bounded.

Below, we let G be the set of simple, undirected graphs whose vertex set is a finite subset of N. We say that a subset P ⊆ G is a graph problem. Intuitively, a dynamic programming algorithm working on tree decompositions may be understood as a procedure that takes a graph G ∈ G and a rooted tree decomposition D of G as input, and constructs a certain amount of data for each node of D. The data at node t is constructed by induction on the height of t, and in general, this data is used to encode the existence of a partial solution on the graph induced by bags in the sub-tree of D

rooted at t. In the below definition, this is captured in the relation ProcessC,G,D(t). Such an algorithm accepts the input graph G if the data associated with the root node contains a string belonging to a set of accepting strings, captured below in the set AcceptC,G,D. We formalize this intuitive notion in the following concept of dynamic programming core.

Definition 6 (Dynamic Programming Core). A dynamic programming core is an algorithm C that takes a graph G ∈ G and a rooted tree decomposition D of G as input, and produces the following data.

• A finite set AcceptC,G,D ⊆ 2{0,1}∗ .
• A finite set ProcessC,G,D(t) ⊆ (2{0,1}∗)δ(t)+1 for each t ∈ V (D).

We let τ(C,G,D) be the overall time necessary to construct the data associated with all nodes of D. The size of C on a pair (G, D) is defined as

Next, we define the notion of a witness for a dynamic programming core. Intuitively such witnesses are certificates of existence of a solution.

Definition 7. Let C be a dynamic programming core, G be a graph in G, and D = (T, q, X) be a rooted tree decomposition of G. A (C,G,D)-witness is a function α : V (T) → {0, 1}∗ such that the following conditions are satisfied.

1. For each t ∈ V (T), with children t1, . . . , tδ(t), (α(t), α(t1), . . . , α(tδ(t))) ∈ ProcessC,G,D(t).

Using the notion of witness, we define formally what it means for a dynamic programming core to solve a combinatorial problem.

Definition 8. We say that a dynamic programming core C solves a problem P if for each graph G ∈ G, and each rooted tree decomposition D of G, G ∈ P if and only if a (C, G, D)- witness exists.

Theorem 9. Let P be a graph problem and C be a dynamic programming core that solves P. Given a graph G ∈ G and a rooted tree decomposition D of G, one can determine whether G ∈ P in time O (∑t∈V (T ) |ProcessC,G,D(t)| + τ (C, G, D)).

4.1 Dynamic Programming Cores for Vertex Problems

Let C be a dynamic programming core. A C-vertexmembership function is a function ρ : N × {0, 1}∗ → {0, 1} such that for each graph G, each rooted tree decomposition D = (T, q,X) of G and each (C,G,D)-witness α, it holds that ρ(v, α(t)) = ρ(v, α(t′ )) for each edge (t, t′ ) ∈ E(T) and each vertex v ∈ Xt ∩ Xt′ . Intuitively, if G is a graph and D is a rooted tree decomposition of G, then a C-vertexmembership together with a (C,G,D)-witness, provide an encoding of a subset of vertices of the graph. More precisely,

be this encoded vertex set. Given a C-vertex-membership function ρ, we let ˆ ρ : {0, 1}∗ → 2N be the function that sets ˆ ρ(w) = {v ∈ N | ρ(v, w) = 1} for each w ∈ {0, 1}∗ .

Let P be a vertex-problem, C be a dynamic programming core, and ρ be a C-vertex-membership function. We say that (C, ρ) solves P if for each graph G ∈ G, each subset S ⊆ V (G), and each rooted tree decomposition D, (G, S) ∈ P if and only if there exists a (C,G,D)-witness α such that S = Sρ(G, D, α).

The following theorem is the main result of this section. It shows how to transform dynamic programming cores for problems P1, . . . , Pr into a dynamic programming core for the problem Divd (P1, . . . , Pr).

Theorem 10. Let P1, . . . , Pr be vertex-problems, let (Ci, ρi) be a dynamic programming core for Pi, and let d be an integer. The problem Divd (P1, . . . , Pr), on graph G with rooted tree decomposition D = (T, q, X), can be solved in time

4.2 An Illustrative Application of Theorem 10

In this subsection we show how to apply Theorem 10 in the construction of an improved dynamic programming algorithm for DIVERSE VERTEX COVER. The first thing to do is to describe a dynamic programming core CVC for k-VERTEX COVER. Given a graph G and a rooted tree decomposition D = (T, q,X), this dynamic programming core CVC pro-

Provided the width of the decomposition is at most k, this can be done in time O((2k+1 · (k + 1))δ(t) · k · δ(t)) for each t ∈ V (T), where the factor k · δ(t) appears as we need the conditions E(G[Xt \ S]) = ∅ and ∀i ∈ [1, δ(t)] , Si ∩ Xt = S ∩Xti to be verified. It is easy to verify that CVC is a dynamic programming core for the VERTEX COVER problem. As described in Remark 4, we know that we can construct a rooted path decomposition of G of width k. We are now considering this rooted path decomposition. Thus, for each t ∈ V (T), |ProcessC,G,D(t)| ≤ 2 · 2k+1 · (k + 1). By Theorem 10, we obtain the following corollary, improving Corollary 5.

Corollary 11. DIVERSE VERTEX COVER can be solved on an input (G, k, r, d) in time

Note that we obtain a slightly better running time than for Corollary 5. This is due to the fact that verifying the properties E(G[Xt \ S]) = ∅ and ∀i ∈ [1, δ(t)] , Si ∩Xt = S ∩Xti is done when constructing CVC and not when constructing C. Note also that, formally, we need to construct CVC r times but as it is r times the same, we do the operation only once.

5 Diversity in Kernelization

Another key concept in the field of parameterized complexity is that of a kernelization algorithm [Fomin et al., 2019]. We have obtained some parallel results about the kernelization complexity of diverse problems as well that we want to briefly sketch in this section. A polynomial kernel of a parameterized problem is a polynomial-time algorithm that given any instance either solves it, or constructs in polynomial time an equivalent 1 instance whose size is polynomial in the parameter. It is known that a parameterized problem is FPT if and only if it has a (not necessarily polynomial) kernel, and a natural step after proving a parameterized problem to be FPT is to decide whether or not it has a polynomial kernel.

We show that the diverse variants of several basic problems parameterized by the number of requested solutions plus solution size admit polynomial kernels as well. This is done via a variant of the recently introduced notion of loss-less kernels [Carbonnel and Hebrard, 2016] which are a special class of kernelizations that - very roughly speaking - for each but polynomially many bits of the input can either decide whether it has to be part of every solution or if it may be added to a solution without 'destroying' it.

For instance, consider the famous Buss kernel for VERTEX COVER [Buss and Goldsmith, 1993]: Given a graph G and an integer k, we want to decide if G has a vertex cover of size k. Each vertex of degree at least k + 1 must be in each solution. Otherwise, we have to include its (at least) k + 1 neighbors, exceeding the size constraint. On the other hand, each isolated (degree-0) vertex can be included in a vertex cover without destroying it, but it does not cover any edge. In the 'non-diverse' variant, we may remove these isolated vertices, and in the diverse variant, we have to keep some of them - they may be used to increase diversity - however, polynomially (in k and r) many such vertices suffice. Via such arguments, we obtain the following result about polynomial kernels of diverse problems.

Theorem 12. The following diverse subset minimization problems parameterized by k + r admit polynomial kernels:

• DIVERSE VERTEX COVER, on O(k(k + r)) vertices;
• DIVERSE d-HITTING SET for fixed d, on O(kd + kr) vertices;
• DIVERSE POINT LINE COVER, on O(k(k + r)) points;
• DIVERSE FEEDBACK ARC SET IN TOURNAMENTS, on O(k(k + r)) vertices.

6 Conclusion

In this work, we considered a formal notion of diversity of a set of solutions to combinatorial problems in the setting of parameterized algorithms. We showed how to emulate treewidth based dynamic programming algorithms in order to solve diverse problems in FPT time, with the number r of requested solutions being an additional parameter.

1 Meaning that the constructed instance is a YES-instance if and only if the original instance was.

This line of research is now wide open, with many natural questions to address. As all our results are of a positive nature, we ask: when can diversity be a source of hardness? Concretely, a natural target in parameterized complexity would be to identify a parameterized problem Π that is FPT, however DIVERSE Π being W[1]-hard when r is an additional parameter. For positive results, an interesting research direction would be to generalize our framework for diverse problems to other well studied width measures for graphs, as well as to other structures, such as matroids.

In this work, we considered the sum of all pairwise Hamming distances of a set as a measure of diversity. As pointed out, this measure has some weaknesses, and another widely used measure is the minimum Hamming distance. In this setting, we only obtain FPT-results when the diversity is bounded by a function of the treewidth and the number of solutions, but not in general. So, a natural follow-up question is whether or not we can obtain FPT-results under the minimum Hamming distance, even if the diversity is unbounded.

Acknowledgements

M. Fellows, F. Rosamond, and G. Philip acknowledge support from the Research Council of Norway grant "Parameterized Complexity for Practical Computing (PCPC)" (NFR, no. 274526). M. Fellows, F. Rosamond, L. Jaffke, M. de Oliveira Oliveira, and G. Philip acknowledge support from the Trond Mohn Foundation (TMS). J. Baste acknowledges support from the German Research Foundation (DFG, no. 388217545). T. Masaˇr´ık acknowledges support from the European Research Council (ERC, no. 714704), and from Charles University's grants GAUK 1514217 and SVV-2017260452. He recently started a postdoc at Simon Fraser University, Canada. M. de Oliveira Oliveira acknowledges support from the Research Council of Norway (NFR, no. 288761). G. Philip acknowledges support from the NFR grants "MULTIVAL" and "CLASSIS", and from the European Research Council (ERC, no. 819416).