appropriate way.

######  Lemma 24.

If $\bar{H}_{j}$ is a left child of $\bar{H}_{i}$ and $\bar{H}_{i}$ is not a
root hammock then $l(C_{j})\in
T_{\text{BFS}}(\bar{r}_{i},\bar{r}_{j})\subseteq\bar{T}_{i}$.

###### Proof.

First, notice that since $\bar{r}_{j}\in\bar{T}_{i}$ we know that both
$l(C_{j})$ and $l(C_{i})$ are ancestors of $\bar{r}_{j}$ and so $l(C_{j})$ and
$l(C_{i})$ are related. Thus, if $l(C_{j})\not\in
T_{\text{BFS}}(\bar{r}_{i},\bar{r}_{j})$ then it must be the case that
$\bar{r}_{i}\prec l(C_{j})$; suppose for the sake of contradiction that indeed
$\bar{r}_{i}\prec l(C_{j})$.

We first claim that there is a path $P_{1}$ with edges contained in
$\bar{T}_{i}$ from $\bar{r}_{j}$ to a vertex $v$ which is in a cycle $C$ in
$\hat{H}_{i}$. Further, if $u=\text{high}(V(\bar{T}_{i})\cap V(C))$ and
$u^{\prime}=\text{high}(V(\bar{T}_{i}^{\prime})\cap V(C))$ then we will have
$v\neq u,u^{\prime}$. Let us argue why such a $P_{1}$ exists. It suffices to
argue that there is some $v\in\hat{T}_{i}$ where $v\neq\hat{r}_{i}$ and a path
between $\bar{r}_{j}$ and $\hat{T}_{i}$ ending in $v$ since by Lemma 21 the
existence of such an $v$ would give us our required cycle. By noting that
$\hat{r}_{i}=\bar{r}_{i}$ we can further simplify what we must prove. In
particular, let $\bar{H}_{i^{\prime}}$ be the parent of $\bar{H}_{i}$ in
$\bar{\mathcal{H}}$ which we know exists by our assumption that $\bar{H}_{i}$
is not a root hammock. Additionally, notice that we always know that
$\bar{r}_{i}=\hat{r}_{i}$ since if $\bar{r}_{i}$ were strictly higher than
$\hat{r}_{i}$ it would be because it lies in a connected component of
$H_{\text{HJ}}\setminus\hat{H}$ incident to both $\bar{r}_{i}$ and
$\hat{r}_{i}$. Such a component is incident to $\bar{H}_{i^{\prime}}$ by
definition of a forest of hammocks. Even stronger, such a component must be
incident to $\hat{H}_{i^{\prime}}$ since every component of
$H_{\text{HJ}}\setminus\hat{H}$ incident to $\bar{H}_{i^{\prime}}$ is also
incident to $\hat{H}_{i^{\prime}}$ which means that any such component would
always be assigned to $i^{\prime}$.

Thus, it suffices to argue that that there is some $v\in\hat{T}_{i}$ where
$v\neq\bar{r}_{i}$ and a path between $\bar{r}_{j}$ and $\hat{T}_{i}$ ending
in $v$. Note that $\bar{r}_{j}$ was added to $\bar{T}_{i}$ either because a
component of $H_{\text{HJ}}\setminus\hat{H}$ was assigned to $i$ or because it
was already $\hat{T}_{i}$. In particular, either $\bar{r}_{j}\in\hat{T}_{i}$
or $\bar{r}_{j}\in\bar{T}_{i}\setminus\hat{T}_{i}$.

  1. 1.

Suppose $\bar{r}_{j}\in\hat{T}_{i}$. In this case we can let our path from
$\bar{r}_{j}$ to $\hat{T}_{i}$ be the trivial path consisting only of
$\bar{r}_{j}$; it remains only to show that $\bar{r}_{j}\neq\bar{r}_{i}$.
However, it cannot be the case that $\bar{r}_{j}=\bar{r}_{i}$ since otherwise
we would have that $H_{j}$ is a child of $\bar{H}_{i^{\prime}}$ not $H_{i}$ in
$\bar{\mathcal{H}}$, a contradiction.

  2. 2.

Suppose $\bar{r}_{j}\in\bar{T}_{i}\setminus\hat{T}_{i}$. It follows that
$\bar{r}_{j}$ is incident to a component $F\subseteq T_{\text{BFS}}$ of
$H_{\text{HJ}}\setminus\hat{H}$ which is assigned to $i$ with exactly one
vertex $v$ in $V(\hat{T}_{i})$. In this case we can let our path from
$\bar{r}_{j}$ to $\hat{T}_{i}$ be the path in $F$ from $\bar{r}_{j}$ to $v$;
it remains only to argue that $v\neq\bar{r}_{i}$. However, if $v$ were equal
to $\bar{r}_{i}$ then we would have that $F$ shares a vertex with
$\bar{H}_{i^{\prime}}$ and, even stronger, $F$ shares a vertex with
$\hat{H}_{i^{\prime}}$. It follows that $F$ would be assigned to
$\bar{H}_{i^{\prime}}$, not $\bar{H}_{i}$, a contradiction.

Next, we claim that there is a path $P_{2}$ from $r$ to $\bar{r}_{j}$ such
that $P_{2}\cap V(\bar{H}_{i})=\\{\bar{r}_{j}\\}$. Let $P_{2}^{\prime}$ an
arbitrary path contained in $\bar{H}_{j}$ from $\bar{r}_{j}^{\prime}$ to
$\bar{r}_{j}$. Since $\bar{H}_{i}$ and $\bar{H}_{j}$’s vertex sets only
intersect on $\bar{r}_{j}$, it follows that $P_{2}^{\prime}\cap
V(\bar{H}_{i})=\\{\bar{r}_{j}\\}$. Next we form $P_{2}$ by concatenating
$P_{2}^{\prime}$ with $T_{\text{BFS}}(l(C_{j}),\bar{r}_{j}^{\prime})$. We
claim that $T_{\text{BFS}}(l(C_{j}),\bar{r}_{j}^{\prime})\cap
V(\bar{H}_{i})=\emptyset$. Suppose for the sake of contradiction that there is
some $x\in T_{\text{BFS}}(l(C_{j}),\bar{r}_{j}^{\prime})\cap V(\bar{H}_{i})$.
If $x\in\bar{T}_{i}$ then $\bar{r}_{i}$ is an ancestor of both $\bar{r}_{j}$
and $\bar{r}_{j}^{\prime}$ and so $l(C_{j})\prec l(C_{i})$, contradicting our
assumption that $\bar{r}_{i}\prec l(C_{j})$. On the other hand, if
$x\in\bar{T}_{i}^{\prime}$ then we have that $\bar{r}_{i}^{\prime}$ is an
ancestor of $\bar{r}_{j}^{\prime}$; since $\bar{r}_{j}\in\bar{T}_{i}$, it
follows that $C_{i}=C_{j}$, contradicting our assumption that $C_{i}$ and
$C_{j}$ are distinct lca-equivalence classes. Thus, $P_{2}$ is indeed from $r$
to $\bar{r}_{j}$ and satisfies $P_{2}\cap V(\bar{H}_{i})=\\{\bar{r}_{j}\\}$.

We conclude by observing that the above gives us a clawed cycle with $C$ as
the cycle with paths $T_{\text{BFS}}(r,u)$, $T_{\text{BFS}}(r,u^{\prime})$ and
$P_{1}\oplus P_{2}$, a contradiction. ∎

We now demonstrate that the tree structure of $\bar{\mathcal{H}}$ reflects the
structure of our lca-equivalence classes. As the previous lemma handled the
left child case, most of this proof will be focused on the right child case.

######  Lemma 25.

$\bar{H}_{j}\preceq_{\bar{\mathcal{H}}}\bar{H}_{i}$ implies $C_{j}\preceq
C_{i}$ for every $i,j$.

###### Proof.

It suffices to show that if $\bar{H}_{j}$ is a child of $\bar{H}_{i}$ in
$\bar{\mathcal{H}}$ then $C_{j}\preceq C_{i}$; thus, let $\bar{H}_{i}$ and
$\bar{H}_{j}$ be an arbitrary parent-child pair in $\bar{\mathcal{H}}$. Since
$\bar{\mathcal{H}}$ is a rooted forest of hammocks by Lemma 22 we know that
$V(\bar{H}_{i})\cap V(\bar{H}_{j})=\bar{r}_{j}$ and since $l(C_{i})$ and
$l(C_{j})$ are ancestors of every vertex in $\bar{H}_{i}$ and $\bar{H}_{j}$
respectively, we know that $l(C_{i})$ and $l(C_{j})$ are both ancestors of
$\bar{r}_{j}$ and therefore either $C_{i}\prec C_{j}$ or $C_{j}\preceq C_{i}$.

Suppose for the sake of contradiction that $C_{i}\prec C_{j}$ and suppose
minimality of this counter-example; in particular, suppose that there are no
ancestors $\bar{H}_{i^{\prime}}$ and $\bar{H}_{j^{\prime}}$ of $\bar{H}_{j}$
in $\bar{\mathcal{H}}$ where $\bar{H}_{i^{\prime}}$ is the parent of
$\bar{H}_{j^{\prime}}$ but $l(C_{i^{\prime}})\prec l(C_{j^{\prime}})$. It
follows that for every pair of parent-child pairs $\bar{H}_{i^{\prime}}$ and
$\bar{H}_{j^{\prime}}$ which are ancestors of $\bar{H}_{j}$ in
$\bar{\mathcal{H}}$ we know that $C_{j^{\prime}}\preceq C_{i^{\prime}}$.
Moreover, letting $\bar{H}_{k}$ be the root hammock of the tree of hammocks
containing $\bar{H}_{i}$ and $\bar{H}_{j}$ in $\bar{\mathcal{H}}$, it follows
that $C_{i^{\prime}}\preceq C_{k}$ for any ancestor $\bar{H}_{i^{\prime}}$ of
$\bar{H}_{j}$. Additionally, since we chose $\bar{H}_{k}$ to maximize
$h(C_{k})$ and $C_{j}\prec C_{i}$, there must be some pair of ancestors
$\bar{H}_{j^{\prime}}$ and $\bar{H}_{i^{\prime}}$ of $\bar{H}_{j}$ where
$C_{j^{\prime}}\prec C_{i^{\prime}}$ (since otherwise we would have
$C_{k}\prec C_{j}$).

It follows that there is a sequence of hammocks
$\bar{H}_{0},\bar{H}_{1},\bar{H}_{2},\bar{H}_{3},\ldots,\bar{H}_{\alpha},\bar{H}_{\alpha+1}$
where $l(C_{l})=l(C_{l^{\prime}})$ for $l,l^{\prime}\in[\alpha]$ and
$\bar{H}_{l+1}$ is the child of $\bar{H}_{l}$ in $\bar{\mathcal{H}}$ for
$0\leq l\leq\alpha$ where $\alpha\geq 1$ but
$l(C_{1})=\ldots=l(C_{\alpha})\prec l(C_{0}),l(C_{\alpha+1})$; here, we have
slightly abused notation and relabeled $\bar{H}_{i^{\prime}}$,
$\bar{H}_{j^{\prime}}$, $\bar{H}_{i}$ and $\bar{H}_{j}$ to $\bar{H}_{0}$,
$\bar{H}_{1}$, $\bar{H}_{\alpha}$ and $\bar{H}_{\alpha+1}$ respectively. We
let $u:=l(C_{l})$ for $l\in[\alpha]$ and let $v_{l}$ be the child of $u$ in
$T_{\text{BFS}}$ whose subtree contains $r_{l}$ Moreover, we claim that by
Lemma 24 we know that for each $l\in[\alpha]$ we must have that
$\bar{H}_{l+1}$ is a _right_ child of $\bar{H}_{l}$: to see why, notice that
if $\bar{H}_{l+1}$ is a left child of $\bar{H}_{l}$ then Lemma 24 tells us
that $l(C_{l+1})\in T_{l}$ and so $l(C_{l+1})\preceq r_{l}\prec u$; if
$l<\alpha$ this contradicts our assumption that $l(C_{l+1})=u$ and if
$l=\alpha$ this contradicts our assumption that $l(C_{\alpha})=u\prec
l(C_{\alpha+1})$.

We will use the existence of such a sequence of right children to contradict
Lemma 11.

First, we claim that $v_{1}$ and $v_{\alpha+1}$ are connected in
$T_{\text{BFS}}(u)\setminus\\{u\\}$. To see why, first notice that the graph
induced by the union of $\bar{H}_{1},\bar{H}_{2},\ldots,\bar{H}_{\alpha}$ is
connected by virtue of each hammock in this sequence being the parent of the
next hammock in this sequence. $v_{1}$ and $v_{\alpha+1}$ are therefore
connected in $T_{\text{BFS}}(u)\setminus\\{u\\}$ since we also know that
$r_{1}$ and $r_{\alpha+1}$ are both contained in this graph and descendants of
$v_{1}$ and $v_{\alpha+1}$ respectively.

Notice that $\bar{H}_{0}$ and $\bar{H}_{1}$ intersect at $r_{1}\preceq v_{1}$
and $\bar{H}_{\alpha}$ and $\bar{H}_{\alpha+1}$ intersect at
$r_{\alpha+1}\preceq v_{\alpha+1}$. Thus, since $\bar{H}_{0}\prec\bar{H}_{1}$
and $\bar{H}_{\alpha+1}\prec\bar{H}_{\alpha}$, it follows by Lemma 23 that
$\\{u,v_{1}\\}$ and $\\{u,v_{\alpha+1}\\}$ are connected below.

Thus, if we can show that $v_{1}\neq v_{\alpha+1}$ then we will have
contradicted Lemma 11. Suppose for the sake of contradiction that
$v_{1}=v_{\alpha+1}$. Then, there must be some contiguous subsequence
$(v_{\beta},v_{\beta+1},\ldots v_{\beta+\gamma})$ of
$(v_{1},\ldots,v_{\alpha+1})$ for $\gamma\geq 1$ where
$v_{\beta}=v_{\beta+\gamma}$ but $v_{\beta+x}\neq v_{\beta+y}$ for all
$x,y<\gamma$ where $y\neq x$. To simplify notation we assume that $\beta=1$.
We will show that all choices of $\gamma$ contradict the assumption that
$v_{1}=v_{\gamma+1}$ and so it must be the case that $v_{1}\neq v_{\alpha+1}$.
We illustrate each of the following contradictions in Figures 13(a), 13(b) and
13(c).

  1. 1.

Suppose $\gamma=1$ (i.e. there is a single hammock $\bar{H}_{1}$ we are
considering with an lca of $u$). Then we would have that $r_{1}$ and
$r_{1}^{\prime}$ are both descendants of $v_{1}$ and $v_{\gamma+1}$, meaning
$l(C_{1})\preceq v_{1}=v_{\gamma+1}\prec u$, a contradiction to the fact that
$l(C_{1})=u$.

  2. 2.

Suppose $\gamma=2$. Since $\bar{H}_{2}$ is a right child of $\bar{H}_{1}$, we
know that $r_{2}\preceq v_{2}$ _and_ $r_{1}^{\prime}\preceq v_{2}$. Moreover,
we know that $r_{3}\preceq v_{3}$ and $r_{3}\in T_{2}^{\prime}$ and so
$r_{2}^{\prime}\preceq v_{3}=v_{1}$. Summarizing, we have
$r_{1},r_{2}^{\prime}\preceq v_{1}$ and $r_{1}^{\prime},r_{2}\preceq v_{2}$;
however since $v_{1},v_{2}\neq u$, it follows that $C_{1}=C_{2}$,
contradicting our assumption that they are distinct lca-equivalence classes.

  3. 3.

