Group control for procedural rules: parameterized complexity and consecutive domains

Abstract

We consider GROUP CONTROL BY ADDING INDIVIDUALS (GCAI) in the setting of group identification for two procedural rules—the consensus-start-respecting rule and the liberal-start-respecting rule. It is known that GCAI for both rules are \mathsf{\text{NP}}-hard, but whether they are fixed-parameter tractable with respect to the number of distinguished individuals remained open. We resolve both open problems in the affirmative. In addition, we strengthen the \mathsf{\text{NP}}-hardness of GCAI by showing that, with respect to the natural parameter the number of added individuals, GCAI for both rules are \mathsf{\text{W[2]}}-hard. Notably, the \mathsf{\text{W[2]}}-hardness for the liberal-start-respecting rule holds even when restricted to a very special case where the qualifications of individuals satisfy the so-called consecutive ones property. However, for the consensus-start-respecting rule, the problem becomes polynomial-time solvable in this special case. We also study a dual restriction where the disqualifications of individuals fulfill the consecutive ones property, and show that under this restriction GCAI for both rules turn out to be polynomial-time solvable. Our reductions for showing \mathsf{\text{W[2]}}-hardness also imply several algorithmic lower bounds.

Graphical abstract

Keywords

group control by adding individuals / group identification / parameterized complexity / consecutive ones property / FPT / W[2]-hard

1 Introduction

In the model of group identification, we have a group of individuals each of whom holds binary valuations on all individuals including herself, and the model aims to determine who among these individuals are socially qualified by utilizing a certain social aggregation rule [1]. Since the initial works of Kasher [2] and Kasher and Rubinstein [1], group identification has been extensively explored from the perspective of economics, with the main focus being on axiomatic characterizations of different social aggregation rules [3–7].

As social aggregation rules can be seen as special voting systems where individuals are both voters and candidates, inspired by the pioneering work of Bartholdi, Tovey, and Trick [8] on voting control problems, Yang and Dimitrov [9] initiated the study of group identification from a theoretical computer science perspective by investigating the complexity of the GROUP CONTROL BY ADDING/DELETING INDIVIDUALS (GCAI/GCDI) problems. In particular, GCAI/GCDI consists in determining if a given (valuation) profile can be modified by adding/deleting a limited number of individuals to make a given subset of distinguished individuals all socially qualified. Yang and Dimitrov studied the consensus-start-respecting rule and the liberal-start-respecting rule, and showed that GCAI for both rules are \mathsf{\text{NP}}-hard, while GCDI for both rules turned out to be polynomial-time solvable. However, it is left open whether GCAI for these two rules are fixed-parameter tractable (\mathsf{\text{FPT}}) with respect to the number of distinguished individuals. We resolve the open questions in the affirmative by reducing GCAI to a variant of the DIRECTED STEINER TREE problem (Theorems 2 and 3). In addition, we strengthen the above-mentioned \mathsf{\text{NP}}-hardness results by showing that GCAI for both rules are \mathsf{\text{W[2]}}-hard with respect to the number of added individuals (Theorems 4 and 6). Particularly, the \mathsf{\text{W[2]}}-hardness for the liberal-start-respecting rule holds even when restricted to a very special case where the qualifications of individuals satisfy the so-called consecutive ones property. However, for the consensus-start-respecting rule, the problem is polynomial-time solvable in this special case (Theorem 5). We also study a dual restriction where the disqualifications of individuals fulfill the consecutive ones property, and show that under this restriction GCAI for both rules turn out to be polynomial-time solvable (Theorem 7). Our hardness reductions also lead to numerous lower bounds concerning kernelizations and exact algorithms (Corollaries 1–6).

2 Related works

Since the first work of Yang and Dimitrov [9] on the complexity of group control problems, several related problems have been proposed and studied very recently. It should be pointed out that in addition to the consensus-start-respecting rule and the liberal-start-respecting rule, Yang and Dimitrov [9] also studied the class of consent rules proposed by Samet and Schmeidler [7], and established a complete complexity landscape of the group control problems with respect to the consent quotas of these rules. Erdélyi, Reger, and Yang [10, 11] studied the destructive counterparts of the group control problems, group bribery problems, and the problems of determining socially qualified individuals with incomplete information. Later, Erdélyi and Yang [12] studied the complexity of microbribery in group identification. Additionally, Boehmer et al. [13] also considered numerous bribery problems in group identification through the lens of parameterized complexity. Junker [14, 15] later extended the results of Boehmer et al. [13] and studied some other variants of strategic problems in group identification. Motivated by applications in information diffusion in social networks, Blažej [16] studied some generalizations of group control problems for the two procedural rules mentioned above. Very recently, Yang and Dimitrov [17] studied group control problems for the class of consent rules when restricted to two types of cyclic domains which contain the domains studied in the paper as special cases. They showed that these problems, being computationally hard to solve in general, become polynomial-time solvable when the input profile falls into the category of these cyclic domains.

Voting problems restricted to special domains have been widely studied in the literature. Particularly, the consecutive domain has been studied as an analog of single-peaked domain for dichotomous preferences [18, 19]. This domain has been also studied under the name candidate interval [20–23]. It is known that many voting problems which are \mathsf{\text{NP}}-hard in general become polynomial-time solvable when restricted to this domain, with only a few exceptions [24, 25]. For further discussions on the complexity of voting problems in restricted domains, we refer to [26–29] for comprehensive surveys.

It should also be noted that the consecutive domain is equivalent to the so-called consecutive ones property of (0,1)-matrices which has long been explored due to its significant applications in a broad range of areas (cf. the survey [30] and references therein). Recall that a (0,1)-matrix satisfies the consecutive ones property if its columns can be permuted so that in each row all 1s are consecutive.

3 Preliminaries

Throughout this paper we will need the following basic ingredients. For an integer i, [i] is the set of positive integers no greater than i.

3.1 Social aggregation rules

Let N be a set of n individuals. Each individual a\in N has an opinion who from the set N possess a certain qualification and who do not. For a^{\mathrm{\prime }}\in N, we write \phi (a,a^{\mathrm{\prime }})=1 if a qualifies a^{\mathrm{\prime }}, and write \phi (a,a^{\mathrm{\prime }})=0 if a disqualifies a^{\mathrm{\prime }}. The mapping \phi :N\times N\to \left\{0,1\right\} is called a profile over N. A social aggregation rule is a function f assigning a subset f(\phi ,T)\subseteq T to each pair (\phi ,T) of a profile \phi over N and a subset T\subseteq N. The members of f(\phi ,T) are called f socially qualified individuals in T at the profile \phi.

