# Improved Strongly Polynomial Algorithms for Deterministic MDPs,
2VPI Feasibility, and Discounted All-Pairs Shortest Paths

Adam Karczmarz<EMAIL_ADDRESS>Supported by the ERC Consolidator
Grant 772346 TUgbOAT. Institute of Informatics, University of Warsaw and IDEAS
NCBR, Poland

###### Abstract

We revisit the problem of finding optimal strategies for deterministic Markov
Decision Processes (DMDPs), and a closely related problem of testing
feasibility of systems of $m$ linear inequalities on $n$ real variables with
at most two variables per inequality (2VPI).

We give a randomized trade-off algorithm solving both problems and running in
$\widetilde{O}(nmh+(n/h)^{3})$ time using $\widetilde{O}(n^{2}/h+m)$ space for
any parameter $h\in[1,n]$. In particular, using subquadratic space we get
$\widetilde{O}(nm+n^{3/2}m^{3/4})$ running time, which improves by a
polynomial factor upon all the known upper bounds for non-dense instances with
$m=O(n^{2-\epsilon})$. Moreover, using linear space we match the randomized
$\widetilde{O}(nm+n^{3})$ time bound of Cohen and Megiddo [SICOMP‘94] that
required $\tilde{\Theta}(n^{2}+m)$ space.

Additionally, we show a new algorithm for the Discounted All-Pairs Shortest
Paths problem, introduced by Madani et al. [TALG‘10], that extends the DMDPs
with optional end vertices. For the case of uniform discount factors, we give
a deterministic algorithm running in $\widetilde{O}(n^{3/2}m^{3/4})$ time,
which improves significantly upon the randomized bound
$\widetilde{O}(n^{2}\sqrt{m})$ of Madani et al.

##  1 Introduction

Linear programming is one of the most fundamental problems in optimization and
algorithm design. Polynomial-time algorithms solving linear programming
relying on linear algebraic techniques have been known for decades [Kar84,
Kha79], and the recently developed solutions run in the current matrix
multiplication time [vdB20, CLS21, JSWZ21]. All the known polynomial
algorithms are _weakly polynomial_. This means the number of arithmetic
operations they perform depends on the magnitude of the numbers used to
describe the $m$ constraints and $n$ variables of a linear program (LP). It
remains a challenging open problem whether there exists a _strongly
polynomial_ [Meg83b] algorithm whose worst-case number of arithmetic
operations can be bounded by a polynomial in $n$ and $m$ exclusively. The
quest for such an algorithm led to strongly polynomial algorithms for some
important restricted classes of LPs, such as shortest paths, minimum cost
flows [Orl93, Tar85], ’’combinatorial‘‘ LPs [Tar86, DNV20], generalized
maximum flows [OV20, Vég17], and (discounted) Markov Decision Processes
[HMZ13, Ye11].

One of the simplest classes of LPs for which no strongly polynomial algorithm
is known is the class of LPs such that each constraint involves at most two
variables – so-called _two variables per inequality (2VPI)_ programs.
Optimizing 2VPI programs can be reduced to solving the uncapacitated
generalized minimum cost flow problem, for which a _combinatorial_ (i.e., not
relying on algebraic techniques) weakly polynomial algorithm is known
[Way02].111Wayne’s algorithm [Way02] in fact works even for the capacitated
generalized minimum cost flow problem. Interestingly, strongly polynomial
algorithms are known for a seemingly only slightly easier problem of testing
the _feasibility_ of a 2VPI program, where there is no objective function to
optimize and any solution satisfying the constraints is sought.

In this paper, we revisit the _2VPI feasibility_ problem and a closely related
problem of (discounted) _Deterministic Markov Decision Processes_ (DMDPs) in
the strongly polynomial regime.

#### 2VPI feasibility.

The 2VPI feasibility problem has a rich history, and first weakly polynomial
time algorithms [Asp81, AS80] have been developed around the same time as
Khachiyan‘s breakthrough weakly polynomial algorithm for solving general LPs
[Kha79]. Megiddo [Meg83b] initiated the quest for strongly polynomial linear
programming algorithms and obtained an $\widetilde{O}(mn^{3})$ time strongly
polynomial algorithm for 2VPI feasibility using his _parametric search_
technique [Meg83a]. Subsequently, Cohen and Megiddo [CM94] found faster
strongly polynomial algorithms: a deterministic one running in
$O(mn^{2}(\log^{2}{n}+\log{m}))$, and a randomized one running in
$\widetilde{O}(n^{3}+mn)$ time. Hochbaum and Naor [HN94] showed a slightly
faster deterministic algorithm running in $O(mn^{2}\log{m})$ time using a
different approach. These algorithms [CM94, HN94] remain the current state of
the art and all rely on parametric search in some way. However, their drawback
is that they use $\Theta(n^{2}+m)$ space which seems inherent (as will be
explained later on). This stands in sharp contrast with the earlier algorithm
of Megiddo [Meg83b] which needs linear space.

Recently, Dadush et al. [DKNV21] showed a strongly polynomial algorithm for
2VPI that instead uses a label-correcting approach reminiscent of the
classical Bellman-Ford algorithm. However, this algorithm runs in
$O(m^{2}n^{2})$ time, and thus is slower by at least a linear factor than all
the known parametric search-based methods.

#### Monotone 2VPI systems and graphs.

It is well-known (see e.g., [DKNV21, HMNT93]) that testing 2VPI feasibility
can be reduced to the _monotone_ case (M2VPI) where each inequality has at
most one positive coefficient and at most one negative coefficient. Let
$(x)_{v\in V}$ be the variables, and let us index the inequalities with the
elements of a set $E$ of size $m$. Then, after normalization, each inequality
$e$ with variables $x_{u},x_{v}$ (denoted $uv$) is of the form

$x_{u}\leq c(e)+\gamma(e)\cdot x_{v}\hskip 8.53581pt\text{for all }uv=e\in E$
(1)

where $c:E\to\mathbb{R}$ and $\gamma:E\to\mathbb{R}_{+}$. Clearly, such a
system of inequalities can be conveniently represented using a directed
multigraph $G=(V,E)$ with $n$ vertices and $m$ edges.222Throughout (in
particular in (1)), we use the notation $uv=e$ or $e=uv$ to pinpoint that the
tail and the head of the edge $e$ are $u$ and $v$ respectively. We stress that
we allow many edges $e$ with the same tail and head and thus $m$ might exceed
$n^{2}$, e.g., $m$ might be exponential in $n$.

M2VPI systems, if feasible, have a unique _pointwise maximal_ (_pointwise
minimal_) solution ${x^{\max}}=({x_{v}^{\max}})_{v\in V}$
(${x^{\min}}=({x_{v}^{\min}})_{v\in V}$, respectively). This means that for
all feasible points $x$ we have $x_{v}\leq{x_{v}^{\max}}$
($x_{v}\geq{x_{v}^{\min}}$, respectively) for every $v\in V$. It might be the
case that some ${x_{v}^{\max}}$ equal $\infty$ (or ${x_{v}^{\min}}$ equal
$-\infty$) if the feasibility region is unbounded.

Interestingly, variants of some of the known 2VPI feasibility algorithms (see
e.g. [CM94, DKNV21]) also find the pointwise maximal (and symmetrically,
pointwise minimal) solution in the monotone case.

#### Deterministic Markov Decision Processes.

Markov Decision Processes (MDPs) are a popular model for sequential decision
making under uncertainty. Given is a set of _states_ $V$ and a set of actions
$E$ of the form $e=(s(e),p(e),c(e),\gamma(e))$, where $s(e)\in V$, $p(e)$ is a
probability distribution over $V$, $c(e)\in\mathbb{R}$, and
$\gamma(e)\in(0,1)$ ($\gamma(e)$ is usually called a _discount factor_). At a
state $v\in V$, the _controller_ of an MDP has to pick an action $e\in E$ with
$s(e)=v$ (which is assumed to exist). Doing so, the controller gets an
immediate reward $c(e)$. Then, with probability $1-\gamma(e)$, the process
stops. Otherwise, the controller gets transferred to another state $w\in V$
with probability $p(e)(w)$. The goal is to find a _policy_ (i.e., a strategy)
for the controller that allows him to maximize the total reward in this
infinite stochastic process. The optimal strategy for the MDPs is always
deterministic and history independent (see e.g., [Put90]), and thus can be
described using a function $\sigma$ mapping each state $v$ to one of the edges
$e\in E$ with $s(e)=v$. By solving an MDP we typically mean finding one such
$\sigma$. It is known that an MDP instance can be solved using linear
programming [d’E63]. Interestingly, strongly polynomial algorithms are known
if the discount factors $\gamma(a)$ are all equal to a constant
$\gamma\in(0,1)$ [HMZ13, Ye11].

In more restricted deterministic Markov Decision Processes (DMDPs), for each
$a\in A$ the distribution $p(a)$ satisfies $p(a)(w)=1$ for some $w\in V$. As a
result, the action determines the next state uniquely. Such an MDP can be
represented as a directed graph $G$ with a corresponding edge $e=uv$ for each
action $e\in E$ with $s(e)=u$ and $p(e)(v)=1$. The optimal policy $\sigma$
maps each vertex to one of its outgoing edges. An optimal policy for a DMDP
can be obtained by finding the pointwise maximal solution to the system (1),
which, since $\gamma(e)\in(0,1)$ for all $e\in E$, always exists and is
bounded (for a proof, see e.g., [MTZ10]).

Currently, the most efficient known strongly polynomial algorithms for solving
DMDPs in full generality are those testing 2VPI feasibility [CM94, HN94] (see
also [Mad00]). Less efficient strongly polynomial algorithms that avoid
parametric search have also been described [DKNV21, HKZ14].

The special case when all discount factors $\gamma(e)$ are uniform (equal to
$\gamma$, where $\gamma$ can be a parameter, not necessarily a constant)
gained a lot of attention. Madani et al. [MTZ10] showed an $O(mn)$ time
algorithm for this case. Note that improving upon this bound would be a large
breakthrough since $O(nm)$ remains the best known strongly polynomial bound
even for the simpler problem of negative cycle detection. Weaker strongly
polynomial upper bounds can be obtained by analyzing the performance of the
simplex algorithm on such DMDPs [PY15, HKZ14].

#### Discounted APSP.

Madani et al. [MTZ10] also studied the following extension of the DMDPs.
Suppose the controller is allowed to end the process after entering a fixed
state $t\in V$, which is equivalent to adding a zero-cost loop action to $t$.
The _discounted all-pairs shortest paths_ problem asks to find an optimal
policy for every possible start/end state pair $s,t\in V$.

Besides of the motivation arising from DMDPs, the discounted APSP problem is
interesting in its own as a natural generalization of the standard APSP
problem. In this generalization, the cost of a path $P=eQ$ for some $e\in E$
is given by $c(P)=c(e)+\gamma(e)\cdot c(Q)$ (for $\gamma(e)\leq 1$). Note that
in the standard APSP problem we have $\gamma(e)=1$ for all $e\in E$.

The discounted APSP problem turns out to be challenging because the shortest
paths do not possess the optimal substructure property anymore (except for the
path suffixes) and, as a result, the standard $\widetilde{O}(nm)$ or
$O(n^{3})$ time algorithms for APSP fail (see [MTZ10]). However, one can quite
easily solve the problem in $O(mn^{2})$ time by applying a reverse Bellman-
Ford algorithm $n$ times.

Madani et al. [MTZ10] showed that despite the additional challenges, in the
_uniform_ case (when $\gamma(e)$ is equal for all $e$, and thus the cost of a
path $P=e_{0}\cdots e_{k}$ is given by
$c(P)=\sum_{i=0}^{k}c(e)\cdot\gamma^{i}$), the discounted APSP problem can be
solved in $\widetilde{O}(n^{2}\sqrt{m})$ time with a randomized algorithm.
Note that this bound is $\widetilde{O}(n^{3})$ for all $m$ and
$\widetilde{O}(n^{2.5})$ for sparse graphs.333In the uniform case, it does not
make sense to consider the case $m>n^{2}$. They asked whether there exists an
$\widetilde{O}(nm)$ time algorithm for discounted APSP in the uniform case
whose performance would match, up to polylogarithmic factors, the known
algorithms solving the standard APSP problem.

###  1.1 Our results

First of all, we show a strongly polynomial time-space trade-off algorithm for
computing a pointwise maximal solution to a monotone 2VPI system.

######  Theorem 1.1.

For any $h\in[1,n]$, there is a Las Vegas algorithm solving a monotone 2VPI
system in $\widetilde{O}(mnh+(n/h)^{3})$ expected time and
$O(m)+\widetilde{O}(n^{2}/h)$ space. If the system is feasible, the algorithm
computes the pointwise maximal solution. The time bound holds with high
probability.

Recall that due to known reductions [DKNV21, HMNT93], the algorithm behind
Theorem 1.1 can be used to solve the 2VPI feasibility problem in full
generality and also to compute an optimal policy for DMDPs. In particular, by
a suitable choice of the parameter $h$, we conclude the following.

######  Corollary 1.2.

There exist Las Vegas algorithms solving monotone 2VPI systems:

  1. 1.

in $\widetilde{O}(nm+n^{3/2}m^{3/4})$ expected time using
$\widetilde{O}(n^{3/2}m^{1/4})+O(m)$ space,

  2. 2.

in $\widetilde{O}(nm+n^{3})$ expected time using $O(n+m)$ space.

The former bound improves upon the previous best randomized bound
$\widetilde{O}(n^{3}+nm)$ of Cohen and Megiddo [CM94] by a polynomial factor
for non-dense instances with $m=O(n^{2-\epsilon})$, where $\epsilon>0$. This
answers an open problem of Madani et al. [MTZ10].444Who asked whether one can
solve DMDPs in $o(mn^{2})$ strongly polynomial time. Whereas the randomized
algorithm of Cohen and Megiddo [CM94] already improves upon $O(mn^{2})$ time
for most densities, our algorithm is the first to break the $O(mn^{2})$ bound
for _sparse_ graphs. For such instances it also uses subquadratic space,
whereas all the previous algorithms with $o(mn^{3})$ time required
$\Theta(n^{2}+m)$ space. The latter bound matches the previous best bound
[CM94] but using _linear_ space as opposed to quadratic in $n$.

We also give an improved algorithm for the discounted APSP problem.

######  Theorem 1.3.

There exists a deterministic algorithm solving the discounted all-pairs
shortest paths problem in the uniform case ($\gamma(e)=\gamma$ for all $e\in
E$) in $\widetilde{O}(n^{3/2}m^{3/4})$ time.

Whereas we do not achieve the $\widetilde{O}(nm)$ bound in the uniform case,
we improve the bound of Madani et al. [MTZ10] significantly for sparse graphs;
then, our algorithm runs in $\widetilde{O}(n^{2+1/4})$ time. Additionally, our
algorithm is deterministic.

Unfortunately, neither our algorithm nor that of Madani et al. [MTZ10] leads
to an $o(mn^{2})$ time bound for discounted APSP problem in the non-uniform
case. Obtaining such an algorithm is an interesting open problem. The main
obstacle here is that in the case of varying discount factors it is even
unclear whether one can compute _single-source discounted shortest paths_ in
$o(mn^{2})$ time.555As opposed to _single-target_ shortest discounted paths,
which can be computed in $O(mn)$ time using a Bellman-Ford-style procedure.

###  1.2 Technical overview

#### A simple randomized linear-space algorithm.

Our first contribution is a simple Las Vegas randomized algorithm computing a
pointwise maximal solution of a monotone 2VPI system in $O(mn^{2}\log{m})$
time and _linear_ space. Note that this matches the best known deterministic
time bound [HN94] which is achieved using $\Theta(n^{2}+m)$ space.

Like all the previous polynomial algorithms designed specifically for 2VPI
feasibility, we make use of Shostak‘s characterization [Sho81] of the
pointwise maximal solution ${x^{\max}}$ (see Theorem 2.1). Roughly speaking,
it says that for any $v\in V$, ${x_{v}^{\max}}$ equals the minimum upper bound
on $x_{v}$ that can be devised from a simple path/simple cycle pair $(P,C)$
such that $P=v\to w$ for some $w\in V$ and $C$ is a cycle in $G$ going through
$w$ whose product $\gamma(C)$ of values $\gamma(e)$ is less than $1$. It is
easy to verify that such a cycle $C$ implies some absolute upper bound on
$x_{w}$, whereas such a path $P$ implies an upper bound on $x_{v}$ as a
function of $x_{w}$.

Megiddo‘s algorithm [Meg83b] uses this characterization in the following way.
Let $\phi_{w}$ be the tightest upper bound that can be obtained using a simple
cycle $C$ going through $w$. Megiddo shows that each _cycle bound_ $\phi_{w}$
can be computed in $O(mn^{2}\log{m})$ time and linear space with parametric
search. This is possible since $\phi_{w}<\xi$ can be evaluated in $O(mn)$ time
using a Bellman-Ford-style procedure of depth $O(n)$.666Here, by the depth we
mean the parallel time of the algorithm. Thus, computing the cycle bounds
$\phi_{w}$ for all $n$ possible $w\in V$ takes $O(mn^{3}\log{m})$ time. It is
not difficult to show that ${x^{\max}}$ can be obtained by propagating the
bounds $\phi_{w}$ using a Bellman-Ford-style procedure running in $O(nm)$ time
and linear space.

On the other hand, the state-of-the-art algorithms for 2VPI feasibility [CM94,
HN94] do not compute cycle bounds at all. They instead use the following key
lemma attributed to Aspvall and Shiloach [AS80].777The attribution is made
consistently throughout the previous work, e.g., in [CM94, HN94]. Restrepo and
Williamson [RW09] point out that the procedure should be rather tracked to
Aspvall’s Ph.D. thesis [Asp81]; they also argue that the original
implementation [Asp81] uses $O(n^{2})$ space, and provide a linear-space
algorithm accomplishing essentially the same task.

######  Lemma 1.4.

Let $v\in V$ and $\xi\in\mathbb{R}$. One can check whether
${x_{v}^{\max}}<\xi$ in $O(nm)$ time and using linear space.

Cohen and Megiddo [CM94] call the process behind Lemma 1.4 ’’locating‘‘ a
value $\xi$ with respect to ${x_{v}^{\max}}$. Roughly speaking, the procedure
behind Lemma 1.4 looks for a certificate, consisting of a path and a cycle,
that imposes an upper bound on $x_{v}$ tighter than $\xi$.

Hochbaum and Naor [HN94] use Lemma 1.4 to eliminate a single variable $x_{v}$
by replacing it with up to $O(n^{2})$ inequalities (computed via parametric
search) between the neighbors of $v$ in $G$. So, reducing the instance in
terms of the number of variables comes at a cost of densifying the instance.

The deterministic algorithm of Cohen and Megiddo [CM94] leverages Lemma 1.4
while performing a repeated-squaring-style all-pairs shortest paths algorithm.
This algorithm constructs paths of at most $2k$ edges that impose tightest
inequalities between all the $n^{2}$ pairs out of the $n^{2}$ tightest
inequalities imposed by paths of length at most $k$. Picking the right $n^{2}$
paths out of $n^{3}$ possibilities requires applying Lemma 1.4 for each
variable once.

The above explains why for both these approaches [CM94, HN94], the
$\Theta(n^{2})$ space usage seems inherent. Moreover, the usage of Lemma 1.4
(as opposed to computing cycle bounds, which is a slightly easier task) seems
essential as well.

To match the $\widetilde{O}(mn^{2})$ time bound with a linear space algorithm,
we retreat to the original approach of Megiddo [Meg83b]. We observe that if
some cycle $C$ at vertex $v$ with $\gamma(C)<1$ satisfies
$\phi_{v}={x_{v}^{\max}}$, we do not need to compute the cycle bound
$\phi_{w}$ for all other vertices $w\neq v$ of $C$. So this suggests that if
$C$ is large, we can save a lot of time. Moreover, if $\phi_{v}$ is attained
using a cycle with $k$ edges, then the test $\phi_{v}<\xi$ can be performed
correctly in $O(mk)$ time. As a result, parametric search can compute
$\phi_{v}$ correctly in $O(mk^{2}\log{m})$ time as opposed to
$O(mn^{2}\log{m})$. Interestingly, this property of cycle bounds does not
apply to certificates considered in Lemma 1.4. Indeed, it is not clear whether
one can prove a stronger version of Lemma 1.4 that could test in $O(mk)$ time
whether there exists a path-cycle pair of total size $k$ that certifies
${x_{v}^{\max}}<\xi$.888The intuitive reason why this may be hard is as
follows: locating a value $\xi$ wrt. ${x_{v}^{\max}}$ resembles finding a
negative cycle _reachable_ from $v$ in $G$. Whereas one can easily check
whether there exists a negative cycle of $k$ edges _going through_ $v$ in
$O(mk)$ time, it is widely believed that finding such a small negative cycle
in $G$ globally (which can be easily made reachable from an artificial source
vertex with edges to all other vertices) requires cubic time [WW18].