Suppose $\gamma\geq 3$. Let $P$ be an arbitrary path connecting $r_{1}$ and
$r_{\gamma+1}$ in the graph induced by
$\bar{H}_{1},\bar{H}_{2},\ldots,\bar{H}_{\gamma}$. By our assumption that
$\bar{H}_{l+1}$ is a right child of $\bar{H}_{l}$ for $l\in[\gamma]$, we know
that such a path uses at least one edge in $C_{l}$ for $l\in[\gamma]$.
Moreover, we may assume WLOG that $P$ uses exactly one edge from $C_{l}$ for
$l\in[\gamma]$: if $x_{l}$ and $y_{l}$ are the first and last vertices that
$P$ visits in $C_{l}$ then by definition of a hammock there is a path from
$x_{l}$ to $y_{l}$ which uses exactly one edge of $C_{l}$; we assume that
$P$’s subpath restricted to $C_{l}$ is this path. Next, since we have assumed
that $v_{1}$ and $v_{\gamma+1}$ are equal, we know that both $r_{1}$ and
$r_{\gamma+1}$ lie in $T_{\text{BFS}}(v_{1})$. By our choice of $\gamma$, we
have that the graph induced by $T_{\text{BFS}}(r_{1},r_{\gamma+1})\cup P$
contains a cycle $C$ with exactly one edge from at least three $C_{l}$.
However, we can easily form a clawed cycle from such a cycle. In particular,
let $P_{1}$, $P_{2}$ and $P_{3}$ be paths to $C$ from $u$ in $T_{\text{BFS}}$
via $v_{1}$, $v_{2}$ and $v_{3}$ respectively. Then $C$ with these paths is a
clawed cycle, a contradiction.∎

(a) $\gamma=1$: $l(C_{1})\prec u$

(b) $\gamma=2$: $C_{1}=C_{2}$

(c) $\gamma\geq 3$: a clawed cycle

Figure 13: Each of the three contradictions we arrive at in the proof of Lemma
25 based on the value of $\gamma$. In (c) we highlight the cycle of our clawed
cycle in solid yellow and each of its paths in dotted yellow.

####  8.3.2 Extending Along Lca Paths

In this section we show that the above mentioned paths are appropriately
disjoint from one another as well as from the thus far computed hammocks. We
will then use this disjointness to extend $\bar{\mathcal{H}}$ to
$\tilde{\mathcal{H}}$. We formally define these paths—which we illustrate in
illustrate in Figure 14(a)—as follows.

######  Definition 27 (Lca Paths $P_{i}$, $P_{i}^{\prime}$, $\mathcal{P}_{i}$
$\mathcal{P}$).

For each $i$ we let
$P_{i}:=\text{internal}(T_{\text{BFS}}(\bar{r}_{i},l(C_{i})))$ and
$P_{i}^{\prime}:=\text{internal}(T_{\text{BFS}}(\bar{r}_{i}^{\prime},l(C_{i})))$
be the lca paths from $\bar{r}_{i}$ and $\bar{r}_{i}^{\prime}$ respectively to
$l(C_{i})$, excluding the endpoints. We let $\mathcal{P}_{i}$ be the set which
always contains $P_{i}^{\prime}$ and which additionally contains $P_{i}$ if
$\bar{H}_{i}$ is a root hammock in $\bar{\mathcal{H}}$. Lastly, we let
$\mathcal{P}:=\bigcup_{i}\mathcal{P}_{i}$ be the collection of all relevant
lca paths.

(a) Lca paths.

(b) Extending $\bar{\mathcal{H}}$ to $\tilde{\mathcal{H}}$ via lca paths.

Figure 14: An illustration of the paths of our hammock decomposition. Each
such path dotted and given in a color corresponding to its constituent
hammock. On the left we give the paths and on the right we give the result of
adding these paths to $\bar{\mathcal{H}}$, resulting in $\tilde{\mathcal{H}}$.
Notice that each root hammock has two paths in $\mathcal{P}$.

Given the above paths we now describe how we construct $\tilde{\mathcal{H}}$
from $\bar{\mathcal{H}}$ be extending our hammocks along these paths.
Formally, we let $\tilde{H}_{i}$ be the graph induced in $G$ by
$V(\bar{H}_{i})$ along with all vertices in paths in $\mathcal{P}_{i}$. We
also let the root hammocks of $\tilde{\mathcal{H}}$ be the same as the root
hammocks of $\bar{\mathcal{H}}$. We illustrate this in Figure 14(b).

To show that this yields an lca-respecting tree of hammocks we first observe
that all of the above paths are appropriately disjoint.

######  Lemma 26.

For each $P\in\mathcal{P}$ and $i$ we have $V(P)\cap
V(\bar{H}_{i})=\emptyset$. Similarly, for distinct
$P,P^{\prime}\in\mathcal{P}$ we have $V(P)\cap V(P^{\prime})=\emptyset$.

###### Proof.

First, let us show $V(P)\cap V(\bar{H}_{i})=\emptyset$. Let
$P\in\mathcal{P}_{j}$; we assume WLOG that $P=P_{j}^{\prime}$. Suppose that
there is some vertex $v\in V(P_{j}^{\prime})$ which is contained in
$V(\bar{H}_{i})$ and let $v$ be the lowest such vertex in $P_{j}^{\prime}$. It
follows that the path between $\bar{r}_{j}^{\prime}$ and $v$ must be a hammock
joining path between $\bar{H}_{i}$ and $\bar{H}_{j}$.

Continuing, let $e$ be the parent edge of $\bar{r}_{j}^{\prime}$ in
$T_{\text{BFS}}$; $e$ is in the above hammock-joining path and so is contained
in some hammock $\bar{H}_{l}$ which intersects $\bar{H}_{j}$ on
$\bar{r}_{j}^{\prime}$. Since $\bar{H}_{l}$ and $\bar{H}_{j}$ intersect on
$\bar{r}_{j}^{\prime}$, $\bar{H}_{l}$ must be either the parent, sibling or
child of $\bar{H}_{l}$ in $\bar{\mathcal{H}}$ as per Lemma 8. However,
$\bar{H}_{l}$ cannot be the parent or sibling of $\bar{H}_{j}$ since it
intersects $\bar{H}_{j}$ on $\bar{T}_{j}^{\prime}$; thus $\bar{H}_{l}$ is the
child of $\bar{H}_{j}$. We claim that $e\in\hat{H}_{l}$; indeed this is
immediate from the fact that $e$ is incident to $\bar{r}_{j}^{\prime}$ and
since $\bar{H}_{j}$ is the parent of $\bar{H}_{l}$, $e$ would have been
included in $\bar{H}_{j}$, not $\bar{H}_{l}$, if it weren’t in $\hat{H}_{l}$.
However, since $v$ is the parent of $\bar{r}_{j}^{\prime}$ and
$\bar{r}_{j}^{\prime}\in\bar{H}_{l}$, we know that
$\bar{r}_{j}^{\prime}\neq\hat{r}_{l},\hat{r}_{l}^{\prime}$.

Thus, applying Lemma 21 we know that there is a hammock-fundamental cycle
$C\subseteq\hat{H}_{l}$ containing $\bar{r}_{j}^{\prime}$ where
$\bar{r}_{j}^{\prime}$ is not the highest vertex in either
$V(C)\cap\bar{T}_{l}$ or $V(C)\cap\bar{T}_{l}^{\prime}$; let these highest
vertices be $v_{l}$ and $v_{l}^{\prime}$ and notice that to arrive at a
contradiction it suffices to argue that there is a path $P$ from $r$ to
$\bar{r}_{j}^{\prime}$ which is internally vertex disjoint from
$V(\bar{H}_{l})$ since $C$ along with paths $T_{\text{BFS}}(r,v_{l})$,
$T_{\text{BFS}}(r,v_{l}^{\prime})$ and $P$ would then form a clawed cycle. Let
$P$ be the concatenation of $T_{\text{BFS}}(r,\bar{r}_{j})$ with an arbitrary
path in $\bar{H}_{j}$ connecting $\bar{r}_{j}$ and $\bar{r}_{j}^{\prime}$ and
$e$. $\bar{r}_{j}^{\prime}$ is the only vertex which the latter shares with
$\bar{H}_{l}$ so it suffices to show that $T_{\text{BFS}}(r,\bar{r}_{j})$
shares no vertices with $\bar{H}_{l}$. Suppose for the sake of contradiction
that $x\in T_{\text{BFS}}(r,\bar{r}_{j})\cap V(\bar{H}_{l})$. Then, if $x$ and
$\bar{r}_{j}^{\prime}$ were in the same hammock trees of $\bar{H}_{l}$ then we
would have $l(C_{j})\prec l(C_{l})$, contradicting $l(C_{l})\preceq l(C_{j})$
by Lemma 25 and the fact that $\bar{H}_{l}$ is a child of $\bar{H}_{j}$. On
the other hand, if $x$ and $\bar{r}_{j}^{\prime}$ were in different hammock
trees of $\bar{H}_{l}$ then we would have that $C_{j}=C_{l}$, contradicting
the fact that $C_{j}$ and $C_{l}$ are distinct. Thus, we conclude that
$V(P)\cap V(\bar{H}_{i})=\emptyset$.

Next, let us show $V(P)\cap V(P^{\prime})=\emptyset$ for distinct
$P,P^{\prime}\in\mathcal{P}$. We may assume that it is not the case that
$P,P^{\prime}\in\mathcal{P}_{i}$ for some $i$ since then $P$ and $P^{\prime}$
are vertex-disjoint by construction. Thus, WLOG we assume $P=P_{i}^{\prime}$
and $P^{\prime}=P_{j}^{\prime}$ for $i\neq j$. Suppose for the sake of
contradiction that $P_{i}^{\prime}$ and $P_{j}^{\prime}$ share a vertex $x$.
By definition of $P_{i}^{\prime}$ and $P_{j}^{\prime}$ we know that
$x\neq\bar{r}_{i}^{\prime},\bar{r}_{j}^{\prime}$. Moreover, since in the first
part of this proof we showed that $V(P_{i}),V(P_{j})\cap
V(\bar{H})=\emptyset$, it follows that
$T_{\text{BFS}}(\hat{r}_{i}^{\prime},\bar{r}_{i}^{\prime})\oplus
T_{\text{BFS}}(\bar{r}_{i}^{\prime},x)\oplus
T_{\text{BFS}}(x,\bar{r}_{j}^{\prime})\oplus
T_{\text{BFS}}(\bar{r}_{j}^{\prime},\hat{r}_{j}^{\prime})$ is a hammock-
joining path (Definition 23) and so would have been included in $\bar{H}$.
However, then $x$ would have been included in $\bar{H}$ (by definition of
$\bar{H}$). But, this contradicts the fact that
$V(P_{i}^{\prime}),V(P_{j}^{\prime})\cap V(\bar{H})=\emptyset$. ∎

We conclude that our forest of hammocks is indeed lca-respecting (Definition
17).

######  Lemma 27.

$\tilde{\mathcal{H}}$ is an lca-respecting rooted forest of hammocks where for
each root hammock $\tilde{H}_{k}\in\tilde{\mathcal{H}}$ we have
$\text{lca}(\tilde{r}_{k},\tilde{r}_{k}^{\prime})$ is the parent of
$\tilde{r}_{k}$ and $\tilde{r}_{k}^{\prime}$ in $T_{\text{BFS}}$.

###### Proof.

It is easy to see by the disjointness of the paths in $\mathcal{P}$ that
adding all vertices in $\mathcal{P}_{i}$ (along with all induced edges) to
$\bar{H}_{i}$ indeed results in a hammock. To see that the result is a rooted
forest of hammocks we need only verify that any cycle $C$ continues to only be
incident to at most $1$ hammock. However, notice that the disjointness
properties of our paths guarantee that no cycle can use an edge incident to a
vertex in a path in $\mathcal{P}$; thus, since $\bar{\mathcal{H}}$ was a
forest by Lemma 22, so too is $\tilde{\mathcal{H}}$.

Lastly, to see that the resulting rooted forest of hammocks is lca-respecting
notice that $\tilde{H}_{j}$ is a child of $\tilde{H}_{i}$ in
$\tilde{\mathcal{H}}$ iff $\bar{H}_{i}$ is a parent of $\bar{H}_{j}$ in
$\bar{\mathcal{H}}$ and so the first condition of lca-
respecting—$V(\tilde{H}_{i})\cap V(\tilde{H}_{j})=\\{\tilde{r}_{j}\\}$
whenever $\tilde{H}_{i}$ is a parent of $\tilde{H}_{j}$ in
$\tilde{\mathcal{H}}$—still holds by Lemma 22. The second condition—the parent
of $\tilde{r}_{j}^{\prime}$ in $T_{\text{BFS}}$ is
$\text{lca}(\tilde{r}_{j},\tilde{r}_{j}^{\prime})$ and
$\text{lca}(\tilde{r}_{j},\tilde{r}_{j}^{\prime})\in\tilde{H}_{i}\cup\\{\text{lca}(r_{i},r_{i}^{\prime})\\}$
where $\tilde{H}_{i}$ is the parent of $\tilde{H}_{j}$—holds by definition of
the paths in $\mathcal{P}$ and Lemma 25. The condition on each hammock root
similarly follows. ∎

###  8.4 Extending $\tilde{H}$ to $\mathcal{H}$ by Adding Dangling Subtrees

The last step of our hammock decomposition involves adding subtrees of
$T_{\text{BFS}}$ which consist of unassigned nodes to hammocks. We do this to
ensure that our hammock decompositions indeed partitions all edges of the
input series-parallel graph.

Formally, we construct $\mathcal{H}$ from $\tilde{\mathcal{H}}$ as follows.
Let $E_{p}$ be the collection of the parent edges in $T_{\text{BFS}}$ of
$\tilde{r}_{i}^{\prime}$ for every hammock $H_{i}$ (where as usual we use
$\tilde{r}_{i}$ and $\tilde{r}_{i}^{\prime}$ to denote the hammock roots of
$\tilde{H}_{i}$). We let $T_{0}$ be the connected component of
$T_{\text{BFS}}\setminus(E_{p}\cup E(G[\tilde{\mathcal{H}}]))$ which contains
$r$. For each connected component (i.e. dangling tree) $T\neq T_{0}$ of
$T_{\text{BFS}}\setminus(E_{p}\cup E(G[\tilde{\mathcal{H}}]))$ we add $T$ to
an arbitrary hammock which contains $\text{high}(T)$. As a reminder,
$\text{high}(T)$ gives the vertex in $T$ which is highest in $T_{\text{BFS}}$.
Lastly we designate each hammock $H_{k}$ in $\mathcal{H}$ such that $r_{k}\in
V(T_{0})$ and $\tilde{H}_{k}$ was designated a root hammock in
$\tilde{\mathcal{H}}$ as a root of $\mathcal{H}$. We illustrate the result of
adding the dangling trees in Figure 15(a) and the final hammock decomposition
in Figure 15(b).

(a) Adding dangling trees.

(b) Final hammock decomposition.

Figure 15: The result of adding the dangling trees to each of our hammocks and
the final hammock decomposition. On the right we give $T_{0}$ in dark red.