In what follows we focus in our analysis on two procedural rules: the consensus-start-respecting rule and the liberal-start-respecting rule. The reader is referred to [4] for axiomatic characterizations of these rules.

Consensus-start-respecting rule f ^CSR This rule determines the socially qualified individuals iteratively. First, all individuals qualified by everyone are considered socially qualified. Then, in each iteration, all individuals who are qualified by at least one of the currently socially qualified individuals are added into the set of socially qualified individuals. The iterations terminate when no new individuals can be added this way. Formally, for every T\subseteq N, let

K_0^{\text{C}}(\phi ,T)=\{a\in T\mid \mathrm{\forall }(a^{\prime }\in T)[\phi (a^{\prime },a)=1]\}.

For each integer \ell =1, 2,\dots, let K_{\ell }^{\text{C}}(\phi ,T)=

K_{\ell -1}^{\text{C}}(\phi ,T)\cup \{a\in T\mid \mathrm{\exists }(a^{\prime }\in K_{\ell -1}^{\text{C}}(\phi ,T))[\phi (a^{\prime },a)=1]\}.

Then, f^{\text{CSR}}(\phi ,T)=K_{\ell }^{\text{C}}(\phi ,T) for some integer \ell such that K_{\ell }^{\text{C}}(\phi ,T)=K_{\ell -1}^{\text{C}}(\phi ,T).

Liberal-start-respecting rule f ^LSR This rule is analogous to f^{\text{CSR}} with only the difference that the initial socially qualified individuals are those who qualify themselves. In particular, for every T\subseteq N, let

K_0^{\text{L}}(\phi ,T)=\{a\in T\mid \phi (a,a)=1\}.

For each integer \ell =1, 2,\dots, let K_{\ell }^{\text{L}}(\phi ,T)=

K_{\ell -1}^{\text{L}}(\phi ,T)\cup \{a\in T\mid \mathrm{\exists }(a^{\prime }\in K_{\ell -1}^{\text{L}}(\phi ,T))[\phi (a^{\prime },a)=1]\}.

Then, f^{\text{LSR}}(\phi ,T)=K_{\ell }^{\text{L}}(\phi ,T) for some integer \ell such that K_{\ell }^{\text{L}}(\phi ,T)=K_{\ell -1}^{\text{L}}(\phi ,T).

It should be noted that when K_0^{\text{C}}(\phi ,T)=\mathrm{\varnothing } (resp. K_0^{\text{L}}(\phi ,T)=\mathrm{\varnothing }) we have that f^{\text{CSR}}(\phi ,T)=\mathrm{\varnothing } (resp. f^{\text{LSR}}(\phi ,T)=\mathrm{\varnothing }).

3.2 Consecutive domains

Let ⊳=(a_1,a_2,\dots ,a_n) be a linear order over N. For each individual a\in N, let

{\phi }_{⊳}(a)=(\phi (a,a_1),\phi (a,a_2),\dots ,\phi (a,a_n)).

We say that {\phi }_{⊳}(a) is qualifying consecutive (QC) with respect to the order ⊳ if all 1s are consecutive in {\phi }_{⊳}(a), i.e., there are i,j\in [n] such that i\le j, \phi (a,a_x)=1 for all x such that i\le x\le j, and \phi (a,a_x)=0 for all other possible values of x (if there are any). We say that {\phi }_{⊳}(a) is disqualifying consecutive (DQC) with respect to ⊳ if 0s are consecutive in {\phi }_{⊳}(a). We say that \phi is QC (resp. DQC) if there is at least one linear order ⊳ over N with respect to which every {\phi }_{⊳}(a) where a\in N is QC (resp. DQC).

It is immediately clear from the above definition that checking if a profile is QC or DQC is equivalent to checking if a (0,1)-matrix satisfies the consecutive ones property, which can be done in polynomial-time (cf. [31–33]).

3.3 Group control

Let us now formally state the group control problem we study. Let f be a social aggregation rule.

In what follows, we call members of S distinguished individuals.

3.4 Parameterized complexity

A parameterized problem is subset {\mathrm{\Sigma }}^{\ast }\times \mathbb{N} where \mathrm{\Sigma } is a fixed alphabet. A parameterized problem is \mathsf{\text{FPT}} if there is an algorithm so that for each instance (X,\kappa ) of the problem the algorithm determines correctly if (X,\kappa ) is a YES-instance in time f(\kappa )\cdot |X{|}^{O(1)}, where f is a computable function in the parameter \kappa. The following hierarchy has been developed to classify parameterized problems:

\mathsf{\text{FPT}}\subseteq \mathsf{\text{W[1]}}\subseteq \mathsf{\text{W[2]}}\subseteq \cdots \subseteq \mathsf{\text{XP}}.

A parameterized problem is \mathsf{\text{W[2]}}-hard if all problems in \mathsf{\text{W[2]}} are parameterized reducible to the problem. \mathsf{\text{W[2]}}-hard problems do not admit any \mathsf{\text{FPT}}-algorithms unless the above hierarchy collapses to some level.

A kernelization of an \mathsf{\text{FPT}} problem P is an algorithm which takes an instance (X,\kappa ) of P as input and outputs an instance (X^{\prime },{\kappa }^{\prime }) of P such that

(1) the algorithm runs in polynomial time in the size of (X,\kappa ),

(2) (X,\kappa ) is a YES-instance if and only if (X^{\prime },{\kappa }^{\prime }) is a YES-instance, and

(3) |X^{\prime }|\le g(\kappa ) for some computable function g in \kappa.

If P has a kernelization where g is a polynomial, we say that P admits a polynomial kernel.

For further discussions on parameterized complexity, we refer to [34, 35].

3.5 Useful graph problems

In the following, we introduce some graph problems used to establish our results. We assume the reader is familiar with the basics in graph theory [36, 37].

A bipartite graph is a graph G whose vertices can be divided into two disjoint sets R and B so that the edges of G are only between R and B. A vertex vdominates another vertex u if there is an edge between them. For two disjoint subsets A and B of vertices, we say that A dominates B if every vertex in B is dominated by at least one vertex in A.