With these observations, the randomized approach is roughly as follows. For
some $k$, consider some $\leq n$ chosen cycles $C_{v}$ such that
$|C_{v}|\in[k,2k]$ and ${x_{v}^{\max}}$ is attained using the upper bound
incurred by $C_{v}$ (possibly, in combination with some path from $v$ to
$C_{v}$). Let us denote by $V_{k}$ the set of such vertices $v$. Suppose we
sample $O((n/k)\log{n})$ vertices $s$, and compute for each sample $s$ the
best cycle bound on $x_{s}$ incurred by a cycle of length at most $2k$. Then,
with high probability999That is, with probability at least $1-1/n^{c}$ for an
arbitrarily chosen constant $c\geq 1$., for all $v\in V_{k}$ some sample
$s_{v}$ will hit $C_{v}$ and we will thus correctly compute $\phi_{s_{v}}$ in
$O(mk^{2}\log{n})$ time. Hence, the total time through all $O((n/k)\log{n})$
samples $s_{v}$ will be $O(mnk\log^{2}{n})$. Given all the cycle bounds
$\phi_{s_{v}}$, we can compute the actual tightest upper bounds
${x_{v}^{\max}}$ for all $v\in V_{k}$ in $O(nm)$ time by propagating them
using a Bellman-Ford-style procedure.

By proceeding as sketched above for all $k=2^{j}$, $j=0,\ldots,O(\log{n})$, we
will succeed in computing ${x_{v}^{\max}}$ for all $v\in V$ in
$O(mn^{2}\log^{2}{n})$ time whp. As we show, the sampling can be slightly
refined so that the _expected_ time of the algorithm is $O(mn^{2}\log{m})$,
i.e., exactly matching the best known deterministic bound [HN94].

#### The trade-off algorithm.

Our space-time trade-off is obtained by combining the described linear-space
algorithm with the $\widetilde{O}(n^{3}+nm)$ time algorithm of Cohen and
Megiddo [CM94]. Namely, for some threshold parameter $h$, we handle computing
cycle bounds incurred by short cycles of length less than $h$ in
$\widetilde{O}(nmh)$ time using $O(\log{h})$ initial phases of the linear-
space algorithm. Next, we show that computing the cycle bounds incurred by
long cycles of length $h$ or more can be reduced, again via sampling, to a
smaller (but necessarily dense) 2VPI instance with $\widetilde{O}(n/h)$
variables and $\widetilde{O}((n/h)^{2})$ inequalities. Such an instance can be
solved in $\widetilde{O}((n/h)^{3})$ time. Finally, we show that this
reduction can be performed in $\widetilde{O}(nmh)$ time and using
$\widetilde{O}(n^{2}/h)$ space. The reduction constitutes another application
of parametric search. However, the key that enables its efficient
implementation is the main trick behind the randomized algorithm of Cohen and
Megiddo [CM94], i.e., an $\widetilde{O}(nm)$ expected time procedure that can
run Lemma 1.4 for every vertex $v\in V$ (critically, for each $v$ with a
different threshold $\xi_{v}$) in parallel (see Lemma 5.2).

We now note that whereas the $\widetilde{O}(nmh+(n/h)^{3})$ time trade-off
that we achieve has not been described previously, we believe that it can also
be achieved via a combination of the randomized approach of Cohen and Megiddo
[CM94] and the recent parallel APSP algorithm of Karczmarz and Sankowski
[KS21]. This is because Cohen and Megiddo‘s approach is, technically speaking,
a randomized reduction to parallel APSP in the comparison-addition model.
Namely, if a parallel APSP algorithm with work $W(n,m)$ bound and depth $d$ is
provided, the running time of the reduction is $\widetilde{O}(W(n,m)+d\cdot
nm)$. Since it is known [KS21] that for any $d\in[1,n]$ one can achieve
$W(n,m)=\widetilde{O}(nm+(n/d)^{3})$, the same randomized time bound as in
Theorem 1.1 is obtained ultimately. However, the space requirement remains
$\Theta(n^{2})$ if one proceeds this way, so our approach is significantly
more efficient in terms of space.

#### Certificates of infeasibility.

Shostak‘s characterization [Sho81] (Theorem 2.1) states that if a monotone
2VPI system is infeasible, then there exists a minimal _certificate_ that
consists of at most two cycles and at most one path in $G$. In applications,
e.g., in Wayne‘s generalized minimum cost flow algorithm [Way02], simply
declaring a monotone 2VPI system infeasible (which can be easily done by
checking if the obtained pointwise maximal solution violates the system (1))
is not enough, and a certificate of infeasibility is required. Moreover,
computing such certificates is a bottleneck in Wayne‘s algorithm. We observe
that constructing a certificate can be a very subtle task and it can make 2VPI
feasibility algorithms considerably more complicated (see Section 8). Our
simple randomized algorithm is capable of constructing a certificate of
infeasibility, and thus we improve the space requirement of Wayne‘s algorithm
to linear when relying on a $\widetilde{O}(mn^{2})$ time 2VPI feasibility
algorithm. However, our trade-off algorithm can only provide such a
certificate _conditionally_ on whether the randomized algorithm of Cohen and
Megiddo [CM94] has this property. While Wayne [Way02, Section 6.2] claims that
all the previously known 2VPI feasibility algorithms have this property, we
are unsure this applies to [CM94]. That being said, it is very likely that
that (already complicated) algorithm can be suitably extended. Then, our
trade-off algorithm leads to a faster combinatorial generalized minimum cost
flow algorithm.

#### Discounted all-pairs shortest paths.

In our discounted APSP algorithm, we build upon the observation of Madani et
al. [MTZ10] that allows reducing the general discounted APSP problem to the
case where one only cares about _simple and finite_ paths. Then, to obtain the
improved algorithm for the uniform case, we describe two _different_
approaches for reducing the number of sources of interest. More specifically,
given a discounted shortest paths problem instance $\langle S,V\rangle$ that
requires computing the discounted distances $\delta_{G}(s,t)$ for all
$(s,t)\in S\times V$, a _sources set reduction step_ reduces the problem
$\langle S,V\rangle$ to a problem $\langle S^{\prime},V\rangle$, where
$|S^{\prime}|\ll|S|$.

Both our sources set reduction steps (Lemma 6.8) are based on
deterministically hitting sufficiently long prefixes of discounted shortest
paths from $S$ to $V$. The first reduction leverages the suffix optimality
property of discounted shortest paths (Observation 6.2) whereas the other
takes advantage of $k$-prefix optimality of discounted shortest paths
(Observation 6.3). Starting with the problem $\langle V,V\rangle$, we end up
applying the first reduction step once, and the other $O(\log{n})$ times.

##  2 Preliminaries

#### Paths, cycles, and walks.

To avoid confusion we will use the standard term _walk_ to refer to a non-
necessarily simple path. A _closed walk_ is a walk that starts and ends in the
same vertex. Whenever we write _path_ , we actually mean a _simple path_ with
no repeated vertices, possibly except for its endpoints. A _cycle_ is a closed
simple path with equal source and target. Sometimes when referring to a cycle
we interpret it as a subgraph of $G$, and sometimes, when a cycle has a
distinguished source vertex $s$, we interpret it as an $s\to s$ path. It
should be clear from the context which interpretation we use.

Let $P=e_{1}\ldots e_{k}$ be an $s\to t$ walk in $G$. We define $|P|=k$. The
walk $P$ can be used to devise the following inequality:

$x_{s}\leq
c(e_{1})+\gamma(e_{1})\cdot(c(e_{2})+\gamma(e_{2})\cdot\left(\ldots\cdot(c(e_{k})+\gamma(e_{k})\cdot
x_{t})\right))=\sum_{i=1}^{k}c(e_{i})\left(\prod_{j=1}^{i-1}\gamma(e_{j})\right)+\prod_{i=1}^{k}\gamma(e_{i})\cdot
x_{t}.$

Let us define
$c(P)=\sum_{i=1}^{k}c(e_{i})\left(\prod_{j=1}^{i-1}\gamma(e_{j})\right)$ and
$\gamma(P)=\prod_{i=1}^{k}\gamma(e_{i})$. Then we can write:

$x_{s}\leq c(P)+\gamma(P)\cdot x_{t}.$

Note that if $k=1$, i.e., $P$ consists of a single edge $e_{1}$, we have
$c(P)=c(e_{1})$ and $\gamma(P)=\gamma(e_{1})$. If $P$ can be expressed as
$P=P_{1}P_{2}$, then $c(P)=c(P_{1})+\gamma(P_{1})\cdot c(P_{2})$ and
$\gamma(P)=\gamma(P_{1})\cdot\gamma(P_{2})$.

If $C$ is an $s\to s$ closed walk, we obtain the inequality $x_{s}\leq
c(C)+\gamma(C)\cdot x_{s}$. Depending on the position of $\gamma(C)$ wrt. $1$,
$C$ can be used to obtain upper or lower bounds on $x_{s}$. If $\gamma(C)<1$,
then $C$ implies the inequality $x_{s}\leq\frac{c(C)}{1-\gamma(C)}$. If
$\gamma(C)>1$, then it implies the inequality
$x_{s}\geq\frac{c(C)}{1-\gamma(C)}$. If $\gamma(C)=1$, then the implied
inequality is $0\leq c(C)$. So, assuming $\gamma(C)=1$, if $c(C)<0$, then the
system is infeasible, and otherwise the obtained inequality is trivial.

A _negative unit-gain_ closed walk with $\gamma(C)=1$ and $c(C)<0$ constitutes
a possible _certificate of infeasibility_. Another possible certificate of
infeasibility is a pair of $s\to s$ closed walks $C^{\geq},C^{\leq}$ such that
$\gamma(C^{\geq})>1$, $\gamma(C^{\leq})<1$ and
$\frac{c(C^{\geq})}{1-\gamma(C^{\geq})}>\frac{c(C^{\leq})}{1-\gamma(C^{\leq})}$.
Then the lower- and upper bounds imposed by $C^{\geq}$ and $C^{\leq}$ on
$x_{s}$ respectively are contradictory.

Sometimes, for a cycle $C\subseteq G$ without a distinguished start vertex we
will write $c_{s}(C)$ to denote the cost of $C$ if $C$ is interpreted as an
$s\to s$ path.

Denote by $\mathcal{P}_{s,t}$ the set of _simple_ $s\to t$ paths in $G$. In
particular, let $\mathcal{P}_{s,s}$ be the set of _simple_ cycles in $G$ that
contain $s$.

For any $k\geq 0$, denote by $\mathcal{P}_{s,t}^{k}$ the set of $s\to t$ walks
with at most $k$ edges. Let $\mathcal{C}_{v}^{k}=\mathcal{P}_{v,v}^{k}$ be the
set of closed walks with at most $k$ edges and a distinguished starting vertex
$v$, so that for any $C\in\mathcal{C}_{v}^{k}$, $c(C)$ is well-defined. For
$C\in\mathcal{C}_{v}^{k}$, let $\phi(C)=\frac{c(C)}{1-\gamma(C)}$ be the
_cycle bound_ of $C$. If $C$ has no distinguished source, and we interpret it
as an $s\to s$ path, we similarly set
$\phi_{s}(C)=\frac{c_{s}(C)}{1-\gamma(C)}$.

Finally, note that if $C$ is a walk such that $C=PQ$, then:

$\phi(C)=\frac{c(C)}{1-\gamma(C)}=\frac{c(P)(1-\gamma(QP))+c(P)\gamma(QP)+\gamma(P)\cdot
c(Q)}{1-\gamma(QP)}=c(P)+\gamma(P)\cdot\phi(QP).$ (2)

#### Feasibility of monotone 2VPI systems.

The following key result is attributed (see e.g. [CM94, DKNV21]) to Shostak
[Sho81] and provides a way to test the feasibility of monotone 2VPI inequality
systems. Moreover, if the system is feasible, it gives explicit formulas for
calculating the vectors ${x^{\max}},{x^{\min}}$.

######  Theorem 2.1.

[Sho81] Let:

$\displaystyle x_{v}^{\leq}$ $\displaystyle=\min_{w\in
V}\min_{P\in\mathcal{P}_{v,w}}\left\\{c(P)+\gamma(P)\cdot\min_{\begin{subarray}{c}C\in\mathcal{P}_{w,w}\\\
\gamma(C)<1\end{subarray}}\left\\{\phi(C)\right\\}\right\\},$ (3)
$\displaystyle x_{v}^{\geq}$ $\displaystyle=\max_{w\in
V}\max_{P\in\mathcal{P}_{w,v}}\left\\{\frac{1}{\gamma(P)}\left(\max_{\begin{subarray}{c}C\in\mathcal{P}_{w,w}\\\
\gamma(C)>1\end{subarray}}\left\\{\phi(C)\right\\}-c(P)\right)\right\\}.$

Then:

  1. 1.

If the system (1) is feasible, ${x_{v}^{\max}}=x_{v}^{\leq}$ and
${x_{v}^{\min}}=x_{v}^{\geq}$ for all $v\in V$.

  2. 2.

If $x_{v}^{\leq}<x_{v}^{\geq}$ for some $v$, then the system is infeasible.

  3. 3.

If the system is infeasible, then there exists a certificate of infeasibility
$H\subseteq G$, such that $H$ is either

    1. (a)

a cycle with $\gamma(H)=1$ and $c(H)<0$ (so-called _negative unit-gain
cycle_), or

    2. (b)

$H=C^{\leq}\cup C^{\geq}\cup P$, where, for some possibly equal $s,t\in V$,
$C^{\leq}\in\mathcal{P}_{t,t}$, $C^{\geq}\in\mathcal{P}_{s,s}$,
$P\in\mathcal{P}_{s,t}$, $\gamma(C^{\leq})<1$, $\gamma(C^{\geq})>1$, and
$c_{s}(C^{\geq})>c(P)+\gamma(P)\cdot c_{s}(C^{\leq})$ (so-called _negative
bicycle_).

Theorem 2.1 states that ${x_{v}^{\max}}$ equals the tightest upper bound
incurred on $v$ by a path/cycle pair $(P,C)\in\bigcup_{w\in
V}\mathcal{P}_{v,w}\times\mathcal{P}_{w,w}$. Similarly, ${x_{v}^{\min}}$
equals the tightest lower bound incurred on $v$ by a cycle/path pair
$(C,P)\in\bigcup_{w\in V}\mathcal{P}_{w,w}\times\mathcal{P}_{w,v}$.

#### Propagating bounds through walks.

Suppose for all $v\in V$, $y_{v}\geq{x_{v}^{\max}}$ is a valid upper bound on
$x_{v}$. By _propagating bounds through edges_ we mean the following
operation.101010Cohen and Megiddo [CM94] call this a _push phase_. Madani
[Mad00] calls this _backward propagation_. First, record a copy of each
$y_{u}$ as $y_{u}^{\prime}$. For all $uv=e\in E$, set
$y_{u}:=\min(y_{u},c(e)+\gamma(e)\cdot y_{v}^{\prime})$. The operation clearly
resembles a single phase of the Bellman-Ford algorithm. Note that propagating
bounds through edges keeps the upper bounds valid since $x_{v}\leq y_{v}$
along with $x_{u}\leq c(e)+\gamma(e)x_{v}$ implies that $c(e)+\gamma(e)y_{v}$
is also an upper bound on $x_{u}$.

More generally, we call applying $k\geq 1$ propagation steps _propagating
bounds through walks of length $k$_. It is easy to see that after propagating
bounds through walks of length $k$, the obtained upper bounds $y_{s}$ (for
$s\in V$) satisfy
$y_{s}=\min_{P\in\mathcal{P}_{s,t}^{k}}\\{c(P)+\gamma(P)\cdot
y_{t}^{\prime}\\}$ for any $t\in V$, where $y_{t}^{\prime}$ is the upper bound
on $x_{t}$ _before_ the propagation. Note that propagating through walks of
length $k$ takes $O(mk)$ time and requires linear additional space.

##  3 Simplifying the problem

First of all, note that any closed walk
$C\in\bigcup_{k=1}^{\infty}\mathcal{C}_{v}^{k}$ with $c(C)<0$ and
$\gamma(C)=1$ certifies the infeasibility of the system. Similarly, any triple
$C^{\leq}\in\bigcup_{k=1}^{\infty}\mathcal{P}_{t,t}^{k}$,
$C^{\geq}\in\bigcup_{k=1}^{\infty}\mathcal{P}_{s,s}^{k}$,
$P\in\bigcup_{k=0}^{\infty}\mathcal{P}_{s,t}^{k}$ such that $c(C^{\leq})<1$,
$c(C^{\geq})>1$, and $c(C^{\geq})>c(P)+\gamma(P)\cdot c(C^{\leq})$ certifies
infeasibility of the system. We refer to such certificates as non-simple,
whether to those described in Theorem 2.1 (item 3) as simple.

It is not very difficult to check that any non-simple certificate can be
actually ’’simplified‘‘ in linear time by removing some redundant cycles
(however, e.g., a non-simple negative cycle with $\gamma(C)=1$ might get
simplified into a negative bicycle). That being said, in the following, we
will only care about producing non-simple certificates.

For any $v\in V$, fix $(P_{v},C_{v})$ to be any simple path/simple cycle pair
minimizing the right-hand side of (3), if $x_{v}^{\leq}\neq\infty$. We now
define a set $\mathcal{C}^{*}$ of _distinguished cycles_. If the system (1) is
feasible, we set $\mathcal{C}^{*}$ to be any _maximal_ subset of vertex-
disjoint cycles of $\\{C_{v}:v\in V,x^{\leq}_{v}\neq\infty\\}$. Otherwise, if
it is infeasible, let $v_{\mathrm{bad}}\in V$ be such that
$x_{v_{\mathrm{bad}}}^{\leq}<x_{v_{\mathrm{bad}}}^{\geq}$. Then
$\mathcal{C}^{*}=\\{C_{v_{\mathrm{bad}}}\\}$. Note that such
$v_{\mathrm{bad}}$ exists by Theorem 2.1. Clearly, by the definition, we have
$\sum_{C\in\mathcal{C}^{*}}|C|\leq n$ in any case. In the following we assume
that the distinguished cycles do not have a specified starting point.

######  Definition 3.1.

Let $v\in V$. For $k\geq 1$, we call the value

$\phi_{v,k}=\min\left\\{\phi(C):C\in\mathcal{C}_{v}^{k},\gamma(C)<1\right\\}$

the _$k$ -cycle upper bound_ of $v$ incurred by $G$.

We start with the following technical lemma.

######  Lemma 3.2.

For each $v\in V$ let $x^{*}_{v}\in\mathbb{R}\cup\\{\infty\\}$ be values
satisfying the following: if $x^{*}_{v}\neq\infty$, then there exists
$F_{v}\in\mathcal{P}_{v,f}^{n}$ and $D_{v}\in\mathcal{C}_{f}^{n}$ for some
$f\in V$ such that $\gamma(D_{v})<1$ and
$x^{*}_{v}=c(F_{v})+\gamma(F_{v})\cdot\phi(D_{v})$. Moreover, suppose that for
each $C\in\mathcal{C}^{*}$ there exists such a $w\in V(C)$ that
$x^{*}_{w}\leq\phi_{w,|C|}$. Let

$y^{*}_{v}:=\min_{w\in
V}\min_{P\in\mathcal{P}_{v,w}^{3n}}\left\\{c(P)+\gamma(P)\cdot
x^{*}_{w}\right\\}.$ (4)

If the system (1) is feasible, then for any $v\in V$,
$y^{*}_{v}={x_{v}^{\max}}$. Otherwise, $y^{*}_{v_{\mathrm{bad}}}\leq
x^{\leq}_{v_{\mathrm{bad}}}$ holds.

The values $y^{*}_{v}$, along with endpoints $w_{v}$ of some arbitrary
corresponding walks $P=v\to w_{v}$ minimizing (4), can be found in $O(nm)$
time and linear space.

###### Proof.

First suppose the system is feasible. Then note that in the right hand side of
(3) we can replace the set $\mathcal{P}_{v,w}$ over which $P$ is minimized
with $\mathcal{P}_{v,w}^{4n}$. This cannot decrease $x_{v}^{\leq}$ since it
would then make the vector ${x^{\max}}$ infeasible, which would contradict
Theorem 2.1. Similarly, we can replace $P_{w,w}$ with $\mathcal{C}_{w}^{n}$ in
that formula. Since each finite $x_{v}^{*}$ is an upper bound on $x_{v}$
achieved using a walk of no more than $n$ edges and a closed walk of no more
than $n$ edges, each $y_{v}^{*}$, if finite, is an upper bound on $x_{v}$
achieved using a walk with no more than $3n$ edges and a closed walk with no
more than $n$ edges. It follows that $x_{v}^{\leq}\leq y^{*}_{v}$.

