# On approximating the rank of graph divisors

Kristóf Bérczi MTA-ELTE Momentum Matroid Optimization Research Group and MTA-
ELTE Egerváry Research Group, Department of Operations Research, Eötvös Loránd
University, Budapest, Hungary. Email<EMAIL_ADDRESS>Hung P.
Hoang Institute of Theoretical Computer Science, Department of Computer
Science, ETH Zürich, Switzerland. Email<EMAIL_ADDRESS>Lilla
Tóthmérész MTA-ELTE Egerváry Research Group, Department of Operations
Research, Eötvös Loránd University, Budapest, Hungary. Email:
<EMAIL_ADDRESS>
###### Abstract

Baker and Norine initiated the study of graph divisors as a graph-theoretic
analogue of the Riemann-Roch theory for Riemann surfaces. One of the key
concepts of graph divisor theory is the rank of a divisor on a graph. The
importance of the rank is well illustrated by Baker’s Specialization lemma,
stating that the dimension of a linear system can only go up under
specialization from curves to graphs, leading to a fruitful interaction
between divisors on graphs and curves.

Due to its decisive role, determining the rank is a central problem in graph
divisor theory. Kiss and Tóthmérész reformulated the problem using chip-firing
games, and showed that computing the rank of a divisor on a graph is NP-hard
via reduction from the Minimum Feedback Arc Set problem.

In this paper, we strengthen their result by establishing a connection between
chip-firing games and the Minimum Target Set Selection problem. As a
corollary, we show that the rank is difficult to approximate to within a
factor of $O(2^{\log^{1-\varepsilon}n})$ for any $\varepsilon>0$ unless
$P=NP$. Furthermore, assuming the Planted Dense Subgraph Conjecture, the rank
is difficult to approximate to within a factor of $O(n^{1/4-\varepsilon})$ for
any $\varepsilon>0$.

Keywords: Approximation, Chip-firing, Graph divisors, Minimum target set
selection, Riemann-Roch theory

##  1 Introduction

Motivated by the fact that a finite graph can be viewed as a discrete analogue
of a Riemann surface, Baker and Norine [3] introduced a discrete analogue of
the Riemann-Roch theory for graphs. They adapted the notions of a divisor,
linear equivalence, and rank to the combinatorial setting, and studied the
analogy between the continuous and the discrete cases in the context of linear
equivalence. They further provided several results showing that the notion of
rank plays an important role in various problems. In particular, a graph-
theoretic analogue of the Riemann-Roch theorem holds for this notion of rank.
Therefore, deciding the complexity of computing the rank is a natural question
that is of both algebraic geometric and combinatorial interest. This problem
is attributed to H. Lenstra, and was explicitly posed by many, see [4, 13,
17].

#### Previous work

From the positive side, Luo [16] introduced the notion of rank-determining
sets of metric graphs, and verified the existence of finite rank-determining
sets constructively. Hladký, Král, and Norine [13] confirmed a conjecture of
Baker [2] relating the ranks of a divisor on a graph and on a tropical curve,
and provided a purely combinatorial algorithm for computing the rank of a
divisor on a tropical curve, which can be considered simply as a metric graph,
see [18, 12]. For multigraphs with a constant number of vertices, Manjunath
[17] gave a polynomial time algorithm that computes the rank of a divisor.
Furthermore, by a corollary of the Riemann-Roch theorem, the rank can be
computed in polynomial time for divisors of degree greater than $2g-2$, where
$g$ denotes the cyclotomic number of the graph (also called the genus). Baker
and Shokrieh [4] provided an algorithm that can efficiently check whether the
rank of a divisor on a graph is at least $c$ for any fixed constant $c$. Cori
and le Borgne [10] provided a linear time algorithm for determining the rank
of a divisor on a complete graph.

There are also negative results regarding the complexity of computing the
rank. Amini and Manjunath [1] proposed a general Riemann-Roch theory for sub-
lattices of the root lattice $A_{n}$111$A_{n}$ is the lattice of
$(n+1)$-dimensional integer vectors whose components sum to zero., thus giving
a geometric interpretation of the work of Baker and Norine and generalising it
to sub-lattices of $A_{n}$. They also showed that in the general model
deciding whether the rank of a divisor is at least zero is already NP-hard.
The complexity of computing the rank of a divisor on a graph was settled by
Kiss and Tóthmérész [15] who showed that the problem is NP-hard even in simple
graphs.

#### Our results

As computing the rank of a divisor is NP-hard in general, it is natural to ask
whether it can be approximated within any reasonable factor. Our main
contribution is establishing a connection between computing the rank and
finding a so-called minimum target set in an undirected graph, a central
problem in combinatorial optimization that is notoriously hard to approximate.
A recent paper by Bérczi, Boros, Čepek, Kučera, and Makino [5] showed a
similar connection between finding a minimum key in a directed hypergraph and
finding a minimum target set in an undirected graph, therefore, roughly
speaking, our result places these three classical problems on the same level
of complexity. As a corollary, we deduce strong lower bounds on the
approximability of the rank. In particular, we show that the rank is difficult
to approximate to within a factor of $O(2^{\log^{1-\varepsilon}n})$ for any
$\varepsilon>0$ unless $P=NP$. Furthermore, assuming the Planted Dense
Subgraph Conjecture, we show that the rank is difficult to approximate to
within a factor of $O(n^{1/4-\varepsilon})$ for any $\varepsilon>0$, thus
providing the first polynomial hardness result for the problem. By [16,
Theorem 1.6], our results also apply to computing the rank of a divisor on a
tropical curve.

The rest of the paper is organized as follows. Basic definitions and notation
are introduced in Section 2, together with a brief introduction into graph
divisor theory. The hardness of approximation of the rank of divisors is then
discussed in Section 3.

