How Hard Is It to Impact the Impact of Your Paper?

1 Introduction

Quantitatively evaluating the achievements of scientific researchers plays a significant role in university recruiting, awarding, grant proposal determination, and more. Various measures have been proposed, including the h-index, the i10index, and others. These measures consider a researcher's published papers and the number of citations these papers receive, assigning a numerical score where a higher score is deemed more favorable.

Another relatively recent but impactful bibliometric is the consolidation-disruption (CD) index, initially examined by Funk and Owen-Smith [2017] to assess the degrees of destabilization and consolidation of patents. Wu, Wang, and Evans [2019] first applied this index to scientific publications. According to this index, the contribution of a research paper can fall into the categories of consolidative, disruptive, or somewhere in between. Consolidative implies that a paper adds value to a field by integrating, improving, or expanding upon existing knowledge. Conversely, disruptive indicates that a paper delves into relatively novel directions that may deviate from preceding research, identifies noteworthy flaws in prior studies, or entirely challenges earlier works.

To compute the CD index of a paper p in a citation graph D (a directed graph whose vertices are papers and arcs represent citations between papers), three sets N D F (p), N D B (p), and N D R (p) are identified 1 :

1 The paper being analyzed for its CD index is typically referred

• N D F (p) is the set of nonreferences (papers not cited by p) of p, each of which cites p but none of p's references.
• N D B (p) is the set of nonreferences of p, each of which cites both p and at least one reference of p.
• N D R (p) is the set of nonreferences of p, each of which does not cite p but cites at least one reference of p.

The CD index ranges between -1 and 1. A higher value indicates greater disruption to the related area by the paper, whereas a lower value suggests a more consolidative impact.

The groundbreaking study by Wu, Wang, and Evans [2019] unveiled a somewhat surprising discovery: "large teams develop and small teams disrupt science and technology". Their work has amassed 777 citations (according to Google Scholar as of May 5, 2024), underscoring the significant impact of the CD index in the scientific realm. Based on this index, a more recent investigation conducted by Park, Leahey, and Funk [2023] suggests that papers are much less likely to break with the past in ways pushing science and technology in new directions. Other scholars pointed out that scientific innovation appears to be slowing down, and appealed to academia to "make science disruptive again" [Yanai and Lercher, 2023].

However, concerns regarding the reliability of the CD index have prompted public debate on the application of the index. For example, as noted by Liu, Zhang, and Li [2023], even minor alterations in a paper's references could significantly impact its CD index. This has led several researchers to question the validity of the index and advocate for a more rigorous investigation of its theoretical underpinnings before its widespread adoption [Leibel and Bornmann, 2024]. In pursuit of a preliminary solution to this issue, we study the manipulability of this index. Specifically, we explore the complexity challenges associated with manipulating the CD index of papers using operations such as paper merging, addition, or deletion, through the lens of parameterized complexity. Our problem formulations encompass scenarios in which a scholar seeks to identify a set of representative papers and endeavors to achieve this objective through one of the aforementioned modification operations. The feasibility of these modification operations is evident on academic online platforms like Google Scholar, which allows scholars to manually add new manuscripts, delete articles, and merge their own papers. Our main contributions are as follows.

to as the focal paper. The subscripts F, B, and R respectively stand for the words "focal", "both", and "remaining".

1. We initiate the study of the CD index manipulation problems, and show that they are computationally hard even when restricted to very realistic special cases.
2. In the problem of CD index manipulation by merging papers, a scholar seeks to ensure that at least ℓ papers in a citation graph attain a CD index of at least d (a threshold deemed satisfactory by the scholar), by performing at most β merging operations on papers from a given set W, such as papers authored by the scholar. We depict the similarity relation between papers through a compatibility graph H, where an edge signifies similarity, and only papers exhibiting similarity (forming a clique) are eligible for merging. We show that w.r.t. the parameters β and ℓ, this problem exhibits a W[1]-hardness or a para-NP-hardness lower bound, even when each connected component of H contains at most two papers and the citation graph is acyclic. However, we also derive XP-algorithms for these two parameters.
3. In the problems of CD index manipulation by adding/deleting papers, a scholar aims to ensure that each paper in a given set J has a CD index of at least d by adding/deleting at most k papers. We explore the parameters k and |J|. The results for these problems exhibit a diverse range, including both fixed-parameter tractability and fixed-parameter intractability. It is noteworthy that the complexity varies in certain instances when considering cases where d = 1 and d < 1. Moreover, we identify several complexity dichotomies w.r.t. the parameter |J|. Another interesting finding is that when d = 1 and the parameter is k, the problem of adding papers is W[2]-hard, while the problem of deleting papers is fixed-parameter tractable (FPT).
4. We also explore variants of the manipulation problems involving paper addition/deletion where the scholar does not concern themselves with the specific number of papers added or deleted. Our results indicate that, for the paper addition operation, the complexity of the original problem and the variant coincide. However, for the pa-

