Well-Structured Committees

1 Introduction

Given a set of candidates and a collection of voters - each expressing her preferences over the candidates - a natural task is to select a committee of candidates that would correspond to the voter opinions. The study of selecting good committees is usually approached through the subfield of computational social choice [Brandt et al., 2016; Endriss, 2017] known as multiwinner elections [Faliszewski et al., 2017a]). This study has proven to be quite fruitful: Among other topics, researchers have studied the complexity of winner determination for various multiwinner voting rules (see, e.g., [Procaccia et al., 2008; Brill et al., 2019]); the complexity of related manipulative actions (see, e.g., [Procaccia et al., 2007; Faliszewski et al., 2017b]); few frameworks of such rules (see, e.g., [Faliszewski et al., 2016; Faliszewski et al., 2018]); and certain related axiomatic properties (see, e.g., [Elkind et al., 2017; Aziz et al., 2017a]).

One aspect that is usually overlooked is the possibility of certain interactions and dependencies between candidates. For example, some candidates might be incompatible to a certain extent, perhaps due to different personalities; or some candidates might possess more efficient means of communication among them, allowing them to cooperate more effectively than others (we explain this in detail in the paragraph "Candidate Networks and Graph Properties"). Indeed, some papers do take such externalities between candidates into account; e.g., Bredereck et al. [2018] (and others) study a setting in which candidates have attributes (e.g., occupation), and the task is to select a committee that is diverse enough. Izsak et al. [2018] study a setting of a candidate network modeling certain submodularities and supermodularities between groups of candidates. Talmon [2018] studies certain related interactions wrt a voter network (and not a candidate network).

Here we consider the following setting (formal definitions are given in the paragraph "Voter Preferences and Candidate Networks"): Given a graph over a set C of m candidates - a candidate graph; a collection of n ordinal votes over the same set C (that is, each of the n corresponding voters ranks all the m available candidates) - a preference profile; and a desired committee size k, we are interested in finding a committee that is "good" with respect to both (1) the voter preferences and (2) the candidate graph. Our setting is parameterized by both (1) a multiwinner voting rule R, which takes the collection of n ordinal votes and assigns a score to each possible committee (a committee is a subset of C containing exactly k candidates) based on the voter preferences alone and (2) a graph property Q, which takes the candidate graph and look for each possible committee (corresponding to a vertex subset in the graph) that satisfies property Q based on the candidate graph alone. For specific R and Q, we are interested in designing efficient algorithms that find a committee with the highest R-score possible among all committees satisfying Q. We describe our specific R's and Q's further on.

While, as we show, the combinatorial problems we study here are generally intractable, we nevertheless develop several efficient algorithms for certain special cases of these problems. In particular, we discuss certain problem parameters that allow for efficient parameterized algorithms; as well as consider some domain restrictions and various restrictions on the candidate graphs that allow for efficient algorithms for these cases. As a added benefit, some of our algorithms solve known graph problems such as BUDGETED MAXIMUM WEIGHT TERMINAL STEINER TREE (BUDGMAXWT-TST) and MAXIMUM NODE-WEIGHTED k-TREE

(MAX-NODEWT-k-TREE), thus our results are of separate interest wrt these problems.

Voter Preferences and Multiwinner Rules

In multiwinner elections the task is to select a committee that best corresponds to the voter preferences. Formally, a multiwinner election consists of a set C of m candidates, a collection of n ordinal votes (i.e., rankings) of C, and a committee size k. A multiwinner voting rule takes a multiwinner election as input and outputs a set of k candidates from C as a winning committee.