We proceed to show that this indeed results in a hammock decomposition
(Definition 18). We begin by observing that $\mathcal{H}$ is an appropriate
forest of hammocks.

######  Lemma 28.

$\mathcal{H}$ is an lca-respecting rooted forest of hammocks with base tree
$T_{0}$.

###### Proof.

We first observe that each $H_{i}$ is indeed a hammock: since we only add a
dangling tree $T$ to $\tilde{H}_{i}$ if $\text{high}(T)$ is contained in
$\tilde{H}_{i}$ and so the roots of $H_{i}$ are unrelated. Moreover all the
$H_{i}$ must be edge disjoint by the edge disjointness of the
$\tilde{\mathcal{H}}$ and how we construct our $H_{i}$.

Next, we will argue the cycle property of forests of hammocks; namely that any
cycle’s edges are fully contained within a single hammock, thereby showing
that $\mathcal{H}$ is a forest of hammocks.

First, we observe that if $\\{u,v\\}$ is an edge in a dangling tree $T$ where
$v\prec u$ then there does not exist a cross edge $e_{c}=\\{u_{c},v_{c}\\}\in
E_{c}$ such that $u_{c}\in T_{\text{BFS}}(v)$ but $v_{c}\not\in
T_{\text{BFS}}(u)$. To see why this is the case suppose that such an $e_{c}$
existed and belonged to hammock $\tilde{H}_{i}\in\tilde{\mathcal{H}}$ and
recall that by Lemma 27 $\tilde{\mathcal{H}}$ is an lca-respecting rooted
forest of hammocks. By definition of $e_{c}$ we know that
$u\prec\text{lca}(\tilde{r}_{i},\tilde{r}_{i}^{\prime})$ which is to say that
$\text{lca}(\tilde{r}_{i},\tilde{r}_{i}^{\prime})$ lies strictly higher in
$T_{\text{BFS}}$ than $u$. But, since $\tilde{\mathcal{H}}$ is lca-respecting
and $\text{lca}(\tilde{r}_{k},\tilde{r}_{k}^{\prime})$ is the parent of
$\tilde{r}_{k}^{\prime}$ for any root hammock $\tilde{H}_{k}$ by Lemma 27, it
follows that
$T_{\text{BFS}}(u_{c},\text{lca}(\tilde{r}_{i},\tilde{r}_{i}^{\prime}))\setminus\text{lca}(\tilde{r}_{i},\tilde{r}_{i}^{\prime})$
is contained in $\tilde{H}$ and so $\\{u,v\\}$ is contained in $\tilde{H}$,
contradicting our assumption that it is in a dangling tree.

It follows that if a cycle uses two edges $\\{w,u\\}$ and $\\{u,v\\}$ and
$\\{u,v\\}$ lies in a dangling tree then it must be the case that both edges
are child edges of $u$, i.e. $w,v\prec u$.

On the other hand, notice that if we have a cycle which uses $\\{w,u\\}$ and
$\\{u,v\\}$ then there must be some cross edge between $T_{\text{BFS}}(w)$ and
$T_{\text{BFS}}(u)$. Such a cross edge will belong to some hammock
$\tilde{H}_{i}$ for which either $w$ or $v$ is $\tilde{r}_{i}^{\prime}$ and so
either $\\{w,u\\}$ or $\\{u,v\\}$ will be in $E_{p}$, contradicting the fact
that our cycle cannot use any edges of $E_{p}$. Thus, no cycle uses an edge of
a dangling tree and so $\mathcal{H}$ is a forest of hammocks.

Next, observe that by construction every connected component of
$G[\mathcal{H}]$ will contain exactly one hammock $\tilde{H}_{k}$ of
$\tilde{\mathcal{H}}$ which was designated a root in $\tilde{\mathcal{H}}$
where $\tilde{r}_{k}=r_{k}\in T_{0}$ and so $\mathcal{H}$ is a _rooted_ forest
of hammocks (i.e. it assigns exactly one root per connected component of
$G[\mathcal{H}]$).

It remains to argue that $\mathcal{H}$ is lca-respecting with base tree
$T_{0}$. In particular, we must show if $H_{j}$ is the child of $H_{i}$ then
$V(H_{i})\cap V(H_{j})=\\{r_{j}\\}$ and the parent of $r_{j}^{\prime}$ in
$T_{\text{BFS}}$ is $\text{lca}(r_{j},r_{j}^{\prime})$ and
$\text{lca}(r_{j},r_{j}^{\prime})\in V(H_{i})$ or
$\text{lca}(r_{j},r_{j}^{\prime})=\text{lca}(r_{i},r_{i}^{\prime})$. Notice
that if $\tilde{H}_{j}$ is the child of $\tilde{H}_{i}$ in
$\tilde{\mathcal{H}}$ then we know that $H_{j}$ will be the child of $H_{i}$
in $\mathcal{H}$ and so this is immediate from Lemma 27. On the other hand, if
$H_{j}$ is the child of $H_{i}$ but $\tilde{H}_{j}$ was not the child of
$\tilde{H}_{i}$ then it must be the case that there is some dangling tree $T$
which connects $\tilde{r}_{j}$ to $\tilde{H}_{i}$ which was added to
$\tilde{H}_{i}$. It follows that $\tilde{H}_{j}$ was a root hammock in
$\tilde{\mathcal{H}}$ and so by Lemma 27 we know that $V(H_{i})\cap
V(H_{j})=\\{r_{j}\\}$ and the parent of
$r_{j}^{\prime}=\tilde{r}_{j}^{\prime}$ in $T_{\text{BFS}}$ is
$\text{lca}(r_{j},r_{j}^{\prime})$ and $\text{lca}(r_{j},r_{j}^{\prime})\in
V(H_{i})$. Additionally we must show that for each root hammock $H_{k}$ we
have $r_{k}\in V(T_{0})$ and the parent of $r_{k}$ and $r_{k}^{\prime}$ in
$T_{\text{BFS}}$ is $\text{lca}(r_{k},r_{k}^{\prime})$ and
$\text{lca}(r_{k},r_{k}^{\prime})\in V(T_{0})$. The former is immediate by how
we choose our roots and the latter follows from Lemma 27. ∎

Concluding, we have our hammock decomposition.

######  Lemma 29.

$(T_{0},\mathcal{H},E_{p})$ is a hammock decomposition which can be computed
in deterministic poly-time.

###### Proof.

First, notice that $(T_{0},\mathcal{H},E_{p})$ indeed partitions all edges by
construction. Moreover, by Lemma 28 we know that $\mathcal{H}$ is an lca-
respecting rooted forest of hammocks with base tree $T_{0}$. $G[\mathcal{H}]$
contains all shortest cross edge paths since $G[\bar{\mathcal{H}}]$ contains
all shortest cross edge paths by Lemma 22 and $G[\bar{\mathcal{H}}]$ is a
subgraph of $G[\mathcal{H}]$.

Lastly, we note that the above hammock decomposition is easily computable in
deterministic poly-time. In particular $\hat{\mathcal{H}}$ is trivial to
compute, $\bar{\mathcal{H}}$ can be computed by applying one valid assignment,
seeing which is the hammock guaranteed to exist by Lemma 18 in $I(T)$ for each
$T$ in $H_{\text{HJ}}\setminus\hat{H}$ and then assigning $T$ to this hammock.
$\tilde{\mathcal{H}}$ is trivially computable from $\bar{\mathcal{H}}$ and
$\mathcal{H}$ is trivially computable from $\tilde{\mathcal{H}}$. ∎

The above lemma immediately gives Theorem 4.

##  9 Scattering Chops via Hammock Decompositions

In this section, we prove Theorem 3. In particular, we show that every series-
parallel graph is $O(1)$-scatter-choppable (Definition 9) which by Lemma 4
demonstrates that every series-parallel graph is $O(1)$-scatterable (in
polynomial time). Combining this fact with Theorem 2 will give our SPR
solution. We will demonstrate that every series-parallel graph is
$O(1)$-scatter-choppable by using our hammock decompositions and, in
particular, Theorem 4.

The concrete lemma we will prove in this section is as follows. Clearly, the
lemma below combined with Lemma 4 proves Theorem 3.

######  Lemma 30.

Consider a graph $G$ with a hammock decomposition $\\{H_{j}\\}$. Then, there
exists a $c$-fuzzy, $O(1)$-scattering, $\Delta$-chop of $G$ with respect ot an
arbitrary root $r\in V$.

Figure 16: Construction of a $c$-fuzzy, $O(1)$-scattering, $\Delta$-chop.
There are two hammocks in the picture, $H_{j}$ and $H_{k}$.

Our $c$-fuzzy, $O(1)$-scattering, $\Delta$-chop construction is as follows;
see also Figure 16.

  1. 1.

Compute the $\Delta$-chops $A_{i}=\\{v\in V:(i-1)\Delta\leq
d(r,v)<i\Delta\\}$, and initialize $A^{\prime}_{i}=A_{i}$ for all $i$

  2. 2.

For each hammock $H_{j}$, independently in parallel:

    1. (a)

For each $A_{i}$ with $V(H_{j})\cap A_{i}\neq\emptyset$, independently in
parallel:

      1. i.

If $r_{j}\in A_{i}$ and $d(r,r_{j})\geq i\Delta-c\Delta$, then move all of
$\\{v\in V(H_{j}^{\prime})\cap A_{i}:i\Delta-c\Delta\leq d(r,v)<i\Delta\\}$
from $A^{\prime}_{i}$ to $A^{\prime}_{i+1}$

      2. ii.

If $d(r,r_{j})<i\Delta-c\Delta$, then move all $\\{v\in V(H_{j}^{\prime})\cap
A_{i}:d(r,v)\leq(i-1)\Delta+c\Delta\\}$ from $A^{\prime}_{i}$ to
$A^{\prime}_{i-1}$

In other words, $\mathcal{A}=\\{A_{i}\\}$ are the original $\Delta$-chops and
$\mathcal{A}^{\prime}=\\{A_{i}^{\prime}\\}$ are the sets after the
modifications above. All steps can be performed independently in parallel
because $c=1/3$ means that there is no interference between different $A_{i}$.

  3. 3.

For the base tree $T_{0}$, treat it as a subgraph $H_{j}$ with root $r_{j}=r$
(the root of $T_{BFS}$), and apply step 2(a) to it.

We begin with the following auxiliary lemmas:

######  Lemma 31.

Let $G$ be a series-parallel graph, and consider a (unique) shortest $u$–$v$
path in $G$ that is contained in hammock $H_{i}$. Then, $P$ contains at most
$2$ cross edges in $H_{i}$.

Figure 17: Setting for the proof of Lemma 31. The path $P$ is the red, dotted
path in the left. The green cycle and the blue claw on the right together form
a clawed cycle.

###### Proof.

Assume for contradiction that $P$ contains at least three cross edges. Then,
there exist $u_{1},u_{2},u_{3}$ on one tree of the hammock and
$v_{1},v_{2},v_{3}$ on the other tree such that the path $P$ contains as a
subpath the following edges/paths in order (see Figure 17): the edge $(u,v)$,
the $v_{1}$–$v_{2}$ path in $T_{BFS}$, the edge $(v_{2},u_{2})$, the
$u_{2}$–$u_{3}$ path in $T_{BFS}$, and the edge $(u_{3},v_{3})$. We first
claim that it is impossible for the following two conditions to hold
simultaneously, since they would imply that $G$ contains a $K_{4}$ minor:

  1. 1.

$\text{lca}(v_{1},v_{2})$ is a descendant of $\text{lca}(v_{1},v_{2},v_{3})$
(the least common ancestor of $v_{1},v_{2},v_{3}$), and

  2. 2.

$\text{lca}(u_{2},u_{3})$ is a descendant of $\text{lca}(u_{1},u_{2},u_{3})$.

Suppose for contradiction that both of these conditions hold. For ease of
notation, define
$u_{23}=\text{lca}(u_{2},u_{3}),u_{123}=\text{lca}(u_{1},u_{2},u_{3}),v_{12}=\text{lca}(v_{1},v_{2}),v_{123}=\text{lca}(v_{1},v_{2},v_{3})$.
Then, we can find a clawed cycle as follows (see Figure 17). Take the cycle
composed of edge $(u_{1},v_{1})$, the $v_{1}$–$v_{2}$ path in $T_{BFS}$, the
edge $(v_{2},u_{2})$, and the $u_{2}$–$u_{1}$ path in $T_{BFS}$, which
contains $u_{23}$ and $u_{123}$ as distinct vertices. Take the claw rooted at
$v_{123}$ with following branches: the $v_{123}$–$u_{123}$ path in $T_{BFS}$,
the $v_{123}$–$v_{12}$ path in $T_{BFS}$, and the path composed of the
$v_{123}$–$v_{3}$ path in $T_{BFS}$, the edge $(v_{3},u_{3})$, and the
$u_{3}$–$u_{23}$ path in $T_{BFS}$. This clawed cycle identifies a $K_{4}$,
contradicting the assumption that $G$ is series-parallel.

Therefore, one of the two conditions is false. Suppose first that (1) is
false, which means that $v_{12}=v_{123}$. Replace the segment of $P$ from
$v_{12}$ to $v_{3}$ with the $v_{123}$–$v_{3}$ path in $T_{BFS}$, which is a
shortest $v_{123}$–$v_{3}$ path, so the length of the path cannot increase
after the replacement. It follows that the replacement path is also a shortest
$u$–$v$ path, contradicting the assumption that the shortest path is unique.

If (2) is false, then we can similarly replace the segment of $P$ from
$u_{23}$ to $u_{3}$ with the $u_{123}$–$u_{3}$ path in $T_{BFS}$, ∎

######  Lemma 32.

For each monotone path $P\in T_{BFS}$ of length at most $c\Delta$, the path
has $O(1)$ edges cut by $\mathcal{A}^{\prime}$.

###### Proof.

First, suppose that the path $P$ is disjoint from the base tree $T_{0}$. We
handle the base tree $T_{0}$ at the end of the proof.

Suppose that for some $i$, the path $P$ has an edge $(u,v)$ cut by
$\mathcal{A}^{\prime}$ that satisfies
$d(r,u),d(r,v)\in[i\Delta,i\Delta+c\Delta]$. The only way for this to happen
is if $u$ and $v$ belong to two different hammocks $H_{j},H_{\ell}$, and step
(a)ii. was applied to one hammock (say $H_{j}$) but not the other. In that
case, we have $r_{j}\notin A_{j}$, so $d(r,r_{j})<i\Delta$. Let $v^{\prime}$
be the first vertex on $P$ after exiting $H_{j}$. Then, we must have
$d(r,v^{\prime})<d(r,r_{j})$ regardless of whether $P$ exits $H_{j}$ via
$r_{j}$ or via $\text{lca}(r_{j},r_{j}^{\prime})$. It follows that
$d(r,v^{\prime})<d(r,r_{j})<i\Delta$, and since $P$ has length at most
$c\Delta$ for $c=1/3$, it will never again visit a vertex whose distance from
$r$ is in $[i^{\prime}\Delta,i^{\prime}\Delta+c\Delta]$ for some integer
$i^{\prime}$.