Recall that we have fixed $P_{v},C_{v}$ for any $v$ to be some simple
path/simple cycle minimizing the right-hand side of (3) when defining the
distinguished cycles $\mathcal{C}^{*}$. We first argue that if some $z\in V$
lies on both $C_{v}$ and $C_{w}$ for $v\neq w$, then
$\phi_{z}(C_{v})=\phi_{z}(C_{w})$. Otherwise, we would wlog. have
$\phi_{z}(C_{w})<\phi_{z}(C_{v})$. Then, if $P_{v}=v\to w$, then for the $v\to
z$ subpath $Q$ of $C_{v}$ we would have

$\displaystyle x_{v}^{\leq}$ $\displaystyle\leq
c(P_{v}Q)+\gamma(P_{v}Q)\cdot\phi_{z}(C_{w})$
$\displaystyle<c(P_{v}Q)+\gamma(P_{v}Q)\cdot\phi_{z}(C_{v})$
$\displaystyle=c(P_{v})+\gamma(P_{v})\cdot(c(Q)+\gamma(Q)\cdot\phi_{z}(C_{v}))$
$\displaystyle=c(P_{v})+\gamma(P_{v})\cdot\phi_{v}(C_{v})$
$\displaystyle=x_{v}^{\leq},$

where in the penultimate step we use Equation (2). This is clearly a
contradiction.

Now fix some $v\in V$. Let $C_{v}^{\prime}\in\mathcal{C}^{*}$ be such that
there exists a vertex $s\in V(C_{v})\cap V(C_{v}^{\prime})$. Such a
$C_{v}^{\prime}$ exists since $\mathcal{C}^{*}$ is maximal. Moreover, for some
$t\in V(C_{v}^{\prime})$ we have

$c(F_{t})+\gamma(F_{t})\cdot\phi(D_{t})=x^{*}_{t}\leq\phi_{t,|C_{v}^{\prime}|}\leq\phi_{t}(C_{v}^{\prime}),$

where $\gamma(D_{t})<1$, $F_{t}\in\mathcal{P}_{t,f}^{n}$, and
$D_{t}\in\mathcal{C}_{f}^{n}$ for some $f\in V$. For $P_{v}=v\to w$, let $Q$
be the $w\to s$ subpath of the cycle $C_{v}$, and let $R$ be the $s\to t$
subpath of the cycle $C_{v}^{\prime}$. We obtain:

$\displaystyle x_{v}^{\leq}$
$\displaystyle=c(P_{v})+\gamma(P_{v})\cdot\phi_{v}(C_{v})$
$\displaystyle=c(P_{v})+\gamma(P_{v})\cdot(c(Q)+\gamma(Q)\cdot\phi_{s}(C_{v}))$
$\displaystyle=c(P_{v})+\gamma(P_{v})\cdot(c(Q)+\gamma(Q)\cdot\phi_{s}(C_{v}^{\prime}))$
$\displaystyle=c(P_{v})+\gamma(P_{v})\cdot(c(Q)+\gamma(Q)\cdot(c(R)+\gamma(R)\cdot\phi_{t}(C_{v}^{\prime})))$
$\displaystyle=c(P_{v}QR)+\gamma(P_{v}QR)\cdot\phi_{t}(C_{v}^{\prime}).$

We also have $x_{v}^{\leq}\leq
c(P_{v}QRF_{t})+\gamma(P_{v}QRF_{t})\cdot\phi(D_{t})=c(P_{v}QR)+\gamma(P_{v}QR)\cdot
x^{*}_{t}$ since, as discussed before, in (3) we can equivalently minimize
over pairs of walks of length no more than $4n$ and closed walks of length at
most $n$. So we obtain:

$x_{v}^{\leq}=c(P_{v}QR)+\gamma(P_{v}QR)\cdot\phi_{t}(C_{v}^{\prime})\geq
c(P_{v}QR)+\gamma(P_{v}QR)\cdot x^{*}_{t}\geq x_{v}^{\leq}.$

It follows that $x_{v}^{\leq}=c(P_{v}QR)+\gamma(P_{v}QR)\cdot x^{*}_{t}$.
Finally, since $P_{v}QR\in\mathcal{P}_{v,t}^{3n}$, $y^{*}_{v}\leq
x_{v}^{\leq}$.

We have proved that if the system is feasible, we indeed have
$y^{*}_{v}=x_{v}^{\leq}$ for all $v\in V$. By Theorem 2.1, it follows that
$y^{*}_{v}={x_{v}^{\max}}$ for all $v\in V$.

Now assume that the system is infeasible. Let
$P_{v_{\mathrm{bad}}}=v_{\mathrm{bad}}\to w$. Then there exists $t\in
V(C_{v_{\mathrm{bad}}})$ such that if $Q$ is the $w\to t$ path of
$C_{v_{\mathrm{bad}}}$, then

$\displaystyle x_{v_{\mathrm{bad}}}^{\leq}$
$\displaystyle=c(P_{v_{\mathrm{bad}}})+\gamma(P_{v_{\mathrm{bad}}})\cdot\phi_{w}(C_{v_{\mathrm{bad}}})$
$\displaystyle=c(P_{v_{\mathrm{bad}}})+\gamma(P_{v_{\mathrm{bad}}})\cdot(c(Q)+\gamma(Q)\cdot\phi_{t}(C_{v_{\mathrm{bad}}}))$
$\displaystyle\geq
c(P_{v_{\mathrm{bad}}})+\gamma(P_{v_{\mathrm{bad}}})\cdot(c(Q)+\gamma(Q)\cdot
x^{*}_{t})$
$\displaystyle=c(P_{v_{\mathrm{bad}}}Q)+\gamma(P_{v_{\mathrm{bad}}}Q)\cdot
x^{*}_{t}$ $\displaystyle\geq y^{*}_{t},$

as clearly $P_{v_{\mathrm{bad}}}Q\in\mathcal{P}_{v,t}^{3n}$ holds.

The algorithm to compute the ultimate values $y_{v}^{*}$ is to simply set
$y_{v}^{*}:=x_{v}$ initially and then propagate these values through paths of
length no more than $3n$. This takes $O(nm)$ time. Propagation can be easily
extended to store an endpoint $w_{v}$ of some path $P$ such that
$y_{v}^{*}=c(P)+\gamma(P)\cdot x^{*}_{w}$. ∎

We now argue that in $O(mn\log{n})$ time we can reduce solving monotone 2VPI
feasibility to the following more restricted problem.

######  Problem 3.3.

Compute a vector of values $x_{v}^{*}$, $v\in V$, satisfying:

  * •

If $x_{v}^{*}\neq\infty$, then $x_{v}^{*}=c(F)+\gamma(F)\cdot\phi(D)$ for some
$F\in\mathcal{P}_{v,w}^{n}$, $D\in\mathcal{C}_{w}^{n}$, $\gamma(D)<1$.

  * •

For each $C\in\mathcal{C}^{*}$, there exists a vertex $s\in V(C)$ such that
$x_{s}^{*}\leq\phi_{s,|C|}$.

######  Remark 3.4.

If we seek a certifying monotone 2VPI feasibility algorithm, then the
algorithm solving Problem 3.3 has to possess the following additional
properties:

  * •

The algorithm is allowed to fail but then a certificate of infeasibility of
the system is required.

  * •

After the values $x_{v}^{*}$ are successfully computed, the algorithm may be
requested to compute a corresponding walk/closed walk pair $(F,D)$ as defined
above for some _single given_ $v$ with $x_{v}^{*}\neq\infty$.

First, suppose the system is feasible. Then, indeed Lemma 3.2 implies that the
pointwise maximal solution can be computed after solving Problem 3.3. By
symmetry in Theorem 2.1, the values ${x_{v}^{\min}}$ can be computed by
finding the pointwise maximal solution for a ’’reverse‘‘ instance $G^{R}$,
where each edge $e$ is reversed, has cost $c^{R}(e)=-c(e)/\gamma(e)$, and
$\gamma^{R}(e)=1/\gamma(e)$.

If the system is infeasible and while solving Problem 3.3 we do not encounter
a certificate of infeasibility, then the values $y^{*}_{v}$ from Lemma 3.2
(whose definition does not depend on feasibility) are computed correctly. The
same applies to the analogously defined ’’reverse‘‘ values $(y^{*}_{v})^{R}$.
Recall that if the system is infeasible then for some $v$ we have
$x^{\leq}_{v_{\mathrm{bad}}}<x^{\geq}_{v_{\mathrm{bad}}}$. Lemma 3.2
guarantees that $y^{*}_{v_{\mathrm{bad}}}\leq x^{\leq}_{v_{\mathrm{bad}}}$ in
such case. The same applies to the value $(y^{*}_{v_{\mathrm{bad}}})^{R}$,
i.e., $x^{\geq}_{v_{\mathrm{bad}}}\leq(y^{*}_{v_{\mathrm{bad}}})^{R}$. As a
result, we have $y^{*}_{v_{\mathrm{bad}}}<(y^{*}_{v_{\mathrm{bad}}})^{R}$. We
do not know $v_{\mathrm{bad}}$ beforehand, but its existence proves that
$y^{*}_{g}<(y^{*}_{g})^{R}$ for some $g\in V$. Clearly, we can find one such
$g$ in $O(n)$ time.

Since $y_{g}^{*}=\min_{w\in
V}\min_{P\in\mathcal{P}_{g,w}^{3n}}\left\\{c(P)+\gamma(P)\cdot
x^{*}_{w}\right\\}$, the following lemma, proved in Section 7, can be used to
produce such a walk $S_{g}=g\to w_{g}$ that
$y^{*}_{g}=c(S_{g})+\gamma(S_{g})\cdot x^{*}_{w_{g}}$.

######  Lemma 3.5.

Let $s,t\in V$ and $\alpha\in\mathbb{R}$. Then, an $s\to t$ walk
$Q\in\mathcal{P}_{s,t}^{k}$ lexicographically minimizing the pair
$(c(Q)+\gamma(Q)\cdot\alpha,\gamma(Q))$ can be constructed in $O(mk\log{k})$
time and linear space.

We can thus request from the algorithm solving Problem 3.3 a walk/closed walk
pair $F,D$ with $\gamma(D)<1$ such that
$x^{*}_{w_{g}}=c(F)+\gamma(F)\cdot\phi(D)$. Symmetrically, we can construct a
walk $S_{g}^{R}=u_{g}\to g$, and a pair $F^{R},D^{R}$ (note that
$S_{g}^{R},F^{R},D^{R}$ are walks in $G$, not $G^{R}$) such that
$(y^{*}_{g})^{R}=\left((\phi(D^{R})-c(F^{R}))/\gamma(F^{R})\right)-c(S_{g}^{R}))/\gamma(S_{g}^{R})$.
Observe that then the closed walks $D,D^{R}$ along with the walk $F^{R}\cdot
S_{g}^{R}\cdot S_{g}\cdot F$ form a negative bicycle that constitutes a
certificate of infeasibility.

##  4 A simple randomized linear-space algorithm

In this section, we describe a simple randomized algorithm solving Problem
3.3. The following lemma gives a method for computing values $\phi_{v,k}$ for
any $k$. The proof is quite technical and and is deferred to Section 8.

######  Lemma 4.1.

Let $v\in V$ and $k\leq n$. Then, in $O(mk^{2}\log{m})$ time and linear space
one can compute either the value $\phi_{v,k}$ (along with a closed walk
$C\in\mathcal{C}_{v}^{k}$ such that $\gamma(C)<1$ and $\phi(C)=\phi_{v,k}$ if
$\phi_{v,k}\neq\infty$) or a set of at most two closed walks certifying the
infeasibility of the system.

Note that Problem 3.3 can be easily solved deterministically in
$O(mn^{3}\log{m})$ time by setting $x^{*}_{v}=\phi_{v,n}$ for each $v\in V$.
However, for example, for large distinguished cycles $C\in\mathcal{C}^{*}$ it
would be enough to set $x^{*}_{u}=\phi_{u,|C|}$ for just one vertex $u\in
V(C)$, instead of all $|C|$ vertices. Unfortunately, it is not clear how to
construct $\mathcal{C}^{*}$ deterministically without computing $\phi_{v,n}$
for all $v\in V$, which again takes $O(mn^{3}\log{m})$ time. We will thus use
random sampling to hit all the distinguished cycles. For example, to hit all
distinguished cycles of length $\Theta(n)$ with high probability, only
$\widetilde{O}(1)$ samples are needed.

The simple randomized algorithm proceeds in $O(\log{n})$ phases numbered
$0,\ldots,\ell$, where $\ell$ is the largest integer such that $2^{\ell}\leq
n$. Initially, $x_{v}^{*}=\infty$ for all $v$. Consider the $j$-th phase. In
the $j$-th phase we repeat the following $t_{j}=\lceil
n/2^{j}\rceil\cdot(\ell+2-j)^{3}$ times. First, sample a vertex $v\in V$
uniformly at random. Then, compute $\phi_{v,2^{j+1}}$ using Lemma 4.1 and set
$x_{v}^{*}:=\min(x_{v}^{*},\phi_{v,2^{j+1}})$. If Lemma 4.1 fails with a
certificate of infeasibility, we terminate with that certificate.

######  Lemma 4.2.

If no certificate of infeasibility is produced, then with constant
probability, for each distinguished cycle $C\in\mathcal{C}^{*}$ there exists
$v\in V(C)$ such that $\phi(D_{v})\leq x_{v}^{*}\leq\phi_{v,|C|}$ for some
$D_{v}\in\mathcal{C}_{v}^{n}$.

###### Proof.

Denote by $p$ the probability that we fail to achieve the goal from the
lemma‘s statement. So our aim is on proving that $p$ is bounded from above by
a constant less than $1$.

Let $\mathcal{C}^{*}_{j}\subseteq\mathcal{C}^{*}$ be the subset of cycles of
$\mathcal{C}^{*}$ of size between $2^{j}$ and $2^{j+1}$. Since the cycles in
$\mathcal{C}^{*}$ are vertex-disjoint, we have
$\sum_{C\in\mathcal{C}^{*}}|C|\leq n$. As a result, $|\mathcal{C}^{*}_{j}|\leq
n/2^{j}$.

In the following, _to hit a cycle $C\in\mathcal{C}^{*}_{j}$_ means to sample a
vertex that is an element of $V(C)$. Clearly, after a cycle is hit with $v\in
V(C)$, we set $x^{*}_{v}$ to a value no more than
$\phi_{v,2^{j+1}}\leq\phi_{v,|C|}$. Let $p_{j}$ be the probability that during
phase $j$ we fail to hit some $C\in\mathcal{C}^{*}_{j}$. By the union bound,
we have:

$p\leq\sum_{j=0}^{\ell}p_{j}.$

Imagine that we sample vertices in the $j$-th phase indefinitely. For any
$S\subseteq\mathcal{C}^{*}_{j}$, let the random variable $X_{j,S}$ denote the
minimal number of initial samples in the $j$-th phase that hit every cycle in
$S$ at least once.

We now show that for any $S\subseteq\mathcal{C}^{*}_{j}$,
$\mathbb{E}[X_{j,S}]\leq\frac{n}{2^{j}}\cdot\sum_{i=1}^{|S|}\frac{1}{i}$. We
prove the claim by induction on $|S|$. The case $S=\emptyset$ is trivial. For
any $C\in\mathcal{C}^{*}_{j}$, the probability that a sample hits the cycle
$C$ is clearly $|C|/n$. Moreover, let $y=\sum_{C\in S}|C|$. We have:

$\displaystyle\mathbb{E}[X_{j,S}]$ $\displaystyle=1+\left(\sum_{C\in
S}\frac{|C|}{n}\cdot\mathbb{E}[{X_{j,S\setminus\\{C\\}}}]\right)+\frac{n-y}{n}\cdot\mathbb{E}[X_{j,S}]$
$\displaystyle\leq 1+\left(\sum_{C\in
S}\frac{|C|}{n}\cdot\left(\frac{n}{2^{j}}\cdot\sum_{i=1}^{|S|-1}\frac{1}{i}\right)\right)+\frac{n-y}{n}\cdot\mathbb{E}[X_{j,S}]$
$\displaystyle\leq
1+\frac{y}{2^{j}}\cdot\left(\sum_{i=1}^{|S|-1}\frac{1}{i}\right)+\left(1-\frac{y}{n}\right)\cdot\mathbb{E}[X_{j,S}].$

By a simple transformation, and since $y\geq|S|\cdot 2^{j}$, we obtain:

$\mathbb{E}[X_{j,S}]\leq\frac{n}{y}+\frac{n}{2^{j}}\cdot\sum_{i=1}^{|S|-1}\frac{1}{i}\leq\frac{n}{2^{j}}\cdot\frac{1}{|S|}+\frac{n}{2^{j}}\cdot\sum_{i=1}^{|S|-1|}\frac{1}{i}=\frac{n}{2^{j}}\cdot\sum_{i-1}^{|S|}\frac{1}{i},$

as desired. By the obtained bound and $|\mathcal{C}^{*}_{j}|\leq n/2^{j}$, we
have:

$\mathbb{E}\left[X_{j,\mathcal{C}^{*}_{j}}\right]\leq\frac{n}{2^{j}}\cdot\sum_{i=1}^{|\mathcal{C}^{*}_{j}|}\frac{1}{i}\leq\frac{n}{2^{j}}\left(\ln\frac{n}{2^{j}}+1\right)\leq\frac{n}{2^{j}}\cdot\log_{2}{\frac{2n}{2^{j}}}\leq\frac{n}{2^{j}}(\ell+2-j).$

Since in the $j$-th phase we perform sampling $t_{j}=\lceil
n/2^{j}\rceil\cdot(\ell+2-j)^{3}$ times, we have:

$p_{j}\leq\mathbb{P}\left[X_{j,\mathcal{C}^{*}_{j}}>t_{j}\right]\leq\mathbb{P}\left[X_{j,\mathcal{C}^{*}_{j}}>\mathbb{E}\left[X_{j,\mathcal{C}^{*}_{j}}\right]\cdot(\ell+2-j)^{2}\right]\leq\frac{1}{(\ell+2-j)^{2}},$

where the latter bound above follows by Markov‘s inequality. Consequently, we
have:

$p\leq\sum_{j=0}^{\ell}p_{j}\leq\sum_{j=0}^{\ell}\frac{1}{(\ell+2-j)^{2}}\leq\left(\sum_{j=1}^{\infty}\frac{1}{i^{2}}\right)-1=\frac{\pi^{2}}{6}-1<\frac{2}{3},$

which concludes the proof. ∎

######  Lemma 4.3.

The $\ell+1$ phases of the algorithm require $O(mn^{2}\log{m})$ time and
linear space.

###### Proof.

By Lemma 4.1, the running time can be bounded as follows:

$\sum_{j=0}^{\ell}\left(O\left(m\cdot(2^{j})^{2}\log{m}\right)\cdot\left\lceil\frac{n}{2^{j}}\right\rceil\cdot(\ell+2-j)^{3}\right)=O\left(nm\log{m}\cdot\sum_{j=0}^{\ell}2^{j}(\ell+2-j)^{3}\right).$

Moreover, we have:

$\sum_{j=0}^{\ell}2^{j}(\ell-j+1)^{3}=2^{\ell+2}\cdot\sum_{j=0}^{\ell}\frac{(\ell+2-j)^{3}}{2^{\ell+2-j}}\leq
2^{\ell+2}\cdot\sum_{j=0}^{\infty}\frac{j^{3}}{2^{j}}=2^{\ell+2}\cdot
O(1)=O(n).$

∎

######  Remark 4.4.

The purpose of using $\lceil n/2^{j}\rceil\cdot(\ell+2-j)^{3}$ samples instead
of simply e.g., $\Theta(\lceil n/2^{j}\rceil\cdot\ell)$ (which would guarantee
high probability correctness) in the $j$-th phase is to save an $O(\log n)$
factor in the final expected time bound.

######  Lemma 4.5.

There is a Las Vegas algorithm solving a monotone 2VPI system (or producing a
minimal certificate of infeasibility) in $O(mn^{2}\log{m})$ expected time and
linear space. With high probability, the algorithm finishes in
$O(mn^{2}\cdot\log{m}\cdot\log{n})$ time.

###### Proof.

The lemmas 4.2 and 4.3 combined show that $\ell+1$ phases produce a correct
solution or certify infeasibility with probability at least $1/3$ in
$O(mn^{2}\log{m})$ time.