per deletion problem, the variant is easier to solve than the original one.

Our results are summarized in Table 1 and Table 2.

2 RelatedWorks

Our study is closely related to the works of van Bevern et al. [2020; 2016], who are the first to explore the complexity of determining if a scholar could improve their hindex by adding, deleting, or merging papers. 2 In a subsequent paper, Pavlou and Elkind [2016] studied the complexity of similar problems for the g-index and the i10-index.

From a motivational standpoint, our work also bears relevance to election control problems. These problems model scenarios where an election controller endeavors to influence the election outcome by adding/deleting a(n) (un)limited number of voters/candidates [Bartholdi III et al., 1992; Baumeister and Rothe, 2016; Erd´elyi et al., 2021; Erd´elyi et al., 2020; Faliszewski and Rothe, 2016; Yang, 2019].

The CD index can be mathematically regarded as an "centrality measure" of vertices in a network. Problems involving improving the influence of a vertex by adding/deleting vertices or edges (or arcs) have been thoroughly explored in the literature. Betzler et al. [2014] investigated the problems of determining whether a given vertex can achieve a maximum/minimum degree by adding/deleting vertices. Variants of the problems restricted to special graph classes have also received attention [Li et al., 2023; Mishra et al., 2015]. Analogous problems concerning other centrality measures have been studied as well [Bergamini et al., 2018; D'Angelo et al., 2019; D'Angelo et al., 2015]. Furthermore, concepts for quantifying the centrality of groups of vertices and associated centrality-maximizing or -minimizing problems have also been examined [Waniek et al., 2023; Waniek et al., 2022]. For comprehensive summaries of many centrality measures, please refer to [Das et al., 2018; Singh, 2022; Wan et al., 2021].

Finally, we would like to point out that very recently, several variants of the CD index have been proposed [Leydesdorff et al., 2021; Wang et al., 2023; Yang et al., 2023]. Particularly, Jiang and Liu [2023] proposed an analogous index for measuring the disruption of journals.

2 The conference versions of the two papers first appeared in 2016 and 2015, respectively.

|J| = 2: NP-h (Thm.10) |J| = 2: NP-h (Thm.11) XP (trivial)

|J| = 3: NP-h (Thm.17)

Table 2: The complexity of CD index manipulation by adding/deleting papers. All hardness results except the one for CDMANI-DEL∞ with d < 1 hold for acyclic citation graphs. The tractability result for CD-MANI-DEL∞ with d < 1 and |J| = 2 holds for acyclic citation graphs, while other tractability results hold for general citation graphs.

3 Preliminaries

We assume the reader is familiar with the basics of graph theory [Bang-Jensen and Gutin, 2018; West, 2000].

3.1 Citation Graphs and the CD index

A citation graph D is a digraph, where each vertex represents a scientific paper, and an arc from v to u, denoted (v, u), means that v cites u. We use V (D) to denote the vertex set of D, and use A(G) to denote its arc set. Throughout the paper, we use the terms "vertex" and "paper" interchangeably. The set of inneighbors of v ∈ V (D) in D is Γ-D (v) = {u ∈ V (D) \ {v} : (u, v) ∈ A(D)}. The set of outneighbors of v in D is Γ+D (v) = {u ∈ V (D) \ {v} : (v, u) ∈ A(D)}. We call papers in Γ+D (v) the references of v, and call those in Γ-D (v) the citations of v. Let ΓD(v) = Γ-D (v) ∪ Γ+D (v). For S ⊆ V (D), let Γ+D (S) = (⋃v∈S Γ+D (v)) \ S and let Γ-D (S) = (⋃v∈S Γ-D (v)) \ S. For v ∈ V (D), we define