Suppose next that $P$ has an edge $(u,v)$ cut by $\mathcal{A}^{\prime}$ that
satisfies $d(r,u),d(r,v)\in[i\Delta-c\Delta,i\Delta)$. The only way for this
to happen is if $u$ and $v$ belong to two different hammocks $H_{j},H_{\ell}$,
and step (a)i. was applied to one hammock (say $H_{j}$) but not the other. In
that case, we have $d(r,r_{\ell})<i\Delta-c\Delta$. By the same argument from
before, $P$ must exit $H_{\ell}$ at some vertex $v^{\prime}$ satisfying
$d(r,v^{\prime})<d(r,r_{\ell})<i\Delta-c\Delta$, and it will never again visit
a vertex whose distance from $r$ is in
$[i^{\prime}\Delta-c\Delta,i^{\prime}\Delta)$ for some integer $i^{\prime}$.

Finally, it is easy to see by steps (a)i. and (a)ii. that $P$ cannot have any
edge $(u,v)$ cut by $\mathcal{A}^{\prime}$ that satisfy
$d(r,u),d(r,v)\in(i\Delta+c\Delta,(i+1)\Delta-c\Delta)$.

It follows that $P$ cuts at most one edge in each of the ranges
$\bigcup_{i\in\mathbbm{Z}}[i\Delta,i\Delta+c\Delta]$,
$\bigcup_{i\in\mathbbm{Z}}[i\Delta-c\Delta,i\Delta)$, and
$\bigcup_{i\in\mathbbm{Z}}(i\Delta+c\Delta,(i+1)\Delta-c\Delta)$, and at most
$O(1)$ edges in between the ranges.

Finally, we consider the case when $P$ intersects the base tree $T_{0}$. Let
$P_{0}=P\cap T_{0}$ be the subpath of $P$ inside $T_{0}$, and let
$P^{\prime}=P-P_{0}$ be the remainder of $P_{0}$, the latter of which has
$O(1)$ edges cut by $\mathcal{A}^{\prime}$ from before. Since $T_{0}$ is a
tree, $P_{0}$ cuts at most one edge in $T_{0}$ by construction, so in total,
$P=P_{0}\cup P^{\prime}$ has $O(1)$ edges cut by $\mathcal{A}^{\prime}$. ∎

######  Lemma 33.

For each shortest cross edge path $P$ of length less than $c\Delta$, the path
has at most $O(1)$ edges cut by $\mathcal{A}^{\prime}$.

###### Proof.

By property (1) of Definition 18, the shortest cross edge path $P$ is
contained in $G[\mathcal{H}]$, where $\mathcal{H}$ is the set of hammocks. Let
$H_{m}$ be the hammock of lowest depth (in $\mathcal{T}$) that shares an edge
with $P_{m}$. Remove the subpath $P_{m}\cap H_{m}$ from $P_{m}$, which splits
it further into two paths $P_{1},P_{2}$, each of which is monotone with
respect to the tree structure $\mathcal{T}$ in the following sense: the set of
hammocks that share edges with $P_{1}$ form a monotone path in the tree
$\mathcal{T}$ of hammocks, and the same for $P_{2}$. By Lemma 31, $P_{m}\cap
H_{m}$ is cut at most twice by $\mathcal{A}^{\prime}$. It suffices to argue
that $P_{1}$ is cut $O(1)$ times by $\mathcal{A}^{\prime}$; the argument for
$P_{2}$ will be symmetric.

Let $(x,y)$ be the first edge on $P_{1}$ that is cut by
$\mathcal{A}^{\prime}$. (If none exist, then we are done.) Suppose that $x\in
A^{\prime}_{i+1}$ and $y\in A^{\prime}_{i}$, and let $H_{j}$ be a hammock
containing $y$. Our goal is to show that all edges on $P_{1}$ that are cut by
$\mathcal{A}^{\prime}$ must belong to $H_{j}$. Assuming this, we are done by
Lemma 31.

We have two cases:

  1. 1.

$x=r_{\ell}$ is an endpoint for a child hammock $H_{\ell}$ of $H_{j}$. In this
case, regardless of whether step (a)i. is applied, we must have
$i\Delta-c\Delta\leq d(r,r_{\ell})\leq i\Delta$. We first claim that $P_{1}$
cannot cross between $A^{\prime}_{i}$ and $A^{\prime}_{i-1}$. Suppose
otherwise that it contains an edge $(u,v)$ with $u\in A^{\prime}_{i}$ and
$v\in A^{\prime}_{i-1}$. Then, we must have $d(r,v)\leq(i-1)\Delta+c\Delta$
(regardless if step (a)ii. was applied). So the path $P_{1}$ has length at
least $d(r,r_{\ell})-d(r,v)\geq\Delta-2c\Delta=c\Delta$, contradicting the
assumption that $P_{1}$ has length less than $c\Delta$.

We now claim that $P_{1}$ cannot cross between $A^{\prime}_{i}$ and
$A^{\prime}_{i+1}$ in hammock $H_{j}$ or beyond. In this case, we must have
$d(r,r_{j})<i\Delta-c\Delta$, since otherwise step (a)i. would add all
vertices in $V(H_{j})\cap A_{i}$ to $A_{i+1}^{\prime}$. Therefore, in order to
cross between $A^{\prime}_{i}$ and $A^{\prime}_{i+1}$ in $H_{j}$, the path
$P_{1}$ must reach a vertex $v$ with $d(r,v)>i\Delta+c\Delta$ since step
(a)ii. was applied to $A_{i}$. But then the path $P_{1}$ has length at least
$d(r,v)-d(r,r_{\ell})\geq c\Delta$, contradicting the assumption that $P_{1}$
has length less than $c\Delta$.

  2. 2.

Hammock $H_{j}$ contains both $x,y$. In this case, we must have
$d(r,r_{j})<i\Delta-c\Delta$, since otherwise step (a)i. would add all
vertices in $V(H_{j})\cap A_{i}$ to $A_{i+1}^{\prime}$. The argument that
$P_{1}$ cannot cross between $A^{\prime}_{i}$ and $A^{\prime}_{i-1}$ is
identical. We now claim that $P_{1}$ cannot cross between $A^{\prime}_{i}$ and
$A^{\prime}_{i+1}$ in any hammock after $H_{j}$. We have $d(r,x)\geq i\Delta$
(regardless if step (a)ii. was applied), and in order for $P_{1}$ to travel to
any hammock after $H_{j}$, it must reach either $r_{j}$ or
$\text{lca}(r_{j},r_{j}^{\prime})$. But then it has length at least
$d(r,x)-d(r,r_{j})\geq\Delta$, a contradiction.

∎

With the above lemmas in hand, we finally prove Lemma 30. Consider two
vertices $u,v$ of distance at most $\Delta$ in $G$. We want to show that the
(unique) shortest $u$–$v$ path $P_{0}$ has $O(1)$ edges cut by
$\mathcal{A}^{\prime}$. Partition $P_{0}$ into $O(1)$ many subpaths of length
less than $c\Delta$ each. We will transform each subpath into a different
shortest path between the two endpoints, and which has $O(1)$ edges cut by
$\mathcal{A}^{\prime}$.

We further subdivide path $P$ as follows. First, if $P$ contains no cross
edges, then it consists of at most two monotone paths, so by Lemma 32, it is
cut $O(1)$ times by $\mathcal{A}^{\prime}$. Therefore, for the rest of the
proof, we assume that $P$ has at least one cross edge. Let $P_{l}$ be the
subpath of $P$ from the beginning to just before the first cross edge of $P$,
and let $P_{r}$ be the subpath that begins just after the last cross edge of
$P$ and continues until the end. Let $P_{m}$ be the remaining subpath after
removing $P_{l},P_{r}$, so that $P_{l},P_{m},P_{r}$ partition the edges of
$P$. The subpaths $P_{l},P_{r}$ consist of at most two monotone paths in
$T_{BFS}$, so by Lemma 32, they are each cut $O(1)$ times by
$\mathcal{A}^{\prime}$. The subpath $P_{m}$ is a cross edge path, so by Lemma
33, it is cut $O(1)$ times.

##  10 Future Work

We conclude with directions for future work. First, we reiterate the main open
question in this area as previously stated by many prior works:

  1. 1.

For fixed $h$ does every $K_{h}$-minor-free graph admit an $O(1)$-SPR
solution?

The most exciting next step in settling this long-standing open question would
be to tackle the planar case. In particular, if one could demonstrate the
existence of a forest-like structure similar to hammock decompositions for
planar graphs then the techniques introduced in this work would solve the
planar case. Notably, it is not too hard to see that the reduction of Filtser
[20] of $O(1)$-SPR to $O(1)$-scattering partitions works even if every
shortest path is only approximately preserved by the scattering partition. In
particular, the reduction of Filtser [20] still works if one can only provide
a low-diameter partition where for any vertices $u$ and $v$ there is _some_
path between $u$ and $v$ with length at most $O(1)\cdot d_{G}(u,v)$ which is
incident to at most $O(1)$ parts. Consequently, the arguments presented in
this paper show that one need only demonstrate the existence of a forest-like
structure which _approximates_ the distances between cross edges up to a
constant to make use of the scattering chops introduced in this work. Thus, an
extremely promising next avenue would be to show that every planar graph has a
forest-like subgraph which approximately preserves the distances between all
cross edges.

## References

  * Ahmed et al. [2020] Reyan Ahmed, Greg Bodwin, Faryad Darabi Sahneh, Keaton Hamm, Mohammad Javad Latifi Jebelli, Stephen Kobourov, and Richard Spence.  Graph spanners: A tutorial review.  _Computer Science Review_ , 37:100253, 2020.
  * Althöfer et al. [1993] Ingo Althöfer, Gautam Das, David Dobkin, Deborah Joseph, and José Soares.  On sparse spanners of weighted graphs.  _Discrete & Computational Geometry_, 9(1):81–100, 1993.
  * Arora et al. [1998] Sanjeev Arora, Michelangelo Grigni, David R Karger, Philip N Klein, and Andrzej Woloszyn.  A polynomial-time approximation scheme for weighted planar graph tsp.  In _Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)_ , volume 98, pages 33–41, 1998.
  * Bartal [1996] Yair Bartal.  Probabilistic approximation of metric spaces and its algorithmic applications.  In _Symposium on Foundations of Computer Science (FOCS)_ , pages 184–193. IEEE, 1996.
  * Basu and Gupta [2008] Amitabh Basu and Anupam Gupta.  Steiner point removal in graph metrics.  _Unpublished Manuscript, available from http://www. math. ucdavis. edu/~ abasu/papers/SPR. pdf_ , 1:25, 2008.
  * Bern et al. [1987] Marshall W. Bern, Eugene L. Lawler, and Alice L Wong.  Linear-time computation of optimal subgraphs of decomposable graphs.  _Journal of Algorithms_ , 8(2):216–235, 1987\.
  * Bodlaender [1998] Hans L Bodlaender.  A partial k-arboretum of graphs with bounded treewidth.  _Theoretical computer science_ , 209(1-2):1–45, 1998.
  * Bodlaender and De Fluiter [1996] Hans L Bodlaender and Babette De Fluiter.  Parallel algorithms for series parallel graphs.  In _Annual European Symposium on Algorithms (ESA)_ , pages 277–289. Springer, 1996.
  * Caspi and Dekel [1995] Yuval Caspi and Eliezer Dekel.  Edge coloring series parallel graphs.  _Journal of Algorithms_ , 18(2):296–321, 1995\.
  * Chan et al. [2006] T-H Hubert Chan, Donglin Xia, Goran Konjevod, and Andrea Richa.  A tight lower bound for the steiner point removal problem on trees.  In _International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX)_ , pages 70–81. Springer, 2006.
  * Chebolu et al. [2012] Prasad Chebolu, Mary Cryan, and Russell Martin.  Exact counting of euler tours for generalized series-parallel graphs.  _Journal of Discrete Algorithms_ , 10:110–122, 2012.
  * Cheung [2018] Yun Kuen Cheung.  Steiner point removal—distant terminals don’t (really) bother.  In _Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)_ , pages 1353–1360. SIAM, 2018.
  * Cheung et al. [2016] Yun Kuen Cheung, Gramoz Goranci, and Monika Henzinger.  Graph minors for preserving terminal distances approximately-lower and upper bounds.  In _International Colloquium on Automata, Languages and Programming (ICALP)_ , 2016.
  * De Fluiter and Bodlaender [1997] Babette De Fluiter and Hans L Bodlaender.  Parallel algorithms for treewidth two.  In _International Workshop on Graph-Theoretic Concepts in Computer Science_ , pages 157–170. Springer, 1997.
  * Englert et al. [2014] Matthias Englert, Anupam Gupta, Robert Krauthgamer, Harald Racke, Inbal Talgam-Cohen, and Kunal Talwar.  Vertex sparsifiers: New results from old techniques.  _SIAM Journal on Computing_ , 43(4):1239–1262, 2014.
  * Eppstein [1992] David Eppstein.  Parallel recognition of series-parallel graphs.  _Information and Computation_ , 98(1):41–55, 1992\.
  * Fakcharoenphol et al. [2004] Jittat Fakcharoenphol, Satish Rao, and Kunal Talwar.  A tight bound on approximating arbitrary metrics by tree metrics.  _Journal of Computer and System Sciences_ , 69(3):485–497, 2004.
  * Filtser [2018a] Arnold Filtser.  Steiner point removal with distortion o(log k), using the noisy-voronoi algorithm.  _arXiv preprint arXiv:1808.02800_ , 2018a.
  * Filtser [2018b] Arnold Filtser.  Steiner point removal with distortion o (log k).  In _Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)_ , pages 1361–1373. SIAM, 2018b.
  * Filtser [2020] Arnold Filtser.  Scattering and sparse partitions, and their applications.  In _International Colloquium on Automata, Languages and Programming (ICALP)_ , 2020.
  * Filtser et al. [2018] Arnold Filtser, Robert Krauthgamer, and Ohad Trabelsi.  Relaxed voronoi: A simple framework for terminal-clustering problems.  In _Annual ACM-SIAM Symposium on Simplicity in Algorithms (SOSA)_ , 2018.
  * Goranci et al. [2020] Gramoz Goranci, Monika Henzinger, and Pan Peng.  Improved guarantees for vertex sparsification in planar graphs.  _SIAM Journal on Discrete Mathematics_ , 34(1):130–162, 2020.
  * Gupta [2001] Anupam Gupta.  Steiner points in tree metrics don’t (really) help.  In _Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)_ , pages 682–690, 2001.
  * Gupta et al. [2004] Anupam Gupta, Ilan Newman, Yuri Rabinovich, and Alistair Sinclair.  Cuts, trees and l1-embeddings of graphs.  _Combinatorica_ , 24(2):233–269, 2004.
  * Hadlock [1975] Frank Hadlock.  Finding a maximum cut of a planar graph in polynomial time.  _SIAM Journal on Computing_ , 4(3):221–225, 1975\.
  * He and Yesha [1987] Xin He and Yaacov Yesha.  Parallel recognition and decomposition of two terminal series parallel graphs.  _Information and Computation_ , 75(1):15–38, 1987\.
  * Kamma et al. [2015] Lior Kamma, Robert Krauthgamer, and Huy L Nguyen.  Cutting corners cheaply, or how to remove steiner points.  _SIAM Journal on Computing_ , 44(4):975–995, 2015\.
  * Khuller [1989] Samir Khuller.  Ear decompositions.  _SigAct News_ , 20(1):128, 1989.
  * Kikuno et al. [1983] Tohru Kikuno, Noriyoshi Yoshida, and Yoshiaki Kakuda.  A linear algorithm for the domination number of a series-parallel graph.  _Discrete Applied Mathematics_ , 5(3):299–311, 1983.
  * Klein et al. [1993] Philip Klein, Serge A Plotkin, and Satish Rao.  Excluded minors, network decomposition, and multicommodity flow.  In _Annual ACM Symposium on Theory of Computing (STOC)_ , pages 682–690, 1993.
  * Krauthgamer and Rika [2020] Robert Krauthgamer and Havana Inbal Rika.  Refined vertex sparsifiers of planar graphs.  _SIAM Journal on Discrete Mathematics_ , 34(1):101–129, 2020.
  * Krauthgamer et al. [2014] Robert Krauthgamer, Huy L Nguyen, and Tamar Zondiner.  Preserving terminal distances using minors.  _SIAM Journal on Discrete Mathematics_ , 28(1):127–141, 2014.
  * Lee and Rashtchian [2012] James R. Lee and Cyrus Rashtchian.  A simpler proof of the kpr theorem.  https://tcsmath.wordpress.com/tag/klein-plotkin-rao/, January 2012\.
  * Robertson and Seymour [2004] Neil Robertson and Paul D Seymour.  Graph minors. xx. wagner’s conjecture.  _Journal of Combinatorial Theory, Series B_ , 92(2):325–357, 2004.
  * Roditty et al. [2005] Liam Roditty, Mikkel Thorup, and Uri Zwick.  Deterministic constructions of approximate distance oracles and spanners.  In _International Colloquium on Automata, Languages and Programming (ICALP)_ , pages 261–272. Springer, 2005.
  * Takamizawa et al. [1982] Kazuhiko Takamizawa, Takao Nishizeki, and Nobuji Saito.  Linear-time computability of combinatorial problems on series-parallel graphs.  _Journal of the ACM (JACM)_ , 29(3):623–641, 1982\.
  * Thorup and Zwick [2005] Mikkel Thorup and Uri Zwick.  Approximate distance oracles.  _Journal of the ACM (JACM)_ , 52(1):1–24, 2005\.
  * Wimer [1987] Thomas Victor Wimer.  Linear algorithms on k-terminal graphs.  _PhD Thesis_ , 1987.  AAI8803914.