##  2 Preliminaries

#### Basic notation

We denote the sets of _integer_ and _nonnegative integer_ numbers by
$\mathbb{Z}$, and $\mathbb{Z}_{+}$, respectively. Let $V$ be a ground set and
$X\subseteq V$ be a subset of $V$. For a function $f:V\to\mathbb{Z}$, we use
$f(X)\coloneqq\sum_{v\in X}f(v)$.

Let $G=(V,E)$ be a graph with _vertex set_ $V$ and _edge set_ $E$. Throughout
the paper, we allow multiple edges between a pair of vertices. Given
$Z\subseteq V$ and $F\subseteq E$, the _degree of $Z$ in $F$_ is the number of
edges in $F$ going between $Z$ and $V\setminus Z$ and is denoted by
$d_{F}(Z)$. In particular, for a vertex $v\in V$, we denote by $d_{F}(v)$ the
degree of $v$ in $F$. The _degree vector_ or _degree sequence_ of $G$ is then
the vector $d_{G}\in\mathbb{Z}^{V}_{+}$ with $d_{G}(v)\coloneqq d_{E}(v)$. For
two vertices $u,v\in V$, $d_{G}(v,u)$ refers to the _number of edges
connecting $v$ and $u$_ in $G$.

#### Chip-firing

We give a brief overview of the basic definitions of graph divisor theory due
to Baker and Norine [3]. For a graph $G=(V,E)$, a _divisor_ is an assignment
$f:V\to\mathbb{Z}$ of an integer number to each vertex. We usually refer to
the value $f(v)$ as the _number of chips_ on $v$, even though $f(v)$ might be
negative, and hence we also refer to $f$ as a _chip configuration_. The
_degree_ of a divisor $f$ is defined as $\deg(f)\coloneqq f(V)=\sum_{v\in
V}f(v)$. The set of divisors admits an equivalence-relation, called _linear
equivalence_ , which is defined based on the operation of _firing a vertex_.
For an arbitrary vertex $v$, the firing of $v$ modifies the divisor $f$ to
$f^{\prime}$ with

$f^{\prime}(u)=\begin{cases}f(v)-d_{G}(v)&\text{if }u=v,\\\
f(u)+d_{G}(v,u)&\text{if }u\neq v.\end{cases}$

That is, $v$ sends a chip along each edge incident to it, and as a result, the
number of chips on $v$ decreases by the degree of $v$. Note that the degree of
the divisor is not changed by the firing.

Two divisors $f$ and $g$ are called _linearly equivalent_ if $f$ can be
transformed into $g$ by a sequence of firings, denoted by $f\sim g$. Note that
linear equivalence is indeed an equivalence relation, since a firing of $v$
can be ‘reversed’ by firing every other vertex once. A divisor $f$ is called
_effective_ if $f(v)\geq 0$ for each $v\in V$. A divisor is called _winnable_
if it is linearly equivalent to an effective divisor. A basic quantity
associated to a divisor is its _rank_ , defined as

$\operatorname{rank}_{G}(f)\coloneqq\min\\{\deg(g)\mid\text{
$g:V\to\mathbb{Z}$ is effective, $f-g$ is not winnable}\\}-1.$

In other words, because of the minus one in the definition, the rank of a
divisor measures the maximum number of chips that can be removed arbitrarily
from $f$ so that the resulting divisor is winnable.

We say that a vertex $v$ is _active_ with respect to a divisor $f$ if
$f(v)\geq d_{G}(v)$. The _chip-firing game_ is a one player game, where a step
consists of choosing an active vertex, if there exists any, and firing it222In
some works, non-active vertices are also allowed to fire, resulting in a
negative number of chips on them. In such a setting, a firing of a vertex $v$
is called _legal_ if $v$ is active, and games consisting of legal firings are
called _legal_ as well. As we only consider legal games in this work, we
dismiss the word ‘legal’ throughout.. The game is _non-trivial_ if at least
one vertex gets fired. We say that the game _halts_ if we get to a divisor
that has no active vertex; such a divisor is called _stable_. The milestone
result of Björner, Lovász, and Shor [8] states that starting from a given
divisor, either every game halts and ends with the same stable divisor, or
every game continues indefinitely. That is, the choices of the player do not
influence whether the game halts or not, as it only depends on the starting
divisor. Based on this theorem, we call a divisor $f$ _halting_ if the chip-
firing game starting from $f$ eventually halts, and _non-halting_ otherwise.

Recall that $d_{G}$ denotes the divisor that for any vertex $v$ has $d_{G}(v)$
chips. Let us denote by $\mathbf{1}$ the divisor that has 1 chip on every
vertex. The winability of a divisor can be characterized by the chip-firing
game the following way, see [3, Corollary 5.4].

######  Proposition 1 (Baker and Norine).

A divisor $f$ on a graph $G$ is winnable if and only if $d_{G}-\mathbf{1}-f$
is a halting divisor.

######  Remark 2.

In [3] it is assumed that $d_{G}-\mathbf{1}-f$ has a nonnegative amount of
chips on each vertex. However, the theorem remains true without this
assumption (see for example [15, Remark 2.6]), hence we do not suppose
nonnegativity of divisors in the chip-firing game.

To measure the deviation of a divisor $f$ of $G$ from being non-halting, we
introduce its _distance from a non-halting state_

$\operatorname{dist^{nh}_{\mathnormal{G}}}(f)\coloneqq\min\\{\deg(g)\mid
g\text{ is an effective divisor of $G$},f+g\text{ is non-halting}\\}.$