• N D B (v) = {u ∈ Γ-D (v) \Γ+D (v) : Γ+D (u)∩Γ+D (v) ̸= ∅}.
• N D F (v) = {u ∈ Γ-D (v)\Γ+D (v) : Γ+D (u)∩Γ+D (v) = ∅}.
• N D R (v) = {u ∈ V (D) \ (ΓD(v) ∪ {v}) : Γ+D (u) ∩ Γ+D (v) ̸= ∅}.

For each X ∈ {F, B, R}, let nDX (v) = |N D X (v)|.

Definition 1 (CD Index). The CD index of a paper v in a citation graph D is nDF (v)-nDB (v) nDF (v)+nDB (v)+nDR (v) if the denominator is nonzero, and is undefined otherwise.

Notice that, by definition, for two papers v and v′ citing each other, 3 when we analyze the CD index of v, v′ is classified as a reference of v and, hence, is excluded from N D F (v) ∪N D B (v) ∪N D R (v). See Figure 2 for an illustration.

3.2 The Merging Operation

Before formally introducing the manipulation problems, we need to clarify a few points.

First, in practice, scholars usually only merge papers with similar titles or topics. To formulate this assumption, we adopt the notion of compatibility graph used by van Bevern et al. [2016]. A compatibility graph is an undirected graph H whose vertices represent papers, and an edge between two papers represents that the two papers share some kind of similarity. A subset of papers can be merged into one paper only if they form a clique in the compatibility graph.

3 This scenario might occur in cases where, for instance, two research groups independently discover the same result almost simultaneously, and the authors mutually agree to acknowledge each other's work for the sake of ensuring a secure publication, respectfulness, or addressing ethical considerations.

Second, it is essential to elucidate the CD index of a paper subsequent to certain merging operations. In the study of the h-index manipulation problems, van Bevern et al. [2016] examined three methodologies to ascertain the citation count a paper accrues post-merging operations. In our framework, not only the quantity but also the categories of these citations hold significance. Hence, the straightforward adoption of the three approaches is not viable. Nevertheless, the fundamental principle of an approach employed by van Bevern et al. [2016] posits that merging a set of papers entails considering this set as a singular entity. We find this approach to be the most intuitive and natural, thus opting to incorporate it into our study.

A lingering puzzle remains: how do we handle selfcitations? In the majority of prior related research, selfcitation is typically excluded or encountered infrequently in experimental works. However, the act of merging papers has the potential to transform a citation graph that initially lacks self-citation into one where self-citation is present. This transformation is exemplified when a paper is merged with some of its references. Such a scenario is not uncommon, particularly in computer science areas, where merging the journal version and its conference versions occurs, with the journal version often citing the conference versions. We emphasize that all our hardness reductions are meticulously designed to prevent the occurrence of such self-citations.

Having resolved potential confusion, let us now proceed to formalize the aforementioned discussion.

Definition 2 (Merging Operation). A merging operation on a subset P ⊆ V (D) of papers in a citation graph D entails:

1. Create a new paper vP and add arcs so that the set of outneighbors of vP is exactly Γ+D (P), and the set of in-

neighbors of vP is exactly Γ-D (P).

(2) Remove all papers in P fromD.

We use DP to denote the citation graph obtained from D by performing the merging operation on P .

For a partition P of a subset W ⊆ V (D), we use DP to denote the citation graph obtained from D by performing merging operations on all P ∈ P, one after another. As P is a partition, the order of parts of P in which the operations are executed is immaterial to the resulting graph. For S ⊆ W, we define SP = {vP : P ∈ P, P ∩ S ̸= ∅}. Let P ≥2 = {P ∈ P : |P| ≥ 2}. We say that P complies with a compatibility graph H if every P ∈ P induces a clique of H. For an illustration of the above discussion, see Figure 3.

3.3 Parameterized Complexity

An instance of a parameterized problem is a tuple (I, κ), where κ is a numerical parameter. A parameterized problem is FPT (resp. XP) if it is solvable in time f(κ) · |I|O(1) (resp. |I|f(κ) ), where f is a computable function and |I| is the size of I. A well established hierarchy in the realm of parameterized complexity is FPT ⊆ W[1] ⊆ W[2] ⊆ · · · ⊆ XP. A problem is W[i]-hard if all problems in W[i] are parameter reducible to it. Unless FPT = W[i], W[i]-hard problems do not admit FPT-algorithms, but they (not necessarily all) may have XP-algorithms. A para-NP-hard problem is unlikely to even have an XP-algorithm: a problem is para-NP-hard if there is a constant c such that the problem is NP-hard even when the parameter is fixed to any constant no smaller than c. For further insights, refer to [Cygan et al., 2015].