##  Appendix A Metric Nested Ear Decompositions from Hammock Decompositions

A classic result of Eppstein [16] shows that a graph is a 2-vertex-connected
series-parallel graph if it has a “nested ear decomposition.” These nested ear
decompositions need not be unique and, in general, may have little to do with
the metric induced by the series-parallel graph. In this section we show how
to apply our hammock decompositions to find, among all possible nested ear
decompositions, a nested ear decomposition with strong properties regarding
how the metric and the nested ear decomposition interact.

We now give a series of definitions and theorems which formalize the nested
ear decompositions of Khuller [28] and Eppstein [16].

######  Definition 28 (Open Ear Decompositions).

An ear is a path whose endpoints may coincide. An ear decomposition is a
partition of the edges of a graph into (the edges of) ears
$P_{1},P_{2},\ldots$ where for each $i$ $\text{internal}(P_{i})$ is disjoint
from all vertices in $P_{1},\ldots,P_{i-1}$ and the two endpoints of $P_{i}$
are contained among the vertices of $P_{1},\ldots,P_{i-1}$. An ear
decomposition is open if the two endpoints of each $P_{i}$ for $i\geq 2$ are
distinct.

Khuller [28] introduced the notion of a tree ear decomposition and Eppstein
[16] strengthened this to the idea of a nested ear decomposition.

######  Definition 29 (Tree, Nested Ear Decomposition).

A tree ear decomposition is an open ear decomposition where for $i>1$ we have
that $P_{i}$ has both endpoints in the same $P_{j}$. A nested ear
decomposition is a tree ear decomposition where for each $P_{j}$ the
collection of ears with both endpoints in $P_{i}$ form a collection of nested
intervals.

Recall that a graph is 2-vertex connected if the deletion of any one vertex
still leaves the graph connected.

######  Theorem 5 (Eppstein [16]).

A 2-vertex-connected graph is series-parallel if and only if it has a nested
ear decomposition.

Concluding, we apply our hammock decompositions to strengthen the result of
Eppstein [16] to respect the input metric in the following way. Recall that a
shortest cross edge path is a path that starts and ends with a cross edge and
is also a shortest path.

######  Theorem 6.

Let $G=(V,E)$ be a 2-vertex-connected series-parallel graph with unit weights
and unique shortest path lengths. Fix a root $r\in V$ and a BFS tree
$T_{\text{BFS}}$ with cross edges $E_{c}:=E\setminus E(T_{\text{BFS}})$. Then
there is a collection of edges $E_{p}\subseteq E(T_{\text{BFS}})$ such that
$G$ has a nested ear decomposition $P_{1},P_{2},\ldots$ where

  1. 1.

Each $P_{i}$ is of the form $P_{u}\oplus\\{u,v\\}\oplus P_{v}$ where $P_{u}$
and $P_{v}$ are monotone paths from $u$ and $v$ towards $r$ and $\\{u,v\\}\in
E_{c}$.

  2. 2.

$|E(P_{i})\cap E_{p}|\leq 1$ and $(V,E\setminus E_{p})$ contains all shortest
cross edge paths. Furthermore after deleting all ears which contain an edge of
$E_{p}$ any two ears in the same connected component contain cross edges with
the same lca.

###### Proof.

Let $(T_{0},\mathcal{H},E_{p})$ be the hammock decomposition (Definition 18)
as guaranteed by Theorem 4.

We claim that since $G$ is 2-vertex-connected it must be the case that $T_{0}$
is a star with center $r$ and $\mathcal{H}$ consists of a single tree of
hammocks where $r_{k}$ and $r_{k}^{\prime}$ are children of $r$. To see why,
notice that since $G$ is $2$-vertex connected, for any children $u$ and $v$ of
$r$ there must be some cross edge with one endpoint in $T_{\text{BFS}}(u)$ and
another in $T_{\text{BFS}}(v)$ (since otherwise the deletion of $r$ would
separate the graph into 2 connected components). It follows that such a cross
edge will belong to a tree of hammocks which contains both $u$ and $v$ as
hammock roots. Applying this to all pairs of children of $r$ shows that all
children of $r$ must belong in the same hammock, thereby showing $T_{0}$ is a
star and $\mathcal{H}$ consists of a single tree of hammocks.

Continuing, we can construct the claimed nested ear decomposition as follows.
We let $D$ be our nested ear decomposition so far. We will process hammocks in
$\mathcal{H}$ in a BFS order according to the parent-child relationships
induced between hammocks in $\mathcal{H}$. To process a single hammock $H_{i}$
we simply find a candidate cross edge $\\{u,v\\}=e\in D\setminus E(H_{i})\cap
E_{c}$ and add to our nested ear decomposition $D$ the ear consisting of the
concatenation of $P_{u}$, $P_{v}$ and $e$ where $P_{u}$ is the path gotten by
going from $u$ towards $v$ until hitting a vertex in $D$ and $P_{v}$ is
defined symmetrically. We always choose as our cross edge $\\{u,v\\}$ an edge
such that there does not exist another cross edge
$\\{u^{\prime},v^{\prime}\\}$ in $E(H_{i})$ with either $u\prec u^{\prime}$ or
$v\prec v^{\prime}$.

It is easy to verify that if no candidate cross edge with the above properties
exists then there exists a clawed cycle.

The above construction satisfies properties (1) and (2) in the above theorem
statement by the properties of our hammock decompositions and so it remains
only to argue that the result is a nested ear decomposition.

First, we observe that the result of the above process will indeed partition
all edges. Every cross edge is included by construction. An edge in
$T_{\text{BFS}}$ will be added to $D$ the first time any cross edge with an
endpoint below it is processed. Since our graph is 2-vertex connected every
edge in $T_{\text{BFS}}$ has some cross edge with an endpoint below it and so
every edge in $T_{\text{BFS}}$ will end up in $D$

Our ear decomposition will be open by definition of our hammock decompositions
and, in particular, by the fact that the roots of a hammock are unrelated and
by the fact that $\mathcal{H}$ is lca-respecting.

Next, we verify that the result of this process is a tree ear decomposition.
Suppose for the sake of contradiction that the result of our construction is
not a tree ear decomposition. In particular, suppose $P_{l}$ is an ear with
one endpoint in $P_{i}$ and another endpoint in $P_{j}$. By definition of our
construction it must be the case that $P_{i}$ and $P_{j}$ are derived from
cross edges, say $e_{i}$ and $e_{j}$, which belong to the same hammock.
However, it then follows that the hammock fundamental cycle formed by $e_{i}$
and $e_{j}$ can be used to construct a clawed cycle, a contradiction. A
similar argument shows that if our ear decomposition fails to be nested then
we can find a clawed cycle. ∎

##  Appendix B Hammock Decomposition Construction Figures

In this section we give all of the illustrations of the construction of our
hammock decompositions on a single graph in Figure 18.

(a) Series parallel graph $G$.

(b) Lca-equivalence classes.

(c) Initial hammocks $\hat{\mathcal{H}}$.

(d) $\bar{\mathcal{H}}$ via hammock-joining paths.

(e) Lca paths $\mathcal{P}$.

(f) $\tilde{\mathcal{H}}$ via lca paths.

(g) $\mathcal{H}$ via dangling trees.

(h) Final hammock decomposition with $T_{0}$.

Figure 18: An illustration of the construction of our hammock decomposition on
a series-parallel graph.


#  On Second-Order Cone Functions

Shafiu Jibrin & James W. Swift
Department of Mathematics and Statistics
Northern Arizona University
Flagstaff, AZ 86011-5717, USA

###### Abstract

We consider the second-order cone function (SOCF)
$f:\mathbb{R}^{n}\to\mathbb{R}$ defined by $f(x)=c^{T}x+d-\|Ax+b\|$. Every
SOCF is concave. We give necessary and sufficient conditions for strict
concavity of $f$. The parameters $A\in\mathbb{R}^{m\times n}$ and
$b\in\mathbb{R}^{m}$ are not uniquely determined. We show that every SOCF can
be written in the form
$f(x)=c^{T}x+d-\sqrt{\delta^{2}+(x-x_{*})^{T}M(x-x_{*})}$. We give necessary
and sufficient conditions for the parameters $c$, $d$, $\delta$, $M=A^{T}A$,
and $x_{*}$ to be uniquely determined. We also give necessary and sufficient
conditions for $f$ to be bounded above.

_2000 Mathematics Subject Classification:_ 90C22, 90C25, 90C51.

_Keywords and phrases:_ Second-order cone constraint, second-order cone
programming, second-order cone function, convexity, optimization, interior-
point methods.

_email address:_<EMAIL_ADDRESS><EMAIL_ADDRESS>
##  1 Introduction

Second-order cone programming is an important convex optimization problem [4,
8, 14, 12]. A second-order cone constraint has the form $\|Ax+b\|\leq
c^{T}x+d$, where $\|\cdot\|$ is the Euclidean norm. This second-order cone
constraint is equivalent to the inequality $f(x)\geq 0$, where $f$ is what we
call a second-order cone function. The solution set of the constraint is
convex, and the function $f$ is concave [4, 10].

######  Definition 1.

A _second-order cone function (SOCF)_ is a function
$f:\mathbb{R}^{n}\to\mathbb{R}$ that can be written as

$f(x)=c^{T}x+d-\|Ax+b\|,$ (1.1)

for some choice of $c\in\mathbb{R}^{n}$, $d\in\mathbb{R}$,
$A\in\mathbb{R}^{m\times n}$, and $b\in\mathbb{R}^{m}$.

In second-order cone programming a linear function of $x$ is minimized subject
to one or more second-order cone constraints, along with the constraint
$Fx=g$, where $F\in\mathbb{R}^{p\times n}$ and $g\in\mathbb{R}^{p}$. The
solution set of $Fx=g$ is an affine subspace, and we will show that the
restriction of an SOCF to an affine subspace is another SOCF. Thus, from a
mathematical point of view the constraint $Fx=g$ is not necessary, although in
applications it can be convenient. In this paper we do not consider the
constraint $Fx=g$ but instead focus on understanding the family of SOCFs.

There are interior-point methods for solving second-order cone programming
problems. These methods usually use SOCFs to impose the second-order cone
constraints [7, 8, 10, 2]. The current research was started to get a deeper
understanding of SOCFs to improve the interior-point algorithm in [2]. Solvers
for second-order cone programming problems include CVXOPT and MATLAB [6, 1].
The study of second-order cone programming and its applications has continued
to generate interest for over three decades [13, 3, 14, 5].

In this paper we give a thorough description of the family of SOCFs. In the
form of Equation (1.1), the parameters $A$ and $b$ are not uniquely
determined, since $\|Ax+b\|=\|Q(Ax+b)\|=\|(QA)x+(Qb)\|$ for any orthogonal
$m\times m$ matrix $Q$. We show that every SOCF can be written in the form

$f(x)=c^{T}x+d-\sqrt{\delta^{2}+(x-x_{*})^{T}M(x-x_{*})},$

with the parameters $\delta\geq 0$, $x_{*}\in\mathbb{R}^{n}$, and the positive
semidefinite $M=A^{T}A\in\mathbb{R}^{n\times n}$ replace the parameters $A$
and $b$. We show that these new parameters are unique if and only if $M$ is
positive definite.

It is known that every SOCF $f$ is concave [4, 10]. We show that $f$ is
strictly concave if and only if $\text{rank}(A)=n$ and
$b\not\in\text{col}(A)$. In terms of the new parameters, the SOCF is strictly
concave if and only if $M$ is positive definite and $\delta>0$.

In the case where $M$ is positive definite we show that $f$ is bounded above
if and only if $c^{T}M^{-1}c\leq 1$. We show that the convex set
$\\{x\in\mathbb{R}^{n}\mid f(x)\geq 0\\}$ is bounded if and only if $M$ is
positive definite and $c^{T}M^{-1}c<1$.

##  2 Properties of Second-Order Cone Functions

The SOCFs on $\mathbb{R}$ (that is, $n=1$) are the simplest to understand, and
give insight into the general case.

######  Example 2.

Consider $f:\mathbb{R}\to\mathbb{R}$ defined by Equation(1.1) with
$A=\left[\begin{smallmatrix}1\\\ 0\end{smallmatrix}\right]$ and
$b=\left[\begin{smallmatrix}-x_{*}\\\ \delta\end{smallmatrix}\right]$. Thus
$Ax+b=\left[\begin{smallmatrix}x-x_{*}\\\ \delta\end{smallmatrix}\right]$, and
$\|Ax+b\|=\sqrt{\delta^{2}+(x-x_{*})^{2}}$, so
$f(x)=cx+d-\sqrt{\delta^{2}+(x-x_{*})^{2}}$. Figure 1 shows several graphs
with various values of the real parameters $\delta$, $x_{*}$, $c$, and $d$. If
$\delta\neq 0$, then $f$ is smooth and strictly concave, as shown by the solid
graphs. If $\delta=0$, then $f(x)=dx+d-|x-x_{*}|$ is piecewise linear with a
corner at $(x_{*},cx_{*}+d)$, as shown by the dashed graphs. Note that
$f(x_{*})=cx_{*}+d-|\delta|$ for any value of $\delta$, so the solid graphs in
Figure 1 (with $\delta=0.2$) pass a distance 0.2 below the corner of the
dashed graphs (with $\delta=0$), as indicated by the double arrows.