Using this notation, the rank of a divisor can be formulated as
$\operatorname{rank}_{G}(f)=\operatorname{dist^{nh}_{\mathnormal{G}}}(d_{G}-\mathbf{1}-f)-1$.
Hence computing the rank of a divisor is equivalent to computing the distance
of a related divisor, that is, the minimum number of chips that needs to be
added to the related divisor to make the chip-firing game non-halting.

Dist-Nonhalt
Input: A graph $G=(V,E)$ and a divisor $f:V\to\mathbb{Z}$. Goal: Compute the
distance $\operatorname{dist^{nh}_{\mathnormal{G}}}(f)$ of $f$ from a non-
halting state.

The following result provides a sufficient condition for a divisor $f$ being
non-halting, see [19, Lemma 4].

######  Proposition 3 (G. Tardos).

Let $G=(V,E)$ be a graph and $f:V\to\mathbb{Z}$ be a divisor. If there is a
chip-firing game starting from $f$ where each vertex fires at least once, then
$f$ is a non-halting configuration.

A divisor $f$ is called _recurrent_ if there is a non-trivial chip-firing game
starting from $f$ that leads back to $f$. Clearly, a recurrent divisor $f$ is
also non-halting. Besides the distance of a divisor from a non-halting state,
its _distance from a recurrent state_ also plays a central role in our
investigations, defined as

$\operatorname{dist^{r}_{\mathnormal{G}}}(f)\coloneqq\min\\{\deg(g)\mid
g\text{ is an effective divisor of $G$, $f+g$ is recurrent}\\}.$

Dist-Rec
Input: A graph $G=(V,E)$ and a divisor $f:V\to\mathbb{Z}$. Goal: Compute the
distance $\operatorname{dist^{r}_{\mathnormal{G}}}(f)$ of $f$ from a recurrent
state.

We will use the following characterization of recurrence, due to Biggs [6,
Lemma 3.6]. As [6] uses a slightly different model, we include a short proof
here.

######  Proposition 4.

[6, Lemma 3.6] Let $G=(V,E)$ be a connected graph and $f:V\to\mathbb{Z}$ be a
divisor. Then $f$ is recurrent if and only if there is a game starting from
$f$ in which each vertex fires exactly once.

###### Proof.

The ‘if’ direction is obvious, hence we concentrate on the ‘only if’
direction. Assume that $f$ is a recurrent divisor. Then, by definition, there
is a non-trivial game that transforms $f$ to itself. We claim that in such a
game each vertex fires the same number of times. Indeed, otherwise let
$Z\subsetneq V$ denote the proper subset of vertices that fired a minimum
number of times. As every vertex in $V\setminus Z$ fired more times than the
vertices in $Z$ and $G$ is connected, $Z$ necessarily gains chips compared to
$f$, a contradiction. By [7, Lemma 4.3], there also exists a game starting
from $f$ in which each vertex fires exactly once, concluding the proof. ∎

#### Minimum Target Set Selection

In the Minimum Target Set Selection problem (Min-TSS), introduced by Kempe,
Kleinberg, and É. Tardos [14], we are given a simple graph $G=(V,E)$ with
$|V|=n$, together with a threshold function $\tau:V\to\mathbb{Z}_{+}$, and we
consider the following activation process. As a starting step, we can activate
a subset $S\subseteq V$ of vertices. Then, in every subsequent round, a vertex
$v$ becomes activated if at least $\tau(v)$ of its neighbors are already
active. Note that once a vertex is active, it remains active in all future
rounds. The goal is to find a minimum sized initial set $S$ of active vertices
(called a _target set_) so that the activation spreads to the entire graph
(i.e., all vertices are eventually activated). For ease of notation, we
measure the size of an optimal solution by

$\operatorname{ts}_{G}(\tau)\coloneqq\min\\{|S|\mid S\subseteq V,\ \text{$S$
is a target set of $G$ with respect to $\tau$}\\}.$

Min-TSS
Input: A simple graph $G=(V,E)$ and thresholds $\tau:V\to\mathbb{Z}_{+}$.
Goal: Find a minimum sized target set attaining $\operatorname{ts}_{G}(\tau)$.

Min-TSS has long been a focus of research due to its wide applications in real
life scenarios. Unfortunately, not only finding a smallest target set but also
approximating the minimum value is difficult. Under the assumption $P\neq NP$,
Feige and Kogan [11, Theorem 3.5] showed that the problem is difficult even in
3-regular graphs.

######  Proposition 5 (Feige and Kogan).

Unless $P=NP$, Min-TSS cannot be approximated to within a factor of
$O(2^{\log^{1-\varepsilon}n})$ for any $\varepsilon>0$ even in $3$-regular
graphs with $\tau(v)\in\\{1,2\\}$ for $v\in V$.

Also, Charikar, Naamad, and Wirth [9] proved that, assuming the Planted Dense
Subgraph Conjecture, Min-TSS is difficult to approximate within a polynomial
factor.

######  Proposition 6 (Charikar, Naamad, and Wirth).

Assuming the Planted Dense Subgraph Conjecture, Min-TSS cannot be approximated
to within a factor of $O(n^{1/2-\varepsilon})$ by a probabilistic polynomial-
time algorithm for any $\varepsilon>0$.

##  3 Hardness of approximating the rank

Now we turn to the proof of the main result of the paper, and show that
approximating the rank of a graph divisor within reasonable bounds is hard.
The high level idea of the proof is the following. First, we show that the
Minimum Target Set Selection problem reduces to computing the distance of a
divisor on an auxiliary undirected graph from a recurrent state (Section 3.1).
Then we show that computing the distance of a divisor from a recurrent state
reduces to computing the distance of a divisor on a slightly modified graph
from a non-halting state (Section 3.2). As the computation of the rank is
equivalent to computing the distance from a non-halting state for an
appropriately modified divisor, the lower bounds on the approximability of the
rank will follow by Propositions 5 and 6; see Theorem 14.

