11institutetext: Department of Computer Science, University of Arizona
22institutetext: Department of Computer Science, Georgia Institute of
Technology

# Weighted Additive Spanners

Reyan Ahmed 11 Greg Bodwin 22 Faryad Darabi Sahneh 11 Stephen Kobourov 11
Richard Spence 11

###### Abstract

A _spanner_ of a graph $G$ is a subgraph $H$ that approximately preserves
shortest path distances in $G$. Spanners are commonly applied to compress
computation on metric spaces corresponding to weighted input graphs. Classic
spanner constructions can seamlessly handle edge weights, so long as error is
measured _multiplicatively_. In this work, we investigate whether one can
similarly extend constructions of spanners with purely _additive_ error to
weighted graphs. These extensions are not immediate, due to a key lemma about
the size of shortest path neighborhoods that fails for weighted graphs.
Despite this, we recover a suitable amortized version, which lets us prove
direct extensions of classic $+2$ and $+4$ unweighted spanners (both all-pairs
and pairwise) to $+2W$ and $+4W$ weighted spanners, where $W$ is the maximum
edge weight. Specifically, we show that a weighted graph $G$ contains all-
pairs (pairwise) $+2W$ and $+4W$ weighted spanners of size $O(n^{3/2})$ and
$O(n^{7/5})$ ($O(np^{1/3})$ and $O(np^{2/7})$) respectively. For a technical
reason, the $+6$ unweighted spanner becomes a $+8W$ weighted spanner; closing
this error gap is an interesting remaining open problem. That is, we show that
$G$ contains all-pairs (pairwise) $+8W$ weighted spanners of size $O(n^{4/3})$
($O(np^{1/4})$).

###### Keywords:

Additive spanner Pairwise spanner Shortest-path neighborhood

##  1 Introduction

An _$f(\cdot)$ -spanner_ of an undirected graph $G=(V,E)$ with $|V|=n$ nodes
and $|E|=m$ edges is a subgraph $H$ which preserves pairwise distances in $G$
up to some error prescribed by $f$; that is,

$\operatorname{dist}_{H}(s,t)\leq f(\operatorname{dist}_{G}(s,t))\ \text{for
all nodes }s,t\in V.$

Spanners were introduced by Peleg and Schäffer [25] in the setting with
multiplicative error of type $f(d)=cd$ for some positive constant $c$. This
setting was quickly resolved, with matching upper and lower bounds [4] on the
sparsity of a spanner that can be achieved in general. At the other extreme
are (purely) _$c$ -additive spanners_ (or $+c$ spanners), with error of type
$f(d)=d+c$. More generally, if $f(d)=\alpha d+\beta$, we say that $H$ is an
_$(\alpha,\beta)$ -spanner_. Intuitively, additive error is much stronger than
multiplicative error; most applications involve shrinking enormous input
graphs that are too large to analyze directly, and so it is appealing to avoid
error that scales with distance.

Additive spanners were thus initially considered perhaps too good to be true,
and they were discovered only for particular classes of input graphs [22].
However, in a surprise to the area, a seminal paper of Aingworth, Chekuri,
Indyk, and Motwani [3] proved that nontrivial additive spanners actually exist
_in general_ : every $n$-node undirected unweighted graph has a $2$-additive
spanner on $O(n^{3/2})$ edges. Subsequently, more interesting constructions of
additive spanners were found: there are $4$-additive spanners on $O(n^{7/5})$
edges [11, 7] and $6$-additive spanners on $O(n^{4/3})$ edges [5, 21]. There
are also natural generalizations of these results to the _pairwise_ setting,
where one is given $G=(V,E)$ and a set of demand pairs $P\subseteq V\times V$,
where only distances between node pairs $(s,t)\in P$ need to be approximately
preserved in the spanner [20, 19, 6, 12, 8, 10].

Despite the inherent advantages of additive error, multiplicative spanners
have remained the more well-known and well-applied concept elsewhere in
computer science. There seem to be two reasons for this:

  1. 1.

Abboud and Bodwin [1] (see also [18]) give examples of graphs that have no
$c$-additive spanner on $O(n^{4/3-\varepsilon})$ edges, for any constants
$c,\varepsilon>0$. Some applications call for a spanner on a near-linear
number of edges, say $O(n^{1+\varepsilon})$, and hence these must abandon
additive error if they need theoretical guarantees for every possible input
graph. However, there is some evidence that many graphs of interest bypass
this barrier; e.g. graphs with good expansion or girth properties [5].

  2. 2.

Spanners are often used to compress metric spaces that correspond to
_weighted_ input graphs. This includes popular applications in robotics [23,
14, 9, 28], asynchronous protocol design [26], etc., and it incorporates the
extremely well-studied case of Euclidean spaces which have their own suite of
applications (see book [24]). Current constructions of multiplicative spanners
can handle edge weights without issue, but purely additive spanners are known
for unweighted input graphs only.

Addressing both of these points, Elkin et al. [16] (following [15]) recently
provided constructions of _near-additive_ spanners for weighted graphs. That
is, for any fixed $\varepsilon,t>0$, every $n$-node graph $G=(V,E,w)$ has a
$(1+\varepsilon,O(W))$-spanner on $O(n^{1+1/t})$ edges, where $W$ is the
maximum edge weight.111Their result is actually a little stronger: $W$ can be
the maximum edge weight on the shortest path between the nodes being
considered. This extends a classic unweighted spanner construction of Elkin
and Peleg [17] to the weighted setting. Additionally, while not explicitly
stated in their paper, their method can be adapted to a $+2W$ purely additive
spanner on $O(n^{3/2})$ edges (extending [3]).

The goal of this paper is to investigate whether or not all the other
constructions of spanners with purely additive error extend similarly to
weighted input graphs. As we will discuss shortly, there is a significant
barrier to a direct extension of the method from [16]. However, we prove that
this barrier can be overcome with some additional technical effort, thus
leading to the following constructions. In these theorem statements, all edges
have (not necessarily integer) edge weights in $(0,W]$. Let $p=|P|$ denote the
number of demand pairs and $n=|V|$ the number of nodes in $G$.

######  Theorem 1.1.

For any $G=(V,E,w)$ and demand pairs $P$, there is a $+2W$ pairwise spanner
with $O(np^{1/3})$ edges. In the all-pairs setting $P=V\times V$, the bound
improves to $O(n^{3/2})$.

######  Theorem 1.2.

For any $G=(V,E,w)$ and demand pairs $P$, there is a $+4W$ pairwise spanner
with $O(np^{2/7})$ edges. In the all-pairs setting $P=V\times V$, the bound
improves to $O(n^{7/5})$.

These two results exactly match previous ones for unweighted graphs [11, 19,
20, 3], with $+2W$ ($+4W$) in place of $+2$ ($+4$). Theorem 1.1 is partially
tight in the following sense: it implies that $O(n^{3/2})$ edges are needed
for a $+2W$ spanner when $p=O(n^{3/2})$, and neither of these values can be
unilaterally improved. Relatedly, Theorem 1.2 implies that $O(n^{7/5})$ edges
are needed for a $+4W$ spanner when $p=O(n^{7/5})$; it may be possible to
improve this, but it would likely imply an improved $+4W$ all-pairs spanner
over [11] which will likely be hard to achieve (see discussion in [7]).

Our next two results are actually a bit weaker than the corresponding
unweighted ones [19, 13, 27]: for a technical reason, we take on slightly more
error in the weighted setting (the corresponding unweighted results have $+6$
and $+2$ error respectively).

######  Theorem 1.3.

For any $G=(V,E,w)$ and demand pairs $P$, there is a $+8W$ pairwise spanner
with $O(np^{1/4})$ edges. In the all-pairs setting $P=V\times V$, the bound
improves to $O(n^{4/3})$.

######  Theorem 1.4.

For any $G=(V,E,w)$ and demand pairs $P=S\times S$, there is a $+4W$ pairwise
spanner with $O(n|S|^{1/2})$ edges.

We summarize our main results in Table 1, contrasted with known results for
unweighted graphs.

Unweighted | Weighted
---|---
Stretch | Size | Stretch | Size
$+2$ |  $O(n^{3/2})$ [3] | $+2W$ |  $O(n^{3/2})$ [this paper], [16]
$+4$ |  $O(n^{7/5})$ [11, 7] | $+4W$ |  $O(n^{7/5})$ [this paper]
$+6$ |  $O(n^{4/3})$ [5, 21, 30] | $+6W$ | ?
$+c$ |  $\Omega(n^{4/3-\varepsilon})$ [1, 18] | $+8W$ |  $O(n^{4/3})$ [this paper]
Table 1: Table of additive spanner constructions for unweighted and weighted
graphs, where $W$ denotes the maximum edge weight.

###  1.1 Technical Overview: What’s Harder With Weights?

There is a key point of failure in the known constructions of unweighted
additive spanners when one attempts the natural extension to weighted graphs.
To explain, let us give some technical background. Nearly all spanner
constructions start with a _clustering_ or _initialization_ step: taking the
latter exposition [21], a _$d$ -initialization_ of a graph $G$ is a subgraph
$H$ obtained by choosing $d$ arbitrary edges incident to each node, or all
incident edges to a node of degree less than $d$. After this, many additive
spanner constructions leverage the following key fact (the one notable
exception is the $+2$ all-pairs spanner, which is why one can recover the
corresponding weighted version from prior work):

######  Lemma 1 ([13, 20, 19, 11], etc.).

Let $G$ be an undirected unweighted graph, let $\pi$ be a shortest path, and
let $H$ be a $d$-initialization of $G$. If $\pi$ is missing $\ell$ edges in
$H$, then there are $\Omega(d\ell)$ different nodes adjacent to $\pi$ in $H$.

###### Proof.

For each missing edge $(u,v)\in\pi$, by construction both $u$ and $v$ have
degree at least $d$ in $H$ (otherwise, $\text{deg}_{H}(u)<d$, in which edge
$(u,v)$ is added in the $d$-initialization $H$). By the triangle inequality,
any given node is adjacent to at most three nodes in $\pi$. Hence, adding
together the $\geq d$ neighbors of each of the $\ell$ missing edges, we count
each node at most three times so the number of nodes adjacent to $\pi$ is
still $\Omega(d\ell)$.

The difficulty of the weighted setting is largely captured by the fact that
Lemma 1 fails when $G$ is edge-weighted. As a counterexample, let $\pi$ be a
shortest path consisting of $\ell+1$ nodes and $\ell$ edges of weight
$\varepsilon$. Additionally, consider $d$ nodes, each connected to every node
along $\pi$ with an edge of weight $W>\varepsilon\ell$. A candidate
$d$-initialization $H$ consists of selecting every edge of weight $W$. In this
case, all $\ell$ edges in $\pi$ are missing in $H$, but there are still only
$d\neq\Omega(d\ell)$ nodes adjacent to $\pi$ in $H$.

$d$ nodes$\ell+1$
nodes$W>\varepsilon\ell$$\varepsilon$$\varepsilon$$\varepsilon$$\varepsilon$$\varepsilon$$\varepsilon$$\varepsilon$$\varepsilon$$\pi$
Figure 1: A counterexample to Lemma 1 for weighted graphs.