RBDS is a well-known \mathsf{\text{NP}}-hard problem, and from the parameterized complexity point of view it is \mathsf{\text{W[2]}}-hard with respect to \kappa [35]. We will use this problem to establish our fixed-parameter intractability results.

Some of our problems are solved by reducing to a variant of the DIRECTED STEINER TREE problem defined below. For a graph (resp. digraph) G, we use V(G) to denote its vertex set, and use E(G) to denote its edge (resp. arc) set. For a subset J of edges (resp. arcs) of G, V(J) is the set of vertices incident with edges (resp. arcs) in J.

It is known that DST is \mathsf{\text{NP}}-hard and, moreover, it is \mathsf{\text{FPT}} with respect to the number of terminals |X| [38–40]. More precisely, DST can be solved in O^{\ast }(2^{|X|}) time [38, 39, 41, 42].

We shall use DVWST as an intermediate problem to establish our \mathsf{\text{FPT}}-results. Note that DVWST can be trivially transformed into DST in polynomial time by splitting each vertex into two vertices connected by one arc with the same weight as the original vertex. Therefore, DVWST is also \mathsf{\text{FPT}} with respect to the number of terminals (Theorem 1).

4 Our results

We shall first study two \mathsf{\text{FPT}}-algorithms for GCAI in the general domain, and then we explore the complexity of GCAI restricted to the QC and the DQC domains.

4.1 The general domain

First, we resolve the open questions regarding GCAI for f^{\text{CSR}} and f^{\text{LSR}} in the affirmative, starting with the one for f^{\text{CSR}}. To this end, we first show that the DVWST problem is \mathsf{\text{FPT}} with respect to the number of terminals.

Theorem 1 DVWST can be solved in O^{\ast }(2^{\ell }) time where \ell is the number of terminals.

The proof of Theorem 1 is deferred to the Appendix.

Bellow we study a lemma which suggests that to solve GCAI for f^{\text{CSR}} we can make a guess on one of the individuals who is qualified by all individuals in the final profile. This enables us to split an instance of GCAI for f^{\text{CSR}} into polynomially many subinstances which are then solved via Theorem 1.

The incidence graph of a profile \phi over N, denoted G_{\phi }, is the digraph whose vertices are exactly the individuals in N, and there is an arc from a\in N to a^{\prime }\in N if and only if a qualifies a^{\prime }. Note that the incidence graph may contain loops.

Lemma 1 Let \phi be a profile over a set N of individuals so that f^{\text{{CSR}}}(\phi ,N)\ne \mathrm{\varnothing }. Let a\in N be an individual qualified by all individuals in N with respect to \phi. Then, for every a^{\prime }\in N\setminus \{a\}, it holds that a^{\prime }\in f^{\text{{CSR}}}(\phi ,N) if and only if there is a directed path from a to a^{\prime } in G_{\phi }.

Proof Let \phi, a, and a^{\prime } be as stipulated in the lemma. It is clear from the definition of f^{\text{CSR}} that if there is a directed path from a to a^{\prime }, then a^{\prime }\in f^{\text{CSR}}(\phi ,N). It remains to show the other direction. Assume that a^{\prime }\in f^{\text{CSR}}(\phi ,N). Due to the definition of f^{\text{CSR}}, there must be an individual b\in N who is in the initial set of socially qualified individuals, and there is a directed path from b to a^{\prime } in the incidence graph G_{\phi } of \phi. So, b is qualified by all individuals including a, implying that there is a directed path from a to a^{\prime } in G_{\phi }.　　　　　　　　　　□

Observe that if an individual in S qualifies another individual in S, then if the former is socially qualified so is the latter. The following reduction rule implements this observation.

Reduction Rule 1 If there are two distinct distinguished individuals a,a^{\prime }\in S such that a qualifies a^{\prime }, move a^{\prime } from S into T\setminus S.

For a subset Y of vertices in a digraph G, let

N_G^{-}(Y)=\{v\in V(G)\setminus Y\mid \mathrm{\exists }(u\in Y)[(v,u)\in E(G)]\}

be the set of inneighbors of vertices in Y, without Y itself, and let

N_G^{+}(Y)=\{v\in V(G)\setminus Y\mid \mathrm{\exists }(u\in Y)[(u,v)\in E(G)]\}

be the set of outneighbors of vertices in Y, without Y itself. Merging Y is the operation that creates one vertex v_Y so that N_G^{-}(\{v_Y\})=N_G^{-}(Y) and N_G^{+}(\{v_Y\})=N_G^{+}(Y), and removes all vertices of Y from G. We call v_Y the merging vertex of Y.

Armed with Lemma 1 and Reduction Rule 1, we are ready to present our first \mathsf{\text{FPT}}-algorithm.

Theorem 2 GCAI for f^{\text{{CSR}}} is \mathsf{\text{FPT}} with respect to the number \ell of distinguished individuals. More precisely, it can be solved in O^{\ast }(2^{\ell }) time.

Proof Let I=(N,\phi ,S,T,k) be an instance of GCAI for f^{\text{CSR}}. We first exhaustively apply Reduction Rule 1 to I so that in the resulting instance no individual in S qualifies another different individual in S. Then, we split the instance into |N| subinstances, each of which takes I and an individual a^{\ast }\in N as input, and determines if there exists U\subseteq N\setminus T of at most k individuals so that S\subseteq f^{\text{CSR}}(\phi ,T\cup U), a^{\ast }\in T\cup U, and all individuals in T\cup U qualify a^{\ast }. That is, a^{\ast } is our guessed individual who is in the initial set of socially qualified individuals in the final profile. Obviously, the original instance I is a YES-instance if and only if at least one of the subinstances is a YES-instance.