3.4 Remarks

All reductions presented in the paper are executable in polynomial time, and the problems utilized in the reductions are NP-hard. Hence, if a problem is asserted to be W[1]/W[2]- hard, it is also NP-hard. Moreover, for a para-NP-hardness result, we exclusively present the reduction for the minimum c where the NP-hardness holds when the parameter is set to c. These reductions can be slightly modified by incorporating dummy structures to demonstrate the hardness for all parameters greater than c. Furthermore, it's worth noting that W[1]/W[2]-hardness w.r.t. a combined parameter κ + κ′ implies W[1]/W[2]-hardness w.r.t. κ and κ′ individually.

4 The Manipulation Problems

Now we formally introduce the CD index manipulation problems. For an integer i, we use [i] to denote the set of all positive integers not exceeding i. Let [0, 1] be the set of all numbers ranging from 0 to 1.

For an undirected graph G, V (G) and E(G) represent the vertex set and the edge set of G, respectively. The first CD index manipulation problem is defined as follows.

CD Index Manipulation by Merging Papers

(CD-MANI-MERGE)

Input: A citation graph D, a subset W ⊆ V (D), a compatibility graph H such that V (H) = V (D), two integers ℓ, β, and a rational number d ∈ [0, 1].

Question: ∃ a partition P of W that complies with H such that |P ≥2 | ≤ β, and at least ℓ papers from W P have a CD index of at least d in DP ?

The subsequent manipulation problems model a scenario where a scholar has selected a set J of papers published in reputable venues, or the papers are regarded as robust papers w.r.t. other measures. This selection is made to strengthen her application for a research grant (or a scientific position, etc.). However, some of the papers exhibit relatively low CD indices. The grant committee, prioritizing projects with innovative ideas or those opening new directions, highly values such aspects. Assume that an online platform, endorsed by the grant entity, offers CD index calculation functions, and scholars are permitted to add new papers (included in a set denoted U) or remove existence ones (included in a set denoted V ) from the system. To increase the chance of success, the scholar grapples with the question of whether she can elevate the CD indices of all these selected papers to a satisfactory level by adding or deleting at most k papers. The two problems are formally defined as follows.

For a citation graph D and a subset S ⊆ V (D), D[S] is the subgraph of D induced by S, and D - S denotes the citation graph obtained from D by removing all papers in S.

CD Index Manipulation by Adding Papers

(CD-MANI-ADD)

Input: A citation graph D, a tuple (V, U) of two disjoint sets of papers such that V ∪ U = V (D), a subset J ⊆ V , an integer k, and a rational number d ∈ [0, 1].

Question: ∃U ′ ⊆ U such that |U ′ | ≤ k and each paper from J has a CD index of at least d in D[V ∪ U ′ ]?

CD Index Manipulation By Deleting Papers

(CD-MANI-DEL)

Input: A citation graph D, a subset J ⊆ V (D), an integer k, and a rational number d ∈ [0, 1].

Question: ∃V ′ ⊆ V (D) \ J such that |V ′ | ≤ k and each paper from J has a CD index of at least d in D - V ′ ?

We also explore a natural variant of CD-MANI-ADD/CDMANI-DEL, where the scholar aims to achieve their goal without considering the addition/deletion budget k. Precisely, the CD-MANI-ADD∞/CD-MANI-DEL∞ problem takes the same input as CD-MANI-ADD/CD-MANI-DEL without k, and determines the existence of a subset U ′ ⊆ U (resp. V ′ ⊆ V (D)) such that each paper from J has a CD index of at least d in D[V ∪U ′ ] (resp. D-V ′ ).

5 Manipulation by Paper Merging

This section is dedicated to the complexity of CD-MANIMERGE. We first show that the problem is hard to solve even when restricted to very special cases. Our reduction is from the CLIQUE problem, which takes as input an undirected graph G and an integer κ, and determines if G has a clique of κ vertices. The problem is W[1]-hard w.r.t. κ even when restricted to regular graphs [Mathieson and Szeider, 2008].