The fix, as it turns out, is simple in construction but involved in proof. We
simply replace initialization with _light initialization_ , where one must
specifically add the lightest $d$ edges incident to each node. With this, the
proof of Lemma 1 is still not trivial: it remains possible that an external
node can be adjacent to arbitrarily many nodes along $\pi$, so a direct
counting argument fails. However, we show that such occurrences can
essentially be amortized against the rising and falling pattern of missing
edge weights along $\pi$. This leads to a proof that _on average_ an external
node is adjacent to $O(1)$ nodes in $\pi$, which is good enough to push the
proof through. We consider this weighted extension of Lemma 1 to be the main
technical contribution of this work, and we are hopeful that it may be of
independent interest as a structural fact about shortest paths in weighted
graphs.

##  2 Neighborhoods of Weighted Shortest Paths

Here we introduce the extension of Lemma 1. Following the technique in [21],
define a _$d$ -light initialization_ of a weighted graph $G=(V,E,w)$ to be a
subgraph $H$ obtained by including the $d$ lightest edges incident to each
node (or all edges incident to a node of degree less than $d$). Ties between
edges of equal weight are broken arbitrarily; for clarity we assume this
occurs in the background so that we can unambiguously refer to “the lightest
$d$ edges” incident to a node. We prove the weighted analogue of Lemma 1.

######  Theorem 2.1.

If $H$ is a $d$-light initialization of an undirected weighted graph $G$, and
there is a shortest path $\pi$ in $G$ that is missing $\ell$ edges in $H$,
then there are $\Omega(d\ell)$ nodes adjacent to $\pi$ in $H$.

We give some definitions and notation which will be useful in the proof of
Theorem 2.1. Let $s$ and $t$ be the endpoints of a shortest path $\pi$, and
let $M:=\pi\setminus E(H)$ be the set of edges in $\pi$ currently missing in
$H$ so that $|M|=\ell$. For convenience we consider these edges to be oriented
from $s$ to $t$, so we write $(u,v)\in M$ to mean that
$\operatorname{dist}_{G}(s,u)<\operatorname{dist}_{G}(s,v)$ and
$\operatorname{dist}_{G}(u,t)>\operatorname{dist}_{G}(v,t)$. Suppose the edges
in $M$ are labeled in order $e_{1}$, $e_{2}$, …, $e_{\ell}$ where
$e_{i}=(u_{i},v_{i})$, and let $w_{i}$ denote the weight of edge $e_{i}$.
Given $u\in V$, let $N^{*}(u)$ denote the _$d$ -neighborhood_ of $u$ as
follows:

$N^{*}(u):=\left\\{v\in V\ \mid\ (u,v)\text{ is one of the lightest $d$ edges
incident to $u$}\right\\}.$

We will show that the size of the union of the $d$-neighborhoods of the nodes
$u_{1}$, …, $u_{\ell}$ is $\Omega(d\ell)$, that is

$\left|\bigcup\limits_{(u,v)\in M}N^{*}(u)\right|=\Omega(d\ell)$

noting that the above set is a subset of all nodes adjacent to $\pi$. In
particular, the above set may not contain nodes $v^{\prime}$ connected to
$u\in\pi$ by an edge that is 1) among the $d$ lightest incident to
$v^{\prime}$, 2) _not_ among the $d$ lightest incident to $u$. However, the
above set necessarily contains all nodes $v^{\prime}$ which are connected to
some $u_{i}$ or $v_{i}$ by an edge among the $d$ lightest incident to $u_{i}$
or $v_{i}$. We remark that if the $d$-neighborhoods $N^{*}(u_{1})$,
$N^{*}(u_{2})$, …, $N^{*}(u_{\ell})$ are pairwise disjoint, then
$|\bigcup_{(u,v)\in M}N^{*}(u)|=d\ell$, which immediately implies there are at
least $d\ell$ nodes adjacent to $\pi$ in $H$. Hence for the remainder of the
proof, we assume there exist $i$ and $k$ with $1\leq i<k\leq\ell$ such that
$N^{*}(u_{i})\cap N^{*}(u_{k})$ is nonempty. We use the convention that if $a$
and $b$ are integers with $b<a$, then $\sum_{i=a}^{b}f(i)=0$. The following
lemma holds (see Figure 2):

$x$$u_{i}$$u_{k}$$e_{i}$$e_{i+1}$$e_{k-1}$$e_{k}$$s$$t$$\pi$ Figure 2:
Illustration of Lemma 2. The bold dashed curves represent subpaths in $H$.

######  Lemma 2.

Let $\pi$ be a shortest path, let $x\in V$ be a node such that $x\in
N^{*}(u_{i})\cap N^{*}(u_{k})$ for some $1\leq i<k\leq\ell$, and consider the
edges $e_{i},\ldots,e_{k}\in M$ with weights $w_{i},\ldots,w_{k}$. Then

$w_{k}\geq\sum\limits_{i^{\prime}=i+1}^{k-1}w_{i^{\prime}}.$

###### Proof.

Consider the subpath of $\pi$ from $u_{i}$ to $u_{k}$, denoted
$\pi[u_{i}\leadsto u_{k}]$. We have

$\displaystyle\sum\limits_{i^{\prime}=i}^{k-1}w_{i^{\prime}}$
$\displaystyle\leq\text{length}\left(\pi[u_{i}\leadsto u_{k}]\right)$
$\displaystyle\leq w(u_{i},x)+w(x,u_{k})$ ($\pi[u_{i}\leadsto u_{k}]$ is a
shortest path) $\displaystyle\leq w_{i}+w_{k}$

where the last inequality follows from the fact that edges
$(u_{i},x),(x,u_{k})$ are among the $d$ lightest edges incident to $u_{i}$ and
$u_{k}$ respectively (since $x\in N^{*}(u_{i})\cap N^{*}(u_{k})$), but $e_{i}$
and $e_{k}$ are not, since they are omitted from $H$. Lemma 2 follows by
subtracting $w_{i}$ from both sides of the above inequality.

For the next part, for edge $e\in M$, say that $e$ is _pre-heavy_ if its
weight is strictly greater than the preceding edge in $M$, and/or _post-heavy_
if its weight is strictly greater than the following edge in $M$. For
notational convenience, if an edge is not pre-heavy, we say the edge is pre-
light. Similarly, if an edge is not post-heavy, we say the edge is post-light.
By convention, the first edge $e_{1}\in M$ is pre-light and the last edge
$e_{\ell}\in M$ is post-light. We state the following simple lemma; recall
that $|M|=\ell$.

######  Lemma 3.

Either more than $\dfrac{\ell}{2}$ edges in $M$ are pre-light, or more than
$\dfrac{\ell}{2}$ edges in $M$ are post-light.

###### Proof.

Let $S_{1}$ be the set of edges in $M$ which are pre-light, and let $S_{2}$ be
the set of edges in $M$ which are post-light. Note that $e_{1}\in S_{1}$ and
$e_{\ell}\in S_{2}$. For each of the $\ell-1$ pairs of consecutive edges
$(e_{i},e_{i+1})$ in $M$ where $i=1,\ldots,\ell-1$, it is immediate by
definition that either $e_{i}\in S_{2}$ or $e_{i+1}\in S_{1}$ (or both if
$w_{i}=w_{i+1}$). These statements imply $|S_{1}|+|S_{2}|\geq\ell+1$, so at
least one of $S_{1}$ or $S_{2}$ has cardinality at least
$\frac{\ell+1}{2}>\frac{\ell}{2}$.

In the sequel, we assume without loss of generality that more than
$\frac{\ell}{2}$ edges in $M$ are pre-light; the other case is symmetric by
exchanging the endpoints $s$ and $t$ of $\pi$. We can now say the point of the
previous two lemmas: together, they imply that _most_ edges $(u,v)\in M$ have
mostly non-overlapping $d$-neighborhoods $N^{*}(u)$. That is:

######  Lemma 4.

Let $\pi$ be a shortest path. For any node $x\in V$, there exist at most three
nodes $u$ along $\pi$ such that $x\in N^{*}(u)$ and edge $(u,v)\in M$ is pre-
light.

###### Proof.

Suppose for sake of contradiction there exist four nodes $u_{i}$, $u_{a}$,
$u_{b}$, $u_{k}$ with $1\leq i<a<b<k\leq\ell$ such that $x$ belongs to the
$d$-neighborhoods of $u_{i}$, $u_{a}$, $u_{b}$, and $u_{k}$, and the edges
$(u_{i},v_{i})$, $(u_{a},v_{a})$, $(u_{b},v_{b})$, and $(u_{k},v_{k})$ are
pre-light. In particular, we have $k\geq i+3$ and $x\in N^{*}(u_{i})\cap
N^{*}(u_{k})$. By Lemma 2 and the above observation, we have

$w_{k}\geq\sum_{i^{\prime}=i+1}^{k-1}w_{i}^{\prime}=w_{i+1}+\ldots+w_{k-1}\geq
w_{i+1}+w_{k-1}$

By assumption, $e_{k}=(u_{k},v_{k})$ is pre-light, so $w_{k-1}\geq w_{k}$, and
the above inequality implies $w_{k}\geq w_{i+1}+w_{k-1}\geq w_{i+1}+w_{k}$, or
$w_{i+1}=0$. Since edge weights are strictly positive, we have contradiction,
proving Lemma 4.

Finally, define set $X^{*}$ as follows:

$X^{*}:=\bigcup\limits_{\begin{subarray}{c}(u,v)\in M\\\ \text{ is pre-
light}\end{subarray}}N^{*}(u).$

By Lemma 3 and the above pre-heavy assumption, there are more than
$\frac{\ell}{2}$ pre-light edges $(u,v)$, so the multiset containing all
$d$-neighborhoods $N^{*}(u)$ contains more than $\frac{d\ell}{2}$ nodes. By
Lemma 4, any given node is contained in at most three of these
$d$-neighborhoods, implying $|X^{*}|>\dfrac{d\ell}{6}$. Since $X^{*}$ is a
subset of $|\bigcup_{(u,v)\in M}N^{*}(u)|$, we conclude that there are
$\Omega(d\ell)$ nodes adjacent to $\pi$ in $H$. proving Theorem 2.1.

##  3 Spanner Constructions

We show how Theorem 2.1 can be used to construct additive spanners on edge-
weighted graphs. These constructions are not significant departures from prior
work; the main difference is applying Theorem 2.1 in the right place.

###  3.1 Subset and Pairwise Spanners

######  Definition 1 (Pairwise/Subset Additive Spanners).

Given a graph $G=(V,E,w)$ and a set of demand pairs $P\subseteq V\times V$, a
subgraph $H=(V,E_{H}\subseteq E,w)$ is a _$+c$ pairwise spanner_ of $G,P$ if

$\operatorname{dist}_{H}(s,t)\leq\operatorname{dist}_{G}(s,t)+c\text{ for all
}(s,t)\in P.$

When $P=S\times S$ for some $S\subseteq V$, we say that $H$ is a _$+c$ subset
spanner_ of $G,S$.

In the following results, all graphs $G$ are undirected and connected with
(not necessarily integer) edge weights in the interval $(0,W]$, where $W$ is
the maximum edge weight. Let $|V|=n$, let $p=|P|$ denote the number of demand
pairs (for pairwise spanners), and let $\sigma=|S|$ denote the number of
sources (for subset spanners).

######  Theorem 3.1.

Any $n$-node graph $G=(V,E,w)$ with source nodes $S\subseteq V$ has a $+4W$
subset spanner with $O(n\sigma^{1/2})$ edges.