Now we focus on solving a subinstance with a guessed individual a^{\ast }. We assume that a^{\ast } is included in T, since otherwise we simply move a^{\ast } from N\setminus T into T and decrease k by one. As a^{\ast } is supposed to be qualified by all individuals in the final profile, if there is an individual in T who disqualifies a^{\ast }, we directly discard this subinstance and proceed to the next one. Otherwise, we remove from the subinstance all individuals in N\setminus T who disqualify a^{\ast } (this includes deleting them from both N and from \phi). We shall solve the subinstance by reducing it to DVWST. Observe first that by Lemma 1 and the fact that a^{\ast }\in T is qualified by all individuals now, it holds that f^{\text{CSR}}(\phi ,T)\subseteq f^{\text{CSR}}(\phi ,T\cup U) for all U\subseteq N\setminus T, i.e., if an individual is socially qualified in T at \phi, it remains socially qualified when additional individuals from N\setminus T are added into T. We reset S:=S\setminus f^{\text{CSR}}(\phi ,T), i.e., we remove from S all individuals which are already socially qualified in T at \phi. In light of the above observation, the subinstances before and after the resetting of S are equivalent. Now we create an instance of DVWST as follows. The digraph G in the DVWST instance is obtained from the incidence graph of \phi over N by merging f^{\text{CSR}}(\phi ,T). Obviously, a^{\ast }\in f^{\text{CSR}}(\phi ,T), and so f^{\text{CSR}}(\phi ,T) is nonempty. Let u denote the merging vertex of f^{\text{CSR}}(\phi ,T), and we let it be the given root of the DVWST instance. Furthermore, we let every individual in N\setminus T have weight 1, and let all the other individuals (including u) have weight 0. The terminals are those in S, and the weight upper bound is p=k.

If there is a subset J of vertices of total weight at most k so that there is a directed path from u to every terminal a\in S in G, then a is f^{\text{CSR}} socially qualified in (\phi ,J\cup \{u\}\cup S) due to Lemma 1. Moreover, as all individuals in N\setminus T have weight 1 and all the other individuals have weight 0, we know that J contains at most k individuals from N\setminus T, implying that J\cap (N\setminus T) is a YES-certificate for the subinstance. For the opposite direction, if there is a subset U\subseteq N\setminus T of at most k individuals so that for all a\in S it holds that a\in f^{\text{CSR}}(\phi ,T\cup U), then due to Lemma 1 there is a directed path from u to a in the subgraph of G induced by T\cup U. As the total weight of vertices in U is at most k, the instance of DVWST is a YES-instance.

Regarding the running time, let \ell =|S| be the number of distinguished individuals. As there are at most |N| subinstances to consider and each of them can be solved in O^{\ast }(2^{\ell }) time (Theorem 1), the whole algorithm runs in O^{\ast }(2^{\ell }) time.　　　□

An analogous result for the liberal-start-respecting rule exists. In fact, the algorithm in this case is simpler. We first use a reduction rule to refine the structure of instances of GCAI for f^{\text{LSR}}.

Reduction Rule 2 If there are a,a^{\prime }\in S such that a qualifies a^{\prime }, move a^{\prime } from S into T\setminus S.

Notice that the difference between Reduction Rule 1 and Reduction Rule 2 is that in the second rule a and a^{\prime } may be the same, while the first reduction rule requests that a and a^{\prime } are distinct. The reason is that under f^{\text{LSR}} every individual qualifying herself is already socially qualified without needing other individuals’ qualifications.

Theorem 3 GCAI for f^{\text{{LSR}}} is \mathsf{\text{FPT}} with respect to the number \ell of distinguished individuals. More precisely, it can be solved in O^{\ast }(2^{\ell }) time.

Proof Let I=(N,\phi ,S,T,k) be an instance of GCAI for f^{\text{LSR}}. We first apply Reduction Rule 2 to I iteratively until it does not apply. Then, we solve the instance by reducing it to a DVWST instance as follows. The digraph G of the DVWST instance is obtained from the incidence graph of \phi over N by creating one new vertex u and creating arcs from u to every individual in N qualifying herself (i.e., \{a\in N\mid \phi (a,a)=1\}). We set u as the root, and set S as the set of the terminals. Finally, we let the weight of all individuals in N\setminus T be 1, and let those of others be 0. Similar to the analysis in the proof of Theorem 2, we can show that the two instances are equivalent, and the running time of the algorithm is O^{\ast }(2^{\ell }).　　　　　□

Next, we strengthen the \mathsf{\text{NP}}-hardness of GCAI for the consensus-start-respecting rule established in [9] by showing its \mathsf{\text{W[2]}}-hardness with respect to the number of added individuals. We also have a \mathsf{\text{W[2]}}-hardness result for the liberal-start-respecting rule, but we defer the presentation of this result to the next section because it holds even in a specific domain which is not the focus of this section.

Theorem 4 GCAI for f^{\text{{CSR}}} is \mathsf{\text{W[2]}}-hard with respect to the number of added individuals.

Proof We prove the theorem via a reduction from the RBDS problem. Let (G,\kappa ) be an RBDS instance, where G=(R\cup B,E) is a bipartite graph with the vertex partition (R,B), and \kappa is an integer. We create an instance of GCAI for f^{\text{CSR}} as follows. First, we create for each vertex in G an individual denoted by the same symbol for notational brevity. Let N=R\cup B and let S=T=B. We define a profile \phi over N so that:

● each b\in B qualifies all individuals in R and disqualifies all individuals in B; and

● each r\in R qualifies all individuals in R and, moreover, for each individual b\in B it holds that r qualifies b if and only if r dominates b in G.

The instance of GCAI for f^{\text{CSR}} is (N,\phi ,S,T,\kappa ). The reduction can be done in polynomial time. We show the correctness of the reduction as follows.

(\Rightarrow ) Assume that there is a subset R^{\prime }\subseteq R of at most \kappa vertices dominating B. According to the definition of \phi, individuals in R are qualified by all individuals in N. Therefore, it holds that R^{\prime }\subseteq f^{\text{CSR}}(\phi ,B\cup R^{\prime }). Moreover, as R^{\prime } dominates B, for every b\in B there is at least one r\in R which dominates b. By the definition of \phi, r qualifies b, implying that b\in f^{\text{CSR}}(\phi ,B\cup R^{\prime }). As this holds for all b\in B, we know that the instance of GCAI for f^{\text{CSR}} constructed above is a YES-instance.

(\Leftarrow ) Assume that there is a subset R^{\prime }\subseteq R (recall that N\setminus T=R) of cardinality at most \kappa so that B\subseteq f^{\text{CSR}}(\phi ,B\cup R^{\prime }). Let b be any arbitrary individual in B. According to the definition of \phi, b is qualified only by individuals in R who dominate b in G. As b\in f^{\text{CSR}}(\phi ,B\cup R^{\prime }), this implies that R^{\prime } contains at least one vertex dominating b. As this holds for all b\in B, we conclude that R^{\prime } dominates B. Given |R^{\prime }|\le \kappa, we conclude that the RBDS instance is a YES-instance.　　　　□

4.2 The consecutive domains