$c=0,\ d=1,x_{*}=0$${c=0.5,\ d=1,\ x_{*}=-0.5}$$c=1,\ d=1.5,\ x_{*}=-0.5$
Figure 1:  Graphs of second-order cone functions
$f(x)=cx+d-\sqrt{\delta^{2}+(x-x_{*})^{2}}$, as described in Example 2. In
each of the three plots, the parameters $c$, $d$, and $x_{*}$ are indicated.
The dashed curve has $\delta=0$, and solid curve has $\delta=0.2$.

One important property of SOCFs is that their restriction to an affine
subspace is another SOCF. We will frequently restrict to a 1-dimensional
affine subspace.

######  Remark 3.

Let $f:\mathbb{R}^{n}\to\mathbb{R}$ be written in the form of Equation (1.1).
The restriction of $f$ to the affine subspace $\\{x_{0}+By\mid
y\in\mathbb{R}^{k}\\}$, for some $x_{0}\in\mathbb{R}^{n}$ and
$B\in\mathbb{R}^{n\times k}$ is

$f(x_{0}+By)=(c^{T}B)y+(c^{T}x_{0}+d)-\|(AB)y+(Ax_{0}+b)\|,$

which is an SOCF on $\mathbb{R}^{k}$ with the variable $y$.

Recall that a function $f:\mathbb{R}^{n}\to\mathbb{R}$ is _concave_ provided
that $f((1-t)x_{0}+tx_{1})\leq(1-t)f(x_{0})+tf(x_{1})$ for all $x_{0}\neq
x_{1}\in\mathbb{R}^{n}$, and all $t\in(0,1)$. The function is _strictly
concave_ if the inequality is strict. A twice differentiable function
$f:\mathbb{R}\to\mathbb{R}$ is concave if $f^{\prime\prime}(x)\leq 0$ for all
$x$, and strictly concave if the inequality is strict.

######  Lemma 4.

Let $f:\mathbb{R}\to\mathbb{R}$ be the general SOCF of one variable, defined
by $f(x)=cx+d-\|Ax+b\|$ with parameters $c,d\in\mathbb{R}$ and
$A,b\in\mathbb{R}^{m}$. The function $f$ is concave for all parameters, and
$f$ is strictly concave if and only if $A\neq 0$ and $b\not\in\text{col}(A)$.

###### Proof.

If $A=0$, then $f(x)=cx+d-\|b\|$ is linear, and hence concave but not strictly
concave.

$\text{col}(A)$$A$$Ax_{*}$$\|A(x-x_{*})\|$$Ax$$-b$$\delta$$\|Ax+b\|$ Figure 2:
The geometry of an SOCF on $\mathbb{R}$. In this case
$A\in\mathbb{R}^{2}=\mathbb{R}^{2\times 1}$. Note that $Ax_{*}$ is the point
in $\text{col}(A)$ that is closest to $-b$. See Lemma 4.

Assume $A\neq 0$. Then $Ax_{*}$, where $x_{*}=-(A^{T}b)/(A^{T}A)$, is the
point in $\text{col}(A)=\text{span}(A)$ closest to $-b$. Let
$\delta=\|Ax_{*}+b\|$ be the distance from $Ax_{*}$ to $-b$. Thus
$\|Ax+b\|^{2}=\delta^{2}+\|A(x-x_{*})\|^{2}$ by the Pythagorean theorem, and
$f(x)=cx+d-\sqrt{\delta^{2}+\|A(x-x_{*})\|^{2}}=cx+d-\sqrt{\delta^{2}+(A^{T}A)(x-x_{*})^{2}}$.
The constant $A^{T}A$ is a positive real number. The geometry is shown in
Figure 2. Note that $\delta=0$ if and only if $b\in\text{col}(A)$. If
$\delta=0$, then $f(x)=cx+d-\sqrt{A^{T}A}|x-x^{*}|$ is piecewise linear with a
downward bend at $x_{*}$, and hence concave but not strictly concave.

So far, we have proved that $f$ is concave but not strictly concave if $A=0$
or $b\in\text{col}(A)$.

Assume that $A\neq 0$ and $b\not\in\text{col}(A)$. Then $\delta>0$, and $f$
strictly concave, since

$f^{\prime\prime}(x)=\frac{-\delta^{2}A^{T}A}{\big{(}\delta^{2}+A^{T}A(x-x_{*})^{2}\big{)}^{3/2}}$

is defined and negative for all $x$. ∎

######  Theorem 5.

Every second-order cone function $f$ is concave. Furthermore, $f$ is strictly
concave if and only if $\text{rank}(A)=n$ and $b\not\in\text{col}(A)$, using
the parameters in Definition 1.

###### Proof.

Let $x_{0}\neq x_{1}\in\mathbb{R}^{n}$, and define $v=x_{1}-x_{0}$. Let
$g:\mathbb{R}\to\mathbb{R}$ be defined by
$g(t):=f((1-t)x_{0}+tx_{1})=f(x_{0}+tv)=c^{T}(x_{0}+tv)+d-\|A(x_{0}+tv)+b\|$.
It follows directly from the definition that $f$ is (strictly) concave if and
only if $g$ is (strictly) concave for all $x_{0}\neq x_{1}$. Note that
$Av\in\mathbb{R}^{m}$. If $Av=0$, then $g$ is linear. If $Av\neq 0$, then

$g(t)=\tilde{c}\,t+\tilde{d}-\sqrt{\tilde{\delta}^{2}+\|Av\|^{2}(t-t_{*})^{2}},$

where $\tilde{c}=c^{T}v$, $\tilde{d}=c^{T}x_{0}+d$,
$\tilde{\delta}=\|A(x_{0}+t_{*}v)+b\|$, and
$t_{*}=\frac{-(Av)^{T}(Ax_{0}+b)}{(Av)^{T}Av}$ are all real numbers. Thus, $g$
is a second-order cone function of one variable. By Lemma 4, $g$ is concave
for all choices of $x_{0}$ and $x_{1}$, and hence $f$ is concave.

Since $A\in\mathbb{R}^{m\times n}$, it follows that $\text{rank}(A)\leq n$. If
$\text{rank}(A)<n$ then $A^{T}A$ is singular, and there exist $x_{0}\neq
x_{1}=x_{0}+v$ such that $Av=0$ and hence $g$ is linear. If
$b\in\text{col}(A)$ then there exist $x_{0}$ such that $Ax_{0}+b=0$. Thus
$t_{*}=0$ and $C_{2}=0$, and $g$ is piecewise linear with a downward corner.
Thus, if $\text{rank}(A)<n$ or $b\in\text{col}(A)$ (or both), we can find
$x_{0}\neq x_{1}$ such that $g$ is concave but not strictly concave, and hence
$f$ is not strictly concave.

Now assume $\text{rank}(A)=n$ and $b\not\in\text{col}(A)$. It follows that
$Av\neq 0$ and $C_{2}>0$ for all $x_{0}\neq x_{1}$. Lemma 4 implies that $g$
is strictly concave for all $x_{0}\neq x_{1}$, and it follows that $f$ is
strictly concave. ∎

Note that $A\in\mathbb{R}^{n\times n}$ cannot satisfy $\text{rank}(A)=n$ and
$b\not\in\text{col}(A)$. Therefore, any SOCF with $A\in\mathbb{R}^{n\times n}$
is concave but not strictly concave.

######  Example 6.

We give four examples of SOCFs on $\mathbb{R}^{2}$, with different truth
values of $\text{rank}(A)=2$ or $b\in\text{col}(A)$. These SOCFs have $c=0$
and $d=0$, so $f(x)=-\|Ax+b\|$. See Figure 3.

|
---|---
(a) | (b)
|
(c) | (d)
Figure 3:  Graphs of four SOCFs on $\mathbb{R}^{2}$. Note that the graph of
the SOCF (b) is indeed a cone. The top row shows functions with
$\text{rank}(A)=2$ and the bottom row shows $\text{rank}(A)=1$. The left
column shows $b\not\in\text{col}(A)$ and the right column shows
$b\in\text{col}(A)$. All the functions graphed are concave, but only the upper
left function is strictly concave, in agreement with Theorem 5. See Example 6.

_(a)_ $A=\left[\begin{smallmatrix}1&0\\\ 0&1\\\ 0&0\end{smallmatrix}\right]$
and $b=\left[\begin{smallmatrix}0\\\ 0\\\ 0.3\end{smallmatrix}\right]$ yields
$f(x)=-\sqrt{0.09+x_{1}^{2}+x_{2}^{2}}$.

_(b)_ $A=\left[\begin{smallmatrix}1&0\\\ 0&1\end{smallmatrix}\right]$ and
$b=\left[\begin{smallmatrix}0\\\ 0\end{smallmatrix}\right]$ yields
$f(x)=-\sqrt{x_{1}^{2}+x_{2}^{2}}$.

_(c)_ $A=\left[\begin{smallmatrix}1&0\\\ 0&0\\\ 0&0\end{smallmatrix}\right]$
and $b=\left[\begin{smallmatrix}0\\\ 0\\\ 0.3\end{smallmatrix}\right]$ yields
$f(x)=-\sqrt{0.09+x_{1}^{2}}$.

_(d)_ $A=\left[\begin{smallmatrix}1&0\\\ 0&0\end{smallmatrix}\right]$ and
$b=\left[\begin{smallmatrix}0\\\ 0\end{smallmatrix}\right]$ yields
$f(x)=-|x_{1}|$.

Notice that we have frequently rewritten $\|Ax+b\|$ in terms of a square root,
as in Examples 2 and 6. We have also noted that $\|Ax+b\|=\|QAx+Qb\|$ for any
orthogonal matrix $Q$, so many different choices of $A$ and $b$ define the
same SOCF. The next theorem describes a useful way to write an SOCF.

This theorem uses the Moore-Penrose Inverse of a matrix, also called the
pseudoinverse, which has many interesting properties found in [11]. For
example, $x=A^{+}b$ is the least squares solution to $Ax=b$, where
$A^{+}\in\mathbb{R}^{n\times m}$ is the pseudoinverse of
$A\in\mathbb{R}^{m\times n}$.

The next theorem mentions the well-known fact that $A^{T}A$ is a _positive
semidefinite_ matrix, which means that it is symmetric with non-negative
eigenvalues. A _positive definite_ matrix is a symmetric matrix with all
positive eigenvalues. If $A\in\mathbb{R}^{m\times n}$ then $A^{T}A$ is
positive definite if and only if the rank of $A$ is $n$.

######  Theorem 7.

Every SOCF of the form $f(x)=c^{T}x+d-\|Ax+b\|$ is identically equal to

$f(x)=c^{T}x+d-\sqrt{\delta^{2}+(x-x_{*})^{T}M(x-x_{*})},$ (2.1)

where $M=A^{T}A$ is positive semidefinite, $x_{*}=-A^{+}b$, and
$\delta=\|Ax_{*}+b\|$.

###### Proof.

It is well-known that the least squares solution to $Ax=-b$ is
$x_{*}=-A^{+}b$, and that $Ax_{*}=-AA^{+}b$ is the orthogonal projection of
$-b$ onto $\text{col}(A)$. That is, $Ax_{*}$ is the point in $\text{col}(A)$
that is closest to $-b$. Thus, the distance squared from $Ax$ to $-b$ is the
distance squared from $Ax$ to $Ax_{*}$ plus the distance squared from $Ax_{*}$
to $-b$. That is,

$\displaystyle\|Ax+b\|^{2}$ $\displaystyle=\|Ax-Ax_{*}\|^{2}+\|Ax_{*}+b\|^{2}$
$\displaystyle=\|A(x-x_{*})\|^{2}+\|Ax_{*}+b\|^{2}$
$\displaystyle=(x-x_{*})^{T}A^{T}A(x-x_{*})+\|Ax_{*}+b\|^{2}$
$\displaystyle=(x-x_{*})^{T}M(x-x_{*})+\delta^{2}.$

The last equality uses the definitions of $M$ and $\delta$. The result
follows. ∎

######  Remark 8.

For $A\in\mathbb{R}^{m\times n}$, note that $\text{rank}(A)=n$ if and only if
$A^{T}A\in\mathbb{R}^{n\times n}$ is positive definite. The definition of
$\delta$ in Theorem 7 makes it clear that $b\in\text{col}(A)$ if and only if
$\delta=0$. Therefore Theorem 5 implies that an SOCF written in the form of
Equation (2.1) is strictly concave if and only if $M$ is positive definite and
$\delta>0$.

######  Example 9.

The left half of Figure 4 shows the critical point and one contour of the SOCF
$f(x)=-\|Ax+b\|$, with

$A=\begin{bmatrix}1&0\\\ -1&1\\\ 0&2\end{bmatrix},\quad b=\begin{bmatrix}1\\\
1\\\ -1\end{bmatrix}.$

The right part of the same Figure shows the geometry behind Theorem 7, which
describes how to write the function in the form
$f(x)=-\sqrt{\delta^{2}+(x-x_{*})M(x-x_{*})}$. Calculations show

$A^{+}=\frac{1}{9}\begin{bmatrix}5&-4&2\\\ 1&1&4\end{bmatrix},\quad
M=A^{T}A=\begin{bmatrix}2&-1\\\ -1&5\end{bmatrix},\quad\textstyle\
x_{*}=\left(\frac{1}{9},\frac{2}{9}\right),\quad\text{and}\
\delta=\frac{5}{3}.$

The image of the square in $\mathbb{R}^{2}$ under $A$ is the light blue
parallelogram in $\mathbb{R}^{3}$, shown on the right side of Figure 4. The
vectors in $\mathbb{R}^{3}$ are the first (blue) and second (red) column of
$A$. These span the column space of $A$ in $\mathbb{R}^{3}$. The dot in
$\mathbb{R}^{2}$ is $x_{*}$, and the dot in the column space is
$Ax_{*}=-AA^{+}b=\left(1/9,1/9,4/9\right)$, which is the orthogonal projection
of $-b$ onto $\text{col}(A)$. The other dot in $\mathbb{R}^{3}$ is $-b$. The
distance from $Ax_{*}$ to $-b$ is $\delta=5/3$, so $f(x_{*})=-5/3$. The
ellipse on the left is the contour of $f$ with height $-2$. The image of the
ellipse under $A$ is the circle on the right, with is the set of points in the
column space that are distance $2$ from $-b$.

Figure 4: The geometry of the second-order cone function $f(x)=-\|Ax+b\|$,
with $A\in\mathbb{R}^{3\times 2}$ and $b\in\mathbb{R}^{3}$ defined in Example
9. The function can also be written as
$f(x)=-\sqrt{\delta^{2}+(x-x_{*})^{T}M(x-x_{*})}$, were $M=A^{T}A$. The
maximum of $f$ is at $x_{*}=-A^{+}b$, and the maximum value is
$f(x_{*})=-\delta$. The orthogonal projection of $-b$ onto the column space of
$A$ is $Ax_{*}=-AA^{+}b$. The distance from $Ax_{*}$ to $-b$ is $\delta$. One
contour of $f$ is shown. The image of this contour is a circle of points in
$\text{col}(B)$ that are equidistant from $-b$.