Theorem 1. For any positive rational number d < 1, CDMANI-MERGE is W[1]-hard w.r.t. β, even if ℓ = 1, every connected component of the compatibility graph contains at most two papers, and the citation graph is acyclic.

Proof for d = 1/3. Let I = (G, κ) be an instance of CLIQUE, where G is t-regular with t > 0. Let n be the number of vertices of G, and let m = n·t 2 be the number of edges of G. W.l.o.g., we assume t > κ ≥ 7 (otherwise, I can be solved trivially). We create an instance g(I) = (D, W, H, ℓ, β, d), where ℓ = 1, β = κ, and d = 1/3 as follows.

For every v ∈ V (G), we create two vertices v(1) and v(2). For each i ∈ [2], let V (i) = {v(i) : v ∈ V (G)}. For each edge e in G, we create a paper v(e). Additionally, we create two papers v⋆ and y, two sets X and Z, each consisting of 4(n-κ)+t · κ- κ·(κ-1) 2 papers, and a set S of 4(m+2n+1) papers. As t > κ ≥ 7, X and Z are nonempty. The arcs of D are created so that exactly the following citations exist: (1) All papers in X cite v⋆ . (2) The paper v⋆ cites all papers from V (2). (3) All papers in V (1) cite all papers in V (2) ∪ {v⋆ }. (4) For each edge e = {u, v} in G, the paper v(e) cites u(1) and v(1). (5) All papers in V (1) ∪ V (2) cite y. (6) All papers in Z cite all papers in V (1) ∪ V (2) ∪ {y}. (7) All papers from S cite y. Let W = V (1) ∪ V (2) ∪ {v⋆ }. The edge set of the compatibility graph H is {{v(1), v(2)} : v ∈ V (G)}. See Figure 4 for an illustration of the reduction. We prove its correctness below.

(⇒) Assume that G has a clique K of κ vertices. Let ∂G(K) = {e ∈ E(G) : e ∩K ̸= ∅} be the set of edges in G covered by K. Obviously, |∂G(K)| = t · κ - κ·(κ-1) 2 . Let P be a partition of W such that P ≥2 = {{v(1), v(2)} : v ∈ K}. Consider the citation graph DP , i.e., the graph obtained from D by merging, for each vertex v ∈ K, the corresponding two papers v(1) and v(2). It is fairly easy to verify that the CD index of v⋆ in DP is |X|-(|V (1)|-|K|) |X|+(|V (1)|-|K|)+|Z|+|∂G(K)| . Substituting the values of |X|, |V (1)|, |K|, |Z|, and |∂G(K)| into the above expression yields the index threshold 1/3.

(⇐) Assume that there is a partition P of W that complies with the compatibility graph H such that |P ≥2 | ≤ β = κ and e = {v, u}

Figure 4: An illustration of the proof of Theorem 1.

at least one paper fromW P has a CD index of at least 1/3 in the citation graph DP . The presence of y and S precludes any paper from (V (1) ∪ V (2))P from attaining a CD index of at least 1/3. This leaves only the possibility that v⋆ has a CD index of at least 1/3 in DP . Let K = {v ∈ V (G) : {v(1), v(2)} ∈ P ≥2 }. Merging two papers v(1) and v(2) for any v ∈ V (G) changes the membership of v(1) from N D B (v⋆ ) to the set of references of v⋆ , and simultaneously brings all edge-papers covered by v into N D R (v⋆ ). Consequently, the CD index of v⋆ in DP is

Let m′ be the number of edges in G[K]. As G is t-regular, it holds |∂G(K)| = t · |K| -m′ . It follows that (1) is at least 1/3 if and only if |K| = |P ≥2 | = κ and m′ = κ·(κ-1) 2 , i.e., when K is a clique in G.

The above hardness does not cover the case where d = 1. Recall that a paper possesses a CD index of 1 if and only if, among the three sets defining the CD index, exactly the set N D F (v) is nonempty, significantly shrinking the search space. This might seem to simplify the problem. However, a difficulty arises in identifying which papers can have their indices increased to 1 through paper merging. This difficulty leads to the following hardness result.

Theorem 2. For d = 1, CD-MANI-MERGE is W[1]-hard w.r.t. β +ℓ, even if each connected component of the compatibility graph has at most two papers and the citation graph is acyclic.