Now we explore the complexity of GCAI for the two procedural rules restricted to the consecutive domains.

Lemma 2 Let \phi be a profile over N which is QC with respect to a linear order ⊳ of N. Then, all individuals in f^{\text{{CSR}}}(\phi ,N) are consecutive in the order ⊳.

Proof If f^{\text{CSR}}(\phi ,N)=\mathrm{\varnothing }, the lemma vacuously holds. Otherwise, there is an individual a\in N which is qualified by all individuals in N. As \phi is QC with respect to ⊳, all individuals only qualify individuals consecutive in ⊳, and they all qualify a. It follows that all individuals in f^{\text{CSR}}(\phi ,N) are consecutive in ⊳.　　　　　　　　　　　　　　　　　□

Based on Lemma 2, we derive a polynomial-time algorithm for GCAI for f^{\text{CSR}}.

Theorem 5 GCAI for f^{\text{{CSR}}} is polynomial-time solvable when restricted to QC profiles.

Proof Let I=\left(N,\phi ,S,T,k\right) be an instance of GCAI for f^{\text{CSR}} where \phi is QC with respect to a linear order ⊳ over N. Let a_i and a_j be respectively the left-most and the right-most individuals in ⊳ that are from S. Due to Lemma 2, the question of I is equivalent to making a_i and a_j socially qualified in T by adding at most k individuals from N\setminus T into T. In light of this fact, we move all individuals except a_i and a_j from S into T\setminus S. After this operation, S contains at most two individuals (S is a singleton when i=j). Then, we solve the instance in polynomial time by Theorem 2.　　　　　　□

Now we move on to the liberal-start-respecting rule. Unlike f^{\text{CSR}}, we show that GCAI for f^{\text{LSR}} remains computationally hard even when restricted to QC profiles.

Theorem 6 GCAI for f^{\text{{LSR}}} is \mathsf{\text{NP}}-hard and is \mathsf{\text{W[2]}}-hard with respect to the number of added individuals even when restricted to QC profiles.

Proof We prove the theorem by giving a reduction from the RBDS problem to GCAI for f^{\text{LSR}} restricted to QC profiles. Let (G,\kappa ) be an instance of RBDS, where G=(B\cup R,E) is a bipartite graph, and \kappa is an integer. For each b\in B, we construct an individual denoted still by b for notational simplicity. For each r\in R, let d(r) be the degree of r in G. For each r\in R, we construct d(r)+1 individuals r(0),r(1),\dots , r(d(r)). Let C(r)=\{r(i)\mid i\in [d(r)]\} for each r\in R, and let C(R)=\bigcup _{r\in R}C(r). In addition, let N denote the set of the above constructed |B|+|R|+\sum _{r\in R}d(r) individuals, let S=B, and let T=B\cup C(R). We define a profile \phi over N as follows.

● For each red vertex r\in R, the individual r(0) qualifies r(0), r(1), \dots, r(d(r)), and each of r(1), r(2), \dots, r(d(r)) qualifies exactly one neighbor of r in G so that every neighbor of r in G is qualified by exactly one of these d(r) individuals.

● For each a,a^{\prime }\in N where \phi (a,a^{\prime }) is not specified above, we define \phi (a,a^{\prime })=0.

The instance of GCAI is (N,\phi ,S,T,\kappa ).

It is easy to see that the profile \phi is QC. In fact, except those in \{r(0)\mid r\in R\}, every other individual qualifies at most one individual. Moreover, as every r(0) where r\in R qualifies exactly the d(r)+1 individuals created for r, the profile is QC with respect to any linear order over N where for every r\in R the d+1 individuals created for r are consecutive.

The construction takes polynomial time. In the following, we show the correctness of the reduction.

(\Rightarrow ) Assume that there is a subset R^{\prime }\subseteq R of at most \kappa vertices dominating B. Let U=\{r(0)\mid r\in R^{\prime }\}. We show that S\subseteq f^{\text{LSR}}(\phi ,T\cup U). Note that as \phi (r(0),r(0))=1 for all r\in R, and r(0) qualifies also all the other individuals created for r, we know that for every r\in R^{\prime }, the individuals r(0), r(1), \dots, r(d(r)) are all f^{\text{LSR}} socially qualified in T\cup U at \phi. Let b be an individual in S. As R^{\prime } dominates B and B=S, b has at least one neighbor r\in R^{\prime } in G. Then, due to the above construction, there exists an individual r(i) where i\in [d(r)] qualifying b. As r(i)\in f^{\text{LSR}}(\phi ,T\cup U), it follows that b\in f^{\text{LSR}}(\phi ,T\cup U). As this holds for all b\in S, the above constructed instance of GCAI for f^{\text{LSR}} is a YES-instance.

(\Leftarrow ) Assume that there is a U\subseteq N\setminus T such that |U|\le \kappa and S\subseteq f^{\text{LSR}}(\phi ,T\cup U). Let R^{\prime }=\{r\in R\mid r(0)\in U\}. Clearly, |R^{\prime }|=|U|\le \kappa. We claim that R^{\prime } dominates B. Let b be a vertex (individual) in B. By the definition of \phi, b is only qualified by individuals in C(r) where r\in R such that r dominates b. Then, as b\in f^{\text{LSR}}(\phi ,T\cup U), there exist r\in R and i\in [d(r)] such that r(i)\in f^{\text{LSR}}(\phi ,T\cup U) and \phi (r(i),b)=1. Note that the only individual qualifying r(i) is the individual r(0) who qualifies herself. This means that r(0)\in U, and hence r\in R^{\prime }. It also implies that b is dominated by r. As the above argument holds for all b\in B, we conclude that R^{\prime } dominates B, and hence the RBDS instance is a YES-instance.　　　　　　　　　　□

When restricted to DQC, we can show that GCAI for both procedural rules are polynomial-time solvable. A crucial observation is that if an instance is a YES-instance, we need at most two individuals to bring all distinguished individuals into the set of socially qualified individuals. This observation enables us to solve the problem by first guessing the no more than two individuals which together qualify all distinguished individuals, and then solving the remaining part via resetting the guessed individuals as distinguished individuals. As there are polynomially many guesses, by utilizing Theorems 2 and 3, we can solve the problem in polynomial time.

Theorem 7 When restricted to DQC profiles, both GCAI for f^{\text{{CSR}}} and GCAI for f^{\text{{LSR}}} are polynomial-time solvable.