###  3.1 Reduction of Min-TSS to Dist-Rec

Consider an instance $G=(V,E)$ and $\tau:V\to\mathbb{Z}_{+}$ of Min-TSS. We
construct a Dist-Rec instance $G^{\prime}=(V^{\prime},E^{\prime})$ and
$x:V^{\prime}\to\mathbb{Z}$ such that
$\operatorname{ts}_{G}(\tau)=\operatorname{dist^{r}_{\mathnormal{G^{\prime}}}}(x)$.

We define $G^{\prime}$ as follows. For each $v\in V$, we add three vertices
$v_{i}$, $v_{c}$ and $v_{o}$ to $V^{\prime}$. In addition, for each edge
$e=uv\in E$, we add two vertices $p_{uv}$ and $p_{vu}$ to $V^{\prime}$. Now
let $N=|V|+2$. For each vertex $v\in V$, we add $N$ parallel edges between
$v_{i}$ and $v_{c}$ and a single edge between $v_{c}$ and $v_{o}$.
Furthermore, for each edge $e=uv\in E$, we add $N$ parallel edges between
$u_{o}$ and $p_{uv}$, a single edge between $p_{uv}$ and $v_{i}$, $N$ parallel
edges between $v_{o}$ and $p_{vu}$, and a single edge between $p_{vu}$ and
$u_{i}$. These edges together form $E^{\prime}$. For ease of discussion, we
denote by $V^{\prime}_{\circ}\coloneqq\\{v_{i},v_{o}\mid v\in V\\}$ and
$V^{\prime}_{\bullet}\coloneqq\\{v_{c}\mid v\in V\\}\cup\\{p_{uv},p_{vu}\mid
uv\in E\\}$.

(a) An instance of Min-TSS. The numbers denote the thresholds at the vertices.
The set $S=\\{u,v\\}$ is a target set; it is not difficult to check that $S$
has minimum size.

(b) The subgraph of $G^{\prime}$ induced by the vertices
$\\{v_{i},v_{o},u_{i},u_{o}\\}\subseteq V^{\prime}_{\circ}$ and
$\\{v_{c},u_{c},p_{uv},p_{vu}\\}\subseteq V^{\prime}_{\bullet}$. Thick edges
denote a bundle of $N=|V|+2=6$ parallel edges.

(c) The corresponding Dist-Rec instance. The numbers denote the initial chip
distribution $x$ where $x(v)=1$ for each $v\in V^{\prime}_{\bullet}$. Adding
one chip on vertices with double border results in a recurrent divisor.

Figure 1: An illustration of the reduction of Min-TSS to Dist-Rec.

We define the chip configuration $x$ in the following way. For each $v\in V$,
let $x(v_{o})\coloneqq d_{G^{\prime}}(v_{o})-1=N\cdot d_{G}(v)$ and
$x(v_{i})\coloneqq d_{G^{\prime}}(v_{i})-\tau(v)=d_{G}(v)+N-\tau(v)$. For each
$z\in V^{\prime}_{\bullet}$, let $x(z)\coloneqq d_{G^{\prime}}(z)-N=1$. Note
that $0\leq x(z)\leq d_{G^{\prime}}(z)$ holds for each $z\in V^{\prime}$. For
an illustration of the construction, see Figure 1.

We claim that
$\operatorname{ts}_{G}(\tau)=\operatorname{dist^{r}_{\mathnormal{G^{\prime}}}}(x)$.
We prove the two directions separately.

######  Claim 7.

$\operatorname{ts}_{G}(\tau)\geq\operatorname{dist^{r}_{\mathnormal{G^{\prime}}}}(x)$.

###### Proof.

Take a minimum sized target set $S\subseteq V$. Let
$y\in\mathbb{Z}^{V^{\prime}}$ be defined as

$\displaystyle y(z)\coloneqq\begin{cases}1&\text{if $z=v_{o}$ for some $v\in
S$},\\\ 0&\text{otherwise.}\end{cases}$

We claim that $x+y$ is a recurrent chip-configuration on $G^{\prime}$. To see
this, by Proposition 4, it suffices to show that every vertex can fire exactly
once starting from $x+y$. If $u\in S$, then
$(x+y)(u_{o})=d_{G^{\prime}}(u_{o})$, hence these vertices can fire without
receiving any further chips from other vertices; fire all of them in an
arbitrary order. If $u_{o}$ fires, then the vertex $p_{uv}$ receives $N$ chips
for each edge $uv\in E$, therefore, $p_{uv}$ can fire. Fire them when we can.
If a vertex $v\in V$ has at least $\tau(v)$ neighbors in $S$, then $v_{i}$
received at least $\tau(v)$ chips up to this point, that is, the total number
of chips on $v_{i}$ is at least $d_{G^{\prime}}(v_{i})$. Thus, $v_{i}$ can
fire as well. Firing $v_{i}$ sends $N$ chips to $v_{c}$, hence at this point
$v_{c}$ can also fire, which results in sending one chip to $v_{o}$ and making
a firing at $v_{o}$ possible.

Continuing this way, we get that if a vertex $v\in V$ becomes active in the
activation process in the Min-TSS instance, then $v_{o}$ can fire at a certain
point. Hence eventually, there is a moment when $v_{o}$ has fired once for
every $v\in V$. This means that for each edge $uw\in E$ and any of the
vertices $p_{uw}$ and $p_{wu}$, either it fired once or has enough chips to do
so; in the latter case, let it fire. After these, for each vertex $v\in V$,
the vertex $v_{i}$ has either fired once or has enough chips to do so; in the
latter case, let it fire, resulting in a chip configuration for which $v_{c}$
can fire as well. We conclude that eventually each vertex fires (exactly)
once, hence $(x+y)$ is recurrent by Proposition 4 and $y$ is effective.