###### Proof.

The construction of the $+4W$ subset spanner $H$ is as follows, essentially
following [21]. Let $d$ be a parameter of the construction, and let $H$ be a
$d$-light initialization of $G$. Then, while there are nodes $s,t\in S$ such
that $\operatorname{dist}_{H}(s,t)>\operatorname{dist}_{G}(s,t)+4W$, choose
any $s\leadsto t$ shortest path $\pi(s,t)$ in $G$ and add all its edges to
$H$. It is immediate that this algorithm terminates with $H$ a $+4W$ subset
spanner of $G$, so we now analyze the number of edges $|E_{H}|$ in the final
subgraph $H$.

At any point in the algorithm, say that an ordered pair of nodes $(s,v)\in
S\times V$ is _near-connected_ if there exists $v^{\prime}$ adjacent to $v$ in
$H$ such that
$\operatorname{dist}_{H}(s,v^{\prime})=\operatorname{dist}_{G}(s,v^{\prime})$.
We then have the following observation

$\operatorname{dist}_{H}(s,v)\leq\operatorname{dist}_{H}(s,v^{\prime})+W=\operatorname{dist}_{G}(s,v^{\prime})+W.$
(1)

When nodes $s,t\in S$ with shortest path $\pi(s,t)$ are considered in the
construction, there are two cases:

  1. 1.

If there is a node $v^{\prime}$ adjacent in $H$ to a node $v\in\pi(s,t)$, and
the pairs $(s,v)$ and $(t,v)$ are near-connected, then we have by triangle
inequality and (1):

$\displaystyle\operatorname{dist}_{H}(s,t)$
$\displaystyle\leq\operatorname{dist}_{H}(s,v)+\operatorname{dist}_{H}(t,v)$
$\displaystyle\leq(\operatorname{dist}_{G}(s,v^{\prime})+W)+(\operatorname{dist}_{G}(t,v^{\prime\prime})+W)$
$\displaystyle=\operatorname{dist}_{G}(s,v^{\prime})+\operatorname{dist}_{G}(t,v^{\prime\prime})+2W$
$\displaystyle\leq\operatorname{dist}_{G}(s,v)+\operatorname{dist}_{G}(t,v)+4W$
$\displaystyle=\operatorname{dist}_{G}(s,t)+4W.$

where the last equality follows from the optimal substructure property of
shortest paths. In this case, the path $\pi(s,t)$ is not added to $H$.

  2. 2.

Otherwise, suppose there is no node $v^{\prime}$ adjacent in $H$ to a node
$v\in\pi(s,t)$ where $(s,v)$ and $(t,v)$ are near-connected. After adding the
path $\pi(s,t)$ to $H$, every such node $v^{\prime}$ becomes near-connected to
both $s$ and $t$. If there are $\ell$ edges in $\pi(s,t)$ currently missing in
$H$, then by Theorem 2.1 we have $\Omega(\ell d)$ nodes adjacent to
$\pi(s,t)$, so $\Omega(\ell d)$ node pairs in $S\times V$ go from not near-
connected to near-connected. Since there are $\sigma n$ node pairs in $S\times
V$, we add a total of $O(\sigma n/d)$ edges to $H$ in this case.

Putting these together, the final size of $H$ is
$|E_{H}|=O\left(nd+\frac{\sigma n}{d}\right)$. Setting $d:=\sqrt{\sigma}$
proves Theorem 3.1.

We now give our constructions for pairwise spanners. The following lemma will
be useful:

######  Lemma 5 ([7]).

Let $a,b>0$ be absolute constants, and suppose there is an algorithm that, on
input $G,P$, produces a subgraph $H$ on $O(n^{a}|P|^{b})$ edges satisfying

$\operatorname{dist}_{H}(s,t)\leq\operatorname{dist}_{G}(s,t)+c$

for at least a constant fraction of the demand pairs $(s,t)\in P$. Then there
is a $+c$ pairwise spanner $H^{\prime}$ of $G,P$ on $O(n^{a}|P|^{b})$ edges.

Using the slack to satisfy only a constant fraction of the demand pairs, we
have the following proofs.

######  Theorem 3.2.

Any graph $G$ with demand pairs $P$ has a $+2W$ pairwise spanner with
$O(np^{1/3})$ edges.

###### Proof.

Let $d$ and $\ell$ be parameters of the construction, and let $H$ be a
$d$-light initialization of $G$. For each demand pair $(s,t)\in P$ whose
shortest path $\pi(s,t)$ is missing at most $\ell$ edges in $H$, add all edges
in $\pi(s,t)$ to $H$. By Theorem 2.1, any remaining demand pair $(s,t)\in P$
has $\Omega(d\ell)$ nodes adjacent to $\pi(s,t)$. Let $R$ be a random sample
of nodes obtained by including each one independently with probability
$1/(\ell d)$; thus, with constant probability or higher, there exists $r\in R$
and $v\in\pi(s,t)$ such that nodes $r$ and $v$ are adjacent in $H$. Add to $H$
a shortest path tree rooted at each $r\in R$. We then compute:

$\displaystyle\operatorname{dist}_{H}(s,t)$
$\displaystyle\leq\operatorname{dist}_{H}(s,r)+\operatorname{dist}_{H}(r,t)$
$\displaystyle=\operatorname{dist}_{G}(s,r)+\operatorname{dist}_{G}(r,t)$
$\displaystyle\leq\operatorname{dist}_{G}(s,v)+\operatorname{dist}_{G}(v,t)+2W$
$\displaystyle=\operatorname{dist}_{G}(s,t)+2W.$

The distance for each pair $(s,t)\in P$ is approximately preserved in $H$ with
at least a constant probability, which is sufficient for Lemma 5. The number
of edges in the final subgraph $H$ is

$|E(H)|=O(nd+\ell p+n^{2}/(\ell d));$

setting $\ell=n/p^{2/3}$ and $d=p^{1/3}$ proves Theorem 3.2.

######  Theorem 3.3.

Any graph $G$ with demand pairs $P$ has a $+4W$ pairwise spanner with
$O(np^{2/7})$ edges.

###### Proof.

Let $d$ and $\ell$ be parameters of the construction, and let $H$ be a
$d$-light initialization of $G$. For each demand pair $(s,t)\in P$ whose
shortest path $\pi(s,t)$ is missing at most $\ell$ edges in $H$, add all edges
in $\pi(s,t)$ to $H$. To handle each $(s,t)\in P$ whose shortest path
$\pi(s,t)$ is missing at least $n/d^{2}$ edges in $H$, we let $R_{1}$ be a
random sample of nodes obtained by including each node independently with
probability $d^{2}/n$, then add a shortest path tree rooted at each $r\in
R_{1}$ to $H$. By an identical analysis to Theorem 3.2, for each such pair,
with constant probability or higher we have

$\operatorname{dist}_{H}(s,t)\leq\operatorname{dist}_{G}(s,t)+2W.$

Finally, we consider the “intermediate” pairs $(s,t)\in P$ whose shortest path
$\pi(s,t)$ is missing more than $\ell$ but fewer than $n/d^{2}$ edges in $H$.
We add the first and last $\ell$ missing edges in $\pi(s,t)$ to the spanner;
we will refer to the _prefix_ (resp.  _suffix_) of $\pi(s,t)$ to mean the
shortest prefix (suffix) containing these $\ell$ missing edges. By Theorem
2.1, there are $\Omega(\ell d)$ nodes adjacent to the prefix and $\Omega(\ell
d)$ nodes adjacent to the suffix. Let $R_{2}$ be a random sample of nodes
obtained by including each node with probability $1/(\ell d)$, and for each
pair $r,r^{\prime}\in R_{2}$, add to $H$ all edges in the shortest $r\leadsto
r^{\prime}$ path in $G$ among the paths that are missing at most $n/d^{2}$
edges (ignore any pair $r,r^{\prime}$ if no such path exists). With constant
probability or higher, we sample $r,r^{\prime}$ adjacent to nodes
$v,v^{\prime}$ in the prefix, suffix respectively, in which case we have:

$\displaystyle\operatorname{dist}_{H}(s,t)$
$\displaystyle\leq\operatorname{dist}_{H}(s,v)+\operatorname{dist}_{H}(v,v^{\prime})+\operatorname{dist}_{H}(v^{\prime},t)$
$\displaystyle=\operatorname{dist}_{G}(s,v)+\operatorname{dist}_{H}(v,v^{\prime})+\operatorname{dist}_{G}(v^{\prime},t)$
$\displaystyle\leq\operatorname{dist}_{G}(s,v)+\operatorname{dist}_{H}(r,r^{\prime})+2W+\operatorname{dist}_{G}(v^{\prime},t).$

Notice that $\operatorname{dist}_{H}(r,r^{\prime})\leq
2W+\operatorname{dist}_{G}(v,v^{\prime})$, due to the existence of the path
$r\circ\pi(s,t)[v,v^{\prime}]\circ r^{\prime}$ which is indeed missing $\leq
n/d^{2}$ edges. Thus we may continue:

$\displaystyle\leq\operatorname{dist}_{G}(s,v)+\operatorname{dist}_{G}(v,v^{\prime})+4W+\operatorname{dist}_{G}(v^{\prime},t)$
$\displaystyle=\operatorname{dist}_{G}(s,t)+4W.$

The distance for each pair $(s,t)\in P$ is approximately preserved in $H$ with
at least constant probability, which again suffices by Lemma 5, and the number
of edges in $H$ is

$|E(H)|=O\left(nd+p\ell+n^{3}/(\ell^{2}d^{4})\right).$

Setting $\ell=n/p^{5/7}$ and $d=p^{2/7}$ completes the proof of Theorem 3.3.

######  Theorem 3.4.

Any graph $G$ with demand pairs $P$ has a $+8W$ pairwise spanner containing
$O(np^{1/4})$ edges.

###### Proof.

Let $\ell,d$ be parameters of the construction and let $H$ be a $d$-light
initialization of $G$. For each $(s,t)\in P$ whose shortest path $\pi(s,t)$ is
missing $\leq\ell$ edges in $H$, add all edges in $\pi(s,t)$ to $H$.
Otherwise, like before, we add the first and last $\ell$ missing edges of
$\pi(s,t)$ to $H$ (prefix and suffix). Then, randomly sample a set $R$ by
including each node with probability $1/(\ell d)$, and use Theorem 3.1 to add
a $+4W$ subset spanner on the nodes in $R$. By Theorem 2.1, the prefix and
suffix each have $\Omega(\ell d)$ adjacent nodes. Thus, with constant
probability or higher, we sample $r,r^{\prime}\in R$ adjacent to
$v,v^{\prime}$ in the added prefix and suffix respectively. We then compute:

$\displaystyle\operatorname{dist}_{H}(s,t)$
$\displaystyle\leq\operatorname{dist}_{H}(s,v)+\operatorname{dist}_{H}(v,v^{\prime})+\operatorname{dist}_{H}(v^{\prime},t)$
$\displaystyle\leq\operatorname{dist}_{G}(s,v)+\operatorname{dist}_{H}(v,v^{\prime})+\operatorname{dist}_{G}(v^{\prime},t)$
$\displaystyle\leq\operatorname{dist}_{G}(s,v)+\operatorname{dist}_{H}(r,r^{\prime})+2W+\operatorname{dist}_{G}(v^{\prime},t)$
$\displaystyle\leq\operatorname{dist}_{G}(s,v)+\operatorname{dist}_{G}(r,r^{\prime})+6W+\operatorname{dist}_{G}(v^{\prime},t)$
$\displaystyle\leq\operatorname{dist}_{G}(s,v)+\operatorname{dist}_{G}(v,v^{\prime})+8W+\operatorname{dist}_{G}(v^{\prime},t)$
$\displaystyle=\operatorname{dist}_{G}(s,t)+8W.$