Proof Let I=(N,\phi ,S,T,k) be an instance of GCAI for f^{\text{CSR}} (resp. f^{\text{LSR}}), where \phi is DQC with respect to a linear order ⊳=(a_1,a_2,\dots ,a_n) over N. If , we solve the instance in polynomial time by a brute-force search. So, in the following, let us assume that k\ge 2. By a⊵a^{\prime }, we mean either a⊳a^{\prime } or a=a^{\prime }. Let N^{\prime }=\{a\in N\mid \mathrm{\exists }(a^{\prime }\in N)[\phi (a,a^{\prime })=0]\} be the set of individuals in N disqualifying at least one individual in N. For each a\in N^{\prime }, let L(a) be the left-most individual a disqualifies, and let R(a) be the right-most individual a disqualifies in ⊳. More precisely, L(a)=a_j (resp. R(a)=a_j) such that \phi (a,a_j)=0 and, moreover, for all a_i\in N such that \phi (a,a_i)=0 it holds that i\ge j (resp. i\le j). Let

A=\{a\in N^{\prime }\mid \phi (a,a_n)=1,\mathrm{\forall }(a^{\prime }\in N,\phi (a^{\prime },a_n)=1)[R(a)⊵R(a^{\prime })]\}

and let

B=\{a\in N^{\prime }\mid \phi (a,a_1)=1,\mathrm{\forall }(a^{\prime }\in N,\phi (a^{\prime },a_1)=1)[L(a^{\prime })⊵L(a)]\}.

For every subset Z\subseteq N, let

{\mathbf{1}}_{\phi }(Z)=\{a\in N\mid \mathrm{\exists }(a^{\prime }\in Z)[\phi (a^{\prime },a)=1]\}

denote the set of individuals qualified by at least one individual from Z.

Observation 1 Let X be a subset of A\cup B of cardinality at most two so that for each Y\in \{A,B\} it holds that |X\cap Y|=1 whenever Y\ne \mathrm{\varnothing }. Then, if N\setminus N^{\prime }=\mathrm{\varnothing }, for every Z\subseteq N, it holds that {\mathbf{1}}_{\phi }(Z)\subseteq {\mathbf{1}}_{\phi }(X). Moreover, if N\setminus N^{\prime }\ne \mathrm{\varnothing }, for every Z\subseteq N, it holds that {\mathbf{1}}_{\phi }(Z)\subseteq {\mathbf{1}}_{\phi }(\{a\}) for every a\in N\setminus N^{\prime }.

In view of Observation 1, if I is a YES-instance, there exists a subset of at most two socially qualified individuals in the final profile so that every individual in S is qualified by at least one individual in the subset. Therefore, to solve I, we enumerate all subsets S^{\prime }\subseteq N of at most two individuals so that S\subseteq {\mathbf{1}}_{\phi }(S^{\prime }). For each enumerated subset S^{\prime }, we solve an instance I_{S^{\prime }}=(N,\phi ,S^{\prime },T^{\prime },k^{\prime }) of GCAI, where T^{\prime }=T\cup S^{\prime } and k^{\prime }=k-|S^{\prime }\cap (N\setminus T)| (the definitions of T^{\prime } and k^{\prime } correspond to that if an individual in S^{\prime } is from N\setminus T, we move it from N\setminus T into T). By Theorems 2 and 3, each I_{S^{\prime }} can be solved in polynomial time. The original instance I is a YES-instance if and only if there exists at least one enumerated S^{\prime } so that I_{S^{\prime }} is a YES-instance. As we have at most |N{|}^2 enumerations, the whole algorithm takes polynomial time.　　　　　　　　□

5 Concluding remarks

We proved that GCAI for both the consensus-start-respecting rule (f^{\text{CSR}}) and the liberal-start-respecting rule (f^{\text{LSR}}) are \mathsf{\text{FPT}} with respect to the number of distinguished individuals (Theorems 2 and 3), resolving two open questions left in [9]. Additionally, we showed that GCAI for f^{\text{CSR}} and GCAI for f^{\text{LSR}} are \mathsf{\text{W[2]}}-hard with respect to the solution size k (Theorems 4 and 6). Furthermore, we studied GCAI restricted to the qualifying consecutive (QC) domain and the disqualifying consecutive (DQC) domain. We showed that both GCAI for f^{\text{CSR}} and GCAI for f^{\text{LSR}} become polynomial-time solvable when restricted to the DQC domain (Theorem 7). However, when restricted to the QC domain, GCAI for f^{\text{CSR}} is polynomial-time solvable (Theorem 5), while GCAI for f^{\text{LSR}} remains computationally hard (Theorem 6). See Tab.1 for a summary of these results.

Given the fixed-parameter tractability of GCAI stated in Theorems 2 and 3, one may wonder whether the two problems admit polynomial kernels when parameterized by the number of distinguished individuals. Regarding this issue, we remark that both reductions in the proofs of Theorems 4 and 6 are in fact polynomial parameter transformations with respect to the combined parameter |S|+k of the number of distinguished individuals and the number of added individuals. Then, by the lower bound technique developed by Dom, Lokshtanov, and Saurabh [43], we have the following two corollaries refuting the possibility of the existence of polynomial kernels for the two problems.

Corollary 1 GCAI for f^{\text{{CSR}}} does not admit any polynomial kernel with respect to the parameter |T|+k unless the polynomial hierarchy collapses to the third level \left(\mathsf{\text{PH}}={\mathrm{\Sigma }}_{\mathsf{\text{P}}}^{\text{3}}\right).

Note that as S\subseteq T, Corollary 1 implies that GCAI for f^{\text{{CSR}}} is unlikely to admit any polynomial kernel with respect to |S|+k.

Corollary 2 GCAI for f^{\text{{LSR}}} does not admit any polynomial kernel with respect to the parameter |S|+k unless the polynomial hierarchy collapses to the third level. Moreover, this holds even when restricted to QC profiles.

Additionally, note that GCAI is \mathsf{\text{FPT}} with respect to t=|N\setminus T| because it can be solved in O^{\ast }(2^t) time by a brute-force search. Because RBDS is unlikely to admit any polynomial kernel with respect to |R| [34], our reductions in the proofs of Theorems 4 and 6 respectively lead to the following two corollaries.

Corollary 3 GCAI for f^{\text{{CSR}}} does not admit any polynomial kernel with respect to the parameter |N\setminus T| unless the polynomial hierarchy collapses to the third level.