What if d = 1 and we target only a constant number ℓ of papers to have a CD index of 1? In the case where ℓ = 1, we can hypothesize which paper v fromW is the targeted paper, and then focus on making N D F (v) nonempty while ensuring both N D B (v) and N D R (v) are empty. Would this simplicity turn the complexity of the problem? We show that the answer hinges on the structure of the compatibility graph, as elucidated in the ensuing two theorems.

Theorem 3. For d = 1, CD-MANI-MERGE is in XP w.r.t. ℓ, when each connected component of the compatibility graph is of constant size.

Theorem 4. For any positive rational number d ≤ 1, CDMANI-MERGE is NP-hard, even if ℓ = 1, β = 3, and the citation graph is acyclic.

When considering β as the parameter, we obtain:

Theorem 5. CD-MANI-MERGE is in XP w.r.t. β when each connected component of the compatibility graph contains a constant number of papers.

6 Manipulation by Paper Addition

Now we examine the operation of paper addition. We observe that CD-MANI-ADD is in XP when parameterized by k: it can be solved by enumerating all possible sets of at most k papers to be added. Can we enhance the result to fixedparameter tractability? The next theorem answers this question in the negative.

Theorem 6. For any positive rational number d ≤ 1, CDMANI-ADD is W[2]-hard w.r.t. k, even if the citation graph is acyclic.

Furthermore, we show that restricting the value of d to 1 does not render the complexity of the problem FPT, even when associated with a larger parameter. Our result relies on the MULTICOLORED CLIQUE problem, which takes as input an undirected graph G whose vertices are partitioned into κ sets (Vi)i∈[κ], and determines if G has a clique (termed κ-colored clique) which contains exactly one vertex from each Vi for all i ∈ [κ]. The problem is W[1]-hard w.r.t. κ [Fellows et al., 2009].

Theorem 7. For d = 1, CD-MANI-ADD is W[1]-hard w.r.t. |J| + k. This holds even if the citation graph is acyclic.

Proof. Let I = (G, κ) be an instance of MULTICOLORED CLIQUE, where V (G) is partitioned into (V1, V2, . . . , Vκ) and κ ≥ 2. We create an instance of CD-MANI-ADD as follows. For each v ∈ V (G), we create one paper denoted by the same symbol. For each edge e = {v, u} in G, we create one paper p(e). For distinct i, j ∈ [κ], let P{i,j} = {p(e) : e ∈ E(G), e ∩ Vi ̸= ∅, e ∩ Vj ̸= ∅}. Besides, we create a set X = {x1, x2, . . . , xκ} of κ papers and a set Y = {y{i,j} : i, j ∈ [κ], i ̸= j} of κ·(κ-1) 2 papers. Let V =X∪Y be the set of registered papers, and let U = V (G) ⋃i,j∈[κ],i̸=j P{i,j} be the set of unregistered papers. Arcs in D are created so that exactly the following citations exist: (1) For every i ∈ [κ], all papers from Vi cite xi. (2) For distinct i, j ∈ [κ], all papers from P{i,j} cite y{i,j}. (3) For distinct i, j ∈ [κ] and every edge e = {v, u} between Vi and Vj in G, the paper p(e) cites all papers from (Vi ∪ Vj) \ {v, u}. (4) For distinct i, j ∈ [κ], the paper y{i,j} cites all papers from Vi ∪Vj . Let J = X ∪Y and let k = κ + κ·(κ-1) 2 . The instance of CD-MANI-ADD is g(I) = (D, (V ∪ U), J, k, d), where d = 1. See Figure 5 for an illustration.

(⇒) Assume that there is a κ-colored clique K in G. Let P(K) be the set of the κ·(κ-1) 2 papers corresponding to the edges within K. Consider the citation graph D′ = D[V ∪ K ∪ P(K)]. For every xi ∈ X, as |K ∩ Vi| = 1, the construction of the citation graph D ensures that the CD index of xi in D′ is 1. Now consider a paper y{i,j}, where {i, j} ⊆ [κ]. As K is a κ-colored clique of G, it holds that |P(E) ∩ P{i,j}| = 1. W.l.o.g., let P(E) ∩ P{i,j} = {p({v, u})}, where {v, u} ∈ E(G), v ∈ Vi, and u ∈ Vj.

y{i,j}

Figure 5: An illustration of the proof of Theorem 7.