Again, the distance for each pair $(s,t)\in P$ is approximately preserved in
$H$ with at least constant probability, which suffices by Lemma 5. The number
of edges in $H$ is

$|E(H)|=O\left(nd+p\ell+n^{3/2}/\sqrt{\ell d}\right).$

Setting $\ell=n/p^{3/4}$ and $d=p^{1/4}$ completes the proof of Theorem 3.4.

##  4 All-pairs Additive Spanners

We now turn to the _all-pairs_ setting, i.e., demand pairs $P=V\times V$. We
use the following lemma from [7]:

######  Lemma 6 ([7]).

Let $G$ be a graph, and suppose one can choose a function $\pi$ that
associates each node pair to a path between them with the following
properties:

  * •

for all $(s,t)$ the length of the path $\pi(s,t)$ (i.e., the sum of its edge
weights) is $\leq\operatorname{dist}_{G}(s,t)+k$,

  * •

$\pi$ depends only on the input graph $G$ and the number of demand pairs $|P|$
(but not otherwise on the contents of $P$), and

  * •

for some parameter $p^{*}$ and any $|P|\geq p^{*}$ demand pairs, we have

$\left|\bigcup\limits_{(s,t)\in P}\pi(s,t)\right|<|P|.$

Then there is an all-pairs $k$-additive spanner of $G$ containing $\leq p^{*}$
edges.

Notice that all the above pairwise spanner constructions are _demand-
oblivious_ – that is, the approximate shortest paths analyzed in order to
preserve each demand pair in the spanner depend on the random bits of the
construction, which in turn depend on the number of demand pairs $|P|$, but
they do not otherwise depend on the contents of $P$. See [7] for more
discussion of this property. Thus we may apply Lemma 6 as follows. For the
$+2W$ pairwise bound of $O(np^{1/3})$ provided in Theorem 3.2, we note that
the bound is $<p$ for $p=\Omega(n^{3/2})$ demand pairs (and a sufficiently
large constant in the $\Omega$). Hence, taking $p^{*}=\Theta(n^{3/2})$, Lemma
6 says:

######  Theorem 4.1.

Every graph has a $+2W$ spanner on $O(n^{3/2})$ edges.

Identical logic applied to Theorems 3.3 and 3.4 gives:

######  Theorem 4.2.

Every $n$-node graph has a $+4W$ spanner on $O(n^{7/5})$ edges.

######  Theorem 4.3.

Every $n$-node graph has a $+8W$ additive spanner on $O(n^{4/3})$ edges.

##  5 Conclusions and Open Problems

We have shown that most important unweighted additive spanner constructions
have natural weighted analogues. At present, the exceptions are the $+4W$
subset spanner on $O(n|S|^{1/2})$ edges (which should probably have only $+2W$
error) and the $+8W$ all-pairs/pairwise spanners (which should probably have
only $+6W$ error). Closing these error gaps is an interesting open problem. It
would also be interesting to obtain weighted analogues of related concepts,
most notably, the Thorup-Zwick emulators [29], which are optimal [2] in
essentially the same way that the 6-additive spanner on $O(n^{4/3})$ edges is
optimal.

Finally, as mentioned earlier, it would be interesting to find constructions
of _purely_ additive spanners parametrized by some other statistic besides the
maximum edge weight $W$; a natural parameter is $W(u,v)$, the maximum edge
weight along a shortest $u$-$v$ path.

## References

  * [1] Amir Abboud and Greg Bodwin.  The 4/3 additive spanner exponent is tight.  Journal of the ACM (JACM), 64(4):1–20, 2017.
  * [2] Amir Abboud, Greg Bodwin, and Seth Pettie.  A hierarchy of lower bounds for sublinear additive spanners.  In Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 568–576. Society for Industrial and Applied Mathematics, 2017.
  * [3] Donald Aingworth, Chandra Chekuri, Piotr Indyk, and Rajeev Motwani.  Fast estimation of diameter and shortest paths (without matrix multiplication).  SIAM Journal on Computing, 28:1167–1181, 04 1999.
  * [4] Ingo Althöfer, Gautam Das, David Dobkin, and Deborah Joseph.  Generating sparse spanners for weighted graphs.  In Scandinavian Workshop on Algorithm Theory (SWAT), pages 26–37, Berlin, Heidelberg, 1990. Springer Berlin Heidelberg.
  * [5] Surender Baswana, Telikepalli Kavitha, Kurt Mehlhorn, and Seth Pettie.  Additive spanners and ($\alpha$, $\beta$)-spanners.  ACM Transactions on Algorithms (TALG), 7(1):5, 2010.
  * [6] Greg Bodwin.  Linear size distance preservers.  In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 600–615. Society for Industrial and Applied Mathematics, 2017.
  * [7] Greg Bodwin.  A note on distance-preserving graph sparsification.  arXiv preprint arXiv:2001.07741, 2020.
  * [8] Greg Bodwin and Virginia Vassilevska Williams.  Better distance preservers and additive spanners.  In Proceedings of the Twenty-seventh Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 855–872. Society for Industrial and Applied Mathematics, 2016.
  * [9] Leizhen Cai and J. Mark Keil.  Computing visibility information in an inaccurate simple polygon.  International Journal of Computational Geometry & Applications, 7(6):515–538, 1997.
  * [10] Hsien-Chih Chang, Pawel Gawrychowski, Shay Mozes, and Oren Weimann.  Near-Optimal Distance Emulator for Planar Graphs.  In Proceedings of 26th Annual European Symposium on Algorithms (ESA 2018), volume 112, pages 16:1–16:17, 2018.
  * [11] Shiri Chechik.  New additive spanners.  In Proceedings of the twenty-fourth annual ACM-SIAM symposium on Discrete algorithms (SODA), pages 498–512. Society for Industrial and Applied Mathematics, 2013.
  * [12] Don Coppersmith and Michael Elkin.  Sparse sourcewise and pairwise distance preservers.  SIAM Journal on Discrete Mathematics, 20(2):463–501, 2006.
  * [13] Marek Cygan, Fabrizio Grandoni, and Telikepalli Kavitha.  On pairwise spanners.  In Proceedings of 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013), volume 20, pages 209–220, 2013.
  * [14] Andrew Dobson and Kostas E Bekris.  Sparse roadmap spanners for asymptotically near-optimal motion planning.  The International Journal of Robotics Research, 33(1):18–47, 2014\.
  * [15] Michael Elkin.  Computing almost shortest paths.  ACM Transactions on Algorithms (TALG), 1(2):283–323, 2005.
  * [16] Michael Elkin, Yuval Gitlitz, and Ofer Neiman.  Almost shortest paths and PRAM distance oracles in weighted graphs.  arXiv preprint arXiv:1907.11422, 2019.
  * [17] Michael Elkin and David Peleg.  $(1+\epsilon,\beta)$-spanner constructions for general graphs.  SIAM Journal on Computing, 33(3):608–631, March 2004.
  * [18] Shang-En Huang and Seth Pettie.  Lower bounds on sparse spanners, emulators, and diameter-reducing shortcuts.  In Proceedings of 16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT), pages 26:1–26:12, 2018.
  * [19] Telikepalli Kavitha.  New pairwise spanners.  Theory of Computing Systems, 61(4):1011–1036, Nov 2017.
  * [20] Telikepalli Kavitha and Nithin M. Varma.  Small stretch pairwise spanners and approximate $d$-preservers.  SIAM Journal on Discrete Mathematics, 29(4):2239–2254, 2015.
  * [21] Mathias Bæk Tejs Knudsen.  Additive spanners: A simple construction.  In Scandinavian Workshop on Algorithm Theory (SWAT), pages 277–281. Springer, 2014.
  * [22] Arthur Liestman and Thomas Shermer.  Additive graph spanners.  Networks, 23:343 – 363, 07 1993.
  * [23] James D Marble and Kostas E Bekris.  Asymptotically near-optimal planning with probabilistic roadmap spanners.  IEEE Transactions on Robotics, 29(2):432–444, 2013.
  * [24] Giri Narasimhan and Michiel Smid.  Geometric Spanner Networks.  Cambridge University Press, New York, NY, USA, 2007.
  * [25] David Peleg and Alejandro A. Schäffer.  Graph spanners.  Journal of Graph Theory, 13(1):99–116, 1989.
  * [26] David Peleg and Eli Upfal.  A trade-off between space and efficiency for routing tables.  Journal of the ACM (JACM), 36(3):510–530, 1989.
  * [27] Seth Pettie.  Low distortion spanners.  ACM Transactions on Algorithms (TALG), 6(1):7, 2009.
  * [28] Oren Salzman, Doron Shaharabani, Pankaj K Agarwal, and Dan Halperin.  Sparsification of motion-planning roadmaps by edge contraction.  The International Journal of Robotics Research, 33(14):1711–1725, 2014.
  * [29] Mikkel Thorup and Uri Zwick.  Spanners and emulators with sublinear distance errors.  In Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 802–809. Society for Industrial and Applied Mathematics, 2006.
  * [30] David P Woodruff.  Additive spanners in nearly quadratic time.  In International Colloquium on Automata, Languages, and Programming, pages 463–474. Springer, 2010.


In this section we consider a particular heat engine which is consisted of $n$
subsequent ergotropy extractions such that working body evolution is
following:

$(E_{0},\alpha_{0})\xrightarrow{H}(E^{\prime}_{1},\alpha^{\prime}_{1})\xrightarrow{B}(E_{1},\alpha_{1})\xrightarrow{H}(E^{\prime}_{2},\alpha^{\prime}_{2})\xrightarrow{B}(E_{2},\alpha_{2})\xrightarrow{H}\dots\xrightarrow{H}(E^{\prime}_{n},\alpha^{\prime}_{n})\xrightarrow{B}(E_{n},\alpha_{n})\xrightarrow{C}(E_{0},\alpha_{0}).$
(185)

We assume further that each step $H$ is the ergotropy extraction, i.e. $\Delta
R_{S}>0$, and each step $B$ is ergotropy storing such that $W>0$.

###  G.1 Extremal protocol

Let us firstly consider a particular (extremal) protocol such that any heat-
stroke $\hat{U}_{SH}^{(k)}$ is the extremal thermal process and any work-
stroke $\hat{U}_{SB}^{(k)}$ is the maximal ergotropy storing. For this case
energies of the working body are equal to:

$\begin{split}E^{\prime}_{k}=a_{H}^{k}(\omega-
E_{0})\equiv\tilde{E}^{\prime}_{k},\ E_{k}\equiv\omega-a_{H}^{k}(\omega-
E_{0})=\tilde{E}_{k},\end{split}$ (186)

and the total sum of energy changes are given by:

$\begin{split}\Delta R_{S}^{H}&=\sum_{k=0}^{n}\Delta
R_{0}(\tilde{E}_{k})=\sum_{k=0}^{n}[2a_{H}(\omega-\tilde{E}_{k})-\omega]=\frac{2a_{H}(\omega-
E_{0})(1-a_{H}^{n})}{1-a_{H}}-n\omega\equiv\Delta R_{0}^{n}(E_{0}),\\\ \Delta
P_{S}^{H}&=\sum_{k=0}^{n}\Delta
P_{0}(\tilde{E}_{k})=\sum_{k=0}^{n}(1-a_{H})(\omega-\tilde{E}_{k})=(\omega-
E_{0})(1-a_{H}^{n})\equiv\Delta P_{0}^{n}(E_{0}),\\\ \Delta E_{S}^{B}&=-\Delta
R_{0}^{n}(E_{0}).\end{split}$ (187)

###  G.2 General protocol

####  G.2.1 Heat- and work-stroke

From the assumptions that all hot bath steps are the ergotropy extractions,
from which follows that in general each of them can be parameterized as
follows

$\begin{split}&\Delta R_{S}^{H_{k}}=\Delta
R_{0}(E_{k})-R_{k}-g(\lambda_{k}),\\\ &\Delta P_{S}^{H_{k}}=\Delta
P_{0}(E_{k})+R_{k}+g(\lambda_{k})-h(\lambda_{k}).\end{split}$ (188)

In order to fulfill this condition, any energy
$E_{k}<\omega(1-\frac{1}{2a_{H}})$ for $k=1,2,\dots,n-1$.

For work-strokes we assume that each of them leads to the positive work, i.e.
$W_{k}=-\Delta E_{S}^{B_{k}}>0$, then one can write down:

$\begin{split}\Delta E_{S}^{B_{k}}=-\Delta
R_{0}(E_{k})+g(\lambda_{k})+\delta_{k}.\end{split}$ (189)

We assume as previously that each $\lambda_{k}\in(\lambda_{0},1]$ and
$\delta_{k}\in[0,\Delta R_{0}(E_{k})-g(\lambda_{k}))$, however, we notice that
the condition $E_{k}<\omega(1-\frac{1}{2a_{H}})$ imposes here some additional
constraints. Nevertheless, for arbitrary protocol:

$E_{k}=E_{k-1}+\Delta R_{S}^{H_{k-1}}+\Delta P_{S}^{H_{k-1}}+\Delta
E_{S}^{B_{k-1}}=E_{k-1}+\Delta
P_{0}(E_{k-1})+[g(\lambda_{k-1})-h(\lambda_{k-1})+\delta_{k-1},$ (190)

where the last term is always non-negative. For $k=1$ we get

$E_{1}=E_{0}+\Delta
P_{0}(E_{0})+[g(\lambda_{0})-h(\lambda_{0})+\delta_{0}]=\tilde{E}_{1}+[g(\lambda_{0})-h(\lambda_{0})+\delta_{0}]\geq\tilde{E}_{1}.$
(191)

Further, if $\tilde{E}_{k-1}\leq E_{k-1}$ then

$\begin{split}\tilde{E}_{k}&=\tilde{E}_{k-1}+\Delta
P_{0}(\tilde{E}_{k-1})\leq\tilde{E}_{k-1}+\Delta
P_{0}(\tilde{E}_{k-1})+[g(\lambda_{0})-h(\lambda_{0})+\delta_{0}]\\\ &\leq
E_{k-1}+\Delta
P_{0}(E_{k-1})+[g(\lambda_{0})-h(\lambda_{0})+\delta_{0}]=E_{k},\end{split}$
(192)

since $\Delta P_{0}(E)$ is a decreasing function with respect to $E$. Finally,
we prove that $\tilde{E}_{k}\leq E_{k}$ for $k=1,2,\dots,n$, where equality is
for all $\lambda_{k}=1$ and $\delta_{k}=0$. Having this we further assume that
condition $E_{k}<\omega(1-\frac{1}{2a_{H}})$ is at least fulfilled for the
extremal protocol (i.e. when $E_{k}=\tilde{E}_{k}$), and we put:

$\tilde{E}_{k}=E_{k}+s_{k}(\vec{\lambda},\vec{\delta}),$ (193)

where $s_{k}(\vec{\lambda},\vec{\delta})\geq 0$. Finally, we can write down

$\begin{split}\Delta R_{S}^{H}&=\sum_{k=1}^{n}\Delta
R_{S}^{H_{k}}=\sum_{k=1}^{n}[\Delta
R_{0}(\tilde{E}_{k}-s_{k}(\vec{\lambda},\vec{\delta}))-R_{k}-g(\lambda_{k})]\\\
&=\Delta
R_{0}^{n}(E_{0})-2a_{H}s(\vec{\lambda},\vec{\delta})-\sum_{k=1}^{n}[R_{k}+g(\lambda_{k})],\\\
\Delta P_{S}^{H}&=\sum_{k=1}^{n}\Delta P_{S}^{H_{k}}=\sum_{k=1}^{n}[\Delta
P_{0}(\tilde{E}_{k}-s_{k}(\vec{\lambda},\vec{\delta}))+R_{k}+g(\lambda_{k})-h(\lambda_{k})]\\\
&=\Delta
P_{0}^{n}(E_{0})-(1-a_{H})s(\vec{\lambda},\vec{\delta})+\sum_{k=1}^{n}[R_{k}+g(\lambda_{k})-h(\lambda_{k})],\\\
\Delta E_{S}^{B}&=\sum_{k=1}^{n}\Delta E_{S}^{B_{k}}=\sum_{k=1}^{n}[-\Delta
R_{0}(\tilde{E}_{k}-s_{k}(\vec{\lambda},\vec{\delta}))+g(\lambda_{k})+\delta_{k}]\\\
&=-\Delta
R_{0}^{n}(E_{0})+2a_{H}s(\vec{\lambda},\vec{\delta})+\sum_{k=1}^{n}[g(\lambda_{k})+\delta_{k}],\end{split}$
(194)

where
$s(\vec{\lambda},\vec{\delta})=\sum_{k=1}^{n}s_{k}(\vec{\lambda},\vec{\delta})\geq
0$. For the extremal protocol, such that each $\lambda_{k}=1$ and
$\delta_{k}=0$, then $s(\vec{\lambda},\vec{\delta})=0$.

####  G.2.2 Closing the cycle condition

For the many-step engine necessary condition for closing the cycle in this
case generalize to:

$E_{n}\geq\omega-\frac{E_{0}}{a_{C}}\iff
F(\vec{\lambda},\vec{\delta})\geq\omega-E_{0}(1+\frac{1}{a_{C}})-\Delta
P_{0}^{n}(E_{0})+(1-a_{H})s(\vec{\lambda},\vec{\delta})\equiv
K(E_{0},\vec{\lambda},\vec{\delta}),$ (195)

where

$F(\vec{\lambda},\vec{\delta})=\sum_{k=1}^{n}[g(\lambda_{k})-h(\lambda_{k})+\delta_{k}]\geq
0.$ (196)

####  G.2.3 Temperatures regimes

We have following constraints for energies: $E_{k}<\omega(1-\frac{1}{2a_{H}})$
for all $k=1,2,\dots,n-1$ and $\tilde{E}_{k}\leq E_{k}$. In particular, the
energy $E_{n-1}$ just before the last ergotropy extraction has to satisfied
those inequalities, from which follows that
$\tilde{E}_{n-1}<\omega(1-\frac{1}{2a_{H}})$. From this one can derive the
minimal possible value of $E_{0}$ which is given by

$E_{0}<\omega(1-\frac{1}{2a_{H}^{n}}).$ (197)

On the other hand
$a_{H}^{n}>\frac{1}{2-\frac{2E_{0}}{\omega}}\geq\frac{1}{2}$, what constitutes
the possible range of hot temperature at which engine can operate, i.e.

$a_{H}\in(2^{-n},1].$ (198)

The range for cold temperature can be derive as follows. Firstly, let us
estimate an upper bound for the energy $E_{n}$, i.e.

$\begin{split}&E_{n}=E_{n-1}+\Delta
P_{0}(E_{n-1})+g(\lambda_{n-1})-h(\lambda_{n-1})+\delta_{n-1}\\\
&<E_{n-1}+\Delta P_{0}(E_{n-1})+\Delta R_{0}(E_{n-1})=a_{H}(\omega-
E_{n-1})\leq a_{H}(\omega-\tilde{E}_{n-1})=a_{H}^{n}(\omega-
E_{0}),\end{split}$ (199)

where we used a fact that $g(\lambda_{k})-h(\lambda_{k})+\delta_{k}<\Delta
R_{0}(E_{k})$. Further, in order to close the cycle the following has to be
satisfied:

$E_{n}\geq\omega-\frac{E_{0}}{a_{C}}\iff a_{C}\leq\frac{E_{0}}{\omega-E_{n}}.$
(200)

Although, we have

$\frac{E_{0}}{\omega-E_{n}}<\frac{E_{0}}{\omega-a_{H}^{n}(\omega-
E_{0})}<2-a_{H}^{-n},$ (201)

where we used Eq. (197). Finally, the possible range of cold temperatures for
a fixed $a_{H}$ is given by the set

$a_{C}\in[0,2-a_{H}^{-n}),$ (202)

what gives us the condition

$\displaystyle e^{n\beta_{H}\omega}+e^{-\beta_{C}\omega}<2.$ (203)

###  G.3 Maximal efficiency and work production

The upper bound for the many-step efficiency can be estimated as follows

$\begin{split}\eta(E_{0},\vec{\delta},\vec{\lambda})&=\frac{\Delta
R_{0}^{n}(E_{0})-2a_{H}s(\vec{\lambda},\vec{\delta})-\sum_{k=1}^{n}[g(\lambda_{k})+\delta_{k}]}{\Delta
R_{0}^{n}(E_{0})+\Delta
P_{0}^{n}(E_{0})-(1+a_{H})s(\vec{\lambda},\vec{\delta})-\sum_{k=1}^{n}h(\lambda_{k})}\\\
&\leq\frac{\Delta
R_{0}^{n}(E_{0})-2a_{H}s(\vec{\lambda},\vec{\delta})-F(\vec{\lambda},\vec{\delta})}{\Delta
R_{0}^{n}(E_{0})+\Delta
P_{0}^{n}(E_{0})-(1+a_{H})s(\vec{\lambda},\vec{\delta})}.\end{split}$ (204)

Furthermore, one can prove that for any $x\geq 0$

$\begin{split}a_{H}\leq 1&\Rightarrow(1+a_{H})\Delta R^{n}_{0}(E_{0})\leq
2a_{H}(\Delta R^{n}_{0}(E_{0})+\Delta P^{n}_{0}(E_{0}))\\\
&\Rightarrow\frac{\Delta R^{n}_{0}(E_{0})-2a_{H}x}{\Delta
R^{n}_{0}(E_{0})+\Delta P^{n}_{0}(E_{0})-(1+a_{H})x}\leq\frac{\Delta
R^{n}_{0}(E_{0})}{\Delta R^{n}_{0}(E_{0})+\Delta
P^{n}_{0}(E_{0})},\end{split}$ (205)

what leads to the algebraic bound for the efficiency, i.e.

$\begin{split}&\eta(E_{0},\vec{\delta},\vec{\lambda})\leq\frac{\Delta
R_{0}^{n}(E_{0})-2a_{H}s(\vec{\lambda},\vec{\delta})-F(\vec{\lambda},\vec{\delta})}{\Delta
R_{0}^{n}(E_{0})+\Delta
P_{0}^{n}(E_{0})-(1+a_{H})s(\vec{\lambda},\vec{\delta})}\\\ &\leq\frac{\Delta
R_{0}^{n}(E_{0})-2a_{H}s(\vec{\lambda},\vec{\delta})}{\Delta
R_{0}^{n}(E_{0})+\Delta
P_{0}^{n}(E_{0})-(1+a_{H})s(\vec{\lambda},\vec{\delta})}\leq\frac{\Delta
R^{n}_{0}(E_{0})}{\Delta R^{n}_{0}(E_{0})+\Delta
P^{n}_{0}(E_{0})}.\end{split}$ (206)

Work production of the engine is given by:

$P(E_{0},\vec{\delta},\vec{\lambda})=\Delta
R_{0}^{n}(E_{0})-2a_{H}s(\vec{\lambda},\vec{\delta})-\sum_{k=1}^{n}[g(\lambda_{k})+\delta_{k}].$
(207)

Once again we split the problem into two parts: 1)
$E_{0}\geq\varepsilon^{n}_{0}$, and 2) $E_{0}<\varepsilon^{n}_{0}$, however,
in this case