We now discuss how to verify whether the algorithm made a mistake and we need
to rerun it. Consider some run of the algorithm. If the run failed with a
certificate, then we can stop since the system is infeasible for sure.
Otherwise, the run attempted to compute a pointwise maximal solution $x$. If
$x$ does not satisfy (1), which can be tested in $O(m)$ time, then the run
failed to produce a certificate, so we restart. Otherwise, $x$ certifies that
the system is feasible, so we only need to verify whether $x$ is indeed
pointwise maximal. Clearly, if for some $u$ we have $x_{u}<\min_{uv=e\in
E}\\{c(e)+\gamma(e)\cdot x_{v}\\}$, then one can increase $x_{u}$ slightly
without violating the inequalities and obtain a better solution. So the run
indeed made a mistake. Otherwise, $x$ is a vertex of the feasible polytope. So
if $x$ is not optimal, it is possible to move to an adjacent vertex which
improves the objective function $\sum_{v\in V}x_{v}$. Therefore, for each
$uv=e\in E$ with $x_{u}=c(e)+\gamma(e)\cdot x_{v}$ we need to check whether
for some $\alpha>0$ one can increase $x_{u}$ by $\alpha$ and $x_{v}$ by
$\gamma(e)\alpha$ without violating any of the other inequalities. This can be
easily verified in $O(nm)$ time or even near-linear time.

Clearly, the expected number of times the algorithm is repeated before
producing a correct answer is at most $3$. Within $O(\log{n})$ repeats, the
failure probability gets decreased to inversely polynomial in $n$.

Since we only store the values $x_{v}^{*}$ for $v\in V$, the used space is
linear by Lemma 4.1. ∎

##  5 A trade-off algorithm

The randomized trade-off algorithm solving Problem 3.3 is obtained via a
combination of the simple approach of Section 4 with the following result of
Cohen and Megiddo [CM94].

######  Theorem 5.1.

There exists a Las Vegas randomized algorithm testing feasibility and
computing a pointwise maximal solution to a monotone 2VPI system (1) in
$\widetilde{O}(n^{3}+nm)$ time and using $O(n^{2}+m)$ space. The time bound
holds with high probability.

This combination is made possible by the key technical trick from [CM94] that
we state as the following lemma.

######  Lemma 5.2.

[CM94, Proposition 5.2] Suppose the system (1) is feasible. Let
$\xi_{v}\in\mathbb{R}$ for each $v\in V$. In $\widetilde{O}(nm)$ expected time
and linear space one can decide, for each individual $v\in V$, whether
${x_{v}^{\max}}<\xi_{v}$. The algorithm is Las Vegas randomized and the time
bound holds with high probability.

Note the difference between Lemma 5.2 and Lemma 1.4. The latter can detect
whether for _some_ $v$ we have ${x_{v}^{\max}}<\xi_{v}$. Lemma 5.2 can decide
this for _all_ $v\in V$ at once within roughly the same time. However, this
comes at a cost of using randomization that seems difficult to eliminate.
Since the algorithm in [CM94] actually required $O(n^{2})$ space, we will next
sketch this algorithm and explain how the space can be reduced to linear by
using the following generalization of Lemma 1.4.

######  Lemma 5.3.

Suppose the system (1) is feasible. Let
$\xi_{v}\in\mathbb{R}\cup\\{-\infty\\}$ for each $v\in V$.

In $O(nm)$ time and linear space one can decide whether
${x_{v}^{\max}}<\xi_{v}$ holds for _some_ $v\in V$. Moreover, the algorithm
has the following properties.

  * •

If the answer is affirmative, then for some $v$ with ${x_{v}^{\max}}<\xi_{v}$,
a certificate $(P,C)\in\mathcal{P}_{v,w}^{n}\times\mathcal{C}_{w,w}^{n}$ such
that $\gamma(C)<1$ and $c(P)+\gamma(P)\cdot\phi(C)<\xi_{v}$ is returned.
Moreover, in such a case, if $|V(P\cup C)|=\ell$, then the algorithm
terminates in $O(m\ell)$ time.111111We stress that it _does not_ necessarily
hold that if some certificate $(P^{\prime},C^{\prime})$ with
$|V(P^{\prime}\cup C^{\prime})|=\ell$ exists, then the algorithm terminates in
$O(m\ell)$ time. In such a case, the algorithm may still take e.g.,
$\Theta(nm)$ time, but then the returned certificate $(P,C)$ satisfies
$|V(P\cup C)|=\Theta(n)$.

  * •

If ${x_{v}^{\max}}<\xi_{v}$ holds for precisely one $v\in V$, then the
algorithm produces the same certificate regardless of the exact values of
$\xi_{w}\leq{x_{w}^{\max}}$ for all other $w\in V\setminus\\{v\\}$.

Lemma 5.3 can be obtained by adapting and analyzing more carefully the
negative-cost generalized augmenting path detection algorithm of Restrepo and
Williamson [RW09, Section 4]. The proof of Lemma 5.3 can be found in Section
9. Cohen and Megiddo [CM94, Algorithm 2.18] provide a location procedure
achieving almost the same guarantees as in Lemma 5.3, except that their
procedure requires $O(n^{2})$ space.

###### Sketch of the algorithm behind Lemma 5.2.

Let us fix for each $v\in V$ with ${x_{v}^{\max}}<\xi_{v}$ a certificate
$(P_{v},C_{v})$ that Lemma 5.3 produces if run with a vector $\xi^{\prime}$
such that $\xi^{\prime}_{v}=\xi_{v}$ and ${x_{w}^{\max}}\geq\xi^{\prime}_{w}$
for all $w\neq v$. By Lemma 5.3, this certificate is defined uniquely and
regardless of the values $\xi^{\prime}_{w}$ for $w\neq v$.

Given $\xi$, let us call a vertex $v$ _big_ if ${x_{v}^{\max}}<\xi_{v}$. Let
us call a big vertex $\ell$-big if $|V(P_{v}\cup C_{v})|=\Theta(\ell)$.

Roughly speaking, the algorithm in [CM94] does the following. Let $I\subseteq
V$ be the (unknown) set of big vertices that have not yet been determined, and
let $D$ be the set of big vertices that we have detected. Using Lemma 5.3 one
can check if $O(mn)$ time whether $I=\emptyset$ and we should stop. More
generally, using random sampling and Lemma 5.3, in $\widetilde{O}(mn)$ time
one can compute an estimate $g$ approximating $|I|$ up to a constant factor.

If $I\neq\emptyset$, then based on $g$ one can sample
$O(\operatorname{polylog}{n})$ sets $S_{1},\ldots,S_{k}\subseteq V\setminus D$
such that with high probability, at least $\Omega(\log{n})$ of the samples
$S_{i}$ contain a unique big vertex $v$, that can be additionally assumed to
be randomly picked from $I$. Consider running the algorithm of Lemma 5.3 with
a vector $\xi^{\prime}$ such that $\xi^{\prime}_{s}=\xi_{s}$ for $s\in S_{i}$
and $\xi^{\prime}_{s}=-\infty$ for $s\in V\setminus S_{i}$ as an input. If $v$
is $\ell$-big, then the run will terminate in $O(m\ell)$ time. Moreover, one
can prove that if $v$ is randomly picked from $I$, then by propagating the
upper bounds following from the certificate $(P_{v},C_{v})$ through walks of
length $\Theta(\ell)$, with constant probability, we can identify an
$\Omega(\ell/n)$-fraction of the remaining $\ell$-big vertices in $I$. This
propagation requires $O(m\ell)$ time and only linear space [CM94, Section
5.3].

Since we do not know which samples $S_{i}$ contain a unique big vertex and how
big the vertices in $I$ are, we run the above (Lemma 5.3 plus the propagation)
for all samples $S_{1},\ldots,S_{k}$ in parallel, and stop if we succeed in
determining $\Omega(\ell/n\cdot g)=\Omega(\ell/n\cdot|I|)$ new big values
within $\widetilde{O}(m\ell)$ time. One can show that such an event occurs
with high probability.

Intuitively, since identifying an $\Omega(\ell/n)$ fraction of the remaining
big values costs $\widetilde{O}(m\ell)$ time, the algorithm finishes in
$\widetilde{O}(mn)$ time. The space usage is linear by Lemma 5.3 and [CM94,
Section 5.3]. ∎

Unfortunately, it is not entirely clear whether one can extend the already
complicated algorithm behind Theorem 5.1 so that it produces a certificate of
infeasibility if the system is infeasible. As a result, our algorithm in this
section does not produce a certificate, but merely computes ${x^{\max}}$
assuming the system is feasible, and eventually possibly declares the system
infeasible by checking whether ${x^{\max}}$ is feasible (recall, however, that
such a guarantee is sufficient e.g., for DMDPs, where feasibility can be taken
for granted). Given the above, we do not require the algorithm presented in
this section to satisfy the additional requirements stated in Remark 3.4, and
in the following, we can assume that the system is feasible.

Let $h$ be an integer to be chosen later. Suppose we stop the phases of the
algorithm of Section 4 after the earliest phase $j$ with $2^{j}\geq h$. Recall
that this guarantees, with constant probability, that the sampled vertices hit
all the cycles $C\in\mathcal{C}^{*}$ with $|C|\leq 2^{j+1}$. So for each
$C\in\mathcal{C}^{*}$ with $|C|\leq 2^{j+1}$, there exists $v\in V(C)$ such
that $\phi(D_{v})\leq x^{*}_{v}\leq\phi_{v,|C|}$ for some
$D_{v}\in\mathcal{C}_{v}^{n}$ satisfying $\gamma(D_{v})<1$. It can be easily
verified that the phases $0,\ldots,j$ use $\widetilde{O}(mnh)$ time and linear
space.

Generally speaking, our strategy is to reduce handling cycles of
$\mathcal{C}^{*}$ of size more than $h$ to computing a pointwise maximal
solution of a smaller but denser instance of the monotone 2VPI system
feasibility that will be passed to the algorithm of [CM94].

Let $\Psi$ denote the set of those cycles $C\in\mathcal{C}^{*}$ such that
$|C|>h$. Let $S$ be a random subset of $V$ of size $\Theta((n/h)\log{n})$.
With high probability (dependent on the constant hidden in the $\Theta$
notation), $S$ contains not only a vertex of every cycle in $\Psi$, but also a
vertex of _every_ subpath of length $h-1$ of any cycle in $\Psi$. Denote by
$S^{*}$ the set of those $s\in S$ that indeed lie on some cycle in $\Psi$.
Observe that we might have $S^{*}\subsetneq S$.

We now construct a new, smaller instance $G^{\prime}=(S,E^{\prime})$ that will
satisfy the following:

  * •

If $G$ is feasible, $G^{\prime}$ is also feasible.

  * •

For each $s\in S$, the pointwise maximum $({x_{s}^{\max}})^{\prime}$ of
$G^{\prime}$ satisfies either $({x_{s}^{\max}})^{\prime}=\infty$ or
$({x_{s}^{\max}})^{\prime}=c(F)+\gamma(F)\cdot\phi(D)$ for some
$F\in\mathcal{P}_{s,w}^{n}$, $D\in\mathcal{C}_{w}^{n}$, $\gamma(D)<1$ (where
$\mathcal{P}_{s,w}^{n}$ and $\mathcal{C}_{w}^{n}$ are sets of subgraphs of
$G$). Moreover, if $s\in S^{*}$, then additionally
$({x_{s}^{\max}})^{\prime}\leq\phi_{s,n}$.

By the above conditions, setting
$x^{*}_{s}:=\min(x^{*}_{s},({x_{s}^{\max}})^{\prime})$ after the initial $j+1$
phases will meet the requirements of Problem 3.3.

For every pair $s,t\in S$, $E^{\prime}$ will contain a _single_ edge $st$ with
$(c^{\prime}(st),\gamma^{\prime}(st))=(c(Q_{st}),\gamma(Q_{st}))$ where $Q$ is
_any_ walk minimizing $c(Q_{st})+\gamma(Q_{st})\cdot{x_{t}^{\max}}$ among
$s\to t$ walks of at most $h$ edges. Note that $G^{\prime}$ has $|S|^{2}$
edges. Using parametric search [Meg83a], such walks can be found without
computing values ${x_{t}^{\max}}$ exactly. Now let us argue that solving the
problem on $G^{\prime}$ is enough for our needs.

######  Lemma 5.4.

For any $s\in S$, either $({x_{s}^{\max}})^{\prime}=\infty$ or
$({x_{s}^{\max}})^{\prime}=c(F)+\gamma(F)\cdot\phi(D)$ for some
$F\in\mathcal{P}_{s,w}^{n}$, $D\in\mathcal{C}_{w}^{n}$, $\gamma(D)<1$.
Moreover, with high probability, for each $s\in S^{*}$ we have
$({x_{s}^{\max}})^{\prime}\leq\phi_{s,n}$.

###### Proof.

The first part follows since each inequality in $G^{\prime}$ corresponds to to
some chain of inequalities in $G$. Hence, $G^{\prime}$ is feasible and the
existence of $(F,D)$ if $({x_{s}^{\max}})^{\prime}\neq\infty$ follows by
Theorem 2.1.

We will actually prove $({x_{s}^{\max}})^{\prime}={x_{s}^{\max}}$ for $s\in
S^{*}$. This will imply $({x_{s}^{\max}})^{\prime}\leq\phi_{s,n}$ by Theorem
2.1.

Recall that $s\in S^{*}$ lies on some cycle in $\Psi$. Let
$s=s_{1},s_{2},\ldots,s_{q}$ be all the vertices of $S^{*}\cap V(C_{w})$ in
the order they appear on $C_{w}$ starting at $s$. Put $s_{q+1}:=s_{1}$. By
Theorem 2.1, for all $s_{i}$ we have ${x_{s_{i}}^{\max}}=\phi_{s_{i}}(C_{w})$.
Observe that with high probability, for any $s_{i}$, $i=1,\ldots,q$, $s_{i}$
and $s_{i+1}$ are at most $h$ edges apart, as otherwise there would exist a
subpath of $C_{w}$ consisting of $h-1$ edges that is not hit by $S$. Let
$Q_{i}$ be the $s_{i}\to s_{i+1}$ subpath of $C_{w}$; we have $|Q_{i}|\leq h$.
Note that by (2),
${x_{s_{i}}^{\max}}=\phi_{s_{i}}(C_{w})=c(Q_{i})+\gamma(Q_{i})\cdot\phi_{s_{i+1}}(C_{w})=c(Q_{i})+\gamma(Q_{i})\cdot{x_{s_{i+1}}^{\max}}$
holds for any $i$ and moreover, for any $s_{i}\to s_{i+1}$ walk
$Q_{i}^{\prime}\in\bigcup_{k=1}^{\infty}\mathcal{P}_{s_{i},s_{i+1}^{k}}$ in
$G$ we have ${x_{s_{i}}^{\max}}\leq
c(Q_{i}^{\prime})+\gamma(Q_{i}^{\prime})\cdot{x_{s_{i+1}}^{\max}}$. So $Q_{i}$
is a path minimizing $c(Q)+\gamma(Q)\cdot{x_{s_{i+1}}^{\max}}$ over  _all_
$s_{i}\to s_{i+1}$ walks $Q$ in $G$. By $|Q_{i}|\leq h$ and the definition of
$G^{\prime}$, for each edge $e_{i}=s_{i}s_{i+1}$ in $G^{\prime}$ we have

$c^{\prime}(e_{i})+\gamma^{\prime}(e_{i})\cdot{x_{s_{i+1}}^{\max}}=c(Q_{i})+\gamma(Q_{i})\cdot{x_{s_{i+1}}^{\max}}$

We now argue that the cycle $s_{1}s_{2}\ldots s_{q}$ in $G^{\prime}$ implies
the same upper bound on $x_{s}\equiv x_{s_{1}}$ that $C$ implies on $x_{s}$ in
$G$. This will imply ${x_{s}^{\max}}\geq({x_{s}^{\max}})^{\prime}$ as needed.

Since ${x_{s_{i}}^{\max}}=c(Q_{i})+\gamma(Q_{i})\cdot{x_{s_{i+1}}^{\max}}$ for
all $i$, we also have
${x_{s_{i}}^{\max}}=c^{\prime}(e_{i})+\gamma^{\prime}(e_{i})\cdot{x_{s_{i+1}}^{\max}}$
for all $i$. So, by chaining these equations we get:

$\displaystyle{x_{s_{1}}^{\max}}$ $\displaystyle=c(Q_{1}\cdots
Q_{q})+\gamma(Q_{1}\cdots Q_{q})\cdot{x_{s_{1}}^{\max}},$
$\displaystyle{x_{s_{1}}^{\max}}$ $\displaystyle=c(e_{1}\cdots
e_{q})+\gamma(e_{1}\cdots e_{q})\cdot{x_{s_{1}}^{\max}}.$

As a result:

$\frac{c(e_{1}\cdots e_{q})}{1-\gamma(e_{1}\cdots
e_{q})}={x_{s_{1}}^{\max}}=\frac{c(Q_{1}\cdots Q_{q})}{1-\gamma(Q_{1}\cdots
Q_{q})},$

so indeed the cycle $e_{1}\ldots e_{q}$ in $G^{\prime}$ implies the same upper
bound ${x_{s}^{\max}}$ on $x_{s}$ as $C$ in $G$. ∎

After constructing $G^{\prime}$, we will invoke the algorithm of Theorem 5.1
on it. Since $G^{\prime}$ has $\widetilde{O}(n/h)$ vertices and
$\widetilde{O}((n/h)^{2})$ edges, this takes $\widetilde{O}((n/h)^{3})$
expected time with high probability and requires $\widetilde{O}(n/h)$ space.
The final step is to show how to compute $G^{\prime}$.

######  Lemma 5.5.

Given $S$, the instance $G^{\prime}$ can be computed in $\widetilde{O}(mnh)$
time and $O(n^{2}\log{n}/h)$ space.

###### Proof.

Let us first start with a simpler algorithm computing the edges $st\in
E^{\prime}$ for a _single vertex_ $t\in S$ in $\widetilde{O}(mnh)$ time and
linear space. We apply parametric search analogously as we do in the proof of
Lemma 4.1.121212For a more thorough description of an application of
parametric search, see the proof of Lemma 4.1. However, this application is
slightly simpler: here we only care about the tightest bounds imposed by
walks, and not tightest absolute bounds imposed by closed walks, so in
particular we do not have to optimize the values $\gamma(\cdot)$ of the
computed walks. For each bound on walk length $j=0,\ldots,h$, and $v\in V$, we
maintain a walk $P_{j,v}$ (actually, only the values $c(P_{j,v})$ and
$\gamma(P_{j,v})$), such that $P_{j,v}$ minimizes
$c(P)+\gamma(P)\cdot{x_{t}^{\max}}$ over all walks
$P\in\mathcal{P}_{v,t}^{j}$.

To enable computing the walk $P_{j,v}$ based on $\\{P_{j-1,w},w\in V\\}$
without knowing ${x_{t}^{\max}}$, we maintain an interval $(a,b)$ such that
${x_{t}^{\max}}\in(a,b)$. In the first step, we compute the lower envelope of
the set $L_{v}$ of lines $y=(c(e)+\gamma(e)\cdot
c(P_{j-1,w}))+\gamma(e)\gamma(P_{j-1,w})\cdot x$, where $vw=e\in E$, and
record the breakpoints as $X_{v}$. Computing all $X_{v}$ takes $O(m\log{m})$
time in total. We then merge the sets $X_{v}$ into a single sorted sequence
$X$ in $O(m\log{m})$ time. Next, binary search is performed with the aim of
locating two consecutive elements $x_{i},x_{i+1}\in(X\cap(a,b))\cup\\{a,b\\}$
such that ${x_{t}^{\max}}\in(x_{i},x_{i+1})$. Each decision made by binary
search is guided using Lemma 5.3. So finding $x_{i},x_{i+1}$ takes
$O(nm\log{m})$ time. Note that for each $v$ there exists a line in $L_{v}$
that attains $\min\\{f(x):f\in L_{v}\\}$ for all $x\in(x_{i},x_{i+1})$. That
line can be identified easily in $O(\deg_{G}(v))$ time and the corresponding
walk is chosen to constitute $P_{j,v}$. So picking the walks $P_{j,v}$ takes
$O(m)$ time.

Finally, for each $s\in V$ set $c^{\prime}(st)=c(P_{h,s})$ and
$\gamma^{\prime}(st)=\gamma(P_{h,s})$. Note that this satisfies the definition
of $G^{\prime}$.

Since handling a single walk length bound $j$ takes $O(mn\log{m})$ time,
constructing the incoming edges of $t$ in $G^{\prime}$ takes $O(mnh\log{m})$
time. Clearly, we use $O(m)$ space: when proceeding to the next $j$ we require
two numbers per walk $P_{j-1,w}$ for each $w\in V$ be stored. Also, $O(m)$
space is needed to construct the merged sequence $X$ of breakpoints.

To obtain a more efficient solution, albeit at the cost of using
randomization, we make use of Lemma 5.2. We run the above algorithm in
parallel for all $t\in V$. For each $j$, we synchronize the $O(\log{m})$
decisions made by binary search so that the $i$-th decision is made for all
targets $t\in S$ at the same time. Since each decision is of the form
${x_{t}^{\max}}<\xi_{t}$, all of them can be made at once in
$\widetilde{O}(nm)$ expected time using Lemma 5.2. Hence, the running time is
$O(|S|mh\log{m})+\widetilde{O}(nmh)=\widetilde{O}(nmh)$.