Corollary 4 GCAI for f^{\text{{LSR}}} does not admit any polynomial kernel with respect to the parameter |N\setminus T| unless the polynomial hierarchy collapses to the third level. Moreover, this holds even when restricted to QC profiles.

Finally, observe that GCAI can be also solved in O^{\ast }(t^k) time by a brute-force search. As RBDS cannot be solved in O^{\ast }(2^{o(|R|)}) time assuming the Strong Exponential Time Hypothesis (SETH) [34], and it cannot be solved in O^{\ast }(|R{|}^{o(\kappa )}) time assuming ETH [44], our reductions in the proofs of Theorems 4 and 6 imply that these brute-force based algorithms are essentially optimal.

Corollary 5 Unless SETH fails GCAI for f^{\text{{CSR}}} cannot be solved in O^{\ast }(2^{o(t)}) time, and unless ETH fails GCAI for f^{\text{{CSR}}} cannot be solved in O^{\ast }(t^{o(k)}) time.

Corollary 6 Unless SETH fails GCAI for f^{\text{{LSR}}} cannot be solved in O^{\ast }(2^{o(t)}) time, and unless ETH fails GCAI for f^{\text{{LSR}}} cannot be solved in O^{\ast }(t^{o(k)}) time. Moreover, this holds even when restricted to QC profiles.

6 Appendix

Proof of Theorem 1 Let I=(G,X,u,w,p) be an instance of DVWST. We create an instance of DST equivalent to I as follows.

We first create an arc-weighted digraph G^{\prime } obtained from G by performing the following operations:

(1) Replace every vertex v\in V(G)\setminus (X\cup \{u\}) with two vertices v^{\text{in}} and v^{\text{out}}, add an arc from v^{\text{in}} to v^{\text{out}} with weight w(v), and add some other arcs so that the inneighbors of v^{\text{in}} are exactly the inneighbors of v in G, and the outneighbors of v^{\text{out}} are exactly the outneighbors of v in G.

(2) Set the weights of all arcs whose weights have not been specified to be 0.

Let w^{\prime }:E(G^{\prime })\to \mathbb{N}\cup \{0\} be the function corresponding to the above assignment of weights to arcs in G^{\prime }. The instance of DST is (G^{\prime },X,u,w^{\prime },p). The reduction clearly can be done in polynomial time. It remains to show the correctness.

(\Rightarrow ) Assume that the DVWST instance is a YES-instance, i.e., there is a subset J\subseteq V(G)\setminus (X\cup \{u\}) such that \sum _{v\in J}w(J)\le p, and for every terminal x\in X there is a directed path from u to x in the subgraph of G induced by J\cup X\cup \{u\}. Let E^{\prime } be the set of arcs in G of weight 0. Let J^{\prime }=E^{\prime }\cup \{(v^{\text{in}},v^{\text{out}})\mid v\in J\}. It holds that

\sum _{e\in J^{\prime }}{w}^{\prime }(e)=\sum _{v\in J}{w}^{\prime }((v^{\text{in}},v^{\text{out}}))=\sum _{v\in J}w(v)\le p.

Moreover, if u{v}_1{v}_2\cdots v_{t}x is a directed path from the root u to some terminal x\in X in the digraph G, by the definition of G^{\prime } we know that u{v}_1^{\text{in}}{v}_1^{\text{out}}{v}_2^{\text{in}}{v}_2^{\text{out}}\cdots v_t^{\text{in}}{v}_t^{\text{out}}x is a directed path in G^{\prime }. Therefore, the constructed DST instance is a YES-instance.

(\Leftarrow ) Assume that the constructed instance of DST is a YES-instance, i.e., there is a subset J of arcs in G^{\prime } so that \sum _{e\in J}{w}^{\prime }(e)\le p and, moreover, for every terminal x\in X there is a directed path from u to x in the subgraph of G^{\prime } induced by V(J). Let

J^{\prime }=\{v\in V(G)\setminus (X\cup \{u\})\mid (v^{\text{in}},v^{\text{out}})\in J\}.

Similar to the above analysis, we know that \sum _{v\in J^{\prime }}w(v)\le p and for every terminal x\in X we can change any directed path from u to x in the subgraph of G^{\prime } induced by V(J) into a directed path from u to x in the subgraph of G induced by J^{\prime }\cup X\cup \{u\}. In particular, observe that each v^{\text{in}} has a unique outneighbor v^{\text{out}}. So, in any u-x directed path containing a vertex v^{\text{in}}, the next vertex after v^{\text{in}} in the path must be v^{\text{out}}. Therefore, from a directed path from u to x in G^{\prime }, we can obtain a directed path from u to x in G by replacing every occurrence of v^{\text{in}}{v}^{\text{out}} in the path with the vertex v.

The theorem follows from the above reduction and the fact that DST can be solved in O^{\ast }(2^{\ell }) time, where \ell is the number of terminals [38, 39, 41, 42].　　　　　　　　　　　　　□

References

[1] Kasher A, Rubinstein A . On the question “Who is a J?”: a social choice approach.. Logique et Analyse, 1997, 40( 160): 385–395

[2] Kasher A. Jewish collective identity. In: Goldberg D T, Krausz M, eds. Jewish Identity. Temple University Press, 1993, 56−78

[3] Dimitrov D. The social choice approach to group identification. In: Herrera-Viedma E, García-Lapresta J L, Kacprzyk J, Fedrizzi M, Nurmi H, Zadrożny S, eds. Consensual Processes. Berlin: Springer, 2011, 123−134

[4] Dimitrov D, Sung S C, Xu Y . Procedural group identification. Mathematical Social Sciences, 2007, 54( 2): 137–146

[5] Nicolas H . “I want to be a J!”: Liberalism in group identification problems. Mathematical Social Sciences, 2007, 54( 1): 59–70

[6] Miller A D . Group identification. Games and Economic Behavior, 2008, 63( 1): 188–202

[7] Samet D, Schmeidler D . Between liberalism and democracy. Journal of Economic Theory, 2003, 110( 2): 213–233

[8] Bartholdi J J, Tovey C A, Trick M A . How hard is it to control an election?. Mathematical and Computer Modelling, 1992, 16( 8−9): 27–40

[9] Yang Y, Dimitrov D . How hard is it to control a group?. Autonomous Agents and Multi-Agent Systems, 2018, 32( 5): 672–692

