Being an Influencer is Hard: The Complexity of Influence Maximization in Temporal Graphs with a Fixed Source (aamas23-00260)

Given a finite type set \(Q\) with rational masses \(\mu_q\), \(\sum_{q\in Q}\mu_q=1\), a distinguished source \(s\), period \(p\), repeated type relations \(E_1,\ldots,E_p\), influence duration \(\delta\), and posting budget \(b\), where each relation is lifted to complete cohort-to-cohort contacts, choose \(T\subseteq\mathbb{N}\) with \(|T|\le b\) to maximize \(\sum_{q\in Q}\mu_q\mathbf{1}[q\text{ is active at some time under }T]\) under the paper's renewal dynamics.

A society is given by its support: a nonempty list \(Q\) of \(\tau\) types with positive binary-rational masses \(\mu_q\), summing to \(1\); \(\tau\) is the support size, not the number of possible types.
Input also includes a source type \(s\in Q\), positive binary integers \(p,\delta,b\), explicitly listed undirected loopless relations \(E_1,\ldots,E_p\), and a binary-rational threshold \(k\in(0,1]\). Write \(m=\sum_{i=1}^{p}|E_i|\) and let \(L\) be the total input bit length.
At time \(t\geq1\), every related pair of types has complete cohort-to-cohort contact according to \(E_{1+((t-1)\bmod p)}\). Each cohort has a common counter \(c_q(t)\in\{0,\ldots,\delta\}\), and is active exactly when its counter is positive.
A schedule is a finite set \(T\subseteq\mathbb Z_{\geq1}\) with \(|T|\leq b\); each posting activates the entire source cohort. Initially \(c_q(1)=0\) for \(q\neq s\), while \(c_s(1)=\delta\) if \(1\in T\), and zero otherwise.
For \(q\neq s\), set \(c_q(t+1)=\delta\) whenever some contacting cohort is active at \(t\), including when \(q\) is already active; otherwise set \(c_q(t+1)=\max\{c_q(t)-1,0\}\). Set \(c_s(t+1)=\delta\) if \(t+1\in T\), and \(\max\{c_s(t)-1,0\}\) otherwise; contacts never renew the source.
Decide whether some schedule achieves \(\sum_{q\in Q}\mu_q\mathbf1[\exists t\geq1:c_q(t)>0]\geq k\), counting the source mass and allowing influence to continue forever after the last posting.

Is this continuous MaxSpread decision problem in \(\mathrm P\), or is it \(\mathrm{NP}\)-hard, when \(p\) is unrestricted? If it is hard, is it FPT parameterized by \(p\)? State running times in \(m,\tau,L,p,\delta,b\).