Unfortunately, simply running the simple-minded algorithm in parallel leads to
$O(|S|m)=\widetilde{O}(mn/h)$ space usage. To obtain an improved
$\widetilde{O}(n^{2}/h)$ space bound we need to avoid storing the envelopes
and the breakpoint sequences $X$ while proceeding in parallel. The solution is
to instead maintain for each $t$ only a single interval $(a_{t},b_{t})$ such
that ${x_{t}^{\max}}\in(a_{t},b_{t})$. Before the synchronized decision made
by the algorithm of Lemma 5.2, for each $t$ we recompute the envelopes and the
sequence $X$ from scratch, and find the middle element $\xi_{t}$ of
$X\cap(a_{t},b_{t})$. Afterwards, we discard $X$ and the envelopes and only
store $\xi_{t}$. In other words, the space used by the envelopes and
breakpoints is shared between different $t\in S$. Since for a single $j$
binary search makes $O(\log{m})$ steps, this adjustment increases the
$O(|S|mh\log{m})$ term in the running time to
$O(|S|mh\log^{2}{m})=\widetilde{O}(nm)$.

It is however not clear how to eliminate the space cost incurred by
maintaining the walks $P_{j,w}$ for all targets $t\in S$ at once. As a result,
the space usage is $\widetilde{O}(|S|\cdot n)=\widetilde{O}(n^{2}/h)$. ∎

See 1.1

###### Proof.

Recall that running the phases $0,\ldots,j$ of the algorithm of Section 4
until $2^{j}\geq h$ takes $\widetilde{O}(nmh)$ time and linear space.
Constructing the dense graph $G^{\prime}$ takes $\widetilde{O}(nmh)$ time and
$\widetilde{O}(n^{2}/h+m)$ space by Lemma 5.5. Finally, solving the instance
$G^{\prime}$ using Theorem 5.1 takes
$\widetilde{O}(|S|^{3})=\widetilde{O}((n/h)^{3})$ time and
$\widetilde{O}((n/h)^{2})$ space. As we have argued, these steps are enough to
solve Problem 3.3. By Lemma 3.2, additional computation in $O(nm)$ time and
linear space can compute a pointwise maximal solution to the input monotone
2VPI system with high probability.

Recall from the proof of Lemma 4.5 that the solution can be verified in
$O(nm)$ time so that we can make the algorithm Las Vegas by running it until
it computes the correct answer. With high probability $O(\log{n})$ runs are
enough. ∎

See 1.2

###### Proof.

For the former item, pick $h=\max(1,n^{1/2}/m^{1/4})$. For the latter, let the
$\widetilde{O}(n^{2}/h)$ space bound in Theorem 1.1 be actually
$O(n^{2}/h\cdot\log^{c}{n})$. If $m=O(n\log^{c}{n})$, just use the simple
algorithm of Section 4. Otherwise, pick $h=\max(1,(n^{2}\log^{c}{n})/m)$. Then
$h=\Omega(1)$ and $h=O(n)$. ∎

######  Remark 5.6.

If the algorithm of Theorem 5.1 could produce a certificate of infeasibility
(which is likely, after a suitable extension), and the algorithm of Lemma 5.2
could locate values wrt. $x^{\leq}$ without assuming feasibility, then the
trade-off algorithm could also produce a certificate of infeasibility.

In other words, the ability of the trade-off algorithm to certify
infeasibility depends solely on whether the results from [CM94] can be
extended to certify infeasibility.

##  6 Discounted All-Pairs Shortest Paths

Let $\gamma\in(0,1)$ be a fixed discount factor. Let $G=(V,E)$ be a weighted
directed graph with edge costs given by $c:E\to\mathbb{R}$. For a walk
$P\subseteq G$, its cost $c(P)$ is defined as it was before but with
$\gamma(e)\equiv\gamma$ for all $e\in E$. So, if $P=e_{1}\ldots e_{k}$, then
$c(P)=\sum_{i=1}^{k}c(e_{i})\cdot\gamma^{i-1}$. Since $\gamma(e)=\gamma$ for
all $e$, we can assume that $G$ is simple (and thus $m=O(n^{2})$) and thus
writing $c(uv)$ is unambiguous.

A _discounted shortest path_ from $s$ to $t$ is a finite $s\to t$ walk $P$
minimizing $c(P)$. Let $\delta^{k}_{G}(s,t)$ be the minimum cost of a $s\to t$
walk with _exactly_ $k$ edges. The _discounted distance_ $\delta_{G}(s,t)$ is
defined as $\inf_{k\geq 0}\delta^{k}_{G}(s,t)$. Madani et al. [MTZ10] showed
that $\delta_{G}(s,t)$ is not necessarily attained by a finite path even if
all edge costs are positive. So, in particular, a discounted shortest path
needs not be simple. However, they showed [MTZ10, Lemma 5.8] the following
reduction.

######  Lemma 6.1.

[MTZ10] In $O(nm)$ time, the discounted APSP problem on $G$ can be reduced to
a discounted APSP problem on a graph $G^{\prime}$ with $|V(G^{\prime})|=O(n)$
and $|E(G^{\prime})|=O(n+m)$ such that:

  1. (1)

each $v\in V(G)$ is assigned two corresponding vertices
$v^{\prime},v^{\prime\prime}$ in $V(G^{\prime})$,

  2. (2)

for all $u,v\in V(G)$ we have
$\delta_{G}(u,v)=\delta_{G^{\prime}}(u^{\prime},v^{\prime\prime})$,

  3. (3)

for all $s,t\in V(G^{\prime})$ there exists a finite simple path $P=s\to t$ in
$G^{\prime}$ such that $c(P)=\delta_{G^{\prime}}(s,t)$,

  4. (4)

if $k$ is minimum such that
$\delta_{G^{\prime}}^{k}(s,t)=\delta_{G^{\prime}}(s,t)$, then for _every_ walk
$Q=s\to t$ in $G^{\prime}$ such that $c(Q)=\delta_{G^{\prime}}(s,t)$ and
$|Q|=k$, $Q$ is a simple path.

###### Proof.

The properties (1)-(3) are proved in [MTZ10, Lemma 5.8]. We now argue that
property (4) holds as well. Suppose $Q$ is not a simple path, then, it can be
expressed as $Q_{1}CQ_{2}$, where $C$ is a non-empty closed walk. We have
$c(CQ_{2})<c(Q_{2})$, as otherwise we would have $\delta_{G^{\prime}}(s,t)\leq
c(Q_{1}Q_{2})\leq c(Q_{1}CQ_{2})=\delta_{G^{\prime}}(s,t)$ and $Q_{1}Q_{2}$
would have less than $k$ edges, which is impossible. Consequently, we obtain:

$\delta_{G}^{\prime}(s,t)\leq c(Q_{1}CCQ_{2})=c(Q_{1}C)+\gamma(Q_{1}C)\cdot
c(CQ_{2})<c(Q_{1}C)+\gamma(Q_{1}C)\cdot c(Q_{2})=c(Q_{1}CQ_{2}),$

that is, $\delta_{G}^{\prime}(s,t)<\delta_{G}^{\prime}(s,t)$, a contradiction.
∎

In the following, we assume that the above reduction has been applied and we
reset $G:=G^{\prime}$. As a result, we only need to compute
$\min_{k=0}^{n}\\{\delta_{G}^{k}(s,t)\\}$ for all $s,t\in V$. For simplicity,
in the following we put
$\delta_{G}(s,t):=\min_{k=0}^{n}\\{\delta_{G}^{k}(s,t)\\}$. Moreover, for each
pair $s,t\in V$, let $\ell_{s,t}$ denote the minimal number of edges on an
$s\to t$ walk with the minimum cost $\delta_{G}(s,t)$. By Lemma 6.1, all
discounted shortest $s\to t$ paths with $\ell_{s,t}$ edges are simple.

We concentrate on computing the values $\delta_{G}(s,t)$ and not the
respective paths themselves. However, the given algorithms can be easily
extended to produce the representation of all discounted shortest paths within
the same asymptotic time bound. Note that due to the following simple facts
(observed in [MTZ10]), the discounted shortest paths to a single fixed target
vertex $t\in V$ (from all possible sources) can be represented using a tree.

######  Observation 6.2.

Let $P=s\to t$ be a discounted shortest path. Then, every suffix of $P$ is a
discounted shortest path. More formally, if $P=P_{1}P_{2}$, where $P_{2}$ is a
$w\to t$ path, then $P_{2}$ is a discounted shortest path, i.e.,
$c(P_{2})=\delta_{G}(w,t)$.

###### Proof.

We have $c(P)=c(P_{1})+\gamma^{|P_{1}|}\cdot c(P_{2})$. If there existed
another path $Q=w\to t$ with $c(Q)<c(P_{2})$, $P_{1}Q$ would have smaller cost
than $P_{1}P_{2}$ since $\gamma>0$. Then $P$ would not be shortest. ∎

######  Observation 6.3.

Let $P=s\to t$ be a discounted shortest path. Let $1\leq k\leq|P|$. Then the
$k$-prefix of $P$ forms a path with the smallest cost among paths with exactly
$k$ edges and same respective endpoints. More formally, if $P=P_{1}P_{2}$,
where $P_{1}$ is a $s\to w$ path and $|P_{1}|=k$, then
$c(P_{1})=\min\\{c(P):P\in\mathcal{P}_{s,w}^{k},|P|=k\\}$.

###### Proof.

We have $c(P)=c(P_{1})+\gamma^{k}\cdot c(P_{2})$. If there existed another
path $Q=s\to w$ with $|Q|=k$, then $\gamma(P_{1})=\gamma(Q)$ and
$c(Q)<c(P_{1})$, so $QP_{2}$ would have a smaller cost than $P_{1}P_{2}$. ∎

In the following lemmas, we introduce the building blocks of our algorithm for
discounted APSP.

######  Lemma 6.4.

Let $t\in V$ and $k\geq 1$. One can compute $\delta^{\leq
k}_{G}(s,t)=\min_{j=0}^{k}\\{\delta^{j}_{G}(s,t)\\}$ for all $s\in V$ and
$j=0,\ldots,k$ in $O(mk)$ time.

###### Proof.

For $j=0$ we have $\delta^{\leq 0}_{G}(t,t)=0$ and $\delta^{\leq
0}_{G}(s,t)=\infty$ for $s\neq t$. Note that by Observation 6.2, for any $j>0$
and $s\in V$ we have

$\delta^{\leq j}_{G}(s,t)=\min\left(\delta^{\leq j-1}_{G}(s,t),\min_{su\in
E}\\{c(su)+\gamma\cdot\delta_{G}^{\leq j-1}(u,t)\\}\right).$

As a result, all the values $\delta^{\leq k}_{G}(s,t)$ of interest can be
computed using $k$ Bellman-Ford-style steps that take $O(m)$ time each. ∎

######  Lemma 6.5.

Let $s\in V$ and $k\geq 1$. One can compute $\delta^{j}_{G}(s,t)$ for all
$j=0,\ldots,k$ and $t\in V$ in $O(mk)$ time.

###### Proof.

We have $\delta^{0}_{G}(t,t)=0$ and $\delta^{0}_{G}(s,t)=\infty$ for $s\neq
t$. By Observation 6.3, for any $j>0$ and $t\in V$ we have

$\delta^{j}_{G}(s,t)=\min_{ut\in E}\\{\delta^{j-1}_{G}(s,u)+\gamma^{j-1}\cdot
c(ut)\\}.$

As a result, all the required $\delta^{j}_{G}(s,t)$ can be computed in $O(mk)$
time. ∎

######  Lemma 6.6.

Let $s\in V$ and $k\geq 1$. Then, in $O(mk)$ time one can construct a data
structure $D(s)$ answering the following queries.

For a given vector $(v,x_{1},\ldots,x_{l})\in V\times\mathbb{R}^{l}$ such that
$x_{1}\leq\ldots\leq x_{l}$, compute the values:

$D(s,v,x_{l})=\min_{i=0}^{k}\\{\delta_{G}^{i}(s,v)+\gamma^{i}\cdot x_{l}\\},$

for $j=1,\ldots,l$. The query is answered in $O(k+l)$ time.

###### Proof.

The first step is to compute $\delta_{G}^{j}(s,t)$ for all $j=0,\ldots,k$ and
$t\in V$ using Lemma 6.5. For a given $v$, consider the lines
$y=\delta^{i}_{G}(s,v)+\gamma^{i}\cdot x$ for $i=0,\ldots,k$. The lower
envelope $L_{v}$ of these lines can be computed in $O(n)$ time since the
slopes of these lines are sorted in decreasing order. Note that $L_{v}$ can be
interpreted as a plot of the function $D(s,v,x)$. The data structure consists
of the envelopes $L_{v}$ for all $v\in V$.

When a query $(v,x_{1},\ldots,x_{l})$ comes, we match the coordinates
$x_{1},\ldots,x_{l}$ to the segments of $L_{v}$ corresponding to the lines
minimizing each subsequent $x_{i}$. Since the coordinates $x_{i}$ come in
increasing order and $|L_{v}|=O(k)$, answering a query takes $O(k+l)$ time. ∎

######  Lemma 6.7.

Let $S\subseteq V$ and $k\geq 1$. Then, in $O(|S|mk)$ time one can find a set
$X\subseteq V$ of size $O(n/k\log{n})$ such that for all $(s,t)\in S\times V$
satisfying $\ell_{s,t}\geq k$, there exists a path $Q_{s,t}=s\to t$ with
$c(Q_{s,t})=\delta_{G}(s,t)$ such that one of the first $k+1$ vertices of
$Q_{s,t}$ is contained in $X$. We call $X$ a _$k$ -hitting set_ of discounted
shortest paths from $S$ to $V$.

###### Proof.

We first compute $\delta_{G}^{k}(s,t)$ for all $(s,t)\in S\times V$ by
applying Lemma 6.5 for each $s\in S$. This takes $O(|S|mk)$ time. Note that
the algorithm in Lemma 6.5 can be easily extended to also return for each $t$
some (not necessarily simple) walk $P_{s,t}$ with $|P_{s,t}|=k$ and
$c(P_{s,t})=\delta^{k}_{G}(s,t)$, if one exists. Now, let $\mathcal{Q}$ denote
those computed $P_{s,t}$ _that constitute simple paths_ , i.e., satisfy
$V(P_{s,t})=k+1$.

We now prove that a set $X$ hitting all paths in $\mathcal{Q}$ (i.e., such
that $V(P)\cap X\neq\emptyset$ for all $P\in\mathcal{Q}$) is a $k$-hitting set
of discounted shortest paths from $S$ to $V$. Indeed, consider some pair
$s,t\in V$ and some path $R$ with $c(R)=\delta_{G}(s,t)$ and
$|R|=\ell_{s,t}\geq k$. Let $R=R_{1}R_{2}$, where $R_{1}=s\to w$ and
$|R_{1}|=k$. Note that $P_{s,w}$ exists since $R_{1}$ does. By Observation
6.3, we have $c(R_{1})=\delta^{k}_{G}(s,w)=c(P_{s,w})$. So
$c(P_{s,w}R_{2})=\delta_{G}(s,t)$ and $P_{s,w}R_{2}$ is a discounted shortest
$s\to t$ path. If $P_{s,w}$ was not simple, then $P_{s,w}R_{2}$ would be a
non-simple shortest $s\to t$ path with the minimum possible number of edges
$\ell_{s,t}$, which would contradict the property (4) guaranteed by Lemma 6.1.
So $P_{s,w}$ has to be simple and therefore $P_{s,w}\in\mathcal{Q}$. As a
result, $V(P_{s,t})\cap X\neq\emptyset$. Note that the discounted shortest
$s\to t$ path $P_{s,w}R_{2}$ contains a vertex of $X$ among its first $k+1$
vertices, as desired.

Since every element of $\mathcal{Q}$ has precisely $k+1$ _distinct_ vertices
of $V$, one can deterministically compute a set $X$ of size $O((n/k)\log{n})$
that hits all elements in $\mathcal{Q}$ using a folklore greedy algorithm that
repeatedly includes in $X$ an element that hits the most (which is always at
least an $\Omega(k/n)$-fraction) of the remaining elements of $\mathcal{Q}$.
The greedy algorithm can be easily implemented in $O(|\mathcal{Q}|k)=O(|S|nk)$
time. For analysis, see e.g. [Kin99, Lemma 5.2]. ∎

Let us denote denote by $T(r)$ the time needed to compute discounted shortest
paths from $r$ sources ($1\leq r\leq n$) in $G$, as a function of $n$ and $m$.
Of course, our ultimate goal is to compute discounted shortest paths from all
$n$ sources. We will show two different reductions to a problem with a smaller
number of sources.

######  Lemma 6.8.

There exists a constant $c\geq 1$ such that for any $r,h\in[1,n]$ we have:

  1. (1)

$T(r)\leq T(\min(cn/h\cdot\log{n},n))+O(nmh)$,

  2. (2)

$T(r)\leq
T(\min(cn/h\cdot\log{n},n))+O(rmh+(n^{2}/h)\log{n}\cdot(r+\log{n}))$.

###### Proof.

Let $S$ denote the set of $r$ source vertices. Clearly, we can compute
discounted shortest paths that contain less than $h$ edges in $O(rmh)$ by
applying Lemma 6.5 to every source vertex $s\in S$. Hence, we can concentrate
computing discounted shortest paths for such pairs $(s,t)$ that
$\ell_{s,t}\geq h$.

Let $X$ be a $h$-hitting set of discounted shortest paths from $S$ to $V$
computed using Lemma 6.7. The set $X$ has size $O(\min((n/h)\log{n},n))$ and
can be computed in $O(rmh)$ time. Let us compute the values $\delta_{G}(s,t)$
for all $(s,t)\in X\times V$ recursively in $T(|X|)=T(O(\min(n/h\log{n},n)))$
time.

Now consider the item (1). Let us define $d_{j}(s,t)$ for $(s,t)\in V\times V$
and $j=0,\ldots,h$ as follows:

$d_{j}(s,t)=\begin{cases}\delta_{G}(s,t)&\text{ if }j=0\text{ and }s\in X,\\\
\infty&\text{ if }j=0\text{ and }s\notin X,\\\
\min\left(d_{j-1}(s,t),\min_{su\in E}\\{c(su)+\gamma\cdot
d_{j-1}(u,t)\\}\right)&\text{ if }j>0.\end{cases}$

Similarly as in Lemma 6.4, the values $d_{j}(s,t)$ for a single $t\in V$ can
be computed using $h$ Bellman-Ford-style phases in $O(mh)$ time. Through all
$t$, computing them takes $O(nmh)$ time.

We now show that if $\ell_{s,t}\geq h$, then $d_{h}(s,t)=\delta_{G}(s,t)$.
Consequently, we can return $\delta_{G}(s,t)=\min(d_{h}(s,t),\delta_{G}^{\leq
h}(s,t))$ for all $s,t\in S\times V$.

Indeed, let $QR=s\to t$ be a discounted shortest path such that $|Q|=k$ and
there exists $x\in V(Q)\cap X$. The existence of such a path $QR$ is
guaranteed by Lemma 6.7. Let $Q=Q_{1}Q_{2}$, where $Q_{1}=s\to x$. By
Observation 6.2, $Q_{2}R$ is a discounted shortest $x\to t$ path, so
$c(Q_{2}R)=\delta_{G}(x,t)=d_{0}(x,t)$. If $Q_{1}=e_{q}e_{q-1}\ldots e_{1}$,
where $e_{i}=v_{i}v_{i-1}$ then using Observation 6.2 it can be easily proved
inductively that for $j=0,\ldots,q$ we have $d_{j}(v_{j},t)=c(e_{j}\ldots
e_{1}Q_{2}R)$. So $d_{q}(s,t)=c(QR)=\delta_{G}(s,t)$. Since $q\leq h$,
$d_{h}(s,t)\leq d_{q}(s,t)$, and we conclude that $d_{h}(s,t)=\delta_{G}(s,t)$
holds as well. This concludes the proof of item (1).

Let us move to item (2). Compute the data structure $D(s)$ of Lemma 6.6 with
$k=h$ for each $s\in S$. For every $x\in X$, sort the previously computed
values $\delta_{G}(x,t)$, where $t\in V$. This takes
$O(|X|n\log{n})=O((n^{2}/h)\log^{2}{n})$ time. For each $s\in S$, $x\in X$,
$t\in V$ compute the values $D(s,x,\delta_{G}(x,t))$ as defined in Lemma 6.6.
This takes $O(r\cdot(n/h)\log{n}\cdot(h+n))=O(r(n^{2}/h)\log{n})$ time.