The proof Theorem 10, to follow, is subtle. While it is obvious that changing
one parameter will change the function $f$, it is difficult to eliminate the
possibility that more than one parameter can be changed while leaving the
function unchanged. For example, with the form of Equation (1.1), the function
$f$ is unchanged when $A\mapsto QA$ and $b\mapsto Qb$ for an orthogonal matrix
$Q$. The strategy in the proof is to uniquely determine one parameter at a
time in a specific order.

######  Theorem 10.

Assume an SOCF is written in the form of Equation (2.1), and that the same
SOCF is written with possibly different parameters satisfying the same
requirements, so

$f(x)=c^{T}x+d-\sqrt{\delta^{2}+(x-x_{*})^{T}M(x-x^{*})}=\tilde{c}^{T}x+\tilde{d}-\sqrt{\tilde{\delta}^{2}+(x-\tilde{x}_{*})^{T}\tilde{M}(x-\tilde{x}^{*})}$

for all $x$.

  * •

If $M=0$ (the zero matrix), then $\tilde{c}=c$, $\tilde{M}=0$,
$\tilde{d}-\tilde{\delta}=d-\delta$, and $\tilde{x}_{*}$ arbitrary, and

  * •

if $M\neq 0$, then $\tilde{c}=c$, $\tilde{d}=d$, $\tilde{\delta}=\delta$,
$\tilde{M}=M$, and $M\tilde{x}_{*}=Mx_{*}$.

As a consequence, the parameterization of an SOCF in the form of Equation
(2.1) is unique if and only if $M$ is positive definite.

###### Proof.

Recall that $M,\tilde{M}$ are positive semidefinite. It follows that $Mv=0$ if
and only if $v^{T}Mv=0$. Also, recall that $\delta,\tilde{\delta}$ are non-
negative real numbers.

For nonzero $v\in\mathbb{R}^{n}$ and $t\in[0,\infty)$, we consider the
function $f(vt)$ and its asymptotic behavior as $t\to\infty$. If $v^{T}Mv=0$,
then $f(vt)=c^{T}v\,t+d-\sqrt{\delta^{2}+x_{*}^{T}Mx_{*}}$. If $v^{T}Mv\neq
0$, then

$\displaystyle f(vt)$ $\displaystyle=c^{T}v\,t+d-\sqrt{\delta^{2}+(vt-
x_{*})^{T}M(vt-x_{*})}$
$\displaystyle=c^{T}v\,t+d-\sqrt{v^{T}Mv\,t^{2}-2v^{T}Mx_{*}t+x_{*}^{T}Mx_{*}+\delta^{2}}$
$\displaystyle=c^{T}v\,t+d-\sqrt{v^{T}Mv}\,t\,\sqrt{1+\frac{-2v^{T}Mx_{*}\,t+x_{*}^{T}Mx_{*}+\delta^{2}}{v^{T}Mv\,t^{2}}}$
$\displaystyle=\left(c^{T}v-\sqrt{v^{T}Mv}\right)t+d+\frac{v^{T}Mx_{*}}{\sqrt{v^{T}Mv}}+O(1/t)\text{
as }t\to\infty.$

The third equation uses the fact that $t\geq 0$, and the fourth equation uses
the Taylor series $\sqrt{1+\varepsilon}=1+\varepsilon/2+O(\varepsilon^{2})$.

For all $v\neq 0$ we have

$\frac{f(vt)-f(-vt)}{2}=\begin{cases}c^{T}v\,t&\mbox{ if }v^{T}Mv=0\\\
c^{T}v\,t+\frac{v^{T}Mx_{*}}{v^{T}Mv}+O(1/t)&\mbox{ if }v^{T}Mv\neq
0.\end{cases}$ (2.2)

A similar expression where $c$ is replaced by $\tilde{c}$ holds. If
$v^{T}Mv=0$, then $\tilde{c}^{T}v=c^{T}v$. If $v^{T}Mv\neq 0$, then the slope
of the slant asymptote is the same for both sets of parameters, so again
$\tilde{c}^{T}v=c^{T}v$. This holds for all $v$, so $\tilde{c}=c$.

For all $v\neq 0$ we have

$\frac{f(vt)+f(-vt)}{2}=\begin{cases}d-\sqrt{\delta^{2}+x_{*}^{T}Mx_{*}}&\mbox{
if }v^{T}Mv=0\\\ d-\sqrt{v^{T}Mv}\,t+O(1/t)&\mbox{ if }v^{T}Mv\neq
0\end{cases}$ (2.3)

along with a similar expression where $d$ is replaced by $\tilde{d}$, etc. If
$\tilde{M}\neq M$, then there is some vector $v$ such that
$v^{T}\tilde{M}v\neq v^{T}Mv$. This leads to a contradiction since the slope
of the slant asymptote in Equation (2.3) would be different. Thus,
$\tilde{M}=M$.

Assume $M=0$. Then $f(x)=c^{T}x+d-\delta=c^{T}x+\tilde{d}-\tilde{\delta}$,
since $\tilde{c}=c$, and $\tilde{M}=M=0$. Thus,
$\tilde{d}-\tilde{\delta}=d-\delta$.

Assume $M\neq 0$. Then there exists $v\in\mathbb{R}^{n}$ satisfy $Mv\neq 0$.
Using Equation (2.3) with $v^{T}\tilde{M}v=v^{T}Mv\neq 0$, we find that
$\tilde{d}=d$. At this point we conclude, from the equality of the two
expressions for $f$, that
$\delta^{2}+(x-x_{*})^{T}M(x-x_{*})=\tilde{\delta}^{2}+(x-\tilde{x}_{*})^{T}M(x-\tilde{x}_{*})^{T}$
for all $x$. Expanding the quadratic term and canceling like terms, we find
that $\delta^{2}-2x^{T}Mx_{*}=\tilde{\delta}^{2}-2x^{T}M\tilde{x}_{*}$ for all
$x$. Thus $\tilde{\delta}=\delta$ and $M\tilde{x}_{*}=Mx_{*}$.

Now we show that the parameterization of $f$ is unique if and only if $M$ is
positive definite. If $M$ is not positive definite there exist
$x_{*}\neq\tilde{x}_{*}$ such that $M\tilde{x}_{*}=Mx_{*}$. If $M$ is positive
definite then $M\neq 0$ and $M$ is invertible, so $\tilde{x}_{*}=x_{*}$ and
all of the parameters are unique. ∎

######  Example 11.

Let $f(x_{1},x_{2})=-\sqrt{4+(x_{1}-1)^{2}}$ be the SOCF on $\mathbb{R}^{2}$
defined by $c=0$, $d=0$, $\delta=2$, $M=\left[\begin{smallmatrix}1&0\\\
0&0\end{smallmatrix}\right]$, and $x_{*}=(1,0)$. Note that $M$ is not positive
definite. The null space of $M$ is $\text{span}\\{(0,1)\\}$. The
parameterization is not unique since any $x_{*}\in\\{(1,a)\mid
a\in\mathbb{R}\\}$ yields the same SOCF.

While many choices of $A$ and $b$ in the form of Equation (1.1) yield the same
function, there is a canonical choice for $A$ and $b$ starting with the
function in the form of Equation (2.1). Recall that a positive semidefinite
matrix $M$ has a unique positive semidefinite square root, denoted $M^{1/2}$.

######  Theorem 12.

Let $M\in\mathbb{R}^{n\times n}$ be positive semidefinite,
$x_{*}\in\mathbb{R}^{n}$, and $\delta\in\mathbb{R}$. Then
$\delta^{2}+(x-x_{*})^{T}M(x-x_{*})=\|Ax+b\|^{2}$ for

$A=\begin{bmatrix}M^{1/2}\\\ 0\end{bmatrix},\text{ and
}b=\begin{bmatrix}-M^{1/2}x_{*}\\\ \delta\end{bmatrix}.$

The last row of $A\in\mathbb{R}^{(n+1)\times n}$ is all 0s, and the last
component of $b\in\mathbb{R}^{n+1}$ is $\delta$.

###### Proof.

Note that $M^{1/2}$ is symmetric, and

$Ax+b=\begin{bmatrix}M^{1/2}x\\\
0\end{bmatrix}+\begin{bmatrix}-M^{1/2}x_{*}\\\
\delta\end{bmatrix}=\begin{bmatrix}M^{1/2}(x-x_{*})\\\ \delta\end{bmatrix}.$

Thus
$\|Ax+b\|^{2}=\delta^{2}+(x-x_{*})^{T}M^{1/2}M^{1/2}(x-x_{*})=\delta^{2}+(x-x_{*})^{T}M(x-x^{*})$.
∎

######  Remark 13.

It follows from this theorem that any SOCF can be defined in the form of
Equation (1.1) with $A\in\mathbb{R}^{(n+1)\times n}$. While $A$ is an $m\times
n$ matrix with any $m$, using $m>n+1$ is never needed.

Recall that the any non-constant SOCF is not bounded below, since it is
concave. We give necessary and sufficient conditions for an SOCF to be bounded
above with two theorems. The next theorem assumes that $M$ is positive
definite, and the case where $M$ is positive semidefinite is handled in
Theorem 16.

######  Theorem 14.

The SOCF $f:\mathbb{R}^{n}\to\mathbb{R}$ be written in the form (2.1),

$f(x)=c^{T}x+d-\sqrt{\delta^{2}+(x-x_{*})^{T}M(x-x_{*})}$

with $M$ positive definite, is bounded above if and only if $c^{T}M^{-1}c\leq
1$. More specifically,

  1. 1.

if $c^{T}M^{-1}c<1$ and $\delta=0$, then $x_{*}$ is the unique critical point
of $f$, and $f(x_{*})=c^{T}x_{*}+d$ is the global maximum value of $f$,

  2. 2.

if $c^{T}M^{-1}c=1$ and $\delta=0$, then every point in the ray
$\\{x_{*}+tM^{-1}c\mid t\geq 0\\}$ is a critical point of $f$, on which $f$
attains its maximum value of $f(x_{*})=c^{T}x_{*}+d$,

  3. 3.

if $c^{T}M^{-1}c>1$ and $\delta=0$, then $x_{*}$ is the unique critical point
of $f$, but $f$ is not bounded above,

  4. 4.

if $c^{T}M^{-1}c<1$ and $\delta>0$, then $\displaystyle
x_{cp}:=x_{*}+\frac{\delta M^{-1}c}{\sqrt{1-c^{T}M^{-1}c}}$ is the unique
critical point of $f$, and
$f(x_{cp})=c^{T}x_{cp}+d-\delta\sqrt{1-c^{T}M^{-1}c}$ is the global maximum
value of $f$,

  5. 5.

if $c^{T}M^{-1}c=1$ and $\delta>0$, then $f$ has no critical points and $f$
does have a global maximum value, but $f$ is bounded above by $c^{T}x_{*}+d$,
and

  6. 6.

if $c^{T}M^{-1}c>1$ and $\delta>0$, then $f$ has no critical points and $f$ is
not bounded above.

###### Proof.

To simplify the proof, we will analyze the SOCF
$\tilde{f}(x):=c^{T}x-\sqrt{\delta^{2}+x^{T}Mx}$. Note that
$f(x+x_{*})=\tilde{f}(x)+(d+c^{T}x_{*})$, and
$\tilde{f}(x-x_{*})=f(x)-d+c^{T}x_{*}$, so we can easily relate the critical
points, and the upper bounds, of $f$ and $\tilde{f}$.

Case I: $\delta=0$. In this case $\tilde{f}(x)=c^{T}x-\sqrt{x^{T}Mx}$. Let $v$
be any nonzero vector in $\mathbb{R}^{n}$. Since $v^{T}Mv>0$, the function
$t\mapsto\tilde{f}(vt)=(c^{T}v)t-\sqrt{v^{T}Mv}\,|t|$ is not differentiable at
$t=0$. Thus $0\in\mathbb{R}^{n}$ is a critical point of $\tilde{f}$ at which
$\tilde{f}$ is not differentiable, and $f$ has a critical point at $x_{*}$. To
determine if $\tilde{f}$ has a global maximum at 0, define
$g_{v}:[0,\infty)\to\mathbb{R}$ by
$g_{v}(t)=\tilde{f}(vt)=(c^{T}v)t-t\sqrt{v^{T}Mv}$. Note that $g_{v}$ is a
linear function giving the value of $\tilde{f}$ along a ray starting at
$0\in\mathbb{R}^{n}$ with the direction vector $v$. The function $\tilde{f}$
is bounded above if and only if the slope of $g_{v}$ is non-positive for all
directions $v$.

Let $\mathcal{E}=\\{x\in\mathbb{R}^{n}\mid x^{T}Mx=1\\}$. Note that
$\mathcal{E}$ is an ellipsoid centered at $0$, since $M$ is positive definite.
Furthermore, $g_{v}(0)=0$, so $\tilde{f}$ is bounded above if and only if the
maximum value of $\tilde{f}$, restricted to $\mathcal{E}$, is non-positive. We
compute this maximum value using the method of Lagrange multipliers. The
extreme values of $\tilde{f}$ restricted to $\mathcal{E}$ occur at places
where $\nabla(c^{T}x)=\lambda\nabla\sqrt{x^{T}Mx}$. This is equivalent to
$c=\lambda Mx/\sqrt{x^{T}Mx}$, or $\lambda Mx=c$ since $x^{T}Mx=1$ on
$\mathcal{E}$. Thus, the extrema of $\tilde{f}$ are at
$x=\frac{1}{\lambda}M^{-1}c$, where $\lambda$ is determined by $x^{T}Mx=1$.
Thus $\frac{1}{\lambda^{2}}c^{T}M^{-1}MMc=1$, so $\lambda^{2}=c^{T}M^{-1}c$.
There are two antipodal points on $\mathcal{E}$, $x_{\pm}=\frac{\pm
1}{\sqrt{c^{T}M^{-1}c}}M^{-1}c$, with extreme values of $\tilde{f}$ restricted
to $\mathcal{E}$. We see that
$\tilde{f}(x_{\pm})=c^{T}x_{\pm}-1=\pm\sqrt{c^{T}M^{-1}c}-1$. The maximum
value of $\tilde{f}$ restricted to $\mathcal{E}$ is $\sqrt{c^{T}M^{-1}c}-1$,
which occurs at $x_{+}$. Thus, the maximum slope of $g_{v}$ occurs when $v$ is
a positive scalar multiple of $M^{-1}c$, and that maximum slope has the same
sign as $\sqrt{c^{T}M^{-1}c}-1$, Thus, $\tilde{f}$ is bounded above if and
only if $c^{T}M^{-1}c\leq 1$.

If $c^{T}M^{-1}c<1$, then $0$ is the unique critical point of $\tilde{f}$, and
$\tilde{f}(0)=0$ is the global maximum value of $\tilde{f}$. Thus $x_{*}$ is
the unique critical point of $f$, and $f(x_{*})=c^{T}x_{*}+d$ is the global
maximum value of $f$. This proves part 1 in the theorem. If $c^{T}M^{-1}c=1$,
then the linear function $g_{v}$ has slope $0$ when $v=M^{-1}c$, and
$\tilde{f}$ achieves its maximum value of 0 at each point on the ray from $0$
through $M^{-1}c$. Every point in this ray, $\mathcal{C}=\\{tM^{-1}c\mid t\geq
0\\}$, is a critical point. Translating this result to the original $f$ proves
part 2. If $c^{T}M^{-1}c>1$, then the slope of $g_{v}$ is positive for some
$v$. Thus $\tilde{f}$ has an isolated critical point at $0$, but $\tilde{f}$
is not bounded above. This proves part 3 of the theorem.