Many multiwinner voting rules are studied in the literature, out of which we consider the following: Under k-Borda, a voter assigns a score of m - i to a candidate she ranks at the ith position, and the winning committee consists of the k candidates with the highest sum of scores over the voters; under Chamberlin-Courant (CC), a voter assigns a score of m-i to a committee out of which the candidate she ranks the highest (referred to as the voter's representative) is at position i, and the winning committee is of the highest score; under Gehrlein stability (GS), a committee S is chosen such that no committee member c ∈ S has some c′ /∈ S such that more voters rank c′ higher than c than vice versa; this is known as weak Gehrlein stability in the literature [Aziz et al., 2017b], we omit weak just for simplicity.

We chose k-Borda, CC, and GS as they are all well-studied and form a diverse set of multiwinner rules: In particular, following the discussion of Faliszewski et al. [Faliszewski et al., 2017a], k-Borda is polynomial-time computable and an archetypal rule for selecting individually accepted candidates, CC is NP-hard and aims at identifying committees echoing all views present in society, and GS is a generalization of single-winner Condorcet-consistent rules, and it is a natural Condorcet-based multiwinner voting rule.

Candidate Networks and Graph Properties

We put voter preferences aside for a moment, and consider interactions and dependencies between candidates; consider the candidate network, containing one vertex c for each candidate c ∈ C (we thus use candidates and vertices interchangeably):

• Consider a scenario of project team formation. In the election, voters are not people, but the skills required for the project. All the candidates are ranked on the basis of their skills. Now, we would like to form a team which is not only good from the perspective of skills, but also team members should not distrust and dislike each other, as this will affect the project. This can be captured by a candidate network in which there is an edge between two vertices if the corresponding candidates are "incompatible". Such compatibility should also be considered in parliamentary elections, which is usually ignored. A related situation is if there is an edge between two candidates if they are too "similar", and we wish to choose a diverse committee to perform, say, a task for which candidates with different skills are needed. In these cases, it is natural to select a committee that corresponds to an Independent Set of size k in the candidate network (i.e., a set of pairwise nonadjacent vertices). 1

1 One might also settle for committees containing limited number edges; independent set takes this view to the extreme.

· Consider a scenario in which a "good" communication is required between committee members, for example, in a rescue team. Here, again candidates are ranked on the basis of their skills. This can be captured by a candidate network in which there is an edge between two vertices if there is some communication link between the corresponding candidates. Another scenario is choosing positions for routers in a network: one shall ensure router connectivity, while also taking voter preferences into consideration, corresponding to some external features of each router. To foster efficient communication, it would be natural to select a committee that is Connected (i.e., corresponds to a connected subgraph) in the candidate graph.

Voter Preferences and Candidate Networks.

In this paper we combine the two aspects: Voter preferences - modeled via a multiwinner voting rule and candidate networks - modeled via a graph property.

Formally, we study the following problem, parameterized by a graph property Q (a property that is either satisfied by a subgraph or not) and a multiwinner voting rule R.

Definition 1. In the (Q,R)-SCS problem, we are given a set of m candidates, C, a collection of n ordinal votes over C, the committee size k, a candidate graph over C, and the desired score s; the goal is to decide if there exists a committee satisfying Q whose R-score is at least s.

We refer to the optimization version of (Q,R)-SCS, in which the goal is to find a committee with the highest score, as MAX-(Q, R)-SCS. GS is slightly different, as stable committees do not always exist; for GS we require the output committee to be Gehrlein stable, as in Q-GS, the goal is to find a stable committee also satisfying property Q.

Let (E,H, k, s) be an instance of (Q,R)-SCS, where E is a preference profile over candidates C and voter set V, H is a candidate graph, k is the size of committee, and s is the score. When Q is the property of "independence" (i.e., we require the winning committee to form an independent set in H), we refer to (Q, R)-SCS as the CONFLICT FREE-R (CFR) problem. Similarly, when Q is the property of "connectivity" (i.e., when we require that the winning committee be connected in H), we refer to (Q, R)-SCS as the CONNECTED-R (CONN-R) problem.

1.1 Initial Observations

First, we observe that (Q, R)-SCS indeed generalizes winner determination wrt R: In particular, if the candidate graph is empty, then any set of k vertices is an independent set; thus, (Q, R)-SCS is reduced to finding a k-sized committee wrt R. Similarly, if the candidate graph is a clique, then any set of k vertices is connected. (We write R also to refer to Winner Determination for R).

Observation 1. If R is NP-hard (W-hard wrt t), then CF-R is NP-hard (W-hard wrt t), even for empty candidate graphs; and CONN-R is NP-hard (W-hard wrt t), even when the candidate graph is a clique.

Since CC is NP-hard and W[2]-hard wrt k [Procaccia et al., 2008] and GS is NP-hard [Aziz et al., 2017c] and W[1]- hard wrt k [Gupta et al., 2019], using Observation 1 and the fact that (Q,R)-SCS is decidable, we have the following:

Corollary 1. CONN-CC (CF-CC) is NP-complete and W[2]-hard wrt k and CONN-GS (CF-GS) is NP-complete and W[1]-hard wrt k, even when the candidate graph is a clique (respectively, edgeless).

1.2 Paper Structure

Throughout, we study the CF-R and CONN-R problems for R ∈ {CC, k-Borda, GS}. As CC, GS, and finding an independent set of size k are all computationally intractable, we indeed expect most of our problems to be intractable. In fact even though both CONNECTIVITY and k-BORDA are polynomial-time solvable, separately, we nevertheless show that CONN-k-BORDA is NP-complete. We thus concentrate on various ways of breaking this computational intractability: In particular, we use parameterized complexity, domain restrictions (restricting voter preferences), and graph classes (restricting allowed candidate graphs).

We concentrate on natural election parameters, frequently studied in papers on parameterized complexity of computational social choice problems: The number of candidates, m, is frequently small - e.g., in most political elections; the number of voters, n, is sometimes small - e.g., when selecting a jury, judges for a talent competition, or board of directors (see, e.g., [Chen et al., 2015]); and the committee size, k, is small in many real-life scenarios such as in shortlisting tasks, parliamentary elections, and forming a rescue team.

We consider single-peaked profiles, unanimous profiles, and strongly unanimous profiles as domain restrictions; while single-peaked is probably the most popular domain restriction, the other two domain restrictions, though perhaps too restricted to be practically useful, nevertheless provide good insights on the combinatorics of our problems. Additionally, we study our problems on inputs where the candidate graph has a certain structure.

The paper is structured by problems: In Sections 2.1, 2.2, and 2.3 we study connected committees for CC, k-Borda, and GS, respectively; while in Sections 3.1, 3.2, and 3.3 we study conflict-free committees for CC, k-Borda, and GS, respectively. To give a full picture, Table 1 lists all our results. We highlight our most technically-involved results: Theorems 1, 4, and 13. As the table shows, we are able to identify several cases for which efficient algorithms exist for our problems. We mention that, while doing so, we also prove certain results regarding combinatorial problems on graphs that might be of independent interest. Some proof details are missing due to limited space. The notation O⋆ (f(k)) suppresses poly(n) factors.

2 Connected Committees

We study the complexity of finding connected committees.

2.1 Connected-CC

Here, we first give an FPT algorithm wrt n+k. Towards this, we first observe that in polynomial time, MAX-CONN-CC can be reduced to BUDG-MAXWT-TST 2 , in which given an edge-weighted graph G, a set of terminals T, and an integer t; we look for a maximum weight tree of size t containing each of the terminals as leaves, where the size of the tree in the reduced instance, that is t, is n + k. We design an FPT algorithm wrt t for BUDG-MAXWT-TST which can then be used to solve MAX-CONN-CC.

2 It is NP-hard (since TERMINAL STEINER TREE, in which we look for a minimum cost terminal Steiner tree, is NP-hard [Lin and Xue, 2002]).

Our FPT algorithm for BUDG-MAXWT-TST with tree size as the parameter relies on the following result; unlabeled graph is one in which the vertices are not named.

Proposition 1 ([Beyer and Hedetniemi, 1980; Otter, 1948]). There are tn = 2.956n non-isomorphic unlabeled trees on n vertices. Moreover, we can enumerate them in time O(tn).

Theorem 1. BUDG-MAXWT-TST is FPT wrt t. Consequently, MAX-CONN-CC is FPT wrt n + k.

Proof. Let (G, T, t) be the given instance of BUDGMAXWT-TST. Let T ⋆ be a solution to BUDG-MAXWTTST. Using Proposition 1 we enumerate all unlabeled trees Tul on t nodes. For each of these trees, if the number of its leaves is less than |T|, then we discard the tree and move to the next one. For each unlabeled tree Tul, we recast it as the MAX-EDGEWT-TREE-ISO problem as follows: Given an edge-weighted graph G and a tree Tul, we find a maximum edge-weighted tree in G that is isomorphic to Tul. For BUDGMAXWT-TST, we go through each of the unlabeled trees as a potential Tul and apply the algorithm for MAX-EDGEWTTREE-ISO with G and Tul as the input. This step takes 2.956t tO(1) time. By our choice we know that Tul has at least |T| leaves. We first guess an injective mapping from the terminals to the leaves of Tul (there are at most t|T| = 2O(t log t) guesses, in total). Let this mapping be g. Now our problem reduces to MAX-EDGEWT-TREE-ISO where some leaves are already labeled. This can be solved using the algorithm for kTREE [Fomin et al., 2016] in 2.6182t-|T| tO(1) time. (Note that the algorithm given in [Fomin et al., 2016] is for finding a minimum weight isomorphic copy. However, replacing minimum weight q-representative with maximum weight qrepresentative in that algorithm will yield the maximization version of the problem.) This implies that the total running time of our algorithm is upper bounded by the number of unlabeled trees on t vertices, the number of injective mapping from terminals to the leaves of Tul and the algorithm for MAX-EDGEWT-TREE-ISO, where the leaves are already labeled. Thus, the total time required is 2O(t log t) tO(1) . Thus, we can conclude that MAX-CONN-CC is FPT wrt n+k.

While CC is solvable in polynomial time for single-peaked (SP) profiles 3 [Betzler et al., 2013], CONN-CC is not.

Theorem 2. CONN-CC is NP-complete for SP profiles.

This leads us to a more restricted domain, namely unanimous profiles, in which every voter rank the same candidate on top, and strongly unanimous (SU) profiles, in which every voter has the same preference list. We have the following:

3 It is a domain restriction, in which every voter is single-peaked wrt an axis π, i.e, for every voter v, and for each pair of candidates a, b, if either a π b π top(v) or top(v) π b π a holds, where top(v) is the first ranked candidate of voter v, then v ranks b above a.

Observation 2. CONN-CC is NP-complete and W[2]-hard wrt k even for unanimous profiles. But, for SU profiles, MAXCONN-CC can be solved in polynomial time.

As SU profiles are very restricted, we view them as trivial instances and study two related distance parameters.

Lemma 1. MAX-CONN-CC is FPT wrt ℓ + k and q + k, where ℓ is the minimum number of voters that need to change their preference list, and q is the minimum number of consecutive swaps required, so that the profile is SU.

2.2 Connected-k-Borda

Even though k-Borda is polynomial-time solvable, we have the following for CONN-k-BORDA:

Theorem 3. CONN-k-BORDA is NP-complete.

To break the intractability, we first consider parameter k. Towards this, we first observe that in polynomial time, MAX-CONN-k-BORDA can be reduced to MAX-NODEWTk-TREE, in which we are given a node-weighted graph G and need to find a k-sized tree of maximum weight. Given an instance (E,H, k, s) of CONN-k-BORDA, we create an instance (G = H, k′ = k, w = s) of MAX-NODEWT-k-TREE. The weight of each vertex is set to be the Borda score of the corresponding candidate.

Theorem 4. MAX-NODEWT-k-TREE is FPT wrt k. Consequently, MAX-CONN-k-BORDA is FPT wrt k.

Proof. Our proof combines three ingredients: (i) enumeration of unlabeled trees, (ii) the color-coding technique of Alon et al. [1995], and (iii) dynamic programming. Let T denote a solution to MAX-NODEWT-k-TREE. Observe that if we ignore the labels of the vertices of T, then it is isomorphic to an unlabeled tree, say Tul on k vertices and hence Tul will be enumerated when we enumerate all unlabeled trees on k vertices, using Proposition 1. Thus, in O(2.956k kO(1) ) time, we have reduced MAX-NODEWT-k-TREE to a problem of finding a tree in G that is isomorphic to a given tree and has maximum weight - we refer to this problem as MAXNODEWT-TREE-ISO. That is, given a vertex-weighted graph G and a tree Tul, find a maximum weight tree in G that is isomorphic to Tul.

Algorithm for MAX-NODEWT-TREE-ISO 4 : Rather than using the randomized version of color-coding [Alon et al., 1995] for our problem, we directly apply the deterministic version. To that end we use the (n, k)-perfect hash functions. Definition 2. A family of functions f1, . . . , ft from a universe U of size n to a universe of size k is a (n, k)-perfect family of hash functions if for every set S ⊆ U such that |S| = k there exists an i such that the restriction of fi to S is injective.

We need the following result:

Proposition 2 ([Naor et al., 1995]). For any n, k ≥ 1 one can construct an (n, k)-perfect hash family of size ek kO(log k) log n in time ek kO(log k)n log n.

Recall that Tul is an input to MAX-NODEWT-TREE-ISO and T is a hypothetical solution to the problem. To give an algorithm for the MAX-NODEWT-TREE-ISO problem, we convert this into a colored problem by applying Proposition 2.

4 Due to space restriction, we give here slightly sub-optimal algorithm that is easier to explain and sufficient for the result, however, one can design a 2O(k)nO(1) time algorithm using the notion of representative families.

Note that by the definition of (n, k)-perfect family of hash functions, there exists a function, say f, such that the restriction of f to the vertices of V (T) is injective. By trying all possible functions in the hash family, we find the desired one. Let us fix such a function, f. This partitions the vertex set V (G) into Vi = f -1 (i), i ∈ [k]. We refer to each Vi as a color class.

To find a subgraph T of G of maximum weight that is isomorphic to Tul, we "guess", for every vertex of Tul, the color class that contains this vertex. This corresponds to k! = 2O(k log k) guesses. Let this injective (coloring) function be g : V (Tul) → [k]. Given the function g, we root the tree Tul at some arbitrary vertex, say r, and assign to each vertex the name of the color class. Denote this tree by T col ul . We will use T col ul to do a bottom-up dynamic programming from leaves to root. We first perform the following cleaning operation in the graph G: Delete any edge from G that is not a potential edge of T; i.e., delete an edge from G with colored end-points as i, j ∈ [k], if the edge ij /∈ T col ul . We delete all the vertices of degree 0 from G. Next, we go bottom up and delete vertices from color classes that cannot be mapped to T. For a color class Vi such that i is a leaf in T col ul , we do nothing. Now for every vertex j in T col ul , let j1, j2, . . . , jℓ be the children of j. We keep a vertex v ∈ Vj only if it has at least one neighbor in Vjs , for all s ∈ [ℓ].

Observe that there is a tree in G that is isomorphic to Tul iff each color class is non-empty. To find the maximum weight tree isomorphic to Tul, rather T col ul , we do dynamic programming as follows: For a vertex q ∈ V (T col ul ), let T col ul,q denote the subtree of T col ul rooted at q. For a vertex v ∈ Vq, A[v, q] stores the maximum weight of a subtree in G that is rooted at v and isomorphic to T col ul,q . Clearly, if q is a leaf of T col ul , then A[v, q] = w(v). Else, we can compute this using the given recurrence: Let qi, for each i ∈ [ℓ] be the children of q, then: A[v, q] = w(v) + ∑ℓj=1 max {A[u, qj ] : u ∈ N(v) ∩ Vqj }.

The correctness of the recursive relations follows from the disjointness provided by the function g and the cleaning process. The running time of the algorithm is upper bounded by the product of tree enumeration time, number of hashfunctions f, number of functions g, and the dynamic programming; O⋆ (2O(k log k) ) in total.

2.3 Connected-Gehrlein Stable

Here, we obtain some tractability results. To define our parameter, we need the known graph theoretic formulation of GS. Given an election E, the majority graph consists of vertices corresponding to every candidate in the election and if more than half of the voters prefer candidate u over candidate v in the pairwise election between u and v, then there is an arc from u to v. Note that the task of finding a GS committee for (E, k) boils down to finding a k-sized subset S in the majority graph such that no vertex outside S has an out-neighbor in S. When the majority graph is a tournament (i.e., a directed graph in which there is an arc between every pair of vertices), GS has a unique solution, which can be found in polynomial time [Aziz et al., 2017b]. Thus, CONN-GS can be solved in polynomial time as we only need to check connectivity in the solution of GS. As CONN-GS is tractable on tournaments, we study CONN-GS wrt the number h of vertices whose deletion from the majority graph leads to a tournament; we refer to h as the size of tournament vertex deletion set (tvd). Note that h is smaller than the number of pairs of candidates that are in tie. In real-life scenarios, it is usually unlikely to have ties between lots of candidates. The algorithm for the following result is similar to the algorithm in [Gupta et al., 2019], who study h as a parameter for GS.

Theorem 5. CONN-GS can be solved in O⋆ (2h ) time, where h is the size of the minimum tournament vertex deletion set.

We have the following result for a restricted domain.

Observation 3. CONN-GS is NP-complete and W[1]-hard wrt k even for unanimous profile. But, the problem is polynomial-time solvable for SU profiles.

3 Conflict Free Committees

We study the complexity of finding conflict-free committees. Most of the NP-hard and W[1]-hard reductions are from INDEPENDENT SET (IS, in short) which is known to be NPhard [Garey and Johnson, 2002] and W[1]-hard [Downey and Fellows, 1995].

3.1 Conflict Free-Chamberlin Courant

Here, even the parameterization by the number n of voters and the committee score s does not break the intractability, as can be exhibited by a reduction from IS.

Theorem 6. CF-CC is NP-complete and W[1]-hard wrt k even when there is one voter and the score is 0.

Next, we describe an FPT algorithm wrt n for special classes of candidate graphs, in particular, when the number of maximal independent sets in the candidate graph is polynomial (There are graph classes with bounded number of maximal independent sets; most notable is the class of split graphs, in which the number of maximal independent sets is linear in the number of vertices). The algorithm is based on the idea that any solution of CF-CC is a subset of a maximal independent set in the candidate graph. Therefore, we can restrict the election on the candidates to a maximal independent set of H and find a CC committee in this restricted election. Thus, if the number of maximal independent sets is polynomial in the input size, then it can be enumerated in polynomial time [Johnson et al., 1988], and hence we can use the known FPT algorithm for CC wrt n. Thus, we have the following:

Theorem7. If the number of maximal independent sets in the candidate graph H is polynomial, then MAX-CF-CC is FPT wrt n.

Turns out that we can improve the brute-force algorithm for elections with a constant number of voters.

Theorem 8. MAX-CF-CC can be solved in O⋆ (1.1996m) time for a constant number of voters.

Using the idea of enumerating maximal independent sets in the candidate graph, we have the following:

Theorem 9. MAX-CF-CC can be solved in O⋆ (1.4423m) time for SP profiles.

3.2 Conflict Free-k-Borda

We first have the following intractability result which can be exhibited by a reduction from IS.

Theorem 10. CF-k-BORDA is NP-complete and W[1]- hard wrt k even when there is one voter and score is 0.

Using the same intuition as for Theorem 7 that the solution is contained in a maximal independent set of H, and the polynomial time algorithm for k-BORDA, we have the following:

Theorem 11. MAX-CF-k-BORDA can be solved in O⋆ (1.4423m) time.

3.3 Conflict Free-Gehrlein Stable

Here, we obtain that CF-GS is NP-hard even for two voters which can be exhibited by a reduction from IS.

Theorem 12. CF-GS is NP-complete and W[1]-hard wrt k even when there are two voters and the profile is SP.

Next we describe an FPT algorithm wrt the number m of candidates that is better than the brute-force algorithm. To this end, we consider the graph-theoretic formulation of GS (see Section 2.3). Let (M,H, k) be an instance of CF-GS, where M is the majority graph, H is the candidate graph, and k is the size of the committee. The algorithm is based on the following observations that ensure that committee is GS.

1. If a candidate u is in the committee, then its in-reachability set is also in the committee (a vertex v is in the in-reachability set of u, if there is a directed path from v to u).
2. If a candidate u is not in the committee, then its outreachability set is also not in the committee (a vertex v is in the out-reachability set of u, if there is a directed path from u to v).
3. If u and v are neighbors in H, and u is in the inreachability set of v, then v cannot be in the solution.
4. If u is in the committee, then none of its neighbors inH is in the committee.

Following (2) and (3), we apply the following reduction rule. We reuse the notation after application of every reduction rule (RR) and branching rule (BR), and denote the reduced instance by (M, H, k).

RR 1. Let uv ∈ E(H). Suppose that u is in the inreachability set of v in M. Then, delete v and its outreachability set fromM and H.

We define the in-reachability set of a subset of vertices X, denoted by R-(X), as the set containing the in-reachable set of every vertex x ∈ X. Similarly, define the out-reachability set of a subset of vertices X, and denote it by R+(X). Next, we apply several branching rules.

• BR 1. Suppose that u is vertex of degree at least 2 in H. Then, branch on u as follows:
• u is in the solution. We add {u} ∪R-(u) to the solution and delete {u}∪R-(u), N({u}∪R-(u)), and R+(N({u}∪ R-(u))) (out-reachability set of N({u} ∪ R-(u))) fromM and H and obtain the majority graph M ′ and the candidate graph H′ . Recurse on the instance (M ′ , H′ , k - |{u} ∪ R-(u)|).
• u is not in the solution. We delete {u} and R+(u) from M and H and obtain the majority graph M ′ and the candidate graph H′ . Recurse on the instance (M ′ ,H′ , k).
• BR 2. Suppose that u is a vertex with at least one in-neighbor and at least one out-neighbor in M. Then, branch on u in a similar way as in BR 1.
• BR 3. Suppose that u is a vertex with either at least two inneighbors or at least two out-neighbors in M. Then, branch on u in a similar way as in BR 1.

After applying BR 1 to 3, exhaustively, M consists of isolated vertices and disjoint arcs (i.e., arcs that do not share their end-points), and in H, each vertex has degree at most one. Therefore, if M contains at least 2k isolated vertices or if the end-points of the disjoint arcs in M are isolated vertices in H, then we can solve the instance in polynomial time. Otherwise, we branch as follows.

BR 4. Suppose that (u, v) is an arc inM. If either u or v has degree 1 in H, then branch on v in a similar way as in BR 1.

The running time of the whole algorithm is governed by the recurrence T (m) ≤ T (m - 1) + T (m - 3), which solves to O⋆ (1.4656m). Thus, we have the following:

Theorem 13. CF-GS can be solved in O⋆ (1.4656m) time.

Next, we study CF-GS wrt tvd and have the following:

Theorem 14. CF-GS can be solved in O⋆ (1.46h ) time, where h is the size of tournament vertex deletion set in M.

We have the following result in restricted domain:

Observation 4. CF-GS is NP-complete and W[1]-hard wrt k even for unanimous profiles. But, the problem is polynomial-time solvable when the profile is SU.

4 Future Direction

Beside considering other ways of breaking the computational intractability (e.g., using randomization, approximation algorithms, and heuristic methods) and studying further multiwinner rules R and graph properties Q, further research directions include studying other ways of combining multiwinner rules R and graph properties Q, such as by aiming at finding points on the Pareto curve (similarly in spirit to multigoal committee selection [Kocot et al., 2019]) or, e.g., relaxing the requirement of Independent Set by merely minimizing the number of edges between committee members.

Acknowledgments

We are grateful to Dr. Nimrod Talmon for fruitful discussions. Sushmita Gupta was supported by SERB-Starting Research Grant (SRG/2019/001870). Saket Saurabh was supported by European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme (grant no. 819416), and Swarnajayanti Fellowship grant (DST/SJF/MSA- 01/2017-18).