[10] Erdélyi G, Reger C, Yang Y . The complexity of bribery and control in group identification. Autonomous Agents and Multi-Agent Systems, 2020, 34( 1): 8

[11] Erdélyi G, Reger C, Yang Y. Complexity of group identification with partial information. In: Proceedings of the 5th International Conference on Algorithmic Decision Theory. 2017, 182−196

[12] Erdélyi G, Yang Y. Microbribery in group identification. In: Proceedings of the 19th International Conference on Autonomous Agents and Multi-Agent Systems. 2020, 1840−1842

[13] Boehmer N, Bredereck R, Knop D, Luo J. Fine-grained view on bribery for group identification. In: Proceedings of the 29th International Joint Conference on Artificial Intelligence. 2020, 67−73

[14] Junker E. Broadening the complexity-theoretic analysis of manipulative attacks in group identification. Humboldt Universitat zu Berlin, Dissertation, 2022

[15] Junker E. Manipulative attacks and group identification. 2022, arXiv preprint arXiv: 2203.16151

[16] Blažej V. Complexity of games on graphs. Czech Technical University, Dissertation, 2022

[17] Yang Y, Dimitrov D . Group control for consent rules with consecutive qualifications. Mathematical Social Sciences, 2023, 121: 1–7

[18] Brandt F, Brill M, Hemaspaandra E, Hemaspaandra L A . Bypassing combinatorial protections: polynomial-time algorithms for single-peaked electorates. Journal of Artificial Intelligence Research, 2015, 53: 439–496

[19] Faliszewski P, Hemaspaandra E, Hemaspaandra L A, Rothe J . The shield that never was: Societies with single-peaked preferences are more open to manipulation and control. Information and Computation, 2011, 209( 2): 89–107

[20] Peters D. Single-peakedness and total unimodularity: new polynomial-time algorithms for multi-winner elections. In: Proceedings of the 32nd AAAI Conference on Artificial Intelligence. 2018, 1169−1176

[21] Elkind E, Lackner M. Structure in dichotomous preferences. In: Proceedings of the 24th International Joint Conference on Artificial Intelligence. 2015, 2019−2025

[22] Liu H, Guo J. Parameterized complexity of winner determination in minimax committee elections. In: Proceedings of the 15th International Conference on Autonomous Agents and Multi-Agent Systems. 2016, 341−349

[23] Yang Y. On the tree representations of dichotomous preferences. In: Proceedings of the 28th International Joint Conference on Artificial Intelligence. 2019, 644−650

[24] Betzler N, Slinko A, Uhlmann J . On the computation of fully proportional representation. Journal of Artificial Intelligence Research, 2013, 47: 475–519

[25] Skowron P, Yu L, Faliszewski P, Elkind E . The complexity of fully proportional representation for single-crossing electorates. Theoretical Computer Science, 2015, 569: 43–57

[26] Elkind E, Lackner M, Peters D. Structured preferences. In: Endriss U, ed. Trends in Computational Social Choice. AI Access, 2017, 187–207

[27] Hemaspaandra E, Hemaspaandra L A, Rothe J. The complexity of manipulative actions in single-peaked societies. In: Rothe J, ed. Economics and Computation: An Introduction to Algorithmic Game Theory, Computational Social Choice, and Fair Division. Berlin: Springer, 2016, 327−360

[28] Karpov A V . Structured preferences: A literature survey. Automation and Remote Control, 2022, 83( 9): 1329–1354

[29] Elkind E, Lackner M, Peters D. Preference restrictions in computational social choice: A survey. 2022, arXiv preprint arXiv: 2205.09092

[30] Dom M . Algorithmic aspects of the consecutive-ones property. Bulletin of the European Association for Theoretical Computer Science, 2009, 98: 27–59

[31] Peters D, Lackner M . Preferences single-peaked on a circle. Journal of Artificial Intelligence Research, 2020, 68: 463–502

[32] Booth K S, Lueker G S . Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms. Journal of Computer and System Sciences, 1976, 13( 3): 335–379

[33] Hsu W L . A simple test for the consecutive ones property. Journal of Algorithms, 2002, 43( 1): 1–16

[34] Cygan M, Fomin F V, Kowalik Ł, Lokshtanov D, Marx D, Pilipczuk M, Pilipczuk M, Saurabh S. Lower bounds based on the exponential-time hypothesis. In: Cygan M, Fomin F V, Kowalik Ł, Lokshtanov D, Marx D, Pilipczuk M, Pilipczuk M, Saurabh S, eds. Parameterized Algorithms. Cham: Springer, 2015, 467−521

[35] Downey R G, Fellows M R. Fundamentals of Parameterized Complexity. London: Springer, 2013

[36] Bang-Jensen J, Gutin G. Digraphs—Theory, Algorithms and Applications. 2nd ed. London: Springer, 2009

[37] West D B. Introduction to Graph Theory. 2nd ed. Prentice Hall, 2001

[38] Dreyfus S E, Wagner R A . The Steiner problem in graphs. Networks, 1971, 1( 3): 195–207

[39] Guo J, Niedermeier R, Suchý O . Parameterized complexity of arc-weighted directed Steiner problems. SIAM Journal on Discrete Mathematics, 2011, 25( 2): 583–599

[40] Ding B, Yu J X, Wang S, Qin L, Zhang X, Lin X. Finding top-k min-cost connected trees in databases. In: Proceedings of the 23rd International Conference on Data Engineering. 2007, 836−845

[41] Björklund A, Husfeldt T, Kaski P, Koivisto M. Fourier meets Möbius: Fast subset convolution. In: Proceedings of the 39th ACM Symposium on Theory of Computing. 2007, 67−74

[42] Fuchs B, Kern W, Molle D, Richter S, Rossmanith P, Wang X . Dynamic programming for minimum Steiner trees. Theory of Computing Systems, 2007, 41( 3): 493–500

[43] Dom M, Lokshtanov D, Saurabh S . Kernelization lower bounds through colors and IDs. ACM Transactions on Algorithms, 2014, 11( 2): 13

[44] Chen J, Huang X, Kanj I A, Xia G . Strong computational lower bounds via parameterized complexity. Journal of Computer and System Sciences, 2006, 72( 8): 1346–1367

Rights & permissions

The Author(s) 2023. This article is published with open access at link.springer.com and journal.hep.com.cn