Case II: $\delta>0$. The gradient of $\tilde{f}$ at $x$ is

$\nabla\tilde{f}(x)=c-\frac{Mx}{\sqrt{\delta^{2}+x^{T}Mx}}.$

In this case $\tilde{f}$ is smooth, and the critical points of $\tilde{f}$ are
solutions to $\nabla\tilde{f}(x)=0$. Since $M$ is positive definite,
$\tilde{f}$ is strictly concave by Theorem 5 and $\tilde{f}$ has at most one
critical point. If $\tilde{f}$ has a critical point then it must be a global
maximum and hence $\tilde{f}$ is bounded above. Denote the critical point of
$\tilde{f}$ as $x_{cp}$, if it exists, satisfies
$Mx_{cp}=c\sqrt{\delta^{2}+{x_{cp}}^{T}Mx_{cp}}$. It follows that the critical
point is a scalar multiple of $M^{-1}c$. Let $x_{cp}=\alpha M^{-1}c$. The
scalar $\alpha$ satisfies
$\alpha=\sqrt{\delta^{2}+\alpha^{2}(M^{-1}c)^{T}M(M^{-1}c)}=\sqrt{\delta^{2}+\alpha^{2}c^{T}M^{-1}c}$.
If $c^{T}M^{-1}c<1$ the unique solution is
$\alpha_{s}=\delta/\sqrt{1-c^{T}M^{-1}c}$, and if $c^{T}M^{-1}c\geq 1$ there
are no solutions for $\alpha$. Thus if $c^{T}M^{-1}c<1$ the function
$\tilde{f}$ has the critical point $\alpha_{s}M^{-1}c$, and the critical point
of $f$ is $x_{cp}=x_{*}+\alpha_{s}M^{-1}c$, and a calculation of $f(x_{cp})$
completes the proof of part 4.

We have already seen that $\tilde{f}$, and therefore $f$, has no critical
points when $c^{T}M^{-1}c\geq 1$. The results about boundedness and upper
bounds need the following asymptotic analysis. When $\|x\|$ is large then
$x^{T}Mx$ is large of order $O(\|x\|^{2})$ because $M$ is positive definite,
and
$\sqrt{\delta^{2}+x^{T}Mx}=\sqrt{x^{T}Mx}\sqrt{1+\delta^{2}/(x^{T}Mx)}>\sqrt{x^{T}Mx}$.
The Taylor expansion $\sqrt{1+\varepsilon}=1+\varepsilon/2+O(\varepsilon^{2})$
shows that
$\sqrt{\delta^{2}+x^{T}Mx}=\sqrt{x^{T}Mx}\big{(}1+\delta^{2}/(2x^{T}Mx)+O(\|x\|^{-4}\big{)}$.
Thus, an SOCF with $\delta>0$ is always less than the corresponding SOCF with
$\delta=0$, and the difference approaches 0 as $\|x\|\to\infty$. Parts 5 and 6
of the theorem follow. ∎

$c^{T}M^{-1}c<1$$c^{T}M^{-1}c=1$$c^{T}M^{-1}c>1$$\delta=0$$\delta=1$ Figure 5:
Contour plots of six different second-order cone functions defined in Example
15. All functions have the same positive definite matrix $M$. The parameters
$c$ and $\delta$ are chosen to illustrate Theorem 14, which says that $f$ is
bounded above if and only if $c^{T}M^{-1}c\leq 1$. The six parts of Theorem 14
correspond to the six contour plots. The contour with $f(x)=-1$ is a thick red
curve, and the spacing between contours is $\Delta f=0.5$.

######  Example 15.

Figure 5 shows the contour diagrams of 6 SOCFs of the form
$f(x)=c^{T}x-\sqrt{\delta^{2}+x^{T}Mx},$ with
$M=\left[\begin{smallmatrix}2&-1\\\ -1&5\end{smallmatrix}\right]$. The
eigenvalues of $M$ are $(7\pm\sqrt{13})/2$, so $M$ is positive definite and
Theorem 14 applies with the parameters $d=0$ and $x_{*}=(0,0)$. A calculation
shows that $M^{-1}=\frac{1}{9}\left[\begin{smallmatrix}5&1\\\
1&2\end{smallmatrix}\right]$. The other parameters are $\delta=0$ in the top
row, $\delta=1$ in the bottom row, $c=(0.7,0.7)$ in the left column, $c=(1,1)$
in the middle column, and $c=(1.3,1.3)$ in the right column. These values of
$c$ give $c^{T}M^{-1}c=0.7^{2},1$, and $1.3^{2}$, respectively. In the top row
$(0,0)$ is always a critical point and $f(0,0)=0$. In the top middle figure
the contour with height 0 is the ray in the direction
$M^{-1}c=\big{(}\frac{2}{3},\frac{1}{3}\big{)}$. In the bottom left figure we
find that
$x_{cp}=\big{(}\frac{1.4}{3},\frac{0.7}{3}\big{)}/\sqrt{1-.7^{2}}\approx(0.65,0.33)$
and $f(x_{cp})=-\sqrt{1-.7^{2}}\approx-.71$. In the bottom middle figure $f$
is bounded above by 0.

######  Theorem 16.

The SOCF $f:\mathbb{R}^{n}\to\mathbb{R}$ written in the form (2.1),

$f(x)=c^{T}x+d-\sqrt{\delta^{2}+(x-x_{*})^{T}M(x-x_{*})},$

with $M$ positive semidefinite is bounded above if and only if
$c\in\text{col}(M)$ and $c^{T}M^{+}c\leq 1$.

###### Proof.

Since $M$ is symmetric, the Fundamental Theorem of Linear Algebra states that
the null space of $M$ is the orthogonal complement of the column space of $M$.
We can write any $x\in\mathbb{R}^{n}$ as $x=x_{n}+x_{r}$ for unique $x_{n}\in
N(M)$ and $x_{r}\in\text{col}(M)$. Similarly, we split $c=c_{n}+c_{r}$. For a
fixed $x_{*}$, we write $x\in\mathbb{R}^{n}$ as $x=x_{*}+x_{n}+x_{r}$. Thus
$M(x-x*)=M(x_{n}+x_{r})=Mx_{r}$, and the general second-order cone function is

$f(x_{*}+x_{n}+x_{r})=c_{n}^{T}x_{n}+c_{r}^{T}x_{r}+(c^{T}x_{*}+d)-\sqrt{\delta^{2}+{x_{r}}^{T}Mx_{r}}.$

Assume $c\not\in\text{col}(M)$. Then $c_{n}\neq 0$ and $f$ is not bounded
since $f(x_{*}+x_{n})=c_{n}^{T}x_{n}+(c^{T}x_{*}+d-\delta)$ is an unbounded
linear function.

Assume $c\in\text{col}(M)$, so $c_{n}=0$. Define
$g:\text{col}(M)\to\mathbb{R}$ by

$g(x_{r}):=f(x_{*}+x_{n}+x_{r})=c_{r}^{T}x_{r}+(c^{T}x_{*}+d)-\sqrt{\delta^{2}+{x_{r}}^{T}Mx_{r}}.$

Note that $M$, restricted to $\text{col}(M)$ is a nonsingular map, so we can
apply Theorem 14 to $g$ as follows. The pseudo-inverse of $M$ satisfies

$M^{+}(x_{n}+x_{r})=M^{+}x_{r},\quad
MM^{+}(x_{n}+x_{r})=M^{+}M(x_{n}+x_{r})=x_{r}.$

Thus, the restriction of $M^{+}$ to $\text{col}(M)$ is the inverse of the
restriction of $M$ to $\text{col}(M)$. Theorem 14 says that $g$ is bounded
above if and only if $c_{r}^{T}M^{+}c_{r}\leq 1$. Note that
$c^{T}M^{+}c=c_{r}^{T}M^{+}c_{r}$ for any $c\in\mathbb{R}^{n}$.

We have shown that $f$ is not bounded above if $c\not\in\text{col}(M)$. We
have also shown that if $c\in\text{col}(M)$ then $f$ is bounded above if and
only if $c^{T}M^{+}c\leq 1$. These two statements can be combined into one:
$f$ is bounded above if and only if $c\in\text{col}(M)$ and $c^{T}M^{+}c\leq
1$. ∎

######  Remark 17.

If $M$ is positive definite, then $c\in\text{col}(M)=\mathbb{R}^{n}$ and
$M^{+}=M^{-1}$. Thus Theorem 16, in the case where $M$ is positive definite,
implies the that $f$ is bounded above if and only if $c^{T}M^{-1}c\leq 1$,
which is the first part of Theorem 14.

######  Example 18.

Consider the SOCF on $\mathbb{R}^{2}$ with $M=\left[\begin{smallmatrix}4&0\\\
0&0\end{smallmatrix}\right]$, $d=0$, and $x_{*}=(0,0)$,

$f(x)=c_{1}x_{1}+c_{2}x_{2}-\sqrt{\delta^{2}+4x_{1}^{2}}.$

Note that $f(0,x_{2})=c_{2}x_{2}-\delta$ is not bounded above if $c_{2}\neq
0$. If $c_{2}=0$ then $f(x)=c_{1}x_{1}-\sqrt{\delta^{2}+4x_{1}^{2}}\leq
c_{1}x_{1}-2|x_{1}|$ and $f(x)\to c_{1}x_{1}-2|x_{1}|$ as $x_{1}\to\pm\infty$.
Thus, $f$ is bounded above if and only if $c_{2}=0$ and $c_{1}^{2}\leq 4$.

This observation is predicted by Theorem 16. The column space of $M$ is
$\text{col}(M)=\\{(a,0)\mid a\in\mathbb{R}\\}$, so $c\in\text{col}(M)$ is
equivalent to $c_{2}=0$. The pseudo-inverse of $M$ is
$M^{+}=\frac{1}{4}\left[\begin{smallmatrix}1&0\\\
0&0\end{smallmatrix}\right]$, so $c^{T}M^{+}c=c_{1}^{2}/4$, and
$c^{T}M^{-1}c\leq 1$ is equivalent to $c_{1}^{2}\leq 4$.

One of that main uses of SOCFs is to define convex sets for optimization
problems. Optimization over a bounded set is very different from optimization
over a bounded set, so we finish this paper with a simple characterization.

######  Theorem 19.

Let $f:\mathbb{R}^{n}\to\mathbb{R}$ be defined by
$f(x)=c^{T}x+d-\sqrt{\delta^{2}+(x-x_{*})^{T}M(x-x^{*})}$, where $M$ is
positive semidefinite. Then the set $\mathcal{R}:=\\{x\in\mathbb{R}^{n}\mid
f(x)\geq 0\\}$ is closed and convex. Furthermore, $\mathcal{R}$ is bounded if
and only if $M$ is positive definite and $c^{T}M^{-1}c<1$.

###### Proof.

The set $\mathcal{R}$ is convex since $f$ is concave, and it is closed since
$f$ is continuous. If $M$ is not positive definite, then Theorem 16 implies
that $\mathcal{R}$ is not bounded, since $f$ is unbounded if
$c\not\in\text{col}(M)$, and $f$ achieves its maximum value on the unbounded
set $N(M)$ if $c\in\text{col}(M)$. If $M$ is positive definite, then Theorem
14 implies that $\mathcal{R}$ is bounded if and only if $c^{T}M^{-1}c<1$. ∎

######  Remark 20.

In the case where $M$ is positive definite and $c^{T}M^{-1}c<1$, the compact
$\mathcal{R}$ might be trivial. Let
$\tilde{d}:=d-\delta\sqrt{1-c^{T}M^{-1}c}$. The set $\mathcal{R}$ is the empty
set if $\tilde{d}<0$, $\mathcal{R}$ is the singleton set $\\{x_{*}\\}$ if
$\tilde{d}=0$, and $\mathcal{R}$ has a non-empty interior if $\tilde{d}>0$.

##  3 Conclusion

The second-order cone function has important application in optimization
problems. Our work gives necessary and sufficient conditions for strict
concavity of a second-order cone function. We show that every SOCF can be
written in the form $f(x)=c^{T}x+d-\sqrt{\delta^{2}+(x-x_{*})^{T}M(x-x_{*})}$,
which has unique parameters in many cases. This alternative parameterization
allows a deep understanding of the family of SOCFs. We characterize the
critical points and global maxima of $f$, depending on the parameters. We give
necessary and sufficient conditions for $f$ to be bounded above, and for the
set $\\{x\in\mathbb{R}^{n}\mid f(x)\geq 0\\}$ to be bounded.

## References

  * [1] M. Andersen, J. Dahl, and L. Vandenberghe, “CVXOPT - Cone Programming”, Accessed 23 July 2023, http://cvxopt.org/userguide/coneprog.html
  * [2] B. Dawuda, S. Jibrin and I. Abdullahi, “A Weighted Analytic Center for Second-Order Cone Constraints”, Applied and Computational Mathematics, vol. 10, no. 6, 2021, pp. 146-155
  * [3] H. Fawzi, “On representing the positive semidefinite cone using the second-order cone”, Mathematical Programming, vol. 175, no. 1-2, 2019, pp. 109–118.
  * [4] M. S. Lobo, L. Vandenberghe, S. Boyd, H. Lebret, “Applications of second-order cone programming”, Linear Algebra and Its Applications, vol. 284, 1998, pp. 193-228.
  * [5] X. Luo and A. Wächter, “A Quadratically Convergent Sequential Programming Method for Second-Order Cone Programs Capable of Warm Starts”, Optimization Online, 2022, https://optimization-online.org/2022/07/8978/
  * [6] MathWorks, “Second-order cone programming solver - MATLAB coneprog”, Accessed 23 July 2023, https://www.mathworks.com/help/optim/ug/coneprog.html
  * [7] L. Potra, S.J. Wright, “Interior-point methods”, Journal of Computational and Applied Mathematics, vol. 124, no. 1-2,2000, pp. 281–302.
  * [8] R.J. Vanderbei and H. Yurttan , “Using LOQO to Solve Second-Order Cone Programming Problems”, Technical Report SOR-98-09, Statistics and Operations Research, Princeton University, 1998.
  * [9] L. Vandenberghe and S. Boyd, “Convex Optimization”, Cambridge University Press, New York 2004.
  * [10] A. Weigandt, K. Tuthill, S. Jibrin, “Constraint Consensus Methods for Finding Interior Feasible Points in Second-Order Cones”, Journal of Applied Mathematics, vol. 2010, Article ID 307209, 2010, 19 pages
  * [11] Wikipedia, “Moore-Penrose Inverse”, Wikimedia Foundation, Accessed 20 July 2023, https://en.wikipedia.org/wiki/Moore-Penrose_inverse
  * [12] Wikipedia, “Second-Order Cone Programming”, Wikimedia Foundation, Accessed 19 July 2023, https://en.wikipedia.org/wiki/Second-order_cone_programming
  * [13] X. Zhang, D. Sheng, S. W. Sloan and K. Krabbenhoft, “Second-order cone programming formulation for consolidation analysis of saturated porous media”, Computational Mechanics volume, vol. 58, 2016, pp. 29–43.
  * [14] Q. Zhao, W. Fu and Z. Chen, “A Sensitivity Result for Quadratic Second-Order Cone Programming and its Application”, Applications of Mathematics, vol. 66, 2021, pp. 413–436