Consequently, K ∩ Vi = {v} and K ∩ Vj = {u}. According to the reduction, in D′ , v and u are the only references of y{i,j}, p(e) is the only paper citing y{i,j}, and p(e) cites neither v nor u. As a result, the CD index of y{i,j} in D′ is 1. Since |K∪P (K)| = κ+ κ·(κ-1) 2 = k, g(I) is a Yes-instance. (⇐) Assume that there is a subset U ′ ⊆ U of at most k papers such that every paper in J has a CD index of 1 in the citation graph D′ = D[V ∪ U ′ ]. By the construction of D, a necessary condition for an xi ∈ X to have a CD index of 1 in D′ is that U ′ contains at least one paper from Vi. A necessary condition for a paper y{i,j} ∈ Y to have a CD index of 1 in D′ is that U ′ contains at least one paper from P{i,j}. As k = κ + κ·(κ-1) 2 , we know that |U ′ ∩ Vi| = 1 for all i ∈ [κ], and |U ′ ∩ P{i,j}| = 1 for all distinct i, j ∈ [κ]. Let K = U ′ ∩ V (G). We prove that K is a clique in G by contradiction. Assume that K contains two vertices v and u respectively from two distinct Vi and Vj such that there exists no edge between v and u in G. Let {p(e)} = U ′ ∩ P{i,j} where e is an edge in G crossing Vi and Vj. Clearly, e ̸= {v, u}. Then, by the construction of D, p(e) cites at least one of v and u. However, as y{i,j} cites both v and u, the CD index of y{i,j} in D′ cannot be 1, a contradiction. So, K is a clique in G. From |U ′ ∩ Vi| = 1 for all i ∈ [κ], we know that K is a κ-colored clique in G.

The above reduction also applies to CD-MANI-ADD∞. Corollary 1. For d = 1, CD-MANI-ADD∞ is W[1]-hard w.r.t. |J|. This holds even if the citation graph is acyclic.

Theorem 7 dismisses the feasibility of achieving FPTalgorithms when parameterized by |J|, unless FPT=W[1]. Nevertheless, there still exists a potential for the problem to become tractable when |J| is a constant. We first explore this prospect for the case where J is a singleton.

Theorem 8. CD-MANI-ADD is polynomial-time solvable when |J| = 1.

Proof. Let (D, (V, U), J, k, d) be an instance of CD-MANIADD, where J = {v⋆ }. Let X = {u ∈ U : V ∩ Γ+D (v⋆ ) ∩ Γ+D (u) ̸= ∅} be the set of all unregistered papers which cite at least one reference of v⋆ in V . Let U ′ = Γ-D[U] (v⋆ ) \ (X ∪ Γ+D (v⋆ )) be the set of all unregistered citations of v⋆ that do not cite any registered references of v⋆ and not cited by v⋆ . Let k′ = min{k, |U ′ |}, and let U ′′ be any arbitrary k′ -subset of U ′ . We conclude that I is a Yes-instance if and only if v⋆ has a CD index of at least d in D[V ∪ U ′′ ].

As CD-MANI-ADD∞ is Turing reducible to CD-MANIADD, the former is also polynomial-time solvable when |J| = 1. We confirm next that for d = 1, tractability extends to all constant-bounded |J|.

Theorem 9. For d = 1, CD-MANI-ADD and CD-MANIADD∞ are in XP w.r.t. |J|.

However, for other positive values of d, the parameter |J| complicates the problem, as stated in the following theorems.

Theorem 10. For any positive rational number d < 1, CDMANI-ADD is W[1]-hard w.r.t. k, even if |J| = 2 and the citation graph is acyclic.

Theorem 11. For any positive rational number d < 1, CDMANI-ADD∞ is NP-hard, even if |J| = 2 and the citation graph is acyclic.

7 Manipulation by Paper Deletion

We arrive at the problem of CD index manipulation by deleting papers. Clearly, the problem is in XP w.r.t. k. This poses the question if it is indeed FPT for the same parameter. In contrast to the negative answer for the problem of adding papers, we show that the values of d play a decisive role in this regard: CD-MANI-DEL is FPT w.r.t. k if and only if d = 1.

Theorem 12. For d = 1, CD-MANI-DEL is FPT w.r.t. k.

Theorem 13. For any positive rational number d < 1, CDMANI-DEL is W[1]-hard w.r.t. |J|+k. This holds even if the citation graph is acyclic.