By the above,
$\operatorname{ts}_{G}(\tau)=|S|=\deg(y)\geq\operatorname{dist^{r}_{\mathnormal{G^{\prime}}}}(x)$,
concluding the proof of the claim. ∎

######  Claim 8.

$N>\operatorname{dist^{r}_{\mathnormal{G^{\prime}}}}(x)+1$.

###### Proof.

Observe that $\operatorname{ts}_{G}(\tau)\leq|V|$ clearly holds. By Claim 7,
we get
$N=|V|+2\geq\operatorname{ts}_{G}(\tau)+2>\operatorname{dist^{r}_{\mathnormal{G^{\prime}}}}(x)+1$
as stated. ∎

######  Claim 9.

$\operatorname{ts}_{G}(\tau)\leq\operatorname{dist^{r}_{\mathnormal{G^{\prime}}}}(x)$.

###### Proof.

Let $y$ be a chip configuration such that $y\geq 0$, $x+y$ is recurrent, and
$\deg(y)=\operatorname{dist^{r}_{\mathnormal{G^{\prime}}}}(x)$. By Proposition
4, there is a game starting from $x+y$ in which each vertex fires exactly
once; from now on, we consider such a sequence of firings.

Consider a vertex $z\in V^{\prime}_{\bullet}$ and let $w$ be the unique vertex
in $V^{\prime}_{\circ}$ that is connected to $z$ by $N$ parallel edges. By
definition, we have $x(z)=1$. If $z$ fires before $w$ in the game, then $z$
can receive at most one chip from its other neighbor before firing. That is,
$y(z)\geq N-1$ as otherwise $z$ has not enough chips for firing before $w$. By
Claim 8, we have $\operatorname{dist^{r}_{\mathnormal{G^{\prime}}}}(x)<N-1$, a
contradiction. Hence $z$ necessarily fires after $w$ in the game, meaning that
it receives $N$ chips from $w$. That is, it has enough chips to fire even if
$y(z)=0$. As $z$ only fires once and $\deg(y)$ is as small as possible, we
conclude that $y(z)=0$. Moreover, $z$ fires later than $w$ for each $z\in
V^{\prime}_{\bullet}$, where $w$ is the unique neighbor of $z$ that is
connected to $z$ by $N$ parallel edges.

Now consider a vertex $v_{i}$ for some $v\in V$. We show that we may assume
$y(v_{i})=0$. Indeed, suppose that $y(v_{i})=k>0$. Let
$\\{u^{1},\dots,u^{d}\\}$ be the neighbors of $v$ in $G$. We create a new
$y^{\prime}$ by replacing the chips of $y$ from $v_{i}$ to some $u^{j}_{o}$
such that $y^{\prime}$ remains effective with $\deg(y^{\prime})\leq\deg(y)$,
$x+y^{\prime}$ is also recurrent, but $y^{\prime}(v_{i})=0$. (The minimality
of $\deg(y)$, then of course implies $\deg(y)=\deg(y^{\prime})$.) Take a game
started from $x+y$ in which each vertex of $G^{\prime}$ fires exactly once. We
know that $v_{c}$ fires after $v_{i}$ in this game. We have
$(x+y)(v_{i})=\deg_{G^{\prime}}(v_{i})-\tau(v)+k$. Hence by the time $v_{i}$
fires, at least $\max\\{0,\tau(v)-k\\}$ vertices among
$\\{p_{u^{1}v},\dots,p_{u^{d}v}\\}$ fired. Choose $k$ vertices $u_{o}^{j}$
such that $p_{u^{j}v}$ did not fire (or if there are less such vertices,
choose all of them), and put $y^{\prime}(u_{o}^{j})=1$ for each of them.
Moreover, put $y^{\prime}(v_{i})=0$. On all other vertices, let
$y(w)=y^{\prime}(w)$ This way, $y^{\prime}\geq 0$ with
$\deg(y^{\prime})\leq\deg(y)$. Then, started from $x+y^{\prime}$, we can play
the same game as the one started from $x+y$ up to the firing of $v_{i}$.
Moreover, if $y^{\prime}(u^{j}_{o})=1$, then $u_{o}^{j}$ and $p_{u^{j}v}$ can
also fire as $x(u^{j}_{o})=d_{G^{\prime}}(u^{j}_{o})-1$. Hence $v_{i}$
receives at least $\tau(v)$ chips. Thus, $v_{i}$ can also fire, and we can
complete the chip-firing game. (We only brought forward the firings of
$u_{o}^{j}$ and $p_{u^{j}v}$ for some $j$.)

Finally, consider a vertex $v_{o}$ for some $v\in V$. As each vertex fires
exactly once, we get $y(v_{o})\leq
d_{G^{\prime}}(v_{o})-x(v_{o})=d_{G^{\prime}}(v_{o})-(d_{G^{\prime}}(v_{o})-1)=1$.