We now prove that if $\ell_{s,t}\geq h$ then $\delta_{G}(s,t)=\min_{x\in
X}\\{D(s,x,\delta_{G}(x,t))\\}$. Clearly, we have
$\delta_{G}(s,t)\leq\min_{x\in X}\\{D(s,x,\delta_{G}(x,t))\\}$ since each
$D(s,x,\delta_{G}(x,t))$ constitutes the discounted cost of some $s\to t$ path
in $G$. Similarly as before, there exists such an $s\to t$ path $Q_{1}Q_{2}R$
that $c(Q_{1}Q_{2}R)=\delta_{G}(s,t)$, $Q_{1}=s\to y$, $|Q_{1}|\leq h$ and
$y\in V(Q_{1})\cap X$. Note that $c(Q_{2}R)=\delta_{G}(y,t)$ by Observation
6.2. By Observation 6.3, $c(Q_{1})=\delta_{G}^{|Q_{1}|}(s,y)$, and thus

$D(s,y,\delta_{G}(s,t))\leq\delta_{G}^{|Q_{1}|}(s,y)+\gamma^{|Q_{1}|}\cdot\delta_{G}(y,t)=c(Q_{1})+\gamma^{|Q_{1}|}\cdot
c(Q_{2}R)=c(Q_{1}Q_{2}R)=\delta_{G}(s,t).$

We conclude $\min_{x\in X}\\{D(s,x,\delta_{G}(x,t))\\}\leq\delta_{G}(s,t)$ as
desired. ∎

Our discounted APSP algorithm is as follows. Denote by $\langle S,V\rangle$
the problem of computing $\delta_{G}(s,t)$ for all $(s,t)\in S\times V$. So
our goal is to solve the problem $\langle V,V\rangle$.

Let $d\geq 2$ be to be fixed later. In the first step, we apply reduction (1)
of Lemma 6.8 with $h=d$. In $O(nmd)$ time this reduces the problem $\langle
V,V\rangle$ to $\langle S_{1},V\rangle$ for some set $S_{1}\subsetneq V$ with
$|S_{1}|=O(\min(n,(n/d)\log{n}))$.

Next, for $i=1,\ldots,g=O(\log{n})$ we do the following. If
$|S_{i}|=O(\log{n})$, then we solve the problem $\langle S_{i},V\rangle$ in a
simple-minded way by applying Lemma 6.5 with $k=n$ for all $s\in S_{i}$ in
$O(|S_{i}|nm)=O(nm\log{n})$ time. We set $g=i$ and terminate.

Otherwise, we have $|S_{i}|=O(\min(n,(n/d^{i})\log{n}))$. We reduce the
problem to $\langle S_{i+1},V\rangle$ using reduction (2) of Lemma 6.8 with
$h=d^{i+1}$, where $|S_{i+1}|=O(\min(n,(n/d^{i+1})\log{n}))$. This takes

$O(|S_{i}|md^{i+1}+(n^{2}/d^{i+1})\log{n}\cdot(|S_{i}|+\log{n}))=O\left(nmd\log{n}+(n^{3}/d^{2i+1})\log^{2}{n}\right)$

time. Note that $g=O(\log_{d}n)=O(\log{n})$ since $d\geq 2$. Summing through
all $i$ we have:

$\sum_{i=1}^{g}O\left(nmd\log{n}+(n^{3}/d^{2i+1})\log^{2}{n}\right)=O((nmd+(n/d)^{3})\log^{2}{n}).$

This dominates the cost of the first reduction step and the final step solving
$\langle S_{g},V\rangle$. By picking $d=\max(2,n^{1/2}/m^{1/4})$, we obtain
the following theorem. See 1.3

##  7 Reconstructing minimizing paths in linear space

In this section, we prove the following lemma. See 3.5

###### Proof.

We prove the lemma by induction on $k$. If $k=1$, then it is enough to check
all $s\to t$ edges. So suppose $k\geq 2$, and let $k^{\prime}=\lceil
k/2\rceil$. First, let us compute the minimal value
$(\beta,\Gamma)=(c(Q)+\gamma(Q)\cdot\alpha,\gamma(Q))$. This can be done using
$k$ propagation steps in $O(mk)$ time and linear space. The next step is to
compute the pairs $l_{v}^{i}$, $r_{v}^{i}$, where $v\in V$ and
$i=0,\ldots,k^{\prime}$, defined as:

$\displaystyle l_{v}^{i}$
$\displaystyle=\max_{P\in\mathcal{P}_{s,v}^{i}}\left\\{\left((\beta-c(P))\cdot\frac{1}{\gamma(P)},\frac{1}{\gamma(P)}\right)\right\\},$
$\displaystyle r_{v}^{i}$
$\displaystyle=\min_{P\in\mathcal{P}_{v,t}^{i}}\left\\{\left(c(P)+\gamma(P)\cdot\alpha,\gamma(P)\right)\right\\},$

where minimization/maximization is performed lexicographically. Clearly, we
have $l_{v}^{0}=([v=s]\cdot\beta,1)$, and $r_{v}^{0}=([v=t]\cdot\alpha,1)$.
Set $l_{v}^{i}=(l_{v,1}^{i},l_{v,2}^{i})$, and
$r_{v}^{i}=(r_{v,1}^{i},r_{v,2}^{i})$. For $i>0$, we have the following
recursive relations:

$\displaystyle l_{v}^{i}$ $\displaystyle=\max\left(l_{v}^{i-1},\max_{uv=e\in
E}\left\\{\left((l_{u,1}^{i-1}-c(e))\cdot\frac{1}{\gamma(e)},\frac{l_{u,2}^{i-1}}{\gamma(e)}\right)\right\\}\right),$
$\displaystyle r_{v}^{i}$ $\displaystyle=\min\left(r_{v}^{i-1},\min_{vw=e\in
E}\left\\{\left(c(e)+\gamma(e)\cdot r_{w,1}^{i-1},\gamma(e)\cdot
r_{w,2}^{i-1}\right)\right\\}\right).$

In particular, the values $\\{l_{v}^{i},v\in V\\}$ depend only on the values
$\\{l_{v}^{i-1},v\in V\\}$ and the edges of $G$, and can be computed in $O(m)$
time based on those. The values $\\{r_{v}^{i},v\in V\\}$ have an analogous
property. Consequently, we can compute the values $l_{v}^{k^{\prime}}$ and
$r_{v}^{k-k^{\prime}}$ for all $v\in V$ in $O(mk)$ time and $O(n)$ space.

Let us express some optimal path $Q$ as $Q_{1}Q_{2}$, where
$Q_{1}\in\mathcal{P}_{s,z}^{k^{\prime}}$ and
$Q_{2}\in\mathcal{P}_{z,t}^{k-k^{\prime}}$. We have

$c(Q_{1})+\gamma(Q_{1})\cdot(c(Q_{2})+\gamma(Q_{2})\cdot\alpha)=c(Q)+\gamma(Q)\cdot\alpha=\beta,$

and hence we obtain:

$c(Q_{2})+\gamma(Q_{2})\cdot\alpha=(\beta-c(Q_{1}))\cdot\frac{1}{\gamma(Q_{1})}.$

Note that in fact we have
$r_{z}^{k-k^{\prime}}=(c(Q_{2})+\gamma(Q_{2})\cdot\alpha,\gamma(Q_{2}))$, as
otherwise we could replace $Q_{2}$ with an $s\to t$ walk optimizing
$r_{z}^{k-k^{\prime}}$ better than $Q_{2}$ and obtain a better path than $Q$.
Similarly,
$l_{z}^{k^{\prime}}=\left((\beta-c(Q_{1}))\cdot\frac{1}{\gamma(Q_{1})},\frac{1}{\gamma(Q_{1})}\right)$,
as otherwise there would exist a walk
$Q_{1}^{\prime}\in\mathcal{P}_{s,z}^{k^{\prime}}$ with

$\left((\beta-c(Q_{1}^{\prime}))\cdot\frac{1}{\gamma(Q_{1}^{\prime})},\frac{1}{\gamma(Q_{1}^{\prime})}\right)=l_{z}^{k^{\prime}}>\left((\beta-c(Q_{1}))\cdot\frac{1}{\gamma(Q_{1})},\frac{1}{\gamma(Q_{1})}\right).$

Then, we would either have

$\beta\leq
c(Q_{1}^{\prime}Q_{2})+\gamma(Q_{1}^{\prime}Q_{2})\cdot\alpha=c(Q_{1}^{\prime})+\gamma(Q_{1}^{\prime})\cdot(\beta-c(Q_{1}))\cdot\frac{1}{\gamma(Q_{1})}<c(Q_{1}^{\prime})+\gamma(Q_{1}^{\prime})\cdot(\beta-c(Q_{1}^{\prime}))\cdot\frac{1}{\gamma(Q_{1}^{\prime})},$

which reduces to $\beta<\beta$, i.e., a contradiction, or we would have
$c(Q_{1}^{\prime}Q_{2})+\gamma(Q_{1}^{\prime}Q_{2})\cdot\alpha=\beta$ and
$\gamma(Q_{1}^{\prime}Q_{2})<\gamma(Q_{1}Q_{2})$, which would contradict the
optimality of $Q=Q_{1}Q_{2}$.

It follows that $l^{k^{\prime}}_{z,1}=r^{k-k^{\prime}}_{z,1}$ and
$\frac{r^{k-k^{\prime}}_{z,2}}{l^{k^{\prime}}_{z,2}}=\Gamma$. We conclude that
in $O(n)$ time we can find some (possibly different than $z$) vertex $x\in V$
such that $l^{k^{\prime}}_{x,1}=r^{k-k^{\prime}}_{x,1}$ and
$\frac{r^{k-k^{\prime}}_{x,2}}{l^{k^{\prime}}_{x,2}}=\Gamma$, which is
guaranteed to exist by the above.

By the induction hypothesis, one can construct some
$Q_{2}^{*}\in\mathcal{P}_{x,t}^{k-k^{\prime}}$ minimizing the
pair$(c(Q_{2}^{*})+\gamma(Q_{2}^{*})\cdot\alpha,\gamma(Q_{2}^{*}))=r_{x}^{k-k^{\prime}}$
in $O(m(k-k^{\prime}))$ time and linear space. Similarly, one can construct
some $Q_{1}^{*}\in\mathcal{P}_{s,x}^{k^{\prime}}$ minimizing the pair
$\left(c(Q_{1}^{*})+\gamma(Q_{1}^{*})\cdot
r_{x,1}^{k-k^{\prime}},\gamma(Q_{1}^{*})\right)$ in $O(mk^{\prime})$ time and
linear space. Finally, we return the path $Q_{1}^{*}Q_{2}^{*}$.

We now prove that $c(Q_{1}^{*})+\gamma(Q_{1}^{*})\cdot
r_{x,1}^{k-k^{\prime}}=\beta$ and
$\gamma(Q_{1}^{*})\cdot\gamma(Q_{2}^{*})=\Gamma$ from which the correctness
will follow. Clearly, $c(Q_{1}^{*})+\gamma(Q_{1}^{*})\cdot
r_{x,1}^{k-k^{\prime}}\geq\beta$. Let $Q_{1}^{\prime}$ be a path corresponding
to $l_{x}^{k^{\prime}}$. We have:

$c(Q_{1}^{*})+\gamma(Q_{1}^{*})\cdot r_{x,1}^{k-k^{\prime}}\leq
c(Q_{1}^{\prime})+\gamma(Q_{1}^{\prime})\cdot
r_{x,1}^{k-k^{\prime}}=c(Q_{1}^{\prime})+\gamma(Q_{1}^{\prime})\cdot
l_{x,1}^{k^{\prime}}=\beta.$

We conclude that indeed $c(Q_{1}^{*})+\gamma(Q_{1}^{*})\cdot
r_{x,1}^{k-k^{\prime}}=\beta$. It follows that
$\gamma(Q_{1}^{*}Q_{2}^{*})\geq\Gamma$. Suppose
$\gamma(Q_{1}^{*}Q_{2}^{*})>\Gamma=\frac{\gamma(Q_{2}^{*})}{l_{x,2}^{k^{\prime}}}=\gamma(Q_{1}^{\prime})\cdot\gamma(Q_{2}^{*})$,
that is, $\gamma(Q_{1}^{*})>\gamma(Q_{1}^{\prime})$. But then we would have

$\left(c(Q_{1}^{*})+\gamma(Q_{1}^{*})\cdot
r_{x,1}^{k-k^{\prime}},\gamma(Q_{1}^{*})\right)>\left(c(Q_{1}^{\prime})+\gamma(Q_{1}^{\prime})\cdot
r_{x,1}^{k-k^{\prime}},\gamma(Q_{1}^{\prime})\right),$

which would contradict the definition of $Q_{1}^{*}$. As a result,
$\gamma(Q_{1}^{*}Q_{2}^{*})=\Gamma$, as desired.

The running time $T(n,m,k)$ of the algorithm can be bounded:

$\displaystyle T(n,m,1)$ $\displaystyle=O(m)$ $\displaystyle T(n,m,k)$
$\displaystyle=T(n,m,\lfloor k/2\rfloor)+T(n,m,\lceil k/2\rceil)+O(mk).$

In a standard inductive way one can easily prove $T(n,m,k)=O(mk\log{k})$.

The additional space used is $O(n+k)$, since we only use $\Theta(n)$ space
when computing the $O(1)$ parameters of recursive calls (of which are $O(k)$
in total). After these parameters are found, the $\Theta(n)$ space used for
computing the values $l_{v}^{i}$, $r_{v}^{i}$ is not needed anymore. ∎

##  8 Computing the $k$-cycle bounds

In this section we consider computing the $k$-cycle bounds $\phi_{v,k}$ as
defined in Section 3.

######  Lemma 8.1.

Let $v\in V$, $k\leq n$, and $\xi\in\mathbb{R}$. There is a linear-space
algorithm running in $O(mk)$ time and declaring exactly one of the following
statements:

  1. (a)

There exists a closed walk $Q\in\mathcal{C}_{v}^{k}$ with $\gamma(Q)<1$ and
$\phi(Q)<\xi$.

  2. (b)

There exists a closed walk $Q\in\mathcal{C}_{v}^{k}$ with $\gamma(Q)>1$ and
$\phi(Q)>\xi$.

  3. (c)

$\max\\{\phi_{v}(C):C\in\mathcal{C}_{v}^{k},\gamma(C)>1\\}\leq\xi<\phi_{v,k}$.

  4. (d)

There exists a closed walk $Q$ with $c_{v}(Q)<0$ and $\gamma(Q)=1$ certifying
the infeasibility of (1).

  5. (e)

$\phi_{v,k}=\xi$.

Additionally, after the algorithm finishes and if (a), (b), (d), or (e) is
returned, one can request to construct a closed walk $Q$ certifying the
respective statement in $O(mk\log{k})$ time and linear space.

Note that returning (a) implies $\phi_{v,k}<\xi$, and (c) implies
$\phi_{v,k}\geq\xi$. In particular, if (1) is feasible, then (a) is returned
iff $\phi_{v,k}<\xi$, whereas $\phi_{v,k}\geq\xi$ iff either (b) or (c) is
returned.

###### Proof.

Propagate the bounds $y_{v}=\xi$, $y_{u}=\infty$ for all $u\neq v$, through
paths of length at most $k$, and also maintain the values $\gamma_{w}$ such
that after the $i$-th propagation we have $y_{w}\neq\infty$ implies that there
exists a walk $P\in\mathcal{P}_{w,v}^{i}$ with
$(c(P)+\gamma(P)\cdot\xi=y_{w},\gamma(P)=\gamma_{w})$ lexicographically
minimal. This clearly takes $O(mk)$ time and requires linear space.

Let $Q$ be any (possibly empty) closed walk such that
$y_{v}=c(Q)+\gamma(Q)\cdot\xi$ and $\gamma_{v}=\gamma(Q)$ after the
propagation finishes.

Since $\mathcal{C}_{v}$ are actually paths $v\to v$, we have $y_{v}\leq
c_{v}(C)+\gamma(C)\cdot\xi$ for all $C\in\mathcal{C}_{v}^{k}$ after the
propagation. As propagation never increases bounds, we have $y_{v}\leq\xi$.

If eventually $y_{v}<\xi$ and $\gamma(Q)<1$ both hold, then
$c_{v}(Q)+\gamma(Q)\cdot\xi<\xi$ and we obtain
$\frac{c_{v}(Q)}{1-\gamma(Q)}=\phi_{v}(Q)<\xi$ so indeed $\phi_{v,k}<\xi$.
Thus, in this case, item (a) with the closed walk $Q$ is returned.

If $y_{v}<\xi$ and $\gamma(Q)>1$ then
$\phi_{v}(Q)=\frac{c_{v}(Q)}{1-\gamma(Q)}>\xi$. We thus return (b) with closed
walk $Q$. Note that if the system is feasible, for any
$C^{\prime}\in\mathcal{C}_{v}$ with $\gamma(C^{\prime})<1$ we need to have
$\phi_{v}(C^{\prime})\geq\phi_{v}(Q)$. So we indeed have $\phi_{v,k}\geq\xi$
if the system is feasible.

If $y_{v}<\xi$ and $\gamma(Q)=1$, then we obtain $c_{v}(Q)<0$. Recall that the
system is infeasible in such a case and we return item (c) with a certificate
of infeasibility $Q$.

Now suppose $y_{v}=\xi$. Then, for all closed walks
$C^{\prime}\in\mathcal{C}_{v}^{k}$ we have
$c(C^{\prime})+\gamma(C^{\prime})\cdot\xi\geq\xi$. In particular, if
$\gamma(C^{\prime})<1$, then this implies
$\frac{c_{v}(C^{\prime})}{1-\gamma(C^{\prime})}\geq\xi$, whereas if
$\gamma(C^{\prime})>1$ then
$\frac{c_{v}(C^{\prime})}{1-\gamma(C^{\prime})}\leq\xi$. If $\gamma(Q)<1$,
then we have $\phi_{v,k}=\phi_{v}(Q)=\xi$. As a result, we can return (e) in
this case. Otherwise, $\gamma(Q)=1$ which proves that $\phi_{v,k}>\xi$ since
we minimized $\gamma(Q)$ in the second place. We can thus return (c).

By Lemma 3.5, the closed walk can be constructed in additional $O(mk\log{k})$
time and linear space if needed. ∎

See 4.1

###### Proof.

First of all, we can check in $O(mk)$ time if $\phi_{v,k}$ is finite by
checking whether a closed walk $C_{\min}\in\mathcal{C}_{v}^{k}$ that minimizes
$\gamma(C_{\min})$ satisfies $\gamma(C_{\min})<1$. Otherwise, we have
$\phi_{v,k}=\infty$. Note that some closed walk $C_{\min}$ can be computed in
$O(mk\log{k})$ time and linear space by applying Lemma 3.5 with $\alpha=1$ and
all edge costs $c(e)$ for $e\in E$ reset to $0$. So in the following assume
that $\phi_{v,k}$ is finite.

Analogously, we find a closed walk $C_{\max}\in\mathcal{C}_{v}^{k}$ maximizing
$\gamma(C_{\max})$ by applying Lemma 3.5 with $\alpha=1$ and $c(e):=0$,
$\gamma(e):=\frac{1}{\gamma(e)}$ for all $e\in E$. If $\gamma(C_{\max})\leq
1$, then there exists no closed walks $C\in\mathcal{C}_{v}^{k}$ with
$\gamma(C)>1$. If $\gamma(C_{\max})>1$ and $\phi(C_{\max})>\phi(C_{\min})$,
the system is infeasible and these two walks constitute a certificate, so we
can terminate. In the following, let us assume that $\gamma(C_{\max})\leq 1$
or $\phi(C_{\max})\leq\phi(C_{\min})$ holds.

Roughly speaking, for each $j=1,\ldots,k$ and $w\in V$ we wish to compute a
walk $P_{j,w}\in\mathcal{P}^{j}_{w,v}$ (actually, only the values $c(P_{j,k})$
and $\gamma(P_{j,k})$) such that $P_{j,k}$ incurs the tightest upper bound on
$x_{w}$ with respect to $\phi_{v,k}$. In other words, $P_{j,w}$ minimizes
$c(P_{j,w})+\gamma(P_{j,w})\cdot\phi_{v,k}$ among all $w\to v$ walks in $G$
with at most $j$ edges.

More specifically, we maintain an interval
$a,b\in\mathbb{R}\cup\\{-\infty,\infty\\}$ (where $a<b$), and possibly
$C_{\min},C_{\max}\in\mathcal{C}^{k}_{v}$ such that, after the walks $P_{j,w}$
are computed, the following invariants are satisfied.

  1. 1.

Each $P_{j,w}$ lexicographically minimizes the pair $\langle
c(P_{j,w})+\gamma(P_{j,w})\cdot z,\gamma(P_{j,w})\rangle$ _for all_
${z\in(a,b)}$ among all walks in $\mathcal{P}_{w,v}^{j}$.

  2. 2.

Exactly one of the following holds:

    1. (a)