Theorem 13 implies that CD-MANI-DEL is W[1]-hard w.r.t. |J|. However, it does not rule out the possibility of polynomial-time solvability for |J| being a constant. The following three theorems, collectively forming a complexity dichotomy, address this inquiry.

Theorem 14. For d = 1, CD-MANI-DEL is polynomial-time solvable if |J| = 1.

Proof. Let I = (D, J, k, d) be an instance of CD-MANIDEL, where d = 1. W.l.o.g., let J = {v⋆ } ⊆ V (D). We distinguish between two cases.

Case 1: N D F (v⋆ ) ̸= ∅.

Let V ′ = N D B (v⋆ ) ∪ N D R (v⋆ ). We construct a bipartite graph G with the vertex partition (Γ+D (v⋆ ), V ′ ). The edges of G correspond to arcs from V ′ to Γ+D (v⋆ ) in D: if v ∈ V ′ cites u ∈ Γ+D (v⋆ ) in D, we create an edge between v and u in G. To make v⋆ have a CD index of 1 by deleting papers, for each v ∈ V ′ , either v needs to be deleted or all neighbors of v in G need to be deleted. This is equivalent to computing a minimum vertex cover in G, which can be solved in polynomial time, provided with G being bipartite [Lov´asz and Plummer, 1986; K¨onig, 1916; Hopcroft and Karp, 1973]. We conclude I is a Yes-instance if and only if G has a vertex cover of at most k vertices.

Case 2: N D F (v⋆ ) = ∅.

If N D B (v⋆ ) = ∅, we conclude I is a No-instance. Otherwise, to make v⋆ have a CD index of 1 by deleting papers, we need to delete certain papers from Γ+D (v⋆ ) so that some paper v originally from N D B (v⋆ ) becomes a member of the set N D F (v⋆ ). We do not know the identity of v in advance, but there can be at most |N D B (v⋆ )| possibilities. In light of this, for every vertex v ∈ N D B (v⋆ ), we do the following: (1) Decrease k by |Γ+D (v)\{v⋆ }|, and delete all outneighbors of v in D except v⋆ . (2) Run the procedure described in Case 1, and if the output is "Yes", conclude that I is a Yes-instance, otherwise discard v. If all v ∈ N D B (v⋆ ) are discarded, we conclude that I is a No-instance.

Theorem 15. For d = 1, CD-MANI-DEL is NP-hard, even if |J| = 2 and the citation graph is acyclic.

Theorem 16. For any positive rational number d < 1, CDMANI-DEL is NP-hard, even if |J| = 1 and the citation graph is acyclic.

Now we study the variant CD-MANI-DEL∞.

Theorem 17. CD-MANI-DEL∞ is NP-hard even if |J| = 3.

When J contains only one paper v⋆ with at least one citation, we can always achieve a CD index of 1 for v⋆ by deleting all papers except v⋆ and any arbitrary citation of v⋆ . For |J| = 2, we can also obtain a polynomial-time algorithm.

Theorem18. CD-MANI-DEL∞ is polynomial-time solvable when |J| ≤ 2 and when the citation graph is acyclic.

For the case where d = 1, we obtain the following results.

Theorem 19. For d = 1, CD-MANI-DEL∞ is W[1]-hard w.r.t. |J|, even when the citation graph is acyclic.

Theorem 20. For d = 1, CD-MANI-DEL∞ is in XP w.r.t. |J|.

8 Concluding Remarks

We initiated the study of the CD index manipulation problems, offering a comprehensive understanding of the parameterized complexity of these problems for several significant parameters. See Table 1 and Table 2 for a summary. In general, we showed that these problems are hard to solve, with only a few exceptions. It is noteworthy that our results for CD-MANI-MERGE remain applicable even when the compatibility graph comprises a matching along with several isolated vertices, thereby ruling out fixed-parameter tractability of the problem concerning the treewidth of the compatibility graph. This conveys that, at least in theory, the CD index exhibits a high degree of reliability in the aspect of preventing manipulation. However, rather than concluding at this juncture, we aspire for our initiative to ignite further comprehensive investigations aimed at fully addressing questions surrounding the applicability of the CD index. To provide a more tangible direction, our study encourages a meticulous experimental exploration to verify whether these problems are difficult to solve in practice.

Acknowledgments

The author extends sincere appreciation to the three anonymous reviewers of IJCAI 2024 for their invaluable feedback and insightful comments.