Define $S=\\{v\in V\mid y(v_{o})=1\\}$. Our goal is to show that $S$ is a
target set of the Min-TSS instance $(G,\tau)$. We prove this by showing that
the game on $G^{\prime}$ starting from $x+y$ mimics the activation process on
$G$ starting from $S$ in the following sense: by the time a vertex $v_{o}$
becomes active in the chip firing sense, its corresponding vertex $v\in V$
becomes active in the activation process on $G$. This clearly holds for
vertices in $S$. Consider a general phase of the game, and assume that the
condition holds, that is, for each vertex $v_{o}$ that was fired so far, $v$
became active in the Min-TSS instance as well. Let $v\in V\setminus S$ and
assume that $v_{o}$ is the next vertex to fire. Recall that $y(v_{o})=0$ and
that $v_{o}$ has to fire before the vertex $p_{vu}$ for every $uv\in E$. Apart
from these vertices, $v_{o}$ has only one neighbor, namely $v_{c}$. This means
that for $v_{o}$ to have enough chips, $v_{c}$ had to fire before $v_{o}$. As
$v_{i}$ had to fire before $v_{c}$, we get that $v_{i}$ had to fire before
$v_{o}$. As $y(v_{i})=0$, $v_{i}$ needed $\tau(v)$ extra chips to be able to
fire. As $v_{c}$ fired after $v_{i}$, these extra chips could only be procured
from vertices $p_{uv}$ where $uv\in E$. As each of these vertices fired at
most once and each of them sent one chip to $v_{i}$ upon firing, at least
$\tau(v)$ of them had to fire before firing $v_{i}$. This means that at least
$\tau(v)$ of the vertices $u_{o}$ with $uv\in E$ had to fire so far. By our
hypothesis, these vertices $u\in V$ were active in the Min-TSS instance by the
time they fired, implying that $v$ is also active in the Min-TSS instance.

By the above,
$\operatorname{ts}_{G}(\tau)\leq|S|=\deg(y)=\operatorname{dist^{r}_{\mathnormal{G^{\prime}}}}(x)$,
concluding the proof of the claim. ∎

Note that the size of $G^{\prime}$ is polynomial in the size of $G$. In
particular, we have $|V^{\prime}|=3\cdot|V|+2\cdot|E|=O(|V|^{2})$ as $G$ is
simple.

###  3.2 Reduction of Dist-Rec to Dist-Nonhalt

Consider a Dist-Rec instance $G=(V,E)$ and $f:V\to\mathbb{Z}$. We construct a
Dist-Nonhalt instance $G^{\prime}=(V^{\prime},E^{\prime})$ and
$f^{\prime}:V^{\prime}\to\mathbb{Z}$ such that
$\operatorname{dist^{r}_{\mathnormal{G}}}(f)=\operatorname{dist^{nh}_{\mathnormal{G^{\prime}}}}(f^{\prime})$.
Note the following.

######  Claim 10.

$\operatorname{dist^{r}_{\mathnormal{G}}}(f)\leq
2\cdot|E|+\displaystyle\sum_{v\in V:f(v)<0}|f(v)|.$

###### Proof.

If we add $\max\\{0,d_{G}(v)-f(v)\\}$ chips to vertex $v$, then we have a chip
configuration with at least $d_{G}(v)$ chips on each vertex $v$, which is
certainly a recurrent configuration. Moreover, this addition needs at most the
above stated number of chips. ∎

We define $G^{\prime}$ as follows. Let $M$ be an integer large enough such
that

$\operatorname{dist^{r}_{\mathnormal{G}}}(f)+\max\left\\{0,\max_{v\in
V}\\{f(v)-d_{G}(v)\\}\right\\}<M.$

By Claim 10, $M\coloneqq 2\cdot|E|+\sum_{v\in
V:f(v)<0}|f(v)|+\max\left\\{0,\max_{v\in V}\\{f(v)-d_{G}(v)\\}\right\\}+1$ is
sufficient. Let $V^{\prime}\coloneqq V\cup\\{v_{new}\\}$ and let $E^{\prime}$
consist of $E$ together with $M$ parallel edges between $v$ and $v_{new}$ for
each vertex $v\in V$. That is, $|E^{\prime}|=|E|+M\cdot|V|$. Finally, we
define $f^{\prime}(v)\coloneqq f(v)+M$ for $v\in V$ and
$f^{\prime}(v_{new})\coloneqq 0$.

We claim that
$\operatorname{dist^{r}_{\mathnormal{G}}}(f)=\operatorname{dist^{nh}_{\mathnormal{G^{\prime}}}}(f^{\prime})$.
We prove the two directions separately.

######  Claim 11.

$\operatorname{dist^{r}_{\mathnormal{G}}}(f)\geq\operatorname{dist^{nh}_{\mathnormal{G^{\prime}}}}(f^{\prime})$.

###### Proof.

Let $g$ be an effective divisor of minimum degree such that there is a chip-
firing game on $G$ starting from $f+g$ in which each vertex fires exactly
once. We extend $g$ to $V^{\prime}$ by setting $g(v_{new})=0$. We claim that
if $\\{v_{1},\dots v_{k}\\}$ is a sequence of firings starting from $f+g$ on
$G$ in which each vertex occurs at most once, then these vertices can also
fire in the same order starting from $f^{\prime}+g$ on $G^{\prime}$. Indeed,
for each vertex $v\in V$, we have $d_{G^{\prime}}(v)=d_{G}(v)+M$ and
$f^{\prime}(v)+g(v)=f(v)+g(v)+M$. Firing a vertex $v\in V$ modifies the chip-
configuration on other vertices in $V$ the same way in $G$ and in
$G^{\prime}$. Hence if $v_{i}$ has not yet been fired and it has enough chips
in the game on $G$, then it also has enough chips in the game on $G^{\prime}$.
This implies that there is a game on $G^{\prime}$ starting from $f^{\prime}+g$
in which each vertex of $V$ fires exactly once. At this point, $v_{new}$
received $M$ chips from each vertex in $V$, hence it has $M\cdot|V|$ chips. As
its degree is also $M\cdot|V|$, at this point $v_{new}$ can fire, resulting in
a game on $G^{\prime}$ in which each vertex has fired exactly once.