Discrete periodic MaxSpread admits a \(2^p\operatorname{poly}(|V|)\)-time algorithm; the authors also claim hardness for unrestricted periods. Finite-lifetime MaxSpread is \(\mathrm{NP}\)-hard and \(\mathrm{W}[2]\)-hard parameterized by the posting budget. [Verified source](https://arxiv.org/html/2303.11703v2).
No published result settling this exact mass problem was found in the search.

Classification

The problem is \(\mathrm{NP}\)-complete when \(p\) is unrestricted, already for \(\delta=1\), \(k=1\), and relations forming a star centered at the source. It is FPT parameterized by \(p\), including when \(\delta\) and \(b\) are binary encoded.

Put \(D=\min\{\delta,p\}\), \(B=\min\{b,p\}\), and
\( N_{p,B}=\sum_{j=0}^{B}\binom pj. \)
An explicit bit-operation bound is
\[ O\!\left(L^3+\bigl(p^2\tau+pmD+N_{p,B}\tau+1\bigr)L^2\right). \]
In particular, this is at most
\[ O\!\left(L^3+\bigl(p^2(\tau+m)+2^p\tau+1\bigr)L^2\right). \]

The cited paper’s [Theorem 12](https://arxiv.org/html/2303.11703v2#S5) establishes the corresponding unweighted periodic result. Below is a direct proof for the precise mass model, with a finite reachability construction that avoids dependence on the numerical value of a large \(\delta\).

1. Superposition of schedules

Write \(c_q^T(t)\) for the counter under schedule \(T\), and define its eventual spread by
\[ R(T)=\{q\in Q:\exists t\geq1,\ c_q^T(t)>0\}. \]

Lemma 1. For any finite schedules \(A,B\), every type \(q\), and every time \(t\),
\[ c_q^{A\cup B}(t)=\max\{c_q^A(t),c_q^B(t)\}. \]

Proof. At time \(1\), the identity follows directly from the initialization.

Suppose it holds at time \(t\). For a nonsource type \(q\), a contacting cohort is active under \(A\cup B\) exactly when a contacting cohort is active under at least one of \(A,B\). If this happens, the union counter resets to \(\delta\), and at least one individual counter also resets to \(\delta\). Their maximum is therefore \(\delta\).

Otherwise, all three counters decay. The decay map \(f(x)=\max\{x-1,0\}\) satisfies
\[ f(\max\{x,y\})=\max\{f(x),f(y)\}, \]
so the identity is preserved.

For the source, a posting at time \(t+1\) occurs under the union exactly when it occurs under at least one individual schedule. The same reset-or-decay argument applies, because contacts never renew the source. This completes the induction. \(\square\)

Applying the lemma repeatedly gives
\[ R(T)=\bigcup_{u\in T}R(\{u\}). \]
Thus multiple postings create exactly the union of their individual eventual spread sets.

2. Only posting phases matter

For an integer \(z\), define
\[ [z]_p=1+((z-1)\bmod p). \]
For each phase \(a\in\{1,\ldots,p\}\), let \(R_a=R(\{a\})\).

Lemma 2. If \([u]_p=a\), then \(R(\{u\})=R_a\).

Proof. Before its sole posting, each process has all counters zero. After that posting, the sequences of contact relations are identical up to the time shift \(u-a\), which is a multiple of \(p\). Induction on elapsed time after the posting shows that the counter vectors coincide under this shift. Hence the eventually activated types coincide. \(\square\)

Combining the two lemmas,
\[ R(T)=\bigcup_{a\in I(T)}R_a, \qquad I(T)=\{[u]_p:u\in T\}. \]

Conversely, any phase set \(I\subseteq\{1,\ldots,p\}\) is realized by posting at precisely those times in the first period. Therefore the decision problem is exactly
\[ \exists I\subseteq\{1,\ldots,p\},\quad |I|\leq B,\quad \sum_{q\in\bigcup_{a\in I}R_a}\mu_q\geq k. \]
For a nonempty \(I\), the source belongs to the union and its mass is counted.

It remains to compute the sets \(R_a\) in polynomial time despite the infinite continuation and binary lifetime.

3. A finite graph for single-post spread

Construct a directed graph \(H\) with vertex set
\[ V(H)=Q\times\{1,\ldots,p\}. \]
A vertex represents a type receiving a reset to \(\delta\) at the indicated phase. For the source, it represents its initial posting.

For every \(\{x,y\}\in E_j\), consider both orientations \((x,y)\). Whenever \(y\neq s\), add, for every integer \(d\) with \(0\leq d<D\), the arc
\[ (x,[j-d]_p)\longrightarrow(y,[j+1]_p). \]

This arc represents a reset of \(x\), followed by \(d\) elapsed steps, a contact at phase \(j\), and the resulting reset of \(y\) one step later. There are no arcs entering a source vertex.

The graph has \(p\tau\) vertices and at most \(2Dm\) arcs.

Lemma 3. For every phase \(a\),
\[ R_a=\{q\in Q:\text{some }(q,h)\text{ is reachable from }(s,a)\text{ in }H\}. \]

Reachability implies actual spread

Start the single-post process at time \(a\). The source then has counter \(\delta\).

Suppose a graph path has been realized up to a reset of type \(x\) at an actual time \(t\). Consider its next arc, with defining values \(j,d\). Its tail phase guarantees that time \(t+d\) has phase \(j\).

Because \(d<D\leq\delta\), type \(x\) is active at time \(t+d\). Indeed, a reset to \(\delta\) ensures activity for the next \(\delta\) times, and additional renewals cannot shorten that interval. This also holds for the initial source reset.

The corresponding edge is present at time \(t+d\), so its nonsource endpoint \(y\) resets at time \(t+d+1\), whose phase is \([j+1]_p\). Induction realizes the entire finite path. Hence every reachable type is eventually active.

Actual spread implies reachability

We prove by induction on time that every actual reset event has its corresponding vertex reachable in \(H\).

The source posting at time \(a\) corresponds to the starting vertex \((s,a)\).

Consider a nonsource reset of \(y\) at time \(r\). Some type \(x\) is active and contacts \(y\) at time \(r-1\). Let \(h\) be the most recent reset of \(x\) before or at time \(r-1\); if \(x=s\), this is its sole posting at time \(a\). Since \(x\) is active,
\[ 0\leq d_0=(r-1)-h\leq\delta-1. \]
Also \(h<r\), so the vertex \((x,[h]_p)\) is reachable by the induction hypothesis.

Let \(j=[r-1]_p\). If \(\delta<p\), take \(d=d_0\). If \(\delta\geq p\), take \(d=d_0\bmod p\). In both cases,
\[ 0\leq d<D,\qquad [j-d]_p=[h]_p. \]
The construction therefore contains the arc
\[ (x,[h]_p)\longrightarrow(y,[r]_p). \]
This proves reachability for the reset at time \(r\).

Every active nonsource cohort has a preceding reset, since its initial counter is zero and decay cannot create activity. Thus every eventually active type is represented among the reachable vertices. \(\square\)

This proof accounts for renewals, arbitrarily many periods, and all activity after the last posting.

A useful consequence is a finite witness bound: a reachable vertex has a simple path from \((s,a)\) containing at most \(p(\tau-1)\) arcs, because no source vertex can occur after the starting vertex. Each arc advances actual time by at most \(D\). Hence every type in \(R_a\) becomes active by time
\[ a+p(\tau-1)D. \]

4. Algorithm, bit complexity, and membership in \(\mathrm{NP}\)

Build \(H\), then run a graph search from each of its \(p\) source vertices. Constructing the graph and computing all \(R_a\) require
\[ O\bigl(p(p\tau+Dm)\bigr) = O(p^2\tau+pmD) \]
graph operations.

Next enumerate phase subsets of size at most \(B\). For each subset, compute the union of its spread sets and compare its mass with \(k\). Each union can be obtained from the union for a subset with one phase removed, using \(\tau\) Boolean operations. Its mass can then be computed using \(\tau\) exact additions.

To handle rational arithmetic, multiply the input denominators of the masses and threshold to obtain a common denominator. Its bit length is \(O(L)\), since the sum of the encoded denominator lengths is at most \(L\). Every mass sum lies between zero and one, so its scaled numerator also has \(O(L)\) bits. Ordinary exact integer arithmetic permits preprocessing in \(O(L^3)\) bit operations.

Allowing \(O(L^2)\) bit operations per graph, subset, or arithmetic operation gives the stated bound
\[ O\!\left(L^3+\bigl(p^2\tau+pmD+N_{p,B}\tau+1\bigr)L^2\right). \]

Since \(D\leq p\) and \(N_{p,B}\leq2^p\), this proves FPT parameterized by \(p\). Neither \(\delta\) nor \(b\) contributes its numerical value beyond the truncations \(D\) and \(B\); their encoding lengths are included in \(L\).

For membership in \(\mathrm{NP}\), a certificate is a subset of the \(p\) phases. Its size is polynomial in \(L\), because all \(p\) relations are explicitly listed. The verifier computes the required reachability sets and their union mass without enumerating other subsets. Since \(p,\tau,m\) are bounded by the explicit input length, this verification takes polynomial time.

5. Hardness with positive dyadic masses

We reduce from Set Cover: given a nonempty universe \(U=\{u_1,\ldots,u_n\}\), explicitly listed subsets \(S_1,\ldots,S_r\), and a positive budget \(\beta\), decide whether at most \(\beta\) sets cover \(U\). This problem is \(\mathrm{NP}\)-complete.

We may assume \(\bigcup_iS_i=U\): instances violating this condition are immediately negative and can be replaced by a fixed negative instance satisfying it.

Construct
\[ Q=\{s,q_1,\ldots,q_n\},\qquad p=r,\qquad \delta=1,\qquad b=\beta,\qquad k=1, \]
and define
\[ E_i=\{\{s,q_j\}:u_j\in S_i\}. \]
The underlying graph is a star centered at \(s\).

Choose
\[ h=\lceil\log_2(n+1)\rceil,\qquad M=2^h, \]
and assign masses
\[ \mu_{q_j}=\frac1M,\qquad \mu_s=\frac{M-n}{M}. \]
All masses are positive dyadic rationals, and
\[ \mu_s+\sum_{j=1}^n\mu_{q_j}=1. \]
Their total encoding length is polynomial in the Set Cover input size.

With \(\delta=1\), the source is active at time \(t\) exactly when \(t\) is a posting time. Every leaf contacts only the source, and contacts cannot renew the source. Consequently,
\[ q_j\text{ is ever active} \quad\Longleftrightarrow\quad u_j\in\bigcup_{t\in T}S_{[t]_p}. \]

If at most \(\beta\) sets cover \(U\), post at their corresponding phases in the first period. Every leaf and the source become active, achieving mass \(1\).

Conversely, a schedule achieving mass \(1\) must activate every type, because every mass is strictly positive. Its posting phases therefore select at most \(|T|\leq\beta\) sets whose union covers \(U\).

The reduction is polynomial, with
\[ \tau=n+1,\qquad p=r,\qquad m=\sum_{i=1}^{r}|S_i|. \]
It proves \(\mathrm{NP}\)-hardness. Together with membership in \(\mathrm{NP}\), this proves \(\mathrm{NP}\)-completeness.

The same reduction preserves the posting budget, so the standard parameterized Set Cover hardness also yields \(\mathrm{W}[2]\)-hardness parameterized by \(b\).

6. The large-lifetime case

When \(\delta\geq p\), one posting suffices to activate precisely the connected component of \(s\) in the union graph
\[ G=\left(Q,\bigcup_{i=1}^{p}E_i\right). \]

To prove this, take any simple path from \(s\). After a vertex on the path resets, the next path edge appears within the following \(p\) contact times. The vertex remains active throughout those times because \(\delta\geq p\), so the next vertex resets. Induction activates the entire path. No vertex outside the component can be activated.

Thus this case is polynomial-time solvable by computing that component’s mass. The unrestricted hardness arises already from the opposite extreme \(\delta=1\).

⟨structured verdict parsed — rendered above⟩

The output proves the claimed classification for the exact model in USER_TASK: \(\mathrm{NP}\)-completeness for unrestricted \(p\), and fixed-parameter tractability parameterized by \(p\), including binary-encoded \(\delta\) and \(b\). I found no major or minor mathematical issues.

• Superposition of schedules: correct.

The initialization satisfies the claimed counter identity, including the source and postings at time \(1\).

In the inductive step, a contacting cohort is active under the union schedule exactly when it is active under at least one constituent schedule. Therefore a nonsource reset occurs under the union exactly when at least one constituent counter resets. When neither resets, the decay identity preserves the maximum.

The separate source argument correctly uses posting events rather than contacts. This is essential because the source cannot be renewed by its neighbors.

Consequently, the asserted equality \(R(T)=\bigcup_{u\in T}R(\{u\})\) follows for every finite nonempty schedule. The empty schedule also satisfies it: all counters remain zero, and both sides are empty. There is no unproved interaction or synergy assumption.

• Reduction to posting phases: correct.

A single-post process remains identically zero before its posting. If \([u]_p=a\), then \(u-a\) is a nonnegative multiple of \(p\), and the contact sequences following the two postings coincide under that shift. The stated induction therefore establishes equality of their eventual spread sets.

Combining this with superposition justifies discarding repeated posting phases. Conversely, posting at the selected phase numbers in the first period realizes every phase subset without exceeding its cardinality.

Thus the budget truncation \(B=\min\{b,p\}\) is valid. The formulation handles the empty subset correctly, and every nonempty subset includes the source in its spread.

• Finite reachability graph: correct in both directions.

The graph has exactly \(p\tau\) vertices. Each listed undirected edge contributes at most two orientations and \(D=\min\{\delta,p\}\) delays, so the bound of \(2Dm\) arcs is valid. Suppressing arcs whose destination is the source correctly enforces the source exception.

Reachability implies spread. For an arc realized from a reset at time \(t\), its delay satisfies \(0\leq d<D\leq\delta\). Hence the sending cohort is active at \(t+d\): the relevant guaranteed activity interval is from \(t\) through \(t+\delta-1\). Renewals cannot shorten this interval. The phase equation places the required edge at that time, and the receiving nonsource cohort resets one step later. The induction therefore realizes every finite graph path in the single-post process.

Spread implies reachability. Every active sending cohort has a preceding reset, with the source posting serving as its reset. Choosing the latest reset gives \(0\leq d_0\leq\delta-1\), and that reset occurs strictly before the receiving reset, so the induction is well founded.

When \(\delta<p\), using \(d=d_0\) satisfies the graph’s delay range. When \(\delta\geq p\), using \(d=d_0\bmod p\) satisfies \(0\leq d<p=D\) and preserves the required phase equality. This establishes the corresponding graph arc.

The modulo reduction need only preserve phase reachability; it does not claim to reproduce the original event’s absolute time. The proof uses this distinction correctly.

Finally, every active nonsource cohort has experienced a reset because its initial counter is zero. Thus the argument covers all eventual activity, including activity arbitrarily far beyond the posting.

• Finite witness bound: correct.

A reachable vertex has a simple path from the starting source vertex. Since there are no incoming source arcs, such a path contains at most the starting source vertex and the \(p(\tau-1)\) nonsource vertices. Its number of arcs is therefore at most \(p(\tau-1)\).

Each realized arc advances time by \(d+1\leq D\). The claimed activation deadline \(a+p(\tau-1)D\) follows.

The bound also handles \(\tau=1\): the only reachable type is the source, active at time \(a\).

• Algorithm and bit complexity: correct.

Searching from each of the \(p\) source-phase vertices costs \(O(p(p\tau+Dm))=O(p^2\tau+pmD)\) graph operations. Graph construction is absorbed by this bound because \(p\geq1\).

The subset computation can process subsets in increasing cardinality, so a subset’s stored parent union is available when needed. This validates the claimed \(\tau\) Boolean operations per union and \(\tau\) exact additions per mass computation. Retaining those unions may require exponential storage, but no polynomial-space claim is made.

The common-denominator argument is valid: the product’s bit length is bounded by the sum of the encoded denominator lengths, hence by \(O(L)\). Because masses are positive and sum to one, every subset mass has a scaled numerator of \(O(L)\) bits. The preprocessing allowance \(O(L^3)\) and the conservative \(O(L^2)\) allowance per subsequent operation are sufficient.

Accordingly, the stated bound \(O(L^3+(p^2\tau+pmD+N_{p,B}\tau+1)L^2)\) is supported. Substituting \(D\leq p\) and \(N_{p,B}\leq2^p\) yields the claimed FPT bound. There is no hidden iteration up to the numerical values of \(\delta\) or \(b\).

• Membership in \(\mathrm{NP}\): correct.

The phase reduction supplies a certificate consisting of at most \(p\) phase choices. Explicit listing of all \(p\) relations, including empty relations, ensures that \(p\) is bounded by the input length; explicit support and edge lists likewise bound \(\tau\) and \(m\).

The verifier computes graph reachability and one union mass in polynomial time. It need not enumerate other subsets or simulate an unbounded time interval. Thus binary lifetime and budget encodings do not invalidate membership in \(\mathrm{NP}\).

• Set Cover reduction: correct.

The source problem is stated with the required explicit universe, explicit family, and positive budget. Restricting to instances whose family covers the universe is legitimate: uncovered elements certify a negative instance, and replacement by a fixed negative instance satisfying the restriction is routine. Since the universe is nonempty, the restricted family has at least one set, ensuring \(p=r\geq1\).

All constructed relations are undirected and loopless. Under the covering-family restriction, every leaf occurs in the underlying star.

The mass calculation is correct. With \(M=2^{\lceil\log_2(n+1)\rceil}\), one has \(M\geq n+1\), so \(M-n\geq1\). All masses are therefore positive dyadic rationals, and their sum is exactly one. Their total encoding length is polynomial.

For \(\delta=1\), the source is active precisely at posting times. Leaves have no contacts except with the source, and their contacts cannot renew it. Therefore the stated equivalence between leaf activation and membership in a selected phase’s set is exact. It also respects the one-step delay between contact and leaf activation.

A cover produces a schedule achieving mass one. Conversely, positive masses force a schedule achieving mass one to activate every leaf, so its distinct posting phases constitute a cover of size at most \(\beta\). Both reduction directions and the claimed size parameters are valid.

The additional \(\mathrm{W}[2]\)-hardness conclusion follows from Set Cover hardness parameterized by cover size and the parameter-preserving assignment \(b=\beta\). The cited paper also explicitly identifies this source hardness. [Set Cover statement in Section 2](https://arxiv.org/html/2303.11703v2#S2).

• Large lifetime and contextual citation: correct.

When \(\delta\geq p\), the \(p\) contact times beginning at a reset include every phase. A path edge therefore appears while the sending cohort remains active, including the boundary case \(\delta=p\). The written induction activates every vertex in the source’s union-graph component, and no contact can cross outside that component.

Since \(b\geq1\), the required single posting is allowed. Component-mass comparison therefore decides this case in polynomial time.

The attribution to Theorem 12 is accurate: it states the unweighted periodic MaxSpread algorithm with running time \(2^{t_{\max}}\operatorname{poly}(|V(G)|)\). The prover independently establishes the stronger encoding-sensitive bound needed here, so no extension to rational masses or binary lifetime is being assumed from that citation. [Theorem 12](https://arxiv.org/html/2303.11703v2#S5).

Repair feedback: None is required. The unrestricted hardness and FPT result coexist consistently; they do not represent an encoding-dependent split.

⟨structured verdict parsed — rendered above⟩