$\varepsilon^{n}_{0}=\frac{\omega a_{C}a_{H}^{n}}{1+a_{C}a_{H}^{n}}.$ (208)

1) For the first situation if each $\lambda_{k}=1$ and $\delta_{k}=0$, we have
$K_{n}(E_{0},\vec{\lambda},\vec{\delta})\leq 0$ and
$F(\vec{\lambda},\vec{\delta})=0$, what makes the condition (195) fulfilled,
and leads to the maximal value of efficiency:

$\begin{split}\max_{E_{0},\vec{\delta},\vec{\lambda}}[\eta(E_{0},\vec{\delta},\vec{\lambda})]=\max_{E_{0}}[\frac{\Delta
R_{0}^{n}(E_{0})}{\Delta R_{0}^{n}(E_{0})+\Delta
P_{0}^{n}(E_{0})}=\frac{\Delta R_{0}^{n}(\varepsilon^{n}_{0})}{\Delta
R_{0}^{n}(\varepsilon^{n}_{0})+\Delta
P_{0}^{n}(\varepsilon^{n}_{0})}\equiv\eta_{n},\end{split}$ (209)

where

$\begin{split}&\Delta
R_{0}^{n}(\varepsilon^{n}_{0})=\omega[\frac{2a_{H}(1-a_{H}^{n})}{(1+a_{C}a_{H}^{n})(1-a_{H})}-n],\\\
&\Delta R_{0}^{n}(\varepsilon^{n}_{0})+\Delta
P_{0}^{n}(\varepsilon^{n}_{0})=\omega[\frac{(1-a_{H}^{n})(1+a_{H})}{(1+a_{C}a_{H}^{n})(1-a_{H})}-n],\end{split}$
(210)

such that

$\eta_{n}=1-\frac{(1-a_{H})(1-a_{H}^{n})}{(1-a_{H}^{n})(1+a_{H})-n(1+a_{C}a_{H}^{n})(1-a_{H})}.$
(211)

According to above formula, the maximal value of the work production is given
by:

$\max_{E_{0},\vec{\delta},\vec{\lambda}}[P(E_{0},\vec{\delta},\vec{\lambda})]=\Delta
R_{0}^{n}(\varepsilon^{n}_{0})=\omega[\frac{2a_{H}(1-a_{H}^{n})}{(1+a_{C}a_{H}^{n})(1-a_{H})}-n]\equiv
P_{n}.$ (212)

2) For the second subset of possible initial energy we obtain:

$\begin{split}&\eta(E_{0},\vec{\delta},\vec{\lambda})\leq\frac{\Delta
R_{0}^{n}(E_{0})-2a_{H}s(\vec{\lambda},\vec{\delta})-F(\vec{\lambda},\vec{\delta})}{\Delta
R_{0}^{n}(E_{0})+\Delta
P_{0}^{n}(E_{0})-(1+a_{H})s(\vec{\lambda},\vec{\delta})}\leq\frac{\Delta
R_{0}^{n}(E_{0})-F(\vec{\lambda},\vec{\delta})+(1-a_{H})s(\vec{\lambda},\vec{\delta})}{\Delta
R_{0}^{n}(E_{0})+\Delta P_{0}^{n}(E_{0})}\\\ &\leq 1-\frac{\omega-
E_{0}(1+\frac{1}{a_{C}})}{\Delta R_{0}^{n}(E_{0})+\Delta
P_{0}^{n}(E_{0})}=1-\frac{(\omega-E_{0}(1+1/a_{C}))(1-a_{H})}{(\omega-
E_{0})(1-a_{H}^{n})(1+a_{H})-\omega n(1-a_{H})}\equiv
f_{n}(E_{0}).\end{split}$ (213)

One can further show that the function $f_{n}(E_{0})$ is increasing with
respect to $E_{0}$ if and only if

$a_{C}<\frac{(1-a_{H}^{n})(1+a_{H})}{n(1-a_{H})}-1.$ (214)

However, in order to close the cycle we have

$a_{C}<2-a_{H}^{-n}\implies
a_{C}<\frac{(1-a_{H}^{n})(1+a_{H})}{n(1-a_{H})}-1.$ (215)

Finally, one can show that whenever $E_{0}<\varepsilon^{n}_{0}$, then

$\eta(E_{0},\vec{\delta},\vec{\lambda})\leq
f_{n}(E_{0})<f_{n}(\varepsilon^{n}_{0})=1-\frac{(1-a_{H})(1-a_{H}^{n})}{(1-a_{H}^{n})(1+a_{H})-n(1+a_{C}a_{H}^{n})(1-a_{H})}=\eta_{n}.$
(216)

In analogy, the work production can be estimated by the condition (195), i.e.