$\max\\{\phi_{v}(C):C\in\mathcal{C}_{v}^{k},\gamma(C)>1\\}\leq
a<\phi_{v,k}<b$,

    2. (b)

The two walks $C_{\min},C_{\max}\in\mathcal{C}_{v}^{k}$ satisfy
$\gamma(C_{\min})<1$, $\gamma(C_{\max})>1$
and$a<\phi(C_{\max})\leq\phi(C_{\min})<b$.

Initially $a=-\infty$, $b=\infty$. $P_{0,v}$ is an empty walk, and all other
walks $P_{0,w}$ for $w\neq v$ do not exist. One can easily verify that
invariant 1. is satisfied initially, Note that invariant 2.(a) is satisfied
initially if $\gamma(C_{\max})\leq 1$, and 2.(b) is satisfied if
$\phi(C_{\max})\leq\phi(C_{\min})$.

The algorithm will only shrink the interval $(a,b)$. In particular, if the
inequality $\max\\{\phi_{v}(C):C\in\mathcal{C}_{v}^{k},\gamma(C)>1\\}\leq a$
of invariant 2.(a) ever holds for the first time, it will hold till the end
because $a$ can only increase.

Suppose we have computed all the walks $P_{j-1,u}$, $u\in V$. Consider some
desired walk $P_{j,w}$ that we want to compute. If $|P_{j,w}|<j$, then we can
set $P_{j,w}=P_{j-1,w}$. Otherwise, $|P_{j,w}|\geq 1$. Let $P_{j,w}=eQ$, where
$e=wu$. Then the lower bound that $P_{j,w}$ incurs on $x_{w}$ with respect to
$\phi_{v,k}$ is:

$c(eQ)+\gamma(eQ)\cdot\phi_{v,k}=c(e)+\gamma(e)\cdot(c(Q)+\gamma(Q)\cdot\phi_{v,k}).$

Since $\gamma(e)>0$, for a fixed $e$, the above is minimized for
$Q=P_{j-1,u}$. So $c(P_{j,w})+\gamma(P_{j,w})\cdot\phi_{v,k}$ equals:

$\min\left(c(P_{j-1,w})+\gamma(P_{j-1,w})\cdot\phi_{v,k},\min_{wu=e\in
E}\left\\{(c(e)+\gamma(e)\cdot
c(P_{j-1,u}))+\gamma(e)\cdot\gamma(P_{j-1,u})\cdot\phi_{v,k})\right\\}\right).$

However, the inner minimum above is not easy to evaluate without actually
knowing $\phi_{v,k}$. But we don‘t need the minima, but rather the best walk
$eP_{j-1,u}$ for each $w\in V$. To this end, we first compute, for all $w\in
V$ the lower envelope $L_{w}$ of the lines

$y=\gamma(e)\cdot\gamma(P_{j-1,u})\cdot x+(c(e)+\gamma(e)\cdot c(P_{j-1,u})).$

Using a standard convex-hull-like algorithm this takes $O(\deg_{G}(w)\log n)$
time. We record the $x$-coordinates of the breakpoints of the envelope as
$X_{w}$. Through all $w$, computing the envelopes and breakpoints takes
$O(m\log{n})$ time.

Let $X=\\{a,b\\}\cup\left(\left(\bigcup_{w\in V}X_{w}\right)\cap(a,b)\right)$.
We sort the set $X$ in $O(m\log{m})$ time. Then, roughly speaking, we perform
a binary search for the two neighboring $x_{i},x_{i+1}\in X$ such that
${\phi_{v,k}\in(x_{i},x_{i+1})}$. The binary search makes decisions based on
the output of the query $(v,k,\xi=x_{i})$ issued to the algorithm of Lemma
8.1. We now describe how this decision is made in more detail.

We maintain that $a,b\in X$ and repeatedly shrink the interval $[a,b]$ until
$a$ and $b$ are neighboring elements of $X$. Let $g$ be the middle element of
$X$ between $a$ and $b$. We issue the query $(v,k,\xi=g)$ to the procedure of
Lemma 8.1. We have several cases depending on the result returned:

  1. (a)

We set $b=g$ and reset $C_{\min}$ to the closed walk $C$ returned by Lemma
8.1.

  2. (b)

We set $a=g$ and reset $C_{\max}$ to the closed walk $C$ returned by Lemma
8.1.

  3. (c)

We set $a=g$.

  4. (d)

The system is infeasible and we terminate with the certificate returned by
Lemma 8.1.

  5. (e)

We have $\phi_{v,k}=g$ and we terminate with the certificate returned by Lemma
8.1.

If, after applying one of the cases (a) or (b) above, we have
$\phi(C_{\min})<\phi(C_{\max})$, then we terminate with the pair
$(C_{\min},C_{\max})$ as the certificate of infeasibility. We also stress that
in cases (a) and (b), we do not construct $C_{\min}$ or $C_{\max}$ explicitly
so that the query costs $O(mk)$ instead of $O(mk\log{k})$ time. Instead, we
only store the returned walk $C$ implicitly by storing $\phi(C)$ and the
$O(1)$-sized parameters to the respective call of Lemma 8.1. If we later
actually need $C_{\min}=C$ or $C_{\max}=C$ when returning a certificate of
infeasibility, we call Lemma 8.1 once again to reconstruct the closed walk $C$
in $O(mk\log{k})$ time.

We now argue that while binary search proceeds without terminating prematurely
with either $\phi_{v,k}$ or a certificate, invariants $1$. and $2$. are
satisfied. The cases (d) and (e) terminate the algorithm and thus require no
explanation. Also, suppose we have $\phi(C_{\max})\leq\phi(C_{\min})$.

That invariant 1. holds follows by the construction. Consider invariant 2 and
first suppose invariant 2.(a) is satisfied before the binary search step.
Then, clearly cases (a) and (b) maintain that 2.(a) is satisfied. However, if
case (c) applies, we obtain

$\max\\{\phi_{v}(C):C\in\mathcal{C}_{v}^{k},\gamma(C)>1\\}\leq a<\phi_{v,k}$

by Lemma 8.1. But we also have $\phi_{v,k}\leq\phi(C_{\min})<b$, so invariant
2.(b) is satisfied afterwards.

Now suppose that invariant 2.(b) is satisfied before the binary search step.
For 2.(b) to be satisfied afterwards, it is enough to prove that
$a<\phi_{v,k}<b$. As
$\max\\{\phi_{v}(C):C\in\mathcal{C}_{v}^{k},\gamma(C)>1\\}\leq a$ before, case
(b) cannot actually happen. If case (a) applies, then indeed the returned $C$
certifies that $\phi_{v,k}<g$, so we have $a<\phi_{v,k}<b$ afterwards. If case
(3) applies, then we obtain that $g<\phi_{v,k}$, so indeed $a<\phi_{v,k}<b$
afterwards.

The binary search clearly issues $O(\log{m})$ queries to Lemma 8.1, which
takes $O(mk\log{m})$ time for a single $j$.