By Proposition 3, the above implies that $f^{\prime}+g$ is non-halting on
$G^{\prime}$. Hence we have
$\operatorname{dist^{r}_{\mathnormal{G}}}(f)=\deg(g)\geq\operatorname{dist^{nh}_{\mathnormal{G^{\prime}}}}(f^{\prime})$,
concluding the proof of the claim. ∎

######  Claim 12.

$M>\operatorname{dist^{nh}_{\mathnormal{G^{\prime}}}}(f^{\prime})$.

###### Proof.

We choose $M$ such that $M>\operatorname{dist^{r}_{\mathnormal{G}}}(f)$, hence
the claim follows by Claim 11. ∎

######  Claim 13.

$\operatorname{dist^{r}_{\mathnormal{G}}}(f)\leq\operatorname{dist^{nh}_{\mathnormal{G^{\prime}}}}(f^{\prime})$.

###### Proof.

Let $g^{\prime}$ be an effective divisor such that $f^{\prime}+g^{\prime}$ is
non-halting on $G^{\prime}$ and
$\deg(g^{\prime})=\operatorname{dist^{nh}_{\mathnormal{G^{\prime}}}}(f^{\prime})$.
We show that $g^{\prime}(v_{new})=0$, and that for the divisor $g\coloneqq
g^{\prime}|_{V}$ obtained by restricting $g^{\prime}$ to the set of original
vertices, the divisor $f+g$ is recurrent on $G$.

Observe that $f^{\prime}(v_{new})=0$ and $v_{new}$ receives $M$ chips each
time a vertex in $V$ fires. Moreover, $d_{G^{\prime}}(v_{new})$ is divisible
by $M$, hence adding less than $M$ chips on $v_{new}$ has no effect on whether
it is able to fire or not. As
$\operatorname{dist^{nh}_{\mathnormal{G^{\prime}}}}(f^{\prime})<M$, we
conclude that $g^{\prime}(v_{new})=0$.

Now take any game on $G^{\prime}$ starting from $f^{\prime}+g^{\prime}$. We
claim that no vertex $v\in V$ can fire twice before the first firing of
$v_{new}$. Suppose to the contrary that some vertex fires twice before the
first firing of $v_{new}$, and let $v\in V$ be the first such vertex. Then
before its second firing, $v$ received at most $d_{G}(v)$ chips from its
neighbors, and it lost $d_{G^{\prime}}(v)$ chips upon its first firing. Since,
by our assumption, $v$ is now capable of firing for the second time, we get
that $f^{\prime}(v)+g^{\prime}(v)+d_{G}(v)-d_{G^{\prime}}(v)\geq
d_{G^{\prime}}(v)$. As $d_{G^{\prime}}(v)=d_{G}(v)+M$, this implies
$f^{\prime}(v)+g^{\prime}(v)\geq d_{G}(v)+2M$. As $f^{\prime}(v)=f(v)+M$, the
choice of $M$ implies $g^{\prime}(v)\geq
d_{G}(v)-f(v)+M>\operatorname{dist^{r}_{\mathnormal{G^{\prime}}}}(f^{\prime})\geq\operatorname{dist^{nh}_{\mathnormal{G^{\prime}}}}(f^{\prime})=\deg(g^{\prime})$,
a contradiction.

Hence each vertex $v\in V$ fires at most once before the first firing of
$v_{new}$. As $v_{new}$ has to collect $M\cdot|V|$ extra chips to be able to
fire, each vertex $v\in V$ fires exactly once before the first firing of
$v_{new}$. These firings would also be possible when starting from $f+g$ on
$G$, hence $f+g$ is recurrent by Proposition 4. ∎

Note that the size of $G^{\prime}$ might not be polynomial in the size of $G$
as the value of $M$ can be large. However, the above reduction will be applied
to divisors $f$ with $0\leq f(v)\leq d_{G}(v)$ for $v\in V$, in which case the
construction is polynomial. In particular, observe that $|V^{\prime}|=|V|+1$.

###  3.3 Lower bounds

By combining the observations of Sections 3.1 and 3.2 with Propositions 5 and
6, we are ready to prove the main result of the paper.

######  Theorem 14.

Unless $P=NP$, Dist-Nonhalt cannot be approximated to within a factor of
$O(2^{\log^{1-\varepsilon}n})$ for any $\varepsilon>0$. Assuming the Planted
Dense Subgraph conjecture, Dist-Nonhalt cannot be approximated to within a
factor of $O(n^{1/4-\varepsilon})$ for any $\varepsilon>0$.

###### Proof.

Let $G=(V,E)$ be a graph and $\tau:V\to\mathbb{Z}_{+}$ be a threshold
function. According to Section 3.1, computing the value
$\operatorname{ts}_{G}(\tau)$ of the $\operatorname{Min-TSS}$ instance on $G$
and $\tau$ can be reduced to computing
$\operatorname{dist^{r}_{\mathnormal{G^{\prime}}}}(x)$ for a graph
$G^{\prime}=(V^{\prime},E^{\prime})$ having $|V^{\prime}|=3\cdot|V|+2\cdot|E|$
vertices and $|E^{\prime}|=2\cdot(|V|+3)\cdot|E|+|V|$ edges, and a divisor
$x:V^{\prime}\to\mathbb{Z}_{+}$ with $0\leq x(v)\leq d_{G^{\prime}}(v)$ for
each $v\in V^{\prime}$.