$\begin{split}&P(E_{0},\vec{\delta},\vec{\lambda})=\Delta
R_{0}^{n}(E_{0})-2a_{H}s(\vec{\lambda},\vec{\delta})-\sum_{k=1}^{n}[g(\lambda_{k})+\delta_{k}]\\\
&\leq\Delta R_{0}^{n}(E_{0})+\Delta
P_{0}^{n}(E_{0})-\omega+E_{0}(1+\frac{1}{a_{C}})-(1+a_{H})s(\vec{\lambda},\vec{\delta})-\sum_{k=1}^{n}h(\lambda_{k})\\\
&\leq(\omega-
E_{0})(1-a_{H}^{n})\frac{1+a_{H}}{1-a_{H}}-n\omega-\omega+E_{0}(1+\frac{1}{a_{C}})\\\
&=\omega(1-a_{H}^{n})\frac{1+a_{H}}{1-a_{H}}-n\omega-\omega+E_{0}[1+\frac{1}{a_{C}}-\frac{(1-a_{H}^{n})(1+a_{H})}{1-a_{H}}\leq\omega[\frac{2a_{H}(1-a_{H}^{n})}{(1-a_{H})(1+a_{C}a_{H}^{n})}-n].\end{split}$
(217)

###  G.4 Maximal efficiency according to the number of steps

We start by rewriting the general formula for the efficiency as

$\eta_{n}=\frac{A+B}{C+D},$ (218)

where $A=2a_{H}-(1+a_{H}a_{C})$, $C=A+(1-a_{H})$,
$B=2S(n)-(n-1)-a_{H}a_{c}(na_{H}^{n-1}-1)$ and
$D=B+S(n)\frac{1-a_{H}}{a_{H}}$, with
$S(n)=\frac{a_{H}^{2}(1-a_{H}^{n-1})}{1-a_{H}}$ for $n>1$, and $S(1)=0$.

Note that, for $n=1$, $B=D=0$. Therefore, to obtain $\eta_{n}\leq\eta_{1}$ it
is enough to show that $\frac{A}{C}\geq\frac{A+B}{C+D}$, which is equivalent
to $\frac{A}{C}\geq\frac{B}{D}$ for non-zero $C$ and $D$. This in turn demands
that
$(2a_{H}-(1-a_{H}a_{C}))S(n)\frac{1-a_{H}}{a_{H}}\geq(1-a_{H})(2S(n)-(n-1)-a_{H}a_{C}(na_{H}^{n-1}-1))$.
It is equivalent to showing that

$f(n,a_{H},a_{C})=n-1+a_{H}a_{C}(na_{H}^{n-1}-1)-\frac{a_{H}(1-a_{H}^{n-1})}{1-a_{H}}(1-a_{H}a_{C})\geq
0,$ (219)

where we exploited the form of $S(n)$.

First, let us notice that $f(n,a_{H},a_{C})\geq f(n,a_{H},0)$. It is because
$\frac{\partial f(n,a_{H},a_{C})}{\partial
a_{C}}=\frac{a_{H}^{2}(1-a_{H}^{n-1})}{1-a_{H}}+a_{H}(a_{H}^{n-1}n-1)$. The
first term is always positive, while the second is positive for all $n>1$. To
see this, let us point to the necesarry conditions for ergotropy extractions:
$2a_{H}-1\geq 0$ for the first extraction, $2a_{H}^{2}-1\geq 0$ for the
second, up to $2a_{H}^{n}-1\geq 0$ for the $n$-th one. Therefore,
$\frac{\partial f(n,a_{H},a_{C})}{\partial a_{C}}\geq 0$, and we have
$f(n,a_{H},a_{C})\geq f(n,a_{H},0)$.

Finally, let us note that
$f(n,a_{H},0)=n-1-\frac{a_{H}^{2}(1-a_{H}^{n-1})}{1-a_{H}}$ is non-negative
for all $n\geq 1$. Therefore, we have $\eta_{n}\leq\eta_{1}$ for every $n\geq
1$.

###  G.5 Maximal work extraction

For the work extraction protocol with the single heat bath, such that

$\begin{split}&(E_{0},\alpha_{0})\xrightarrow{H}(E^{\prime}_{1},\alpha^{\prime}_{1})\xrightarrow{\text{W-stroke}}(E_{1},\alpha_{1})\xrightarrow{H}(E^{\prime}_{2},\alpha^{\prime}_{2})\xrightarrow{\text{W-stroke}}\\\
&\xrightarrow{\text{W-stroke}}(E_{2},\alpha_{2})\xrightarrow{H}\dots\xrightarrow{H}(E^{\prime}_{n},\alpha^{\prime}_{n})\xrightarrow{\text{W-stroke}}(E_{n},\alpha_{n}).\end{split}$
(220)

The maximal value of work can be deduced from the optimization over the
function

$\max_{\vec{\lambda},\vec{\delta}}[W(\vec{\lambda},\vec{\delta})]=\max_{\vec{\lambda},\vec{\delta}}\left[\Delta
R_{0}^{n}(E_{0})-\sum_{k=1}^{n}[2a_{H}s_{k}(\vec{\lambda},\vec{\delta})+g(\lambda_{k})+\delta_{k}]\right],$
(221)

where straightforwardly we obtain the maximum for $\lambda_{k}=1$ and
$\delta_{k}=0$, such that

$W_{max}=\Delta R_{0}^{n}(E_{0})=\frac{2a_{H}(\omega-
E_{0})(1-a_{H}^{n})}{1-a_{H}}-n\omega.$ (222)

##  Appendix H Stroke operations and Free energy

###  H.1 Second Law proof

Let us consider an arbitrary process with subsequent steps $\hat{U}_{SH}$ and
$\hat{U}_{SB}$. The energy and entropy change of the working body through the
heat-stroke is $\Delta E_{S}^{H}$ and $\Delta S_{S}^{H}$, and for the work-
stroke we have $\Delta E_{S}^{B}$ and $\Delta S_{S}^{B}$. Let us define, a
relative entropy between two states $\hat{\rho}$ and $\hat{\sigma}$, as

$S(\hat{\rho}|\hat{\sigma})=\Tr[\hat{\rho}\log\hat{\rho}]-\Tr[\hat{\rho}\log\hat{\sigma}].$
(223)

For arbitrary CPTP map $\Lambda[\cdot]$ it is valid an inequality:

$S(\hat{\rho}|\hat{\sigma})\geq S(\Lambda[\hat{\rho}]|\Lambda[\hat{\sigma}]).$
(224)

For the heat-stroke we have $\Delta
E_{S}^{H}=\Tr[\hat{H}_{S}(\hat{\sigma}_{S}^{\prime}-\hat{\sigma}_{S})]=Q$
(100), where $\hat{\sigma}_{S}^{\prime}=\Lambda[\hat{\sigma}_{S}]$, and Gibbs
state $\hat{\tau}_{H}$ is invariant under the thermal operation, i.e.
$\Lambda[\hat{\tau}_{H}]=\hat{\tau}_{H}$. As a consequence we obtain:

$\begin{split}&S(\hat{\sigma}_{S}|\hat{\tau}_{H})\geq
S(\hat{\sigma}_{S}^{\prime}|\hat{\tau}_{H})\implies\\\
&-\Tr[\hat{\sigma}_{S}^{\prime}\log\hat{\sigma}_{S}^{\prime}]+\Tr[\hat{\sigma}_{S}\log\hat{\sigma}_{S}]\geq\Tr[(\hat{\sigma}_{S}-\hat{\sigma}_{S}^{\prime})\log\hat{\tau}_{H}]=\beta\Tr[\hat{H}_{S}(\hat{\sigma}_{S}^{\prime}-\hat{\sigma}_{S})],\end{split}$
(225)

what can be rewritten as a well-known Clausius inequality:

$T\Delta S_{S}^{H}\geq\Delta E_{S}^{H}=Q.$ (226)

On the other hand, according to the relation for work-stroke (101), we have
$\Delta S_{S}^{B}=0$. From these one can easily show that

$\Delta F_{S}=\Delta E_{S}^{H}+\Delta E_{S}^{B}-T\Delta S_{S}^{H}\leq\Delta
E_{S}^{B}.$ (227)

Then, due to the energy conservation, i.e. $\Delta E_{S}^{B}=-\Delta
E_{B}^{B}=-W$, we finally obtain

$W\leq-\Delta F_{S}.$ (228)

###  H.2 Free energy and ergotropy extraction

Let us consider the ergotropy extraction via the heat-stroke, i.e. $\Delta
R_{S}^{H}>0$. We will prove that for any such a process $\Delta F_{S}<0$.
Firstly, let us observe that state $\hat{\sigma}_{S}$ with passive energy
$P_{S}$ has entropy equal to:

$S_{S}=S(\hat{\sigma}_{S})=-P_{S}\log[P_{S}]-(1-P_{S})\log[1-P_{S}],$ (229)

and since $P_{S}\in[0,\frac{1}{2}$ the entropy is an increasing function with
respect to the passive energy of the state. Especially, due to the result
given by Eq. (134), the minimal change of the passive energy $\Delta
P_{S}^{H}$ for any ergotropy extraction (i.e. when $\Delta R_{S}^{H}>0$) is
for the extremal process with $\lambda=1$, and for a state without initial
coherences such that $\alpha=0$, what implies also the minimal change of the
entropy $\Delta S_{S}^{H}$. Furthermore, the change of the energy $\Delta
E_{S}^{H}$ is maximal for the extremal process what shows that if inequality
$T\Delta S^{H}_{S}>\Delta E_{S}^{H}$ is fulfilled for $\lambda=1$ and
$\alpha=0$ it is also fulfilled for any other ergotropy extraction.

Let us then analyzed only this extremal case. If the initial energy is
$E_{0}$, then

$\begin{split}\beta\Delta
E_{S}^{H}&=\beta\omega[x(1+e^{-\beta\omega})-1]\equiv f(x),\\\ \Delta
S_{S}^{H}&=S(xe^{-\beta\omega})-S(x)\equiv g(x),\end{split}$ (230)

where $x=1-E_{0}/\omega$, and

$S(x)=-x\log(x)-(1-x)\log(1-x)$ (231)

Firstly, we show that $g(x)$ is a convex function, i.e.

$g^{\prime\prime}(x)=\frac{1-e^{-\beta\omega}}{x(1-x)(1-xe^{-\beta\omega})}>0$
(232)

for $x\in(0,1)$. Next, we prove that function $f(x)$ is a tangent line of the
function $g(x)$ in the point $x_{0}=\frac{1}{1+e^{-\beta\omega}}$. Indeed, it
is seen that

$\begin{split}g^{\prime}(x_{0})&=e^{-\beta\omega}[\log(x_{0})-\log(x_{0}e^{-\beta\omega})]-[\log(x_{0}e^{-\beta\omega})-\log(x_{0})]=\beta\omega(1+e^{-\beta\omega})=f^{\prime}(x),\end{split}$
(233)

and $f(x_{0})=g(x_{0})=0$. It proves that solution $x_{0}$ is the only
solution of the equation $f(x)=g(x)$.

From these follows that equation

$T\Delta S_{S}^{H}=\Delta E_{S}^{H},$ (234)

for the extremal thermal process can be only satisfied if qubit is in a Gibbs
state, i.e. with energy $E_{0}=1-x_{0}/\omega=\frac{\omega
e^{-\beta\omega}}{1+e^{-\beta\omega}}$, however as a consequence, it cannot be
a work extraction process. Thus, for any ergotropy extraction we have

$T\Delta S_{S}^{H}>\Delta E_{S}^{H},$ (235)

what finally proves inequality $\Delta F_{S}<0$.

###  H.3 Free energy and work extraction

Let us consider an arbitrary sequence of $\hat{U}_{SH}$ and $\hat{U}_{SB}$
where the total change of the free energy is equal to

$\Delta F_{S}=\Delta F_{1}^{H}+\Delta F_{1}^{B}+\Delta F_{2}^{H}+\Delta
F_{2}^{B}+\dots=\sum_{k}(\Delta F_{k}^{H}+\Delta F_{k}^{B}).$ (236)

Moreover, for each work-stroke we have $\Delta S_{S}^{B}=0$, thus

$\sum_{k}\Delta F_{k}^{B}=\Delta E_{S}=-W,$ (237)

and as a consequence

$W=-\Delta F_{S}+\sum_{k}\Delta F_{k}^{H},$ (238)

where each $\Delta F_{k}^{H}\leq 0$ (226). Then, we will prove the following:
whenever $\Delta F_{S}<0$ and state $\hat{\sigma}_{S}$ has no initial
ergotropy $R_{0}=0$, it implies that $W<-\Delta F_{S}$.

Firstly, let us observer that this is trivially obeyed if $W\leq 0$.
Otherwise, since for any work-stroke $\Delta F_{m}^{B}=\Delta R_{m}^{B}$, we
have

$\sum_{k}\Delta R_{k}^{B}<0.$ (239)

Next, since ergotropy is non-negative state function, we obtain the following:

$R_{0}+\sum_{k}(\Delta R_{k}^{B}+\Delta R_{k}^{H})\geq 0,$ (240)

and according to the assumption that $R_{0}=0$, it implies that

$\sum_{k}\Delta R_{k}^{H}\geq-\sum_{k}\Delta R_{k}^{B}>0.$ (241)

It is seen that at least one heat-stroke is the ergotropy extraction, i.e.
$\Delta R_{m}^{H}>0$ for some $m$, what further implies $\Delta F_{m}^{H}<0$
(235). Finally, this proves that

$W<-\Delta F_{S}.$ (242)

##  Appendix I Many cycle evolution

###  I.1 Stationary and asymptotic state

In order to analyze the engine after many cycles we define the following map

$T_{n}(\hat{\rho}_{SB})=\Tr_{H,C}(\hat{U}_{n}\hat{\rho}\hat{U}_{n}^{\dagger})$
(243)

where the action of the map on basis states is following:

$\begin{split}\outerproduct{g,m}{g,m}&\xrightarrow{T}a_{H}^{n}(1-a_{C})\outerproduct{g,m+n}{g,m+n},\\\
&+\sum_{k=0}^{n-1}a_{H}^{k}(1-a_{H})\outerproduct{g,m-n+2k}{g,m-n+2k}+a_{H}^{n}a_{C}\outerproduct{e,m+n}{e,m+n}\\\
\outerproduct{e,m}{e,m}&\xrightarrow{T}\outerproduct{g,m-n}{g,m-n}.\end{split}$
(244)

If we trace out the battery we obtain the $S$ map:

$\begin{split}\outerproduct{g}{g}&\xrightarrow{S}(1-a_{H}^{n}a_{C})\outerproduct{g}{g}+a_{H}^{n}a_{C}\outerproduct{e}{e},\\\
\outerproduct{e}{e}&\xrightarrow{S}\outerproduct{g}{g}.\end{split}$ (245)

As it seen, the marginal state does not depend on a battery state at all.
Further, eigenvectors of the $S$ map are equal to

$\begin{split}\vec{v}_{1}&=\outerproduct{g}{g}-\outerproduct{e}{e}\xrightarrow{S}-a_{H}^{n}a_{C}\
\vec{v}_{1},\\\
\vec{v}_{2}&=\outerproduct{g}{g}+a_{H}^{n}a_{C}\outerproduct{e}{e}\xrightarrow{S}\vec{v}_{2},\end{split}$
(246)

and arbitrary qubit state can be decomposed in the basis $\vec{v}_{1},\
\vec{v}_{2}$, i.e.

$p\outerproduct{g}{g}+(1-p)\outerproduct{e}{e}=(p-\frac{1}{1+a_{H}^{n}a_{C}})\vec{v}_{1}-p\vec{v}_{2}.$
(247)

This leads us to the formula for a qubit state after $m$ cycles, i.e.

$\begin{split}p\outerproduct{g}{g}+(1-p)\outerproduct{e}{e}\vec{v}_{2}\xrightarrow{S^{m}}&\left[\frac{1+(a_{H}^{n}a_{C})^{m}}{1+a_{H}^{n}a_{C}}-p(a_{H}^{n}a_{C})^{m}\right]\outerproduct{g}{g}\\\
&+\left[\frac{a_{H}^{n}a_{C}-(a_{H}^{n}a_{C})^{m}}{1+a_{H}^{n}a_{C}}+p(a_{H}^{n}a_{C})^{m}\right]\outerproduct{e}{e},\end{split}$
(248)

what in the limit $m\rightarrow\infty$ gives

$\begin{split}&p\outerproduct{g}{g}+(1-p)\outerproduct{e}{e}\xrightarrow[m\to\infty]{S^{m}}\frac{1}{1+a_{H}^{n}a_{C}}\outerproduct{g}{g}+\frac{a_{H}^{n}a_{C}}{1+a_{H}^{n}a_{C}}\outerproduct{e}{e}.\end{split}$
(249)

It also proves that above state is a fixed point under the transformation $S$.

###  I.2 Work fluctuations

####  I.2.1 Work distribution for three-stroke heat engine

We consider a final state of a battery after $N=2n$ cycles of running the
three-stroke heat engine:

$\begin{split}\hat{\rho}_{B}&=\Tr_{S,H,C}[\hat{U}_{1}^{2n}(\outerproduct{0}{0}_{B}\otimes\hat{\rho}_{S}\otimes\hat{\tau}_{H}^{\otimes
2n}\otimes\hat{\tau}_{C}^{\otimes})\hat{U}_{1}^{2n}{}^{\dagger}]=\sum_{k}P_{2n}(2k)\outerproduct{2k}{2k}_{B}.\end{split}$
(250)

For the simplest three-stroke case, a $T$ map (244) of a single cycle is given
by:

$\begin{split}\outerproduct{g,k}{g,k}&\xrightarrow{T}a_{H}(1-a_{C})\outerproduct{g,k+1}{g,k+1}+(1-a_{H})\outerproduct{g,k-1}{g,k-1}+a_{H}a_{C}\outerproduct{e,k+1}{e,k+1},\\\
\outerproduct{e,k}{e,k}&\xrightarrow{T}\outerproduct{g,k-1}{g,k-1}.\end{split}$
(251)

Let us imagine this process as a random walk with three different transitions:
right $R$ is given by the transition
$\outerproduct{g,k}{g,k}\rightarrow\outerproduct{g,k+1}{g,k+1}$ with
probability $p_{+}=a_{H}(1-a_{C})$, and left $L$ is the transition
$\outerproduct{g,k}{g,k}\rightarrow\outerproduct{g,k-1}{g,k-1}$ with
probability $p_{-}=(1-a_{H})$. The last step is ‘double zero’ transition $OO$
which is a composition of two:
$\outerproduct{g,k}{g,k}\rightarrow\outerproduct{e,k+1}{e,k+1}$ with
probability $p_{0}=a_{H}a_{C}$, and second (deterministic) transition
$\outerproduct{e,k+1}{e,k+1}\rightarrow\outerproduct{g,k}{g,k}$ which brings
the state back to the initial one. It means that transition $OO$ does not
change the position of a walker, however it has length of two iterations.

Let us now consider a process with $2n$ iterations where we have $n_{+}$ right
steps $R$, $n_{-}$ left steps $L$, and $n_{0}$ zeros $O$, and we start in a
state
$\hat{\rho}_{SB}=(p\outerproduct{g}{g}_{S}+(1-p)\outerproduct{e}{e}_{S})\otimes\outerproduct{0}{0}_{B}$.
The probability of occupying the state $\outerproduct{2k}{2k}_{B}$ at the end
of the protocol we define as:

$P_{2n}(2k)=p\ p_{g}(2k,2n)+(1-p)\ p_{e}(2k,2n),$ (252)

where $p_{g}(2k,2n)=p_{gg}(2k,2n)+p_{ge}(2k,2n)$, and $p_{gg}(2k,2n)$ is a
probability of transition
$\outerproduct{g,0}{g,0}\to\outerproduct{g,2k}{g,2k}$, and $p_{ge}(2k,2n)$ is
a probability of transition
$\outerproduct{g,0}{g,0}\to\outerproduct{e,2k}{e,2k}$, and analogously for
$p_{e}(2k,2n)$.

The probability of occupying the state $\outerproduct{g,2k}{g,2k}$ at the end
of the protocol is given by the sum over all trajectories with even number of
zeros $n_{0}$, where the associated probability is given by the trinomial
distribution, i.e.

$p_{gg}(2k,2n)=\sum_{\begin{subarray}{c}n_{+}+n_{-}+n_{0}=2n\\\ n_{0}\text{ -
even}\end{subarray}}\delta_{2k,n_{+}-n_{-}}\ f(n_{+},n_{-},\frac{n_{0}}{2})$
(253)

where

$f(n_{+},n_{-},n_{0})=\frac{(n_{+}+n_{-}+n_{0})!}{n_{+}!n_{-}!n_{0}!}p_{+}^{n_{+}}p_{-}^{n_{-}}p_{0}^{n_{0}}.$
(254)

Furthermore, for odd values of $n_{0}$ all trajectories always end up in the
same final state $\outerproduct{e,2k}{e,2k}$. Then, it is enough to realize
that the last step is always given by the $O$-transition
$\outerproduct{g,k}{g,k}\rightarrow\outerproduct{e,k+1}{e,k+1}$ with
probability $p_{0}=a_{H}a_{C}$, and the rest can be once again calculated from
the trinomial distribution, namely

$\begin{split}p_{ge}(2k,2n)&=p_{0}\sum_{\begin{subarray}{c}n_{+}+n_{-}+n_{0}=2n\\\
n_{0}\text{ - odd}\end{subarray}}\delta_{2k,n_{+}-n_{-}+1}\
f(n_{+},n_{-},\frac{n_{0}-1}{2}).\end{split}$ (255)

Finally, we obtain:

$\begin{split}&p_{g}(2k,2n)=\\\
&=\sum_{i=0}^{m}\sum_{n_{+}=0}^{2(m-i)}\delta_{k,n_{+}-m+i}\
f(n_{+},2n-n_{+}-2i,i)+p_{0}\sum_{i=0}^{m-1}\sum_{n_{+}=0}^{2(m-i)-1}\delta_{k,n_{+}-m+i+1}\
f(n_{+},2n-n_{+}-2i-1,i)\\\
&=\sum_{i=0}^{m}\theta(k+m-i)\theta(-k+m-i)[f(k+m-i,-k+m-i,i)\\\
&+p_{0}\sum_{i=0}^{m-1}\theta(k+m-i-1)\theta(-k+m-i)f(k+m-i-1,-k+m-i,i)]\\\
&=\sum_{i=0}^{m}\theta(k+i)\theta(-k+i)f(k+i,-k+i,m-i)+p_{0}\sum_{i=1}^{m}\theta(k+i-1)\theta(-k+i)f(k+i-1,-k+i,m-i)\\\
&=\sum_{i=|k|}^{m}f(k+i,-k+i,m-i)+\sum_{i=1}^{m}\frac{(k+i)p_{0}}{(m+i)p_{+}}\theta(k+i-1)\theta(-k+i)f(k+i,-k+i,m-i)\\\
&=\sum_{i=|k|}^{m}(1+\frac{(i+k)p_{0}}{(i+m)p_{+}})f(i+k,i-k,m-i).\end{split}$
(256)

Similarly to previous considerations we have

$\begin{split}&p_{g}(2k+1,2n+1)=\\\
&=\sum_{\begin{subarray}{c}n_{+}+n_{-}+n_{0}=2n+1\\\ n_{0}\text{ -
even}\end{subarray}}\delta_{2k,n_{+}-n_{-}-1}\
f(n_{+},n_{-},\frac{n_{0}}{2})+p_{0}\sum_{\begin{subarray}{c}n_{+}+n_{-}+n_{0}=2n+1\\\
n_{0}\text{ - odd}\end{subarray}}\delta_{2k,n_{+}-n_{-}}\
f(n_{+},n_{-},\frac{n_{0}-1}{2})\\\
&=\sum_{i=0}^{n}\sum_{n_{+}=0}^{2(n-i)+1}[\delta_{k,n_{+}-n+i-1}\
f(n_{+},2n+1-n_{+}-2i,i)+p_{0}\delta_{k,n_{+}-n+i}\ f(n_{+},2n-n_{+}-2i,i)]\\\
&=\sum_{i=0}^{n}\sum_{n_{+}=0}^{2i+1}[\delta_{k,n_{+}-i-1}\
f(n_{+},2i+1-n_{+},n-i)+p_{0}\delta_{k,n_{+}-i}\ f(n_{+},2i-n_{+},n-i)]\\\
&=\sum_{i=0}^{n}[\theta(k+i+1)f(k+i+1,-k+i,n-i)+p_{0}\theta(k+i)f(k+i,-k+i,n-i)]\theta(i-k)\\\
&=\sum_{i=0}^{n}[p_{+}\frac{n+i+1}{k+i+1}\theta(k+i+1)+p_{0}\theta(k+i)]f(k+i,-k+i,n-i)\theta(i-k)\\\
&=\theta(-k-1)f(|k|+k,|k|-k-1,n-|k|+1)+\sum_{i=|k|}^{n}(p_{+}\frac{n+i+1}{k+i+1}+p_{0})f(k+i,-k+i,n-i).\end{split}$
(257)

Moreover, if we start in a state $\outerproduct{e,0}{e,0}$, then each
realization starts with a step
$\outerproduct{e,0}{e,0}\rightarrow\outerproduct{g,-1}{g,-1}$. This
straightforwardly leads to the formula:

$p_{e}(2k,2n)=p_{g}(2k+1,2n-1).$ (258)

Finally, for arbitrary state
$\hat{\rho}_{S}=p\outerproduct{g}{g}_{S}+(1-p)\outerproduct{e}{e}_{S}$, we
have

$P_{2n}(2k)=p\ p_{g}(2k,2n)+(1-p)\ p_{g}(2k+1,2n-1).$ (259)

####  I.2.2 Work distribution for charging protocol via uncorrelated qubits

Let us start with a definition of the map $\tilde{T}$:

$\tilde{T}(\hat{\rho}_{SB})=\hat{U}_{SB}(\hat{\rho}_{B}\otimes\hat{\varrho}_{S})\hat{U}_{SB},$
(260)

where

$\hat{\varrho}_{S}=(1-\frac{a_{H}}{1+a_{H}a_{C}})\outerproduct{g}{g}_{S}+\frac{a_{H}}{1+a_{H}a_{C}}\outerproduct{e}{e}_{S}.$
(261)

The action of the map on basis states is following:

$\begin{split}\outerproduct{g,n}{g,n}\xrightarrow{\tilde{T}}\outerproduct{e,n-1}{e,n-1},\
\outerproduct{e,n}{e,n}\xrightarrow{\tilde{T}}\outerproduct{g,n+1}{g,n+1}\end{split}$
(262)

We then consider a battery state after the charging process by $N=2n$
uncorrelated qubits, where in each step the battery and particular qubit
evolve according to the map $\tilde{T}$, namely we define the state:

$\begin{split}\hat{\varrho}_{B}&=\Tr_{S}[\hat{U}_{SB}^{2n}(\outerproduct{0}{0}_{B}\otimes\hat{\varrho}_{S}^{\otimes
2n})\hat{U}_{SB}^{2n}{}^{\dagger}]=\sum_{k}\tilde{P}_{2n}(2k)\outerproduct{2k}{2k}.\end{split}$
(263)

In analogy to the previous consideration we have here once again a random walk
process, however with only left and right transition. For the specific state
$\hat{\varrho}_{S}$ ,the left transition $L$ is observe with probability
$p_{-}=1-\frac{a_{H}}{1+a_{H}a_{C}}$, and right transition $R$ with
probability $p_{+}=\frac{a_{H}}{1+a_{H}a_{C}}$. As a consequence, the final
distribution of the battery is simply given by the binomial distribution:

$\tilde{P}_{2n}(2k)=\binom{2n}{n-|k|}p_{+}^{n-k}p_{-}^{n+k}.$ (264)