After the binary search finishes, $a,b$ are some neighboring elements
$x_{i},x_{i+1}$ of $X$. For each $w\in V$, we pick the walk
$P_{j,w}=eP_{j-1,u}$ such that it attains the minima in the interval
$(x_{i},x_{i+1})$. If there are ties, we pick such $eP_{j-1,u}$ that
$\gamma(e)\gamma(P_{j-1,u})$ is minimized. This is well-defined since by the
definition of breakpoints $x_{i},x_{i+1}$, for any two walks $R,T$ of the form
$eP_{j-1,u}$ we have either $c(R)+\gamma(R)\cdot z\leq c(T)+\gamma(T)\cdot z$
for all $z\in(x_{i},x_{i+1})$, or $c(R)+\gamma(R)\cdot z\geq
c(T)+\gamma(T)\cdot z$ for all $z\in((x_{i},x_{i+1})$. Picking the right walk
$eP_{j-1,u}$ takes $O(m)$ time.

Consider the walk $P_{k,v}$. Recall that $P_{k,v}$ minimizes
$c(P_{k,v})+\gamma(P_{k,v})\cdot z$ for all $z\in(a,b)$. Observe that if
invariant 2.(b) is satisfied, then, since
$\phi(C_{\min}),\phi(C_{\max})\in(a,b)$, we obtain:

$c(P_{k,v})+\gamma(P_{k,v})\cdot\frac{c(C_{\min})}{1-\gamma(C_{\min})}\leq
c(C_{\min})+\gamma(C_{\min})\cdot\frac{c(C_{\min})}{1-\gamma(C_{\min})}=\frac{c(C_{\min})}{1-\gamma(C_{\min})},$
(5) $c(P_{k,v})+\gamma(P_{k,v})\cdot\frac{c(C_{\max})}{1-\gamma(C_{\max})}\leq
c(C_{\max})+\gamma(C_{\max})\cdot\frac{c(C_{\max})}{1-\gamma(C_{\max})}=\frac{c(C_{\max})}{1-\gamma(C_{\max})}.$
(6)

On the other hand, if invariant 2.(a) is satisfied, then for
$C^{*}\in\mathcal{C}_{v,k}$ such that $\phi(C^{*})=\phi_{v,k}\in(a,b)$, we
have:

$c(P_{k,v})+\gamma(P_{k,v})\cdot\frac{c(C^{*})}{1-\gamma(C^{*})}\leq
c(C^{*})+\gamma(C^{*})\cdot\frac{c(C^{*})}{1-\gamma(C^{*})}=\frac{c(C^{*})}{1-\gamma(C^{*})}.$
(7)

Consider the case $\gamma(P_{k,v})<1$ and invariant 2.(b) is satisfied. Then
it follows from (6) that $\phi(P_{k,v})\leq\phi(C_{\max})$. If
$\phi(P_{k,v})<\phi(C_{\max})$, then the pair $(P_{k,v},C_{\max})$ deems the
system infeasible. Otherwise, $\phi(P_{k,v})=\phi(C_{\max})$. So,
$\phi_{v,k}\leq\phi(P_{k,v})$, and if the system is feasible, then
$\phi_{v,k}=\phi(P_{k,v})$. We issue a query $(v,k,\xi=\phi(P_{k,v}))$ to
Lemma 8.1. If the answer to that query is (e), we indeed have
$\phi_{v,k}=\phi(P_{k,v})$ regardless of whether the system is feasible. Note
that if the system is feasible, the procedure of Lemma 8.1 will surely return
(e). On the other hand, if the answer is (a) or (b) then the produced walk $Q$
along with $C_{\max}$ or $P_{k,v}$ respectively forms a certificate of
infeasibility. Clearly, if the answer is (e), we also have a relevant
certificate. Finally, answer (c) cannot arise since
$\phi_{v,k}\leq\phi(P_{k,v})$. Note that $P_{k,v}$ can be constructed in
$O(mk\log{k})$ time and linear space using Lemma 3.5 with
$\alpha=\phi(C_{\max})$.

If $\gamma(P_{k,v})<1$ and invariant 2.(a) is satisfied then
$\phi_{v,k}\leq\frac{c(P_{k,v})}{1-\gamma(P_{k,v})}=\phi(P_{k,v})$ by the
definition of $\phi_{v,k}$ and thus indeed
$\phi_{v,k}=\frac{c(P_{k,v})}{1-\gamma(P_{k,v})}$ since (7) can be rewritten
as

$\phi(P_{k,v})=\frac{c(P_{k,v})}{1-\gamma(P_{k,v})}\leq\frac{c_{v}(C^{*})}{1-\gamma(C^{*})}=\phi_{v,k}.$

So in this case we return $\phi(P_{k,v})$ as $\phi_{v,k}$.

In the following let us set $D=C^{*}$ if invariant 2.(a) is satisfied and
$D=C_{\min}$ if invariant 2.(b) is satisfied. Note that we have
$\phi(D)\in(a,b)$.

Now assume that $\gamma(P_{k,v})>1$. We now prove that then the system is
infeasible and we show how to obtain a relevant certificate. Note that since
we break ties while picking a walk $P_{k,v}$ minimizing
${c(P_{k,v})+\gamma(P_{k,v})\cdot z}$ by minimizing $\gamma(P_{k,v})$,
$\gamma(P_{k,v})>1$ implies that inequality (5) is actually strict if
$D=C_{\min}$, and inequality (7) is strict if $D=C^{*}$ applies. We conclude
that $\phi(P_{k,v})>\phi(D)$. If invariant 2.(b) is satisfied, it follows that
indeed the system is infeasible and the pair $(P_{k,v},C_{\min})$ is a
certificate. If invariant 2.(a) is satisfied, we have a contradiction with
$\phi(P_{k,v})\leq a<\phi(C^{*})$, so such a case cannot actually happen.

Suppose $\gamma(P_{k,v})=1$. By (5) or (7) (whichever applies), we obtain
$c(P_{k,v})\leq 0$. If $c(P_{k,v})<0$, then $P_{k,v}$ is a certificate of
infeasibility. We now prove $c(P_{k,v})=0$ is actually impossible. If this was
the case, we would have equality in (5) or (7), which would imply that the
lines $y=x$ and $y=c(D)+\gamma(D)\cdot x$ cross at $x=\phi(C_{\min})$. As a
result, we would have $c(D)+\gamma(D)\cdot x<c(P_{k,v})+\gamma(P_{k,v})\cdot
x$ for all $x\in\left(\phi(D),b\right)$, where $\phi(C_{\min})<b$ by invariant
2.(b). However, $P_{k,v}$ minimizes $c(P_{k,v})+\gamma(P_{k,v})\cdot x$ for
_all_ $x\in(a,b)$, in particular for all $x\in\left(\phi(D),b\right)$, a
contradiction.

Since there are $O(k)$ different walk lengths $j$, the running time is
$O(mk^{2}\log{m})$. For each walk length $j=1,\ldots,k$ we use $O(m)$ space to
store the envelopes and the sorted breakpoints. However, these are discarded
when proceeding to the next $j$. When moving to the next path length $j$ we
only use $O(n)$ space: two numbers per each walk $P_{j-1,u}$, and possibly an
implicit $O(1)$-space representations of $C_{\min}$, $C_{\max}$. Recall that
applying Lemma 8.1 requires $O(m+k)$ space. ∎

##  9 Proof of Lemma 5.3

In this section, we prove the following lemma. See 5.3

Although the algorithm is identical to that of [RW09, Section 4], in order to
prove the additional properties, we will need to describe it (using our
notation) and re-prove some of its known properties.

Suppose that for each $w\in V$ and $j=1,\ldots,n$ we wish to compute a walk
$Q_{w,j}\in\bigcup_{v\in V}\mathcal{P}_{v,w}^{j}$ such that:

  * •

In the first place, $Q_{w,j}$ maximizes the value
$y_{w,j}=\frac{1}{\gamma(Q_{w,j})}(\xi_{v}-c(Q_{w,j}))$.

  * •

If there are ties, $Q_{w,j}$ minimizes its number of edges $|Q_{w,j}|$.

  * •

If there are still ties, $Q_{w,j}$ maximizes its ultimate edge $p_{w,j}$.
Here, we assume that edges are ordered according to some arbitrary but fixed
order.

For $j=0$, we have $y_{w,0}=\xi_{w}$ for all $w\in V$, and $p_{w,0}=\perp$.
Observe that for $j=1,\ldots,n$, we have the following recursive relations:

$y_{w,j}=\max\left(y_{w,j-1},\max_{uw=e\in
E}\left\\{\frac{1}{\gamma(e)}(y_{u,j-1}-c(e))\right\\}\right),$
$p_{w,j}=\begin{cases}p_{w,j-1}&\text{ if }y_{w,j}=y_{w,j-1},\\\
\operatorname*{argmax}_{uw=e\in
E}\left\\{\left(\frac{1}{\gamma(e)}(y_{u,j-1}-c(e)),e\right)\right\\}&\text{
if }y_{w,j}<y_{w,j-1}.\end{cases}$

As a result, the values $y_{w,j},p_{w,j}$ for $w\in V$ can be computed solely
using the values $y_{u,j-1},p_{u,j-1}$ for $u\in V$ in $O(m)$ time.

Note that if $p_{v,j}=e=uv$ then we have $y_{v,j}=(y_{u,j-1}-c(e))/\gamma(e)$,
and $p_{v,j}=\perp$ iff $y_{v,j}=\xi_{v}$.

The algorithm proceeds in phases. When entering the $j$-th phase,
$j=0,\ldots,n$, we will only require the values $y_{u,j-1},p_{u,j-1}$ for
$u\in V$. Based on them we will compute the values $y_{w,j},p_{w,j}$ for $w\in
V$. We will consider the graphs $H_{l}=(V,\\{p_{w,l}:w\in
V,p_{w,l}\neq\perp\\})$ for $l\in\\{j,j-1\\}$, both of which consist of some
(possibly empty) simple cycles with some out-trees attached.

If $H_{j}$ contains a cycle $C$ with $\gamma(C)<1$, we will terminate the
algorithm with a relevant certificate. Otherwise, if for all $j=1,\ldots,n$
the graph $H_{j}$ does not contain such a cycle, we will declare that
${x_{v}^{\max}}\geq\xi_{v}$ for all $v\in V$. In the following, we give the
algorithm‘s details and analysis.

######  Lemma 9.1.

Suppose $H_{j}$ contains a cycle $C$. Then:

  * •

for some $w\in V(C)$ we have $y_{w,j}>y_{w,j-1}$,

  * •

for all $w\in V(C)$ such that $y_{w,j}>y_{w,j-1}$ we have
$y_{w,j-1}\cdot(1-\gamma(C))>c_{w}(C)$,

  * •

for all $w\in V(C)$ we have $y_{w,j}\cdot(1-\gamma(C))\geq c_{w}(C)$.

###### Proof.

Let us first prove that for some $w^{*}\in V(C)$ we have
$y_{w^{*},j}>y_{w^{*},j-1}$. Since $C\not\subseteq H_{0}$, there has to be
some last iteration $i$, $1\leq i\leq j$ when $C\not\subseteq H_{i-1}$. Since
there exists some edge $wu=e\in E(C)\setminus H_{i-1}$, $p_{w,i}\neq
p_{w,i-1}$, and, as a result, $y_{w,i}>y_{w,i-1}$. Let the vertices appearing
on $C$ be $w=u_{0},u_{1},\ldots,u_{k-1}$, so that an edge
$e_{i}=u_{i}u_{(i+1)\bmod k}$ belongs to $C$ for all $i=0,\ldots,k-1$.

We have
$y_{u_{0},i-1}<y_{u_{0},i}=(y_{u_{k-1},i-1}-c(e_{k-1}))/\gamma(e_{k-1})$. For
any $l=1,\ldots,j-i$, by induction on $l$ one obtains
$y_{u_{l},i+l-1}<y_{u_{l},i+l}$:

$y_{u_{l},i+l-1}=(y_{u_{l-1},i+l-2}-c(e_{l-1}))/\gamma(e_{l-1})<(y_{u_{l-1},i+l-1}-c(e_{l-1}))/\gamma(e_{l-1})=y_{u_{l},i+l}.$

In particular, for $l=j-i$ we obtain $y_{u_{j-1},j-1}<y_{u_{j-1},j}$. By
setting $w^{*}:=u_{j-1}$, we obtain $y_{w^{*},j-1}<y_{w^{*},j}$, as desired.

Once again, let us take some $w\in V(C)$ that $y_{w,j}>y_{w,j-1}$. Let the
vertices appearing on $C$ be $w=u_{0},u_{1},\ldots,u_{k-1}$, so that an edge
$e_{i}=u_{i}u_{(i+1)\bmod k}$ belongs to $C$ for all $i=0,\ldots,k-1$.

For each $e_{i}\in E(C)\subseteq E(H_{j})$ we have $y_{u_{(i+1)\bmod
k},j}=(y_{u_{i},j-1}-c(e_{i}))/\gamma(e_{i})\leq(y_{u_{i},j}-c(e_{i}))/\gamma(e_{i})$.
As a result, by chaining these inequalities we obtain

$y_{w,j}=y_{u_{0},j}\leq\frac{y_{u_{1},j}-c(e_{1}\ldots
e_{k-1})}{\gamma(e_{1}\ldots
e_{k})}=\frac{\frac{y_{v_{0},j-1}-c(e_{0})}{\gamma(e_{0})}-c(e_{1}\ldots
e_{k})}{\gamma(e_{1}\ldots e_{k})}=\frac{y_{w,j-1}-c_{w}(C)}{\gamma(C)}.$

But $y_{w,j}>y_{w,j-1}$, so we obtain

$y_{w,j-1}\cdot\gamma(C)<y_{w,j-1}-c_{w}(C),$

from which the first item of the lemma follows. However, observe that if we
picked $w$ arbitrarily, we would obtain

$y_{w,j}\cdot\gamma(C)\leq y_{w,j-1}-c_{w}(C)\leq y_{w,j}-c_{w}(C),$

which implies the second item of the lemma. ∎

In particular, Lemma 9.1 implies that $H_{j}$ does not contain cycles $C$ with
$\gamma(C)=1$, as otherwise for some $w\in V(C)$ we would have $c_{w}(C)<0$,
which would make the system infeasible.

######  Lemma 9.2.

Suppose the algorithm did not terminate before phase $j$ and $H_{j}$ contains
a cycle $C$ with $\gamma(C)<1$. Then for some $w\in V(C)$:

  * •

$H_{j-1}$ contains a simple path $P_{w}=v\to w$ such that
${x_{v}^{\max}}<\xi_{v}$,

  * •

$c(P_{w})+\gamma(P_{w})\cdot\phi_{w}(C)<\xi_{v}$,

  * •

$|V(P_{w}\cup C)|\geq j/2$.

###### Proof.

First of all, note that $H_{j-1}$ does not contain cycles $C^{\prime}$ with
$\gamma(C^{\prime})\leq 1$. This follows by Lemma 9.1 and the assumption that
the algorithm has not terminated before phase $j$.

Let $w\in V(C)$ be such that $y_{w,j}>y_{w,j-1}$, which implies
$y_{w,j-1}>\phi_{w}(C)$. Such a $w$ exists by Lemma 9.1. Let $P_{w}$ be the
subgraph of $H_{j-1}$ obtained by following the reverse walk consisting of
$p_{w,j-1}=v_{1}w$, $p_{v_{1},j-1}=v_{2}v_{1}$, $p_{v_{2},j-1}=v_{3}v_{2}$,
and so on. By the structure of $H_{j-1}$, $P_{w}$ either (i) is a simple path
$v\to w$ such that $p_{v,j-1}=\perp$, or (ii) consists of a path
$P^{\prime}=v\to w$ and a cycle $C^{\prime}=v\to v$ with
$\gamma(C^{\prime})>1$.

We now argue that if the system is feasible, case (ii) cannot in fact arise.
By Lemma 9.1 we have that $y_{v,j-1}\cdot(1-\gamma(C^{\prime}))\geq
c_{w}(C^{\prime})$, i.e., $y_{v,j-1}\leq\phi_{v}(C^{\prime})$. By chaining
inequalities corresponding to the edges on $P^{\prime}$, we have:
$y_{w,j-1}\leq(y_{v,j-1}-c(P^{\prime}))/\gamma(P^{\prime})\leq(\phi_{v}(C^{\prime})-c(P^{\prime}))/\gamma(P^{\prime})$,
which is equivalent to

$c(P^{\prime})+\gamma(P^{\prime})\cdot y_{w,j-1}\leq\phi_{v}(C^{\prime}).$

By applying $y_{w,j-1}>\phi_{w}(C)$, we have

$c(P^{\prime})+\gamma(P^{\prime})\cdot\phi_{w}(C)<\phi_{v}(C^{\prime}).$

The left-hand side above is an upper bound on $x_{v}$, and the right-hand side
is a lower bound on $x_{v}$. Therefore, the system is infeasible, so this case
cannot happen.

Let us thus focus on the case (i). By chaining the inequalities on $P_{w}$, we
obtain

$c(P_{w})+\gamma(P_{w})\cdot y_{w,j-1}\leq\xi_{v},$ (8)

and by applying $y_{w,j-1}>\phi_{w}(C)$ once again, we have

$c(P_{w})+\gamma(P_{w})\cdot\phi_{w}(C)<\xi_{v},$

which proves that a tighter upper bound on $x_{v}$ than $\xi_{v}$ is possible,
i.e., ${x_{v}^{\max}}<\xi_{v}$.

Finally, by combining (8) and Lemma 9.1, we have:

$\displaystyle(\xi_{v}-c(P_{w}C))\cdot\frac{1}{\gamma(P_{w}C)}$
$\displaystyle=(\xi_{v}-c(P_{w})-\gamma(P_{w})c_{w}(C))\frac{1}{\gamma(P_{w}C)}$
$\displaystyle\geq(\gamma(P_{w})\cdot
y_{w,j-1}-\gamma(P_{w})c_{w}(C))\frac{1}{\gamma(P_{w}C)}$
$\displaystyle=\frac{y_{w,j-1}-c_{w}(C)}{\gamma(C)}$
$\displaystyle>\frac{y_{w,j-1}-y_{w,j-1}(1-\gamma(C))}{\gamma(C)}$
$\displaystyle=y_{w,j-1}.$

Since $y_{w,j-1}$ is at least
$\max_{Q\in\mathcal{P}_{v,w}^{j-1}}\left\\{\frac{\xi_{v}-c(Q)}{\gamma(Q)}\right\\}$,
we conclude that $P_{w}C\notin\mathcal{P}_{v,w}^{j-1}$, i.e., the walk
$P_{w}C$ has at least $j$ edges. Since $P_{w}$ is a simple path, and $C$ is a
simple cycle, $P_{w}C$ has $|V(P_{w})|+|V(C)|$ edges, so we obtain
$2|V(P_{w}\cup C)|\geq|V(P_{w})|+|V(C)|\geq j$. As a result $|V(P_{w}\cup
C)|\geq j/2$. ∎

######  Lemma 9.3.

If for some $v$ we have ${x_{v}^{\max}}<\xi_{v}$, the algorithm will terminate
with a certificate.

###### Proof.

The ’’$\implies$‘‘ part is obvious. For the ’’$\impliedby$‘‘ part we refer to
[RW09, Lemma 4.6]. We only argue that our problem is equivalent to the
negative-cost generalized augmenting path detection problem, as defined in
[RW09]. In this problem, one is given a target vertex $t\in V$ and is asked to
find a so-called _negative GAP_ , which is a closed walk $C=w\to w$ with
$\gamma(C)>1$ along with a walk $P=w\to t$ such that $c(P)<\phi_{w}(C)$.

Consider the graph $G^{\prime}=(V^{\prime},E^{\prime})$, where
$V^{\prime}=V^{\prime}\cup\\{t\\}$, with functions
$c^{\prime}:E^{\prime}\to\mathbb{R}$,
$\gamma^{\prime}:E^{\prime}\to\mathbb{R}$. For each $uv=e\in E$, we have a
corresponding $uv=e^{\prime}\in E^{\prime}$ with
$c^{\prime}(e)=c(e)/\gamma(e)$ and $\gamma^{\prime}(e)=1/\gamma(e)$. Moreover,
for each $v\in V$, we have an edge $vt=e^{\prime}_{v}\in E^{\prime}$ with
$c^{\prime}(e^{\prime}_{v})=-\xi_{v}$, $\gamma^{\prime}(e^{\prime}_{v})=1$.
Note that we have a negative GAP in $G^{\prime}$ iff for some walk $P=w\to v$
and a cycle $C$ with $\gamma^{\prime}(C)>1$, we have
$c^{\prime}(Pe^{\prime}_{v})<\phi^{\prime}_{w}(C)$, or equivalently
$c^{\prime}(P)-\gamma^{\prime}(P)\cdot\xi_{v}<\frac{c^{\prime}_{w}(C)}{1-\gamma^{\prime}(C)}$.
This in turn is equivalent to

$\frac{1}{\gamma(P^{R})}\cdot(c(P^{R})-\xi_{v})<\frac{c_{w}(C^{R})}{\gamma(C^{R})-1}.$

Therefore we have, $c(P^{R})+\gamma(P^{R})\cdot\phi_{w}(C^{R})<\xi_{v}$ and
$P^{R}$ is a $v\to w$ walk, and $C^{R}$ is a $w\to w$ closed walk with
$\gamma(C^{R})<1$. This proves that there is a 1-1 correspondence between
negative GAPs in $G^{\prime}$, and certificates that we seek for in $G$.

Finally, the algorithm that we described is equivalent to that of [RW09,
Figure 2]: applied to $G^{\prime}$, that algorithm computes walks
$Q_{w,j}^{\prime}=w\to v$ minimizing
$c^{\prime}(Q_{w,j}^{\prime})-\gamma^{\prime}(Q_{w,j}^{\prime})\cdot\xi_{v}$,
which is equivalent to maximizing
$\xi_{v}-c^{\prime}(Q_{w,j}^{\prime})=\frac{1}{\gamma((Q_{w,j}^{\prime})^{R})}\left(\xi_{v}-c((Q_{w,j}^{\prime})^{R})\right)$.
So by substituting $Q_{w,j}:=(Q_{w,j}^{\prime})^{R}$ the algorithm computes
walks $Q_{w,j}=v\to w$ in $G$ maximizing
$\frac{1}{\gamma(Q_{w,j}}\left(\xi_{v}-c(Q_{w,j})\right)$, which is precisely
what our version of the algorithm does. The tie-braking rules are the same as
well. ∎

To guarantee consistency, when picking a vertex $w$ in the above lemma to
produce a certificate $(P_{w},C)$, we use $w$ with $y_{w,j-1}>\phi_{w}(C)$
that is minimal according to some fixed order on $V$.

######  Lemma 9.4.

Let ${x_{v}^{\max}}<\xi_{v}$ and ${x_{u}^{\max}}\geq\xi_{u}$ for all $u\in
V\setminus\\{v\\}$. Then, the algorithm terminates with a certificate
$(P_{w},C)$ that does not depend on $\\{\xi_{u}:u\in V\setminus\\{v\\}\\}$.

###### Proof.

Suppose the algorithm run for $\xi$ produces a certificate $(P_{w},C)$ in
phase $j$. Recall that by construction, $P_{w}=e_{1}\ldots e_{k}$, where
$e_{i}=v_{i-1}v_{i}$, and $v_{0}=v$, $v_{k}=w$, and $y_{v,j-1}=\xi_{v}$. For
any $i$, we have

$y_{v_{i},j-1}=(y_{v_{i-1},j-2}-c(e_{i}))/\gamma(e_{i})\leq(y_{v_{i-1},j-1}-c(e_{i}))/\gamma(e_{i}).$

Therefore, by chaining such inequalities, for any $i$ we have:

$y_{w,j-1}\leq(y_{v_{i-1},j-1}-c(e_{i}\ldots e_{k}))/\gamma(e_{i}\ldots
e_{k}).$

Suppose for some $v_{i}$, $i\geq 0$, $Q_{v_{i},j-1}$ is not a $v\to v_{i}$
path, but a $u\to v_{i}$ path, for some $u\neq v$. Then,

$y_{v_{i},j-1}=(\xi_{u}-c(Q_{v_{i},j-1}))/\gamma(Q_{v_{i},j-1}),$

and thus

$y_{w,j-1}\leq(\xi_{u}-c(Q_{v_{i},j-1}e_{i+1}\ldots
e_{k}))/\gamma(Q_{v_{i},j-1}e_{i+1}\ldots e_{k}).$

As a result, we obtain:

$c(Q_{v_{i},j-1}e_{i+1}\ldots e_{k})+\gamma(Q_{v_{i},j-1}e_{i+1}\ldots
e_{k})\cdot y_{w,j-1}\leq\xi_{u}.$

This, in combination with $y_{w,j-1}>\phi_{w}(C)$, shows that
${x_{u}^{\max}}<\xi_{u}$, a contradiction. This proves that $Q_{v_{i},j-1}$ is
a $v\to v_{i}$ path for all $i$.

Next we prove that for each $z\in V(C)$, $Q_{z,j}$ is a $v\to z$ walk. Let
$C=e_{0}\ldots e_{k-1}$ such that $e_{i}=u_{i}u_{(i+1)\bmod{k}}$. Split the
sequence of vertices appearing on $C$ (in order) into maximal segments
$u_{g},\ldots,u_{h}$ such that $y_{u_{g},j}>y_{u_{g},j-1}$ and
$y_{u_{l},j}=y_{u_{l},j-1}$ for all $l=g+1,\ldots,h$. Such a split is possible
since $y_{w,j}>y_{w,j-1}$. For each segment, we have $y_{u_{(h+1)\bmod
k},j}>y_{u_{(h+1)\bmod k},j-1}$.

Consider an arbitrary such segment. We have already proved that
$Q_{u_{(h+1)\bmod k},j-1}$ is a $v\to u_{(h+1)\bmod k}$ path, since the choice
of the vertex $w$ only required $y_{w,j}>y_{w,j-1}$. We also have
$Q_{u_{h},j}=Q_{u_{(h+1)\bmod k},j-1}\cdot e_{h}$ since $p_{u_{h},j}=e_{h}$.
Hence, $Q_{u_{h},j}$ is a $v\to u_{h}$ path. But $y_{u_{h},j}=y_{u_{h},j-1}$,
so in fact $Q_{u_{h},j-1}=Q_{u_{h},j}$ is also a $v\to u_{h}$ path.
Analogously, we inductively prove that subsequently
$Q_{u_{h-1},j}=Q_{u_{h-1},j-1},Q_{u_{h-2},j}=Q_{u_{h-2,j-1}},\ldots,Q_{u_{g+1},j}=Q_{u_{g+1},j-1}$
are also walks starting in $v$. Finally, from $Q_{u_{g+1},j-1}=v\to u_{g+1}$
we conclude that $Q_{u_{g},j}=v\to u_{g}$.

Now, consider a vector $(\xi^{*})_{u\in V}$ such that $\xi_{v}^{*}=\xi_{v}$
and $\xi^{*}_{u}={x_{u}^{\max}}$ for all $u\in V\setminus\\{v\\}$. For any
other vector $(\xi^{\prime})_{v\in V}$ that satisfies the requirements of the
lemma, we have $\xi^{\prime}_{u}\leq\xi^{*}_{u}$ for all $u\in V$. By Lemma
9.3, running the algorithm with the input $\xi^{*}$ produces some certificate
$(P_{s}^{*},C^{*})$ for some $s\in V$, and running it with the input
$\xi^{\prime}$ produces a certificate $(P_{t}^{\prime},C^{\prime})$ for some
$t\in V$.

Denote by $Q_{w,j}^{*},y_{w,j}^{*}$ and $Q_{w,j}^{\prime},y_{w,j}^{\prime}$
the respective paths $Q_{w,j}$ and values $y_{w,j}$ for the inputs $\xi^{*}$
and $\xi^{\prime}$ respectively. Note that for any $w,j$ we have
$y_{w,j}^{*}\geq y_{w,j}^{\prime}$ by the definition of $\xi^{*}$. Moreover,
since $\xi^{*}_{v}=\xi^{\prime}_{v}$, we have that $Q_{w,j}^{*}=v\to w$
implies that $Q_{w,j}^{\prime}=Q_{w,j}^{*}$.

Suppose that the certificate $(P_{s}^{*},C^{*})$ is produced in phase $j$ and
$s$ is chosen minimal possible. Then, as we have proved, for all $z\in
V(P_{s}^{*})$, $Q_{z,j-1}^{*}$ is a $v\to z$ walk. Moreover, for all $z\in
V(C^{*})$, $Q_{z,j}^{*}$ is a $v\to z$ walk. Consequently,
$Q_{z,j-1}^{\prime}=Q_{z,j-1}^{*}$ for all $z\in V(P_{s}^{*})$, and
$Q_{z,j}^{\prime}=Q_{z,j}^{*}$ for all $z\in V(C^{*})$. As a result, the same
cycle $C^{*}$ exists in $H_{j}$ and the same path $P_{s}^{*}$ exists in
$H_{j-1}$ for the input $\xi^{\prime}$. We conclude that the algorithm run for
$\xi^{\prime}$ will terminate with $(P_{s}^{*},C^{*})$ unless it terminates
earlier, i.e., in an earlier phase or in the phase $j$ with a smaller vertex
$t$.

Now suppose that for the input $\xi^{\prime}$, the algorithm terminates
earlier (at phase $j$) than if it was run with the input $\xi^{*}$. Note that
then we need to either have (i) $Q_{z,j-1}^{*}=w\to z$ for some $z\in
V(P_{t}^{\prime})$ and $w\in V\setminus\\{v\\}$, or we have (ii)
$Q_{z,j}^{*}=w\to z$ for some $z\in V(C^{\prime})$ and $w\in
V\setminus\\{v\\}$ – otherwise the run with the input $\xi^{*}$ would have
terminated no later than that for $\xi^{\prime}$.

Consider the case (i). Then, $y_{z,j-1}^{*}\geq y_{z,j-1}^{\prime}$ and if
$P_{t}^{\prime}=R_{1}R_{2}$, where $R_{1}=v\to z$ and $R_{2}=z\to t$, we would
obtain similarly as before $c(Q_{z,j-1}\cdot R_{2})+\gamma(Q_{z,j-1}\cdot
R_{2})\cdot y^{\prime}_{t,j-1}\leq\xi_{w}$, which, along with
$y^{\prime}_{t,j-1}<\phi_{t}(C^{\prime})$ would imply
${x_{w}^{\max}}<\xi_{w}$, a contradiction.

Now let us focus on (ii). Let $C^{\prime}=C_{1}C_{2}$, where $t\to
z=C_{1}=e_{0}\ldots e_{l}$ and $C_{2}=z\to t$. Let $e_{i}=u_{i}u_{i+1}$, so
that $u_{0}=t$ and $u_{l+1}=z$. By chaining the inequalities on $C_{2}$ we
obtain
$\phi_{t}(C^{\prime})<y^{\prime}_{t,j-1}<y^{\prime}_{t,j}\leq(y^{\prime}_{z,j}-c(C_{2}))/\gamma(C_{2})\leq(y^{*}_{z,j}-c(C_{2}))/\gamma(C_{2})=(\xi^{*}_{w}-c(Q_{z,j}^{*}C_{2}))/\gamma(Q_{z,j}^{*}C_{2})$.
As a result, we have
$c(Q_{z,j}^{*}C_{2})+\gamma(Q_{z,j}^{*}C_{2})\cdot\phi_{t}(C^{\prime})<\xi^{*}_{w}$.
So, ${x_{w}^{\max}}<\xi^{*}_{w}$, a contradiction.

We conclude that for any input $\xi^{\prime}$, the algorithm has to terminate
with the same certificate as for the input $\xi^{*}$. As a result, it
terminates with the same certificate for any $\xi$ satisfying the requirements
of the lemma. ∎

#### Acknowledgments.

We thank the anonymous reviewers for their very useful comments.

## References

  * [AS80] Bengt Aspvall and Yossi Shiloach.  A polynomial time algorithm for solving systems of linear inequalities with two variables per inequality.  SIAM J. Comput., 9(4):827–845, 1980.
  * [Asp81] Bengt Ingemar Aspvall.  Efficient algorithms for certain satisfiability and linear programming problems.  PhD thesis, Stanford University, 1981.
  * [CLS21] Michael B. Cohen, Yin Tat Lee, and Zhao Song.  Solving linear programs in the current matrix multiplication time.  J. ACM, 68(1):3:1–3:39, 2021.
  * [CM94] Edith Cohen and Nimrod Megiddo.  Improved algorithms for linear inequalities with two variables per inequality.  SIAM J. Comput., 23(6):1313–1347, 1994.
  * [d’E63] Francois d‘Epenoux.  A probabilistic production and inventory problem.  Management Science, 10(1):98–108, 1963.
  * [DKNV21] Daniel Dadush, Zhuan Khye Koh, Bento Natura, and László A. Végh.  An accelerated newton-dinkelbach method and its application to two variables per inequality systems.  In 29th Annual European Symposium on Algorithms, ESA 2021, September 6-8, 2021, Lisbon, Portugal (Virtual Conference), volume 204 of LIPIcs, pages 36:1–36:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021.
  * [DNV20] Daniel Dadush, Bento Natura, and László A. Végh.  Revisiting tardos‘s framework for linear programming: Faster exact solutions using approximate solvers.  In 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, Durham, NC, USA, November 16-19, 2020, pages 931–942. IEEE, 2020.
  * [HKZ14] Thomas Dueholm Hansen, Haim Kaplan, and Uri Zwick.  Dantzig‘s pivoting rule for shortest paths, deterministic mdps, and minimum cost to time ratio cycles.  In Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, Portland, Oregon, USA, January 5-7, 2014, pages 847–860. SIAM, 2014.
  * [HMNT93] Dorit S. Hochbaum, Nimrod Megiddo, Joseph Naor, and Arie Tamir.  Tight bounds and 2-approximation algorithms for integer programs with two variables per inequality.  Math. Program., 62:69–83, 1993.
  * [HMZ13] Thomas Dueholm Hansen, Peter Bro Miltersen, and Uri Zwick.  Strategy iteration is strongly polynomial for 2-player turn-based stochastic games with a constant discount factor.  J. ACM, 60(1):1:1–1:16, 2013.
  * [HN94] Dorit S. Hochbaum and Joseph Naor.  Simple and fast algorithms for linear and integer programs with two variables per inequality.  SIAM J. Comput., 23(6):1179–1192, 1994.
  * [JSWZ21] Shunhua Jiang, Zhao Song, Omri Weinstein, and Hengjie Zhang.  A faster algorithm for solving general lps.  In STOC ‘21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, Virtual Event, Italy, June 21-25, 2021, pages 823–832. ACM, 2021\.