As $\operatorname{ts}_{G}(\tau)\leq|V|$, we have
$\operatorname{dist^{r}_{\mathnormal{G^{\prime}}}}(x)\leq|V|$. Hence we can
use the reduction of Section 3.2 with $M=|V|+1$. Thus, we have a graph
$G^{\prime\prime}=(V^{\prime\prime},E^{\prime\prime})$ with
$|V^{\prime\prime}|=3\cdot|V|+2\cdot|E|+1$ vertices and
$|E^{\prime\prime}|=2\cdot(|V|+3)\cdot|E|+2\cdot|V|+|V|^{2}$ edges, and a
divisor $x^{\prime\prime}:V^{\prime\prime}\to\mathbb{Z}_{+}$ such that
$\operatorname{ts}_{G}(\tau)=\operatorname{dist^{nh}_{\mathnormal{G^{\prime\prime}}}}(x^{\prime\prime})$.

Combining the above with Propositions 5 and 6, the statements of the theorem
follow. ∎

######  Remark 15.

The above reduction of Min-TSS to Dist-Nonhalt uses an auxiliary graph that
contains parallel edges. Therefore, the stated complexity results hold for
general (i.e. not necessarily simple) graphs. However, in [13, Corollary 22],
Hladký, Kráľ, and Norine proved that if one subdivides each edge of a graph
with a new vertex and places 0 chips on the new vertices, then the rank of the
obtained divisor on the new graph is the same as the rank of the orignal
divisor on the original graph. Using this result, our construction can be
modified in such a way that eventually we get a Dist-Nonhalt instance on a
simple graph, at the expense of having a higher number of vertices. Such a
reduction, assuming the Planted Dense Subgraph Conjecture, still implies a
polynomial hardness to the problem.

######  Remark 16.

The proofs of the paper are based on a construction that resulted in a graph
with large degrees. Deciding the complexity of computing the rank in degree-
bounded graphs remains an interesting open problem.

#### Acknowledgement

Part of the work was done while the first and second authors attended the
“Discrete Optimization” trimester program of the the Hausdorff Institute of
Mathematics, Bonn. The authors are grateful to HIM for providing excellent
working conditions and support.

The third author was supported by the János Bolyai Research Scholarship of the
Hungarian Academy of Sciences, and by the ÚNKP-21-5 New National Excellence
Program of the Ministry of Innovation and Technology of Hungary. The research
has been implemented with the support provided by the Lendület Programme of
the Hungarian Academy of Sciences – grant number LP2021-1/2021, by the
Hungarian National Research, Development and Innovation Office – NKFIH, grant
numbers FK128673, PD132488, and by the Ministry of Innovation and Technology
of Hungary from the National Research, Development and Innovation Fund,
financed under the ELTE TKP 2021-NKTA-62 funding scheme.

## References

  * [1] O. Amini and M. Manjunath.  Riemann-roch for sublattices of the root lattice $A_{n}$.  Electronic Journal of Combinatorics, 17(1):R124–1, 2010.
  * [2] M. Baker.  Specialization of linear systems from curves to graphs.  Algebra & Number Theory, 2(6):613–653, 2008.
  * [3] M. Baker and S. Norine.  Riemann–Roch and Abel–Jacobi theory on a finite graph.  Advances in Mathematics, 215(2):766–788, 2007.
  * [4] M. Baker and F. Shokrieh.  Chip-firing games, potential theory on graphs, and spanning trees.  Journal of Combinatorial Theory, Series A, 120(1):164–182, 2013\.
  * [5] K. Bérczi, E. Boros, O. Čepek, P. Kučera, and K. Makino.  Unique key horn functions.  Theoretical Computer Science, 2022.
  * [6] N. L. Biggs.  Chip-firing and the critical group of a graph.  J. Algebraic Combin., 9(1):25–45, 1999.
  * [7] A. Björner and L. Lovász.  Chip-firing games on directed graphs.  Journal of Algebraic Combinatorics, 1(4):305–328, 1992.
  * [8] A. Björner, L. Lovász, and P. W. Shor.  Chip-firing games on graphs.  European Journal of Combinatorics, 12(4):283–291, 1991.
  * [9] M. Charikar, Y. Naamad, and A. Wirth.  On approximating target set selection.  In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2016.
  * [10] R. Cori and Y. L. Borgne.  The Riemann-Roch theorem for graphs and the rank in complete graphs.  arXiv preprint arXiv:1308.5325, 2013.
  * [11] U. Feige and S. Kogan.  Target set selection for conservative populations.  Discrete Applied Mathematics, 305:119–132, 2021.
  * [12] A. Gathmann and M. Kerber.  A riemann–roch theorem in tropical geometry.  Mathematische Zeitschrift, 259:217–230, 2008.
  * [13] J. Hladký, D. Král, and S. Norine.  Rank of divisors on tropical curves.  Journal of Combinatorial Theory, Series A, 120(7):1521–1538, 2013\.
  * [14] D. Kempe, J. Kleinberg, and É. Tardos.  Maximizing the spread of influence through a social network.  Theory of Computing, 11(4):105–147, 2015.
  * [15] V. Kiss and L. Tóthmérész.  Chip-firing games on Eulerian digraphs and $\mathbf{NP}$-hardness of computing the rank of a divisor on a graph.  Discrete Applied Mathematics, 193:48–56, 2015.
  * [16] Y. Luo.  Rank-determining sets of metric graphs.  Journal of Combinatorial Theory, Series A, 118(6):1775–1793, 2011\.
  * [17] M. Manjunath.  The rank of a divisor on a finite graph: geometry and computation.  arXiv preprint arXiv:1111.7251, 2011.
  * [18] G. Mikhalkin and I. Zharkov.  Tropical curves, their jacobians and theta functions.  Curves and abelian varieties, 465:203–230, 2008.
  * [19] G. Tardos.  Polynomial bound for a chip firing game on graphs.  SIAM Journal on Discrete Mathematics, 1(3):397–398, 1988.