Sorbonne Université, CNRS, LIP6, F-75005 Paris<EMAIL_ADDRESS>Sorbonne Université, CNRS, LIP6, F-75005 Paris, France and Institut
Universitaire de France, Paris<EMAIL_ADDRESS>Sorbonne
Université, CNRS, LIP6, F-75005 Paris<EMAIL_ADDRESS>Evripidis Bampis, Bruno Escoffier and Michalis Xefteris [500]Theory of
computation Design and analysis of algorithms

###### Acknowledgements.

# Improved FPT Approximation for Non-metric TSP

Evripidis Bampis  Bruno Escoffier  Michalis Xefteris

###### Abstract

In the Traveling Salesperson Problem (TSP) we are given a list of locations
and the distances between each pair of them. The goal is to find the shortest
possible tour that visits each location exactly once and returns to the
starting location. Inspired by the fact that general TSP cannot be
approximated in polynomial time within any constant factor, while metric TSP
admits a (slightly better than) $1.5$-approximation in polynomial time, Zhou,
Li and Guo [26] introduced a parameter that measures the distance of a given
TSP instance from the metric case. They gave an FPT $3$-approximation
algorithm parameterized by $k$, where $k$ is the number of triangles in which
the edge costs violate the triangle inequality. In this paper, we design a
$2.5$-approximation algorithm that runs in FPT time, improving the result of
[26].

###### keywords:

TSP, FPT-approximation algorithms, fixed-parameter tractability

###### category:

##  1 Introduction

The Traveling Salesperson Problem (TSP) is a classic optimization problem in
the field of computer science and operations research. In (symmetric) TSP, we
are given a complete undirected graph $G=(V,E)$ with $n$ vertices and an edge
cost function $c:E\rightarrow\mathbb{R}_{\geq 0}$. The goal is to find a
minimum-cost cycle visiting every vertex exactly once (Hamiltonian cycle). TSP
has many applications in the logistics sector, particularly in optimizing and
planning delivery routes. Algorithms that solve TSP instances aid in reducing
both travel time and costs. Unfortunately, TSP is an NP-hard problem [17, 12];
it is solvable in exponential time (in time $O(n^{2}\cdot 2^{n})$ by
algorithms proposed independently by Bellman [3] and Held and Karp [13]), but
not in subexponential time $2^{o(n)}$ under ETH [14].

With respect to (polytime) approximation algorithms, TSP does not admit any
constant ratio approximation algorithm unless $P=NP$ [23], but some classical
subcases are well known to be easier to approximate. In particular, in the
metric case (i.e., when costs of edges satisfy the triangle inequality
$c(u,v)\leq c(u,w)+c(w,u)$), there exists a $3/2$-approximation algorithm in
$O(n^{3})$ time given independently by Christophides [6] and Serdyukov [24].
This ratio of 3/2 has been recently slightly improved [15, 16]. On the other
hand, metric TSP does not admit a PTAS unless $P=NP$ [22]. Arora [2] and
Mitchell [19] have shown that if we further restrict the instances to the
Euclidean case, where vertices are points in the plane (or more generally
points in a $d$-dimentional space) and distances are Euclidean distances, then
the problem (known to remain $NP$-hard) admits a PTAS. The asymmetric version
of the problem (i.e., TSP in directed complete graphs, where $c(u,v)$ may be
different from $c(v,u)$) has been also widely studied. The question whether
metric ATSP admits a constant approximation algorithm had been open for many
years, and recently got a positive answer [25].

In an attempt to generalize (symmetric) metric TSP instances to non-metric
instances, two approaches have been mainly considered. The first one is to
consider that only a relaxed version of the triangle inequality holds. Andreae
and Bandelt [1] proposed to relax the triangle inequality in the following
way: for some $\tau\geq 1$, we require that $c(u,v)\leq\tau[c(u,w)+c(w,v)]$
for every $u,v,w\in V$. For these instances of TSP, they proposed a
$(3\tau^{2}+\tau)/2$-approximation algorithm. Later, Bender and Chekuri [4]
improved this ratio for $\tau>7/3$ with a ratio of $4\tau$, and showed that
getting ratios sublinear in $\tau$ is impossible unless $P=NP$. The ratio has
been further improved for small values of $\tau$ down to $3(\tau+\tau^{2})/4$
in [21].

A second approach is to consider that triangle inequality is only verified in
some parts of the instances. In that vein, Mohan [20] designed a
$7/2$-approximation algorithm for a version of TSP where all vertices can be
partitioned into two parts $V_{1},V_{2}$ such that the induced subgraphs
$G[V_{1}]$ and $G[V_{2}]$ are metric. A recent work [26] defines some
parameters that measure how large is the “non-metric” part of the instance,
and then proposes parameterized approximation algorithms. Parameterized
complexity is a classic approach to solve $NP$-hard problems, the goal of
which is to express the complexity as a function of both the instance size
$|I|$ and a parameter $k$ on the instance. An FPT (for Fixed-Parameter
Tractable) algorithm is an algorithm whose time complexity is upper bounded by
$f(k)|I|^{O(1)}$. We refer the reader to some textbooks on parameterized
complexity such as [11, 7]. For some problems, there exist exact algorithms
with FPT time complexity, but for many others this is not possible, under
plausible complexity theoretic assumptions. A complementary approach to
address this intractability is to study parameterized approximation
algorithms. A parameterized $\rho$-approximation algorithm is a
$\rho$-approximation algorithm that runs in $f(k)\cdot|I|^{O(1)}$ time. Many
problems have been studied under the lens of parameterized approximability. We
refer the reader to the surveys for parameterized approximation algorithms of
[18] and [10]. The aforementioned PTAS of Arora [2] in $d$-dimensional metric
space can be seen as a parameterized PTAS, where the parameter is the
dimension $d$ of the space, as it gives a $(1+\epsilon)$-approximation
algorithm for metric TSP in time $f(d,\epsilon)\cdot n^{2}$ for some function
$f$. Another example is the work by Bockenhauer et al. [5] who studied TSP
with deadlines, in which a subset of $k$ vertices must be visited before a
given time. They designed a parameterized $2.5$-approximation algorithm for
the metric case running in $O(k!\cdot k+n^{3})$ time.

As mentioned above, and very closely related to our work, Zhou, Li and Guo
[26] introduced two parameters that measure the so-called “distance from
approximability” for TSP. In TSP, the distance between the inapproximable and
approximable case “translates” into the distance between a general TSP
instance and a metric TSP instance. First, they considered the number $k$ of
triangles in a general TSP instance, which do not satisfy the triangle
inequality (the edge costs of the triangle), and gave a $3$-approximation
algorithm in time $O\big{(}(3k)!8^{k}\cdot n^{2}+n^{3}\big{)}$. Additionally,
they introduced a second parameter $k^{\prime}$ which measures the minimum
number of vertices whose removal turns a general instance into a metric
instance. They designed a $(6k^{\prime}+9)$-approximation algorithm that runs
in time $O(k^{\prime O(k^{\prime})}\cdot n^{3})$ and a $3$-approximation
algorithm that runs in $O(n^{O(k^{\prime})})$ time. Note that it holds that
$k^{\prime}\leq k$.

#### Our contribution

In this paper, we revisit the problem of designing parameterized approximation
algorithms for TSP using a parameter that measures the distance between a
general TSP instance and a metric one, as introduced in [26]. More
specifically, we consider the parameter $k$ which measures the number of
triangles that violate the triangle inequality, and design an improved
$2.5$-approximation algorithm that runs in time $O\big{(}(3k)!8^{k}\cdot
n^{4}\big{)}$.

Our algorithm first follows almost the same steps as in the $3$-approximation
algorithm of Zhou, Li and Guo [26]. Roughly speaking, they build a specific
connected spanning subgraph of the initial graph, and then double some edges
to get an Eulerian graph. From an Euler tour of this graph they build a
Hamiltonian cycle. We point out a crucial difficulty here: as the graph is not
metric, transforming an Euler tour into a Hamiltonian cycle may increase
significantly its cost; to avoid this, shortcutting should only be done on
triangles satisfying triangle inequality. In our algorithm, instead of
doubling the edges to create an Eulerian graph, we compute a minimum-cost
perfect matching of a specific subgraph, drawing ideas from the Christofides’
algorithm [6]. We point again a difficulty due to non metricity: the usual
bound on the matching cost does not directly follows, as in non metric
instances the best Hamiltonian cycle of a subgraph can be larger that the one
of the initial graph. Adding the matching to the spanning subgraph gives an
Eulerian graph. To avoid the first shortcutting problem mentioned above, we
have an additional step between the construction of the Euler tour and
shortcutting vertices that are visited more than once. This step then allows
us to obtain a Hamiltonian cycle by carefully handling the shortcutting phase.

We also note that our algorithm (like the algorithm in [26]) runs in FPT time
$O(k_{T}!2^{k_{T}}n^{4})$ for the more intuitive parameter $k_{T}$ equal to
the number of vertices that appear in at least one triangle where the triangle
inequality is violated. This parameter can be much smaller than the number of
the violating triangles. In what follows, we first introduce some notation in
Section 2, and then give the description of the algorithm and the analysis of
its time complexity and approximation ratio (Section 3).

##  2 Preliminaries

In this section, we give some basic definitions and notation. We follow the
notation of [26]. Throughout the paper, we consider a simple undirected
complete graph $G(V,E)$ with an edge cost function
$c:E\rightarrow\mathbb{R}_{\geq 0}$. If for every $u,v,w\in V$ it holds that
$c(u,v)\leq c(u,w)+c(v,w)$, then the graph $G$ is called metric. When we refer
to a violating triangle $\Delta(u,v,w)$, we mean that at least one of
$c(u,v)\leq c(u,w)+c(v,w)$, $c(u,w)\leq c(u,v)+c(v,w)$ and $c(v,w)\leq
c(v,u)+c(w,u)$ does not hold. For an edge subset $E^{\prime}\subseteq E$, the
cost of $E^{\prime}$ is the total sum of the cost of its edges and is denoted
by $c(E^{\prime})$. The vertex set of $E^{\prime}$ is denoted by
$V(E^{\prime})$. For a vertex subset $V^{\prime}\subseteq V$, $E(V^{\prime})$
is the set of edges that connects two vertices in $V^{\prime}$, and
$G[V^{\prime}]=(V^{\prime},E(V^{\prime}))$ is the subgraph of $G$ induced by
$V^{\prime}$. For a positive integer $i$, set $[i]=\\{1,2,\dots,i\\}$.

A $t$-forest is an acyclic graph consisting of $t$ disjoint trees. When a
spanning subgraph of $G$ is a $t$-forest, it is called a spanning $t$-forest
of $G$. A spanning $t$-forest that has the minimum cost is a $t$-minimum
spanning forest ($t$-MSF) of $G$.

In this work, we study the TSP problem in which $k$ triangles violate the
triangle inequality. This parameter $k$ can be easily computed in $O(n^{3})$
time by considering all triangles of the input graph. We call a vertex “bad”
if it is contained in at least one of the $k$ violating triangles, and we
denote by $V^{b}$ the set of all bad vertices, with $|V^{b}|\leq 3k$. The rest
of the vertices are called “good” and the set of them is denoted by $V^{g}$.
For $b_{1},b_{2},b_{3}\in V^{b}$, the triangle formed by these three vertices
$\Delta(b_{1},b_{2},b_{3})$ may violate the triangle inequality. For example,
$c(b_{1},b_{3})+c(b_{2},b_{3})$ can be arbitrary less than $c(b_{1},b_{2})$.
Additionally, in any triangle $\Delta(g,u,v)$ that contains at least one
“good” vertex $g\in V^{g}$, with $u,v\in V$, all triangle inequalities between
$g,u,v$ hold.

For the rest of the paper, we denote the length of a TSP tour output by an
algorithm $ALG$ by $c(ALG)$ and that of an optimal (minimum length) TSP
solution $OPT$ by $c(OPT)$.

##  3 Parameterized Approximation for TSP

In this section, we will describe our $2.5$-approximation algorithm for TSP in
FPT time, parameterized by the number of violating triangles $k$. Our
algorithm first follows the initial steps of the $3$-approximation algorithm
of [26], and then carefully constructs a Hamiltonian cycle of all $n$
vertices. Let us first give a rough description of the main steps of our
algorithm, which will be given in more details in Section 3.1.

As in [26], the first step involves "guessing" the positions of bad vertices
in an optimal TSP solution, specifically their order and the "gaps" between
them where good vertices should be placed. This is achieved by enumerating all
possible permutations of the bad vertices and, for each permutation, all
partitions that respect the order of the permutation. In other words, the bad
vertices in each subset of a partition appear together in the optimal TSP
solution and follow the order dictated by the permutation. This means that the
bad vertices in one subset of the partition appear together in the optimal TSP
solution and respect the order of the permutation. Additionally, the subsets
occur in the order of the permutation, and at least one good vertex is
contained between any two consecutive subsets. Then, we compute a minimum-cost
spanning forest of only good vertices rooted at the (bad) end-vertices of the
subsets of the partition. In this way, we fill in the gaps between the subsets
in each partition of permutations with good vertices. A new graph $G^{\prime}$
is created, that contains (1) a Hamiltonian cycle of bad vertices which
follows the order in which an optimal TSP visits them, and (2) the minimum-
cost spanning forest that has been computed. Next, following the general idea
of the Christofides’ algorithm we find a minimum-cost perfect matching on the
vertices of odd degree in the built graph $G^{\prime}$. By adding this perfect
matching to $G^{\prime}$ we get a graph $H$ with only even-degree vertices. We
then make some local modifications, without increasing the total cost of
edges, that will eventually allow us to build a Hamiltonian cycle the cost of
which is not larger than the one of an Euler tour of $H$.

We introduce some additional notation, following the ones in [26], that will
help us describe our algorithm. A bad chain is one bad vertex or a path
consisting of distinct bad vertices. It is denoted by
$q=(b_{1},b_{2},\dots,b_{\ell})$ with $\ell\geq 1$, where $b_{i}\in V^{b}$ for
$i\in[\ell]$ and there exists an edge connecting $b_{i}$ and $b_{i+1}$ for
each $i\in[\ell-1]$. We use $b_{s}(q)$, $b_{e}(q)$ to refer to the starting
and ending vertices, respectively, and use $c(q)$ to denote the total cost of
the edges in $q$.

Moreover, an optimal TSP solution $OPT$ can be decomposed into an ordered
collection of $2t^{opt}$ many paths
$q_{1}^{opt},p_{1}^{opt},q_{2}^{opt},p_{2}^{opt},\dots,p_{t^{opt}}^{opt}$ with
$q_{i}^{opt}$ being a bad chain and
$p_{i}^{opt}=(b_{e}(q_{i}^{opt}),g_{i_{1}}^{opt},\dots,g_{i_{\ell_{i}^{opt}}}^{opt},b_{s}(q_{i+1}^{opt}))$
being the path connecting $b_{e}(q_{i}^{opt})$ and $b_{s}(q_{i+1}^{opt})$ with
only good internal vertices. Here $\ell_{i}^{opt}\geq 1$ and
$q_{t^{opt}+1}^{opt}=q_{1}^{opt}$. Of course $t^{opt}\leq 3k$.

###  3.1 Algorithm and Time Complexity

We are now ready to give the description of Algorithm 1. The algorithm uses
ShortCut (see Algorithm 2) as a subroutine (see Figure 1 and 2 for a graphic
illustration). Note that we assume that there exists at least one good vertex
in graph $G$, otherwise the problem becomes trivial and Algorithm 1 outputs
after Step 2(a) an optimal TSP solution.

Input: $G(V,E)$ with cost function $c:E\rightarrow\mathbb{R}_{\geq 0}$

  1. 11.

Compute all $k$ triangles that violate the triangle inequality, the set of bad
vertices

$V^{b}$ and the set of good vertices $V^{g}$.

* 22.

Enumerate all possible permutations of bad vertices. For each permutation,

3 enumerate all possible partitions of bad vertices into $t$ subsets for each
$t\in[|V^{b}|]$, respecting the corresponding order of permutation.

For each $t$-partition, do the following:

  1. 4(a)

Connect the bad vertices in each subset of the partition in the permutation

5 order, creating $t$ bad chains $Q=(q_{1},\dots,q_{t})$ according to the
order of the permutation. Additionally, connect $q_{i}$ with $q_{i+1}$ with
edge $(b_{e}(q_{i}),b_{s}(q_{i+1}))$,

for each $i\in[t]$ with $q_{t+1}=q_{1}$, resulting in one simple cycle $C$ of
all bad vertices.

* (b)

Compute a $t$-minimum spanning forest ($t$-MSF) $F=(T_{1},\dots,T_{t})$ of
$G[V^{g}\cup\\{b_{e}(q_{i})|i\in[t]\\}]$ rooted at
$\\{b_{e}(q_{i})|i\in[t]\\}$.

* 6(c)

Combine the edges of $C$ and $F$ to form a connected graph $G^{\prime}$ of all
vertices in

$V$. Let $O$ be the set of vertices with odd degree in $G^{\prime}$.

* (d)

Find a minimum-cost perfect matching $M$ in the subgraph induced in $G$ by
$O$.

* 7(e)

Combine the edges of $G^{\prime}$ and $M$ to form a connected multigraph $H$
in which

each vertex has even degree.

* (f)

Call ShortCut($H$) and output a TSP tour of $G$.

Algorithm 1 $2.5$-approximation Algorithm for TSP parameterized by $k$

Input: Multigraph $H$ with vertices $V=V^{g}\cup V^{b}$

  1. 11.

While there exists a double edge between vertices $b_{e}(q_{i}^{opt})$ and
$b_{e}(q_{i+1}^{opt})$ for $i\in[t^{opt}]$

with $q_{1}=q_{t{opt}}$, do the following:

  * •

Replace it with a simple edge that connects the two vertices.

  * 2•

If there is a good vertex $g^{alg}_{i}$ that is adjacent to
$b_{e}(q_{i}^{opt})$, remove the edge

$(b_{e}(q_{i}^{opt}),g^{alg}_{i})$, and add the edge
$(g^{alg}_{i},b_{e}(q_{i+1}^{opt}))$.

* 3•

If there is not such vertex, then find a good vertex $g^{alg}_{i+1}$ that is
adjacent to

$b_{e}(q_{i+1}^{opt})$, remove the edge
$(b_{e}(q_{i+1}^{opt}),g^{alg}_{i+1})$, and add the edge
$(g^{alg}_{i+1},b_{e}(q_{i}^{opt}))$.

* 2.

Form an Eulerian tour $T^{H}$ in $H$.

* 43.

Consider sequence $s$ of the visited vertices in $T^{H}$. Skip every repeated
bad vertex

5 $b\in V^{b}$ that has at least one adjacent good vertex (the first vertex is
adjacent to

the last one in $s$) until all bad vertices are unique.

* 4.

Skip all repeated good vertices and output a Hamiltonian cycle.

Algorithm 2 ShortCut($H$)

Let us first state a lemma that will help us compute the time complexity of
Algorithm 1.

######  Lemma 3.1 (Lemma 1 in [26]).

Given a graph $G=(V,E)$ and a subset $V^{\prime}$ of $V$, a minimum spanning
forest of $G$ rooted at $V^{\prime}$ can be computed in $O(|V|^{2})$ time.

######  Theorem 3.2.

Algorithm 1 runs in $O\big{(}(3k)!8^{k}\cdot n^{4}\big{)}$ time.

######  Proof 3.3.

Step 1 computes $k$ violating triangles in $O(n^{3})$ time. The number of
$t$-partitions of permutations enumerated in Step 2 is
$|V^{b}|!2^{|V^{b}|}=O\big{(}(3k)!8^{k}\big{)}$. For each possible
$t$-partition, Step 2(a) to Step 2(e) take in total $O(n^{4})$. It is easy to
see that the computation of a minimum-cost perfect matching is the most time-
consuming step of Algorithm 1. We can compute a minimum-cost perfect matching
in time $O(n^{4})$ using Edmonds’ algorithm [8, 9]. Note that Algorithm 2 runs
in linear time. Consequently, Algorithm 1 runs in $O\big{(}(3k)!8^{k}\cdot
n^{4}\big{)}$ time.

###  3.2 Analysis of Approximation Ratio

In this section, we prove the correctness of Algorithm 1 and show that it has
an approximation ratio of $2.5$. First, we have that for an optimal TSP
solution
$c(OPT)=\sum_{i=1}^{t^{opt}}c(q_{i}^{opt})+\sum_{i=1}^{t^{opt}}c(p_{i}^{opt})$.

Since we enumerate all partitions of every permutation of bad vertices in Step
2 of Algorithm 1, there exists an enumeration case, where we have $t^{opt}$
bad chains which contain exactly the same bad vertices in the same order as in
$OPT$. In the following, we focus on the case when the permutation of bad
vertices (with the right “gaps” of good vertices) in our algorithm and $OPT$
match. For a graphic illustration of Steps 2(a) and 2(b) of Algorithm 1 see
Figure 1.

First, we compute the cost of the cycle $C$ of bad vertices formed by
Algorithm 1 after Step 2(a). The cost of $C$ is

$c(C)=\sum_{i=1}^{t^{opt}}c(q_{i}^{opt})+\sum_{i=1}^{t^{opt}}c(b_{e}(q_{i}^{opt}),b_{s}(q_{i+1}^{opt})).$
(1)

To prove that the cost of the cycle of bad vertices $C$ is upper bounded by
$c(OPT)$ we use a lemma stated in [26]. In the following, we give its full
proof for completeness.

######  Lemma 3.4 (Lemma 3 in [26]).

For each $i\in[t^{opt}]$, $c(b_{e}(q_{i}^{opt}),b_{s}(q_{i+1}^{opt}))\leq
c(p_{i}^{opt})$, where $q_{t^{opt}+1}^{opt}=q_{1}^{opt}$.

######  Proof 3.5.

Every triangle that contains at least one good vertex satisfies the triangle
inequality (all three of them between the three vertices of the triangle).
Therefore, using repeatedly the triangle inequality we have that for each
$i\in[t^{opt}]:$

$\displaystyle c(b_{e}(q_{i}^{opt}),b_{s}(q_{i+1}^{opt}))\leq
c(b_{e}(q_{i}^{opt}),g_{i_{1}}^{opt})+c(g_{i_{1}}^{opt},b_{s}(q_{i+1}^{opt}))$
$\displaystyle\leq
c(b_{e}(q_{i}^{opt}),g_{i_{1}}^{opt})+c(g_{i_{1}}^{opt},g_{i_{\ell_{i}^{opt}}}^{opt})+c(g_{i_{\ell_{i}^{opt}}}^{opt},b_{s}(q_{i+1}^{opt}))$
$\displaystyle\leq
c(b_{e}(q_{i}^{opt}),g_{i_{1}}^{opt})+c(g_{i_{1}}^{opt},g_{i_{2}}^{opt},\dots,g_{i_{\ell_{i}^{opt}}}^{opt})+c(g_{i_{\ell_{i}^{opt}}}^{opt},b_{s}(q_{i+1}^{opt}))$
$\displaystyle\leq c(p_{i}^{opt}).$

From (1) and Lemma 3.4 we get that after Step 2(a): $c(C)\leq c(OPT)$.

After Step 2(b), we obtain a $t^{opt}$-minimum spanning forest ($t^{opt}$-MSF)
$F=(T_{1},\dots,T_{t^{opt}})$ of
$G[V^{g}\cup\\{b_{e}(q_{i})|i\in[t^{opt}]\\}]$ rooted at
$\\{b_{e}(q_{i})|i\in[t^{opt}]\\}$. As shown in Lemma 5 of [26], it holds that
$c(F)\leq c(OPT)$. Here again, we give the full proof for completeness.

######  Lemma 3.6 (Lemma 5 in [26]).

$c(F)\leq c(OPT)$.

######  Proof 3.7.

It is easy to see that a $t^{opt}$-spanning forest of
$G[V^{g}\cup\\{b_{e}(q_{i})|i\in[t^{opt}]\\}]$ rooted at
$\\{b_{e}(q_{i})|i\in[t^{opt}]\\}$ can be formed by removing some edges and/or
vertices from an optimal solution $OPT$. To show that, we first remove all bad
vertices not in $\\{b_{e}(q_{i})|i\in[t^{opt}]\\}$ and all edges incident to
them from $OPT$. Then, for each $i\in[t^{opt}]$, if $q_{i}^{opt}$ consists of
only one bad vertex, then we remove the edge connecting it with its preceding
good vertex. Thus, we get the desired $t^{opt}$-spanning forest which has cost
greater than or equal to the cost of the $t^{opt}$-minimum spanning forest
$F$.

Figure 1: An illustration of Steps 2(a) and 2(b) of Algorithm 1. $b_{i}$’s are
bad vertices and $g_{i}$’s are good vertices. Top left: the cycle represents
an optimal TSP solution. The algorithm “guesses” the occurrence order of bad
vertices and the “gaps” between bad vertices in the optimal TSP solution, but
the position of good vertices in the solution remains unknown. Top right: In
Step 2(a), Algorithm 1 creates a simple cycle $C$ of only bad vertices
following their order in the optimal solution. Bottom: The algorithm computes
a $4$-minimum spanning forest ($t=4$, as the number of bad chains in the
optimal TSP solution) of good vertices rooted at the bad end-vertices of each
chain ($b_{3},b_{5},b_{6},b_{8}$). Note that in this example, the $4$-minimum
spanning forest does not connect any good vertex to $b_{8}$.

Next, in Step 2(c), a connected graph $G^{\prime}$ that contains all vertices
$V$ of $G$ and the edges of $C$ and $F$ is created. Note that the number of
odd degree vertices $O$ in $G^{\prime}$ is even. Thus, there exists a perfect
matching in the subgraph induced in $G$ by $O$. Note that the vertices of $O$
are either good vertices or bad vertices $\\{b_{e}(q_{i})|i\in[t^{opt}]\\}$
that are roots for the spanning forest $F$, as each (bad) vertex that is not
contained in $F$ has degree exactly $2$, by construction.

In Step 2(d), the algorithm computes a minimum-cost perfect matching $M$ in
the subgraph induced in $G^{\prime}$ by $O$. We will show that $c(M)\leq
c(OPT)/2$.

######  Lemma 3.8.

$c(M)\leq c(OPT)/2$.

######  Proof 3.9.

Consider the optimal TSP tour (cycle) $OPT$ and the subset $O$ of vertices
that have odd degree in $G^{\prime}$. Note that all odd degree vertices are
either good vertices or bad end-vertices $b_{e}(q_{i}^{opt})$. Every
consecutive pair of bad end-vertices in $OPT$ has at least one good vertex
between them and adjacent to one of them in $OPT$. Let us denote by
$(o_{1},o_{2},\dots,o_{|O|})$ the ordered-set of odd degree vertices in
$G^{\prime}$ in the order of $OPT$. We will now shortcut $OPT$ to get a cycle
consisting of only vertices of odd degree. We can write $OPT$ as follows:

$OPT=(o_{1},u_{1_{1}},\dots,u_{1_{\ell_{1}}},o_{2},\dots,o_{|O|},u_{|O|_{1}},\dots,u_{|O|_{\ell_{|O|}}}).$

We have two cases for a pair of consecutive odd degree vertices
$(o_{i},o_{i+1})$:

  1. 1.

If $o_{i}$ or $o_{i+1}$ is a good vertex, then we can apply the triangle
inequality repeatedly using that good vertex and skip all vertices between
$o_{i}$ and $o_{i+1}$ in $OPT$ without increasing the cost.

  2. 2.

If both $o_{i}$ and $o_{i+1}$ are bad vertices, then as we explained there is
a good vertex $g$ between them and adjacent to $o_{i}$ or $o_{i+1}$. Using
that good vertex we can again repeatedly apply triangle inequality and skip
all vertices between $o_{i}$ and $o_{i+1}$ in $OPT$ without increasing the
cost.

Using triangle inequality in the way we described, we can get a simple cycle
of all odd degree vertices with cost upper bounded by $c(OPT)$. Now it is easy
to see that we have two disjoint perfect matchings and at least one them has
cost at most $c(OPT)/2$. Therefore, it also holds that $c(M)\leq c(OPT)/2$.

After Step 2(e) in Algorithm 1, a connected multigraph $H$ of all $n$ vertices
is formed, where each vertex has even degree, and the total cost of all edges
in $H$ is

$c(H)\leq c(C)+c(F)+c(M)\leq 2.5\cdot c(OPT).$

(a)

(b)

(c)

Figure 2: An illustration of Step 1 of ShortCut (Algorithm 2). $b_{i}$’s are
bad vertices and $g_{i}$’s are good vertices. Note that before (and after)
this step, all vertices have even degree. The purpose of this step is to
remove all double edges between bad vertices from the created graph. Here, we
would like to remove the double edge $(b_{3},b_{4})$ ($b_{3},b_{4}$ are both
end vertices, see Figure (a)). As you can see in Figure (b), we remove one
edge $(b_{3},b_{4})$ and the edge $(b_{3},g_{1})$ (red dotted edges). Finally,
we connect $g_{1}$ with $b_{4}$ (green edge) ensuring that the graph is
connected and all vertices have even degree. It is trivial to see that this
step does not increase the total cost of the edges of the graph due to the
triangle inequality in $\Delta(b_{3},g_{1},b_{4})$.

In the last step of the algorithm (Step 2(f)), we run subroutine
$\textsc{ShortCut}(H)$ (see Figure 2 for an illustration). As we explained,
all bad vertices have even degree in $G^{\prime}$ (before matching $M$) except
maybe for the bad end-vertices $b_{e}(q_{i}^{opt})$. Specifically, all bad
vertices that are not end-vertices have degree exactly $2$ before Step 2(d).
Thus, the only case in which a double-edge between two bad vertices can exist
in $H$ is when connecting two bad end-vertices (at least one of them has to
form a bad chain of a single vertex).

In Step 1 of ShortCut, for each double edge between bad vertices
$(b_{e}(q_{i}^{opt}),b_{e}(q_{i+1}^{opt}))$ we first find a good vertex
$g_{i}^{alg}$ that is adjacent to $b_{e}(q_{i}^{opt})$ or a good vertex
$g_{i}^{alg}$ that is adjacent to $b_{e}(q_{i}^{opt})$. To show the existence
of such a good vertex, assume that there are no good vertices adjacent to
either $b_{e}(q_{i}^{opt})$ or $b_{e}(q_{i+1}^{opt})$. Then, by construction
both bad vertices would have degree $2$ before Step 2(d) of Algorithm 1
(before the matching) and a double edge
$(b_{e}(q_{i}^{opt}),b_{e}(q_{i+1}^{opt}))$ could not occur in $H$: both
vertices would be connected with an edge and each one of them would be
connected with another bad vertex in the cycle (the only way that a double
edge would occur is if $b_{e}(q_{i}^{opt}),b_{e}(q_{i+1}^{opt})$ were the only
vertices in $G$, a trivial case). Therefore, there exists such a good vertex
for every double edge between bad vertices.

Assume wlog that we have a good vertex $g_{i}^{alg}$. In Step 1, Algorithm 2
removes an edge $(b_{e}(q_{i}^{opt}),b_{e}(q_{i+1}^{opt}))$ and edge
$(b_{e}(q_{i}^{opt}),g_{i}^{alg})$ and adds edge
$(g_{i}^{alg},b_{e}(q_{i}^{opt}))$. Using triangle inequality

$c(g_{i}^{alg},b_{e}(q_{i}^{opt})\leq(b_{e}(q_{i}^{opt}),b_{e}(q_{i+1}^{opt}))+c(b_{e}(q_{i}^{opt}),g_{i}^{alg}),$

we have that Step 1 does not increase the cost of the edges of the multigraph
$H$. The triangle inequality holds in any triangle that contains a good
vertex. Note also that this step reduces the degree of one bad vertex by 2,
and does not change the degree of other vertices. Then, after this step, every
vertex still has even degree. Thus, in Step 2 an Eulerian tour $T^{H}$ in $H$
can be found. The length of $T^{H}$ is at most $2.5\cdot c(OPT)$.

Consider tour $T^{H}$ as a sequence $s$ of the visited vertices. Let us state
a useful lemma about two occurrences of a bad vertex in $s$.

######  Lemma 3.10.

Let $b^{(1)}$ and $b^{(2)}$ be two (consecutive) occurrences of a bad vertex
$b\in V^{b}$ in $s$. Then, there exists an adjacent good vertex $g\in V^{g}$
in $s$ to one of the two occurrences of $b$.

######  Proof 3.11.

By construction we have that each bad vertex is adjacent to at most $3$ bad
vertices in $H$ (two in the cycle $C$ of bad vertices, and at most one in the
matching $M$) and that there are no double edges between two bad vertices. We
distinguish the following cases:

  * •

If there is only one vertex between $b^{(1)}$ and $b^{(2)}$, it cannot be bad
as there are no double edges connecting bad vertices, so it is a good one and
the statement occurs.

  * •

If there are at least two vertices between $b^{(1)}$ and $b^{(2)}$ then, since
every bad vertex is adjacent to at most $3$ bad vertices in $H$, we have that
there exists at least one good vertex adjacent to either $b^{(1)}$ or
$b^{(2)}$.

Therefore, in all cases the statement of the lemma is true.

Due to Lemma 3.10 we can skip every bad vertex that appears in $s$ more than
once without increasing the cost of the tour using triangle inequality (Step
3). In Step 4, we remove the good vertices that appear more than once in $s$
using again the triangle inequality. Consequently, we get a simple cycle of
all $n$ vertices (TSP tour) with cost $c($ and state the following theorem.

######  Theorem 3.12.

Algorithm 1 has an approximation ratio of $2.5$.

##  4 Conclusion

We studied the TSP problem parameterized by the number of triangles in which
the edge costs violate the triangle inequality and gave a $2.5$-approximation
algorithm that runs in FPT time, improving the approximation ratio of $3$ in
[26]. We believe that this line of work for TSP is particularly interesting
since it bridges the gap between the non-metric and metric case. A natural
question is whether one can further improve the approximation factor, getting
closer to the approximation factor of metric TSP. Another interesting research
direction is to consider the second parameter $k^{\prime}$, introduced in
[26], which measures the minimum number of vertices whose removal turns the
input instance into a metric one. It is an open question if there exists a
constant approximation FPT algorithm parameterized by $k^{\prime}$.

## References

  * [1] Thomas Andreae and Hans-Jürgen Bandelt.  Performance guarantees for approximation algorithms depending on parametrized triangle inequalities.  SIAM Journal on Discrete Mathematics, 8(1):1–16, 1995.
  * [2] Sanjeev Arora.  Polynomial time approximation schemes for euclidean traveling salesman and other geometric problems.  J. ACM, 45(5):753–782, sep 1998.
  * [3] Richard Bellman.  Dynamic programming treatment of the travelling salesman problem.  J. ACM, 9(1):61–63, jan 1962.
  * [4] Michael A. Bender and Chandra Chekuri.  Performance guarantees for the TSP with a parameterized triangle inequality.  Information Processing Letters, 73(1):17–21, 2000.
  * [5] Hans-Joachim Bockenhauer, Juraj Hromkovic, Joachim Kneis, and Joachim Kupke.  The parameterized approximability of TSP with deadlines.  Theory of Computing Systems, 41:431–444, 10 2007.
  * [6] Nicos Christofides.  Worst-case analysis of a new heuristic for the travelling salesman problem.  Technical Report 388, Graduate School of Industrial Administration, Carnegie Mellon University, 1976.
  * [7] Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh.  Parameterized Algorithms.  Springer, 2015.
  * [8] Jack Edmonds.  Maximum matching and a polyhedron with 0,1-vertices.  Journal of Research of the National Bureau of Standards Section B Mathematics and Mathematical Physics, page 125, 1965.
  * [9] Jack Edmonds.  Paths, trees, and flowers.  Canadian Journal of Mathematics, 17:449 – 467, 1965.
  * [10] Andreas Emil Feldmann, Karthik C. S., Euiwoong Lee, and Pasin Manurangsi.  A survey on approximation in parameterized complexity: Hardness and algorithms.  Electron. Colloquium Comput. Complex., TR20, 2020.
  * [11] Jörg Flum and Martin Grohe.  Parameterized Complexity Theory.  Texts in Theoretical Computer Science. An EATCS Series. Springer, 2006.
  * [12] M. R. Garey and D. S. Johnson.  Computers and Intractability: A Guide to the Theory of NP-Completeness.  W. H. Freeman, 1979.
  * [13] Michael Held and Richard M. Karp.  A dynamic programming approach to sequencing problems.  Journal of the Society for Industrial and Applied Mathematics, 10(1):196–210, 1962.
  * [14] Russell Impagliazzo and Ramamohan Paturi.  On the complexity of k-sat.  J. Comput. Syst. Sci., 62(2):367–375, 2001.
  * [15] Anna R. Karlin, Nathan Klein, and Shayan Oveis Gharan.  A (slightly) improved approximation algorithm for metric TSP.  Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2020.
  * [16] Anna R. Karlin, Nathan Klein, and Shayan Oveis Gharan.  A deterministic better-than-3/2 approximation algorithm for metric TSP.  In Alberto Del Pia and Volker Kaibel, editors, Integer Programming and Combinatorial Optimization, pages 261–274, Cham, 2023. Springer International Publishing.
  * [17] Richard Karp.  Reducibility among combinatorial problems.  volume 40, pages 85–103, 01 1972.
  * [18] Dániel Marx.  Parameterized complexity and approximation algorithms.  The Computer Journal, 51(1):60–78, 2008.
  * [19] Joseph S. B. Mitchell.  Guillotine subdivisions approximate polygonal subdivisions: A simple polynomial-time approximation scheme for geometric TSP, k-MST, and related problems.  SIAM Journal on Computing, 28(4):1298–1309, 1999.
  * [20] Usha Mohan, Sivaramakrishnan Ramani, and Sounaka Mishra.  Constant factor approximation algorithm for TSP satisfying a biased triangle inequality.  Theoretical Computer Science, 657:111–126, 2017.
  * [21] Tobias Mömke.  An improved approximation algorithm for the traveling salesman problem with relaxed triangle inequality.  Information Processing Letters, 115(11):866–871, 2015.
  * [22] Christos H. Papadimitriou and Mihalis Yannakakis.  The traveling salesman problem with distances one and two.  Math. Oper. Res., 18(1):1–11, 1993.
  * [23] Sartaj Sahni and Teofilo Gonzalez.  P-complete approximation problems.  J. ACM, 23(3):555–565, jul 1976.
  * [24] A. I. Serdyukov.  O nekotorykh ekstremal’nykh obkhodakh v grafakh.  Upravlyaemye sistemy, 17:76–79, 1978.
  * [25] Ola Svensson, Jakub Tarnawski, and László A. Végh.  A constant-factor approximation algorithm for the asymmetric traveling salesman problem.  J. ACM, 67(6):37:1–37:53, 2020.
  * [26] Jianqi Zhou, Peihua Li, and Jiong Guo.  Parameterized Approximation Algorithms for TSP.  In Sang Won Bae and Heejin Park, editors, 33rd International Symposium on Algorithms and Computation (ISAAC 2022), volume 248 of Leibniz International Proceedings in Informatics (LIPIcs), pages 50:1–50:16, Dagstuhl, Germany, 2022. Schloss Dagstuhl – Leibniz-Zentrum für Informatik.


# Network Function Computation With Different Secure Conditions

Min Xu, Gennian Ge and Minqian Liu M. Xu<EMAIL_ADDRESS>and M. Liu
<EMAIL_ADDRESS>are with the School of Statistics and Data Science, LPMC
& KLMDASR, Nankai University, Tianjin 300071, China. The research of M. Liu
was supported by the National Natural Science Foundation of China under Grant
No. 12131001, and National Ten Thousand Talents Program.G. Ge
<EMAIL_ADDRESS>is with the School of Mathematical Sciences, Capital Normal
University, Beijing 100048, China. The research of G. Ge was supported by the
National Key Research and Development Program of China under Grant Nos.
2020YFA0712100 and 2018YFA0704703, National Natural Science Foundation of
China under Grant No. 11971325, and Beijing Scholars Program.

###### Abstract

In this paper, we investigate function computation problems under different
secure conditions over a network with multiple source nodes and a single sink
node which desires a function of all source messages without error. A
wiretapper has access to some edges of the network. Based on different
practical requirements, we consider two secure conditions named as secure and
user secure respectively. The main parameter concerned here is the computing
rate, which is the average times of the target function that can be computed
securely or user securely without error for one use of the network. In the
secure case, a new upper bound which is tighter than the previous one is
provided for arithmetic sum functions and arbitrary networks. Moreover, we
show that the improved upper bound is strictly tight for tree-like networks.
In the user secure case, we give a sufficient and necessary condition for the
existence of user secure network codes and obtain an upper bound for the
computation capacity.

Keywords: network function computation, secure, user secure, capacity

##  I Introduction

In this paper, we study the problem of function computation over a
communication network with two different secure conditions. The general setup
of secure network function computation can be modeled as follows. In a
communication network characterized by a directed acyclic graph, there is a
sink node which wants to compute a function $f$ about the messages generated
at source nodes independently and uniformly. Meanwhile, there is a wiretapper
who has access to some edge subsets $W$ of the graph, we use $\mathcal{W}$ to
denote all possible wiretap sets. Each link of the network has unit
transmission capacity and each node has unlimited computation capacity. We
hope the sink node can compute the function without error and the wiretapper
can not get any information about the source message or the result of the
function.

In last few years, network function computation has attracted considerable
attention due to its application in sensor networks [1] and data processing
[2], etc. The security problem is necessary to be studied when the network
function computation is applied to practice.

###  I-A Related Works

The main parameter concerned in this paper is the computation capacity for the
sink node to reliably compute the target function over the network under the
secure conditions. It’s obvious that when $\mathcal{W}=\emptyset$, the secure
network function computation problem reduces to non-secure case, which has
been studied in recent years [3, 4, 5, 6, 7]. When the target function is
linear, given the network, the capacity of the network is completely
determined and the construction of achievable network codes is given [4].
However, for general target functions, there are some cut-set type upper
bounds of the computation capacity [5, 6, 7], but these upper bounds are not
always tight. Thus, we will focus on linear target function over finite field
in this paper.

There have been extensive studies and applications of the security problem in
network coding theory. In 2002, Cai and Yeung [12] first investigated the
existence of secure network codes. In network coding problem, there is a
single source node and multiple sink nodes, each wants a copy of the source
message. The secure condition means the wiretapper cannot get any information
about the source message. And some other secure conditions have also been
studied [9, 10]. For secure network function computing, limited work has been
done. Guang et al. [13] developed an upper bound of the capacity of secure
function computing for linear target functions in 2021. And Li et al. [11]
considered another secure condition which they called secret sum.

###  I-B Contributions and Organization

Our main results are as follows. On one hand, we show that Guang’s upper bound
in [13] is not tight by an example. From this example, we establish a new
upper bound of the capacity under the secure condition. Moreover, we show that
for a special class of networks, our new upper bound is tight. On the other
hand, we define a new secure condition based on practical requirements, and
investigate the same problem under the new secure condition. A sufficient and
necessary condition for the existence of secure network codes is addressed and
an upper bound of the computing capacity is obtained.

This paper is organized as follows. Section II introduces network function
computation problems under two different secure conditions and reviews some
existing bounds in related research works. In Sections III and IV, we focus on
the capacity under the secure condition in [13]. We establish our new upper
bound from an example and prove it in Section III. In Section IV, we derive
the condition of the linear transformation which turns a non-secure network
code into a secure one, and show that for a special class of networks, our new
upper bound is tight. For the new security, we address a sufficient and
necessary condition for the existence of secure network codes and establish an
upper bound by information-theoretical approach in Section V. Finally, we give
a conclusion of all results in Section VI.

##  II Model and Preliminaries

###  II-A Model and Secure Conditions

Let $\mathcal{N}=(V,E)$ be a directed acyclic graph where $V$ is the node set
and $E$ is the edge set. For any edge $e\in E$, we use $tail(e)$ and $head(e)$
to denote the tail and head of $e$. For any vertex $v\in V$, let
$In(v)=\\{e\in E:head(e)=v\\}$ and $Out(v)=\\{e\in E:tail(e)=v\\}$,
respectively. An edge sequence $\\{e_{1},e_{2},\cdots,e_{n}\\}$ is a $path$
from node $u$ to node $v$ if $tail(e_{1})=u,head(e_{n})=v$ and
$tail(e_{i+1})=head(e_{i})$ for $i=1,2,\cdots,n-1$. For two nodes $u,v\in V$,
a $cut$ of them is an edge set $C$ such that every path from $u$ to $v$
contains some edges in $C$. If $U\subset V$ is a set of nodes, the cut of $U$
and $v$ is the edge set separating any vertex $u\in U$ from $v$. The minimum
size of a cut of $u$ and $v$ is denoted as $mincut(u,v)$. There are two types
of special nodes in the graph. Source nodes are the nodes which have no
incoming edges and sink nodes are nodes which have no outgoing edges. In this
paper, we focus on multi-source single terminal network, denote the source
nodes as $S=\\{\sigma_{1},\sigma_{2},\cdots,\sigma_{s}\\}$ and the sink node
as $\rho$.

Generally, a target function $f:\mathcal{A}^{s}\mapsto\mathcal{O}$ is needed
to be computed at sink node $\rho$, where $\mathcal{A},\mathcal{O}$ are finite
fields. We assume that each source node in the network $\mathcal{N}$ generates
a sequence of random symbols over $\mathcal{A}$ independently and uniformly,
and each edge of the network transmits a symbol of $\mathcal{B}$ once a time,
where $\mathcal{B}$ is also a finite field. Let the message generated at
source node $\sigma_{i}$ be a random variable $M_{i}$, where
$M_{1},M_{2},\cdots,M_{s}$ are mutually independent. Computing the function
$l$ times implies source $\sigma_{i}$ generates a random vector
$\mathbf{M}_{i}=(M_{i1},\cdots,M_{il})$, and denote all the source messages by
$\mathbf{M}_{S}=(\mathbf{M}_{1},\cdots,\mathbf{M}_{s})$.

In secure network function computation, there is a wiretapper who wants
information about messages in the network. Let $\mathcal{W}$ be all possible
wiretap sets, and the wiretapper can access exactly one edge subset
$W\in\mathcal{W}$. $\mathcal{W}$ is known by the source nodes. The sink node
need to compute target function

$f(\mathbf{M}_{S})=(f(M_{1j},M_{2j},\cdots,M_{sj}):j=1,2,\cdots,l)$

without error while the wiretapper cannot get any useful information. In
network coding case, different secure conditions such as secure [8, 12],
weakly secure [9], strongly secure [10] are considered. In network function
computation case, Guang et al. [13] focused on protecting all source messages
from the wiretapper. Sometimes, in sensor network, the original messages
generated at sources are not important, while the computation result is. Li et
al. considered protecting the arithmetic sum of all source messages from the
wiretapper[11]. They assumed each edge has unlimited transmission capacity,
i.e. each edge can send unlimited symbols of $\mathcal{B}$ once a time. We are
concerned in this paper with the following two secure conditions.

$(secure)\ \ \ \ \ \ \ I(\mathbf{M}_{S};\mathbf{Y}_{W})=0,$ (1) $(user\
secure)\ \ I(f(\mathbf{M}_{S});\mathbf{Y}_{W})=0,$ (2)

where $\mathbf{Y}_{W}$ is the message transmitted by the edges in $W$ and
observed by the wiretapper. In network coding, the message sent by each node
is a function of all the messages the node has. Therefore, random keys are
needed under the secure condition. Otherwise, any edge could leakage the
information about $\mathbf{M}_{S}$. But for the user secure case, random keys
are not necessary.

An $(l,n)$ network code for the secure (or user secure) problem
$(\mathcal{N},f,\mathcal{W})$ is defined as follows. First, we let
$\mathbf{m}_{i}\in\mathcal{A}^{l}$ and $\mathbf{k}_{i}\in\mathcal{K}_{i}$ be
the outputs of the source message $\mathbf{M}_{i}$ and the key
$\mathbf{K}_{i}$ respectively, $\mathcal{K}_{i}=\emptyset$ if random keys are
not necessary. An $(l,n)$ network code consists of a local encoding function
for each edge $e$ which is defined as follows,

$\widehat{\theta}_{e}:\begin{cases}\mathcal{A}^{l}\times\mathcal{K}_{i}\mapsto\mathcal{B}^{n},&\mbox{if
$tail(e)=\sigma_{i}$ for some $i$};\\\ \prod\limits_{d\in
In(tail(e))}\mathcal{B}^{n}\mapsto\mathcal{B}^{n},&\mbox{otherwise},\end{cases}$
(3)

and a decoding function
$\widehat{\varphi}:\prod_{In(\rho)}\mathcal{B}^{n}\mapsto\mathcal{O}^{l}$. By
the definition of local encoding function, the message transmitted by edge $e$
denoted as $U_{e}$ is a function of all source messages and random keys, i.e.
for each $e\in E$,

$\widehat{g}_{e}(\mathbf{m}_{S},\mathbf{k}_{S})=\begin{cases}\widehat{\theta}_{e}(\mathbf{m}_{i},\mathbf{k}_{i}),&\mbox{if
$tail(e)=\sigma_{i}$ for some $i$};\\\
\widehat{\theta}_{e}(\widehat{g}_{In(tail(e))}(\mathbf{m}_{S},\mathbf{k}_{S})),&\mbox{otherwise}.\end{cases}$
(4)

We call $\widehat{g}_{e}$ as global encoding function of edge $e$. An $(l,n)$
network code works for secure or user secure function computation tasks over a
network if the sink node $\rho$ can compute target function without error,
i.e. for all $\mathbf{m}_{S}\in\mathcal{A}^{s\cdot l}$ and
$\mathbf{k}_{S}\in\prod_{i-1}^{s}\mathcal{K}_{i}$

$\widehat{\varphi}(\widehat{g}_{In(\rho)}(\mathbf{m}_{S},\mathbf{k}_{S}))=f(\mathbf{m}_{S}),$
(5)

and for any wiretap set $W$, the secure condition (1) and the user secure
condition (2) are satisfied respectively. The rate of such an $(l,n)$ code
$\mathbf{C}$ is defined by

$R(\mathbf{C})=\frac{l}{n}.$

We say a rate $R$ is achievable if there exists a valid network code with rate
$R$ with respect to $(\mathcal{N},f,\mathcal{W})$, which implies that by using
the network $n$ times, the sink node can compute target function securely (or
user securely) $l$ times. The capacity of the network $\mathcal{N}$ to compute
target function $f$ with possible wiretap set $\mathcal{W}$ is the maximum
achievable rate, i.e.

$\widehat{C}(\mathcal{N},f,\mathcal{W})=\max${$\frac{l}{n}$: there exists a
valid $(l,n)$ network code}.

In this paper, suppose $\mathcal{A}=\mathcal{B}=\mathcal{O}=\mathbb{F}_{q}$,
and $f$ is a linear function over $\mathbb{F}_{q}$, i.e.

$f(x_{1},x_{2},\cdots,x_{s})=\sum\limits_{i=1}^{s}a_{i}\cdot x_{i},$

where $a_{i}\in\mathbb{F}_{q}$ for all $i=1,2,\cdots,s$. Without loss of
generality, let $a_{i}\neq 0$, $\forall i=1,2,\cdots,s$. Otherwise, we can
remove the source nodes $\sigma_{i}$ for those $i$ such that $a_{i}=0$ and
consider computing the same target function over this new network. Moreover,
we let $y_{i}=a_{i}\cdot x_{i}$, and consider the sum function
$f^{\prime}(y_{1},y_{2},\cdots,y_{s})=\sum_{i=1}^{s}y_{i}$ over
$\mathbb{F}_{q}$. A secure (or user secure) network code for
$(f,\mathcal{N},\mathcal{W})$ is equivalent to a secure (or user secure)
network code for $(f^{\prime},\mathcal{N},\mathcal{W})$. From this
observation, we only need to consider the computing capacity for the
arithmetic sum function over $\mathbb{F}_{q}$.

Particularly, we consider the wiretap set with the form

$\mathcal{W}_{r}=\\{W\subset E:|W|\leq r\\},$

where $r$ is defined as the security level. In the rest of this paper, we use
$\widehat{C}(\mathcal{N},f,r)$ to denote
$\widehat{C}(\mathcal{N},f,\mathcal{W}_{r})$.

###  II-B Existing Bounds

First, let’s review some known results about secure network function
computation. For a network $\mathcal{N}$, let $C_{min}$ be the size of minimum
cut of $\mathcal{N}$. We call a cut as $\sigma_{i}$-cut if it is an edge
subset separating $\sigma_{i}$ from $\rho$ and there doesn’t exist any path
from other sources to this cut. For each source node $\sigma_{i}$, the minimum
size of a $\sigma_{i}$-cut is denoted as $D_{min}^{i}$.

An important result for linear network computation over finite field is that
the capacity of network $\mathcal{N}$ is $C_{min}$ [4]. For secure case, Guang
et al. established an upper bound [13]

$\widehat{C}(\mathcal{N},f,r)\leq\min\\{C_{min},D_{min}-r\\},$ (6)

where $D_{min}=\min_{\sigma_{i}\in S}\\{D_{min}^{i}\\}$. On the other hand,
similar to the construction of secure linear network codes, Guang et al. gave
a lower bound [13]

$\widehat{C}(\mathcal{N},f,r)\geq C_{min}-r.$ (7)

Whether the upper bound is tight is not known yet. In the scenario of user
secure, Li et al. investigated the problem under the assumption of unlimited
edge transmission capacity [11]. A sufficient and necessary condition for the
existence of user secure network codes was provided based on the network
topology.

##  III An Improved Upper Bound

We begin this section with an example which shows Guang’s upper bound is not
always tight.

Figure 1: The network has 2 sources and the target function is
$f=x_{1}+y_{1}$.

###### Example III.1

For the secure network function computation problem shown in $Fig.\ \ref{F1}$,
the minimum cut and minimum $\sigma_{i}$-cut in this network have size 1 and 3
respectively, i.e. $C_{min}=1,D_{min}=3$. When the security level $r=2$, which
means the wiretapper has access to any two edges, we have
$\widehat{C}(\mathcal{N},f,r)\leq 1$ from (6). In fact, there doesn’t exist a
secure code in this case. Suppose the wiretapper gets the messages transmitted
by $e_{4}$ and $e_{7}$ which are denoted as $U_{e_{4}}$ and $U_{e_{7}}$. If
there exists a secure network code, then $U_{e_{4}}$ is a function of the
source message and the random key generated at $\sigma_{2}$, i.e.
$U_{e_{4}}=g_{1}(\mathbf{y},\mathbf{k}^{\prime})$. Similarly,
$U_{e_{7}}=g_{2}(\mathbf{x},\mathbf{k},U_{e_{4}})$. Since the sink node can
complete the computation and $U_{e_{5}}$, $U_{e_{6}}$ contain no information
about $\mathbf{k}$, $U_{e_{7}}$ cannot contain any information about
$\mathbf{k}$ either, i.e. $U_{e_{7}}=g_{2}(\mathbf{x},U_{e_{4}})$. Now, after
getting $U_{e_{4}}$ and $U_{e_{7}}$ the wiretapper can get a function of
$\mathbf{x}$, which contradicts the secure condition (1).

From the example, we know that Guang’s upper bound is not tight although it is
tight over some special $(\mathcal{N},f,r)$, see examples in [13]. For any cut
$C$ in a network, let $I_{C}$ be the source nodes separated from $\rho$ by
$C$, i.e.

$I_{C}=\\{\sigma_{i}\in S:$ all paths from $\sigma_{i}$ to $\rho$ pass through
$C\\}$.

From a series of papers in network function computation [5, 6, 7], we know
that each of those sources which can attach to $C$, i.e. there exists a path
from the source to some edges in $C$, also matters to the capacity. Define

$J_{C}=\\{\sigma_{i}\in S\setminus I_{C}:$ there exists a path from
$\sigma_{i}$ to $C\\}$.

Now we define a new edge set for each cut $C$ as follows. Define

$\widehat{B}=\min\\{B\subset E:$ any path from $\sigma_{i}$ to $e$ pass
through, $\forall\sigma_{i}\in J_{C},\forall e\in C\\}$,

where the minimum is taken with respect to the size of $B$. For any cut $C$,
let $A=C\cup\widehat{B}$, and define
$A_{min}=\min_{C\in\Lambda}\\{|A|:A=C\cup\widehat{B}\\}$, where $\Lambda$ is
the collection of all cut sets of the network.

We present our upper bound in the following theorem.

###### Theorem III.2

Let $\mathcal{N}$ be a network and $f$ be an algebraic sum over a finite field
$\mathbb{F}_{q}$. If the security level $r\leq A_{min}$, then

$\widehat{C}(\mathcal{N},f,r)\leq\min\\{C_{min},A_{min}-r\\},$ (8)

and $\widehat{C}(\mathcal{N},f,r)=0$ otherwise.

###### Proof:

For the secure network function computation problem $(\mathcal{N},f,r)$,
suppose there exists an $(l,n)$ secure code. To prove the theorem, we only
need to show $l/n\leq A_{min}-r$.

Let the message generated at source node $\sigma_{i}$ be a random variable
$\mathbf{X}_{i}=(\mathbf{M}_{i},\mathbf{K}_{i})=(M_{i1},\cdots,M_{il},K_{i1},\cdots,K_{ir})$,
where $M_{ij},K_{ij^{\prime}},i\in[s],\ j\in[l],\ j^{\prime}\in[r]$ are
generated independently and uniformly at random over $\mathbb{F}_{q}$. Then by
the definition of entropy function, we have

$\mathbf{H}(\mathbf{M}_{i})=l\cdot\mathbf{H}(M_{ij})=l\cdot\log q,$

where the logarithm base is two. The message transmitted by any edge $e$ is
denoted as $U_{e}\in\mathbb{F}_{q}^{n}$.

Let $A=C\cup B$ be the edge set with size $A_{min}$, where $C$ is a cut of the
network and B is the minimum cut separating $J_{C}$ and $C$. Without loss of
generality, we assume $I_{C}=\\{\sigma_{1}\\}$, and consider a wiretap set
$W\subset A$ with size $r$. Let $\mathbf{Y}_{W}=\\{U_{e}:e\in W\\}$, and
$\mathbf{Y}_{A}=\\{U_{e}:e\in A\\}$. Since each source generates message
independently, we have

$l\cdot\log
q=\mathbf{H}(\mathbf{M}_{1})=\mathbf{H}(\mathbf{M}_{1}|\mathbf{M}_{S\setminus
D}),$ (9)

where $D=J_{C}\cup\\{\sigma_{1}\\}$. The secure condition (1) implies

$\mathbf{H}(\mathbf{M}_{1},\mathbf{M}_{S\setminus
D}|\mathbf{Y}_{W})=\mathbf{H}(\mathbf{M}_{1},\mathbf{M}_{S\setminus D}),$

$\mathbf{H}(\mathbf{M}_{S\setminus
D}|\mathbf{Y}_{W})=\mathbf{H}(\mathbf{M}_{S\setminus D})$.

Expanding both sides of the first equation, we get

$\displaystyle\mathbf{H}(\mathbf{M}_{1}|\mathbf{M}_{S\setminus
D},\mathbf{Y}_{W})+\mathbf{H}(\mathbf{M}_{S\setminus D}|\mathbf{Y}_{W})$
$\displaystyle=\mathbf{H}(\mathbf{M}_{1},\mathbf{M}_{S\setminus
D}|\mathbf{Y}_{W})$
$\displaystyle=\mathbf{H}(\mathbf{M}_{1},\mathbf{M}_{S\setminus D})$
$\displaystyle=\mathbf{H}(\mathbf{M}_{1}|\mathbf{M}_{S\setminus
D})+\mathbf{H}(\mathbf{M}_{S\setminus D}),$

which shows

$\mathbf{H}(\mathbf{M}_{1}|\mathbf{M}_{S\setminus
D},\mathbf{Y}_{W})=\mathbf{H}(\mathbf{M}_{1}|\mathbf{M}_{S\setminus D}).$ (10)

By the definition of edge set $A$, we know that every edge in $A$ transmits a
function of messages generated at sources in $D=J_{C}\cup\\{\sigma_{1}\\}$,
which means $\mathbf{Y}_{W}$ is a function of $\mathbf{M}_{D}$ and
$\mathbf{K}_{D}$. Then,

$\mathbf{H}(\mathbf{M}_{1}|\mathbf{M}_{S\setminus
D},\mathbf{Y}_{W})=\mathbf{H}(\mathbf{M}_{1}|\mathbf{M}_{S\setminus
D},\mathbf{Y}_{W},\mathbf{K}_{S\setminus D}).$ (11)

We claim that

$\mathbf{H}(\mathbf{M}_{1}|\mathbf{M}_{S\setminus
D},\mathbf{Y}_{A},\mathbf{K}_{S\setminus D})=0.$ (12)

This claim can be shown as follows

$\displaystyle\mathbf{H}(\mathbf{M}_{1}|\mathbf{M}_{S\setminus
D},\mathbf{Y}_{A},\mathbf{K}_{S\setminus D})$
$\displaystyle=\mathbf{H}(\mathbf{M}_{1}|\mathbf{M}_{S\setminus\\{1\\}},\mathbf{Y}_{A},\mathbf{K}_{S\setminus\\{1\\}})$
$\displaystyle=\mathbf{H}(\mathbf{M}_{1}|\mathbf{M}_{S\setminus\\{1\\}},\mathbf{Y}_{A},\mathbf{K}_{S\setminus\\{1\\}},\mathbf{Y}_{C^{\prime}})$
$\displaystyle=\mathbf{H}(\mathbf{M}_{1}|\mathbf{M}_{S\setminus\\{1\\}},\mathbf{K}_{S\setminus\\{1\\}},f(\mathbf{M}_{1},\cdots,\mathbf{M}_{s}))$
$\displaystyle\leq\mathbf{H}(\mathbf{M}_{1}|\mathbf{M}_{S\setminus\\{1\\}},f(\mathbf{M}_{1},\cdots,\mathbf{M}_{s}))=0,$

where $C^{\prime}=\bigcup_{i\in S\setminus\\{1\\}}Out(\sigma_{i})$. The first
equality holds for the independence of source messages and keys. By the
definition of $C^{\prime}$, $\mathbf{Y}_{C^{\prime}}$ is a function of
$\mathbf{M}_{S\setminus\\{1\\}}$ and $\mathbf{K}_{S\setminus\\{1\\}}$, then
the second equality follows. The third equation holds since that $A\cup
C^{\prime}$ is a global cut of the network, the target function can be
computed for any global cut messages. And the last equation is from that
$f(\mathbf{M}_{1},\cdots,\mathbf{M}_{s})=\mathbf{M}_{1}+\cdots+\mathbf{M}_{s}$
and $\mathbf{M}_{S\setminus\\{1\\}}$ is known.

Combining (9), (10), (11), (12), we get

$\displaystyle l\cdot\log q$
$\displaystyle=\mathbf{H}(\mathbf{M}_{1}|\mathbf{M}_{S\setminus
D},\mathbf{Y}_{W},\mathbf{K}_{S\setminus D})$
$\displaystyle=\mathbf{H}(\mathbf{M}_{1}|\mathbf{M}_{S\setminus
D},\mathbf{Y}_{W},\mathbf{K}_{S\setminus
D})-\mathbf{H}(\mathbf{M}_{1}|\mathbf{M}_{S\setminus
D},\mathbf{Y}_{A},\mathbf{K}_{S\setminus D})$
$\displaystyle=\mathbf{I}(\mathbf{M}_{1};\mathbf{Y}_{A\setminus
W}|\mathbf{M}_{S\setminus D},\mathbf{K}_{S\setminus D})$
$\displaystyle\leq\mathbf{H}(\mathbf{Y}_{A\setminus W})\leq(|A|-r)\cdot
n\cdot\log q.$

Then we can conclude that

$\frac{l}{n}\leq|A|-r=A_{min}-r.$

∎

Remark.  Comparing with Guang’s upper bound (6), we only change $D_{min}$ to
$A_{min}$. By the definition of $A_{min}$, if $C$ is a $\sigma_{i}$-cut of the
network, then $B=\emptyset$ since $J_{C}=\emptyset$, then $A=C\cup B=C$. Thus
$D_{min}$ is the minimum size of $A$, where the minimum is taken over all
$\sigma_{i}$-cut, and $A_{min}$ is the minimum taken over all cut. Therefore,
$A_{min}\leq D_{min}$ in general, which implies our new upper bound is tighter
than the previous one.

###### Example III.3

Consider the network function computation problem shown in $Fig.\ \ref{F1}$.
For $r=1$, our new upper bound shows $\widehat{C}(\mathcal{N},f,1)\leq 1$,
which is achievable and the secure code is the same as the example in [13].
For $r=2$, applying Theorem III.2, we have $\widehat{C}(\mathcal{N},f,2)\leq
0$, since $A_{min}=2$ for the network. This also matches our analysis in
Example III.1.

##  IV Lower Bound

For the lower bound of the secure computing capacity over a network, we need
to construct an algorithm to generate a secure $(l,n)$-code for any given
network, target function and security level, which is difficult in general.
For non-secure case, most known results about lower bound are obtained by
connecting the problem with equivalent network coding problem [3, 14]. Similar
to the construction of secure network coding problem, Guang et al. [13]
provided a lower bound with rate $C_{min}-r$ by a linear transformation at the
source nodes. In the following, we address a sufficient and necessary
condition of the linear transformation which turns a non-secure network code
into a secure one, and prove that for multi-edge tree graph, the upper bound
in Theorem III.2 is tight.

Recall that an $(l,n)$ network code can be represented by global encoding
functions for all edges in the network, i.e. $\\{\widehat{g}_{e}:e\in E\\}$.

We denote the message generated at each source node $\sigma_{i}$ as
$\mathbf{M}_{i}\in\mathbb{F}_{q}^{n-r}$, and denote the random key as
$\mathbf{K}_{i}\in\mathbb{F}_{q}^{r}$ in this section. Each edge $e\in E$
transmits a message of length 1 over $\mathbb{F}_{q}$. Such a linear secure
code has rate $n-r$, and each global encoding function can be represented by a
column vector $g_{e}\in\mathbb{F}_{q}^{sn}$, i.e.

$\widehat{g}_{e}(\mathbf{M}_{1},\mathbf{K}_{1},\cdots,\mathbf{M}_{s},\mathbf{K}_{s})=(\mathbf{M}_{1},\mathbf{K}_{1},\cdots,\mathbf{M}_{s},\mathbf{K}_{s})\cdot
g_{e}.$

A linear transformation at all source nodes is an $sn\times sn$ matrix $A$
which is a block diagonal matrix,

$A=\begin{pmatrix}A_{1}&0&\cdots&0\\\ 0&A_{2}&\cdots&0\\\
\vdots&\vdots&\ddots&\vdots\\\ 0&0&\cdots&A_{s}\end{pmatrix},$

where $A_{i}$ is an $n\times n$ transformation matrix at source node
$\sigma_{i}$. For $T\subset[sn]$, let $A_{T}$ be the matrix obtained by
selecting the columns of $A$ corresponding to $T$. For instance, $A_{\\{1\\}}$
is the first column of $A$. Then, we can give a sufficient and necessary
condition for the linear transformation transforming a non-secure code into a
secure one.

###### Theorem IV.1

Given the network $\mathcal{N}$, sum function $f$, and security level $r$, if
there exists a non-secure network code $\\{\widehat{g}_{e}:e\in E\\}$ with
rate $R=n$, then it can be transformed into a secure network code with rate
$n-r$ by a linear transformation $A$ if and only if $A$ satisfies

$span(A_{T}^{-1})\cap span(F(W))=\mathbf{0},$ (13)

where $T=\bigcup_{i=0}^{s-1}\\{i+1,i+2,\cdots,i+n-r\\}$.

###### Proof:

Denote all source messages and random keys as a row vector of length $sn$ by
$\mathbf{X}=(\mathbf{M}_{1},\mathbf{K}_{1},\cdots,\mathbf{M}_{s},\mathbf{K}_{s})$.
By the definition of global encoding functions, before transformation, edge
$e\in E$ sends a message $U_{e}=\mathbf{X}\cdot g_{e}$. After transformation,
the message sent by edge $e$ is $U_{e}=\mathbf{X}\cdot A\cdot g_{e}$. Let
$W\subset E$ be a wiretap edge subset, $G(W)=\\{g_{e}:e\in W\\}$, the
wiretapper can get

$\mathbf{Y}_{W}=\mathbf{X}\cdot A\cdot G(W).$

Here, the security condition

$\mathbf{I}(\mathbf{M}_{1},\mathbf{M}_{2},\cdots,\mathbf{M}_{s};\mathbf{Y}_{W})=0$

is equivalent to that there doesn’t exist any vector
$\mathbf{a}\in\mathbb{F}_{q}^{s(n-r)},\mathbf{b}\in\mathbb{F}_{q}^{|W|}$ such
that

$(\mathbf{M}_{1},\mathbf{M}_{2},\cdots,\mathbf{M}_{s})\cdot\mathbf{a}=\mathbf{Y}_{W}\cdot\mathbf{b},$
(14)

since

$(\mathbf{M}_{1},\mathbf{M}_{2},\cdots,\mathbf{M}_{s})=\mathbf{X}\cdot\begin{pmatrix}J_{n,n-r}&0&\cdots&0\\\
0&J_{n,n-r}&\cdots&0\\\ \vdots&\vdots&\ddots&\vdots\\\
0&0&\cdots&J_{n,n-r}\end{pmatrix},$

where $J_{n,n-r}$ is the first $n-r$ columns of an identity matrix of order
$n$. From above, Eq. (14) is equivalent to

$\mathbf{X}\cdot\begin{pmatrix}J_{n,n-r}&0&\cdots&0\\\ 0&J_{n,n-r}&\cdots&0\\\
\vdots&\vdots&\ddots&\vdots\\\
0&0&\cdots&J_{n,n-r}\end{pmatrix}\cdot\mathbf{a}=\mathbf{X}\cdot A\cdot
G(W)\cdot\mathbf{b},$ (15)

then we have

$A^{-1}\cdot\begin{pmatrix}J_{n,n-r}&0&\cdots&0\\\ 0&J_{n,n-r}&\cdots&0\\\
\vdots&\vdots&\ddots&\vdots\\\
0&0&\cdots&J_{n,n-r}\end{pmatrix}\cdot\mathbf{a}=G(W)\cdot\mathbf{b},$ (16)

the lefthand side of Eq. (16) can be represented by $A_{T}^{-1}$, where
$T=\bigcup_{i=0}^{s-1}\\{i+1,i+2,\cdots,i+n-r\\}$. This is equivalent to
$span(A_{T}^{-1})\cap span(F(W))=\mathbf{0}$. ∎

For sum-network, the capacity of network $\mathcal{N}$ is equal to $C_{min}$
[3, 14]. Thus from Theorem IV.1, for secure network sum function computing
problem, we have $\widehat{C}(\mathcal{N},f,r)\geq C_{min}-r$.

We call a graph $\mathcal{N}=(V,E)$ as multi-edge tree if for any node $v\in
V$, there exists a node $u$ such that all the out edges of $v$ are in edges of
$u$, which means $Out(v)\subset In(u)$. We obtain the following corollary.

###### Corollary IV.2

For multi-edge tree graphs, the upper bound in Theorem III.2 is tight.

###### Proof:

In multi-edge tree graphs, for any cut $C$, $J_{C}=\emptyset$. Thus,
$A_{min}=C_{min}$, and by Theorem III.2, the capacity is $C_{min}-r$. And in
Theorem IV.1, there exists a secure network code with rate $C_{min}-r$. ∎

For general network which satisfies $A_{min}>C_{min}$, whether the upper bound
(8) is tight or not is not known yet. But we can provide some necessary
conditions for linear secure global encoding functions. Let
$\widehat{g}_{e}(\mathbf{M}_{1},\mathbf{K}_{1},\cdots,\mathbf{M}_{s},\mathbf{K}_{s})=(\mathbf{M}_{1},\mathbf{K}_{1},\cdots,\mathbf{M}_{s},\mathbf{K}_{s})\cdot
g_{e}$, where $g_{e}$ is a column vector with length $sn$. For any source node
$\sigma_{i}$, let $\widehat{g}_{e}|_{\\{\sigma_{i}\\}}$ be the global encoding
function restricted on $\mathbf{M}_{i},\mathbf{K}_{i}$, i.e.

$\widehat{g}_{e}|_{{\sigma_{i}}}(\mathbf{M}_{i},\mathbf{K}_{i})=(\mathbf{M}_{i},\mathbf{K}_{i})\cdot
g_{e}|_{\\{\sigma_{i}\\}}.$

###### Theorem IV.3

If there exists an $(n-r,1)$ linear secure network code
$\\{\widehat{g}_{e}:e\in E\\}$ for sum-network problem $(\mathcal{N},f,r)$,
then for any cut $C$, the messages $\\{\widehat{g}_{e}|_{I_{C}}:e\in C\\}$
contain all information about $\sum_{\sigma_{i}\in I_{C}}\mathbf{M}_{i}$.

###### Proof:

Suppose we cannot decode $\sum_{\sigma_{i}\in I_{C}}\mathbf{M}_{i}$ from the
truncated messages $\\{\widehat{g}_{e}:e\in C\\}$. Then there must be some
random keys from source nodes $\sigma_{i}\in I_{C}$ we cannot eliminate. Let
$G=C\cup(\cup_{\sigma_{i}\notin I_{C}}Out(\sigma_{i}))$ be a global cut, we
can decode the sum from the messages transmitted on these edges. However,
$\cup_{\sigma_{i}\notin I_{C}}Out(\sigma_{i})$ don’t contain any message about
$\mathbf{K}_{i}$, for $\sigma_{i}\in I_{C}$, which means the random keys in
$\\{\widehat{g}_{e}:e\in C\\}$ cannot be eliminated. Then it’s impossible to
obtain the sum from the global cut. ∎

For the case $A_{min}\geq C_{min}$, if the wiretapper has access to a cut $C$
of the network with size less than $A_{min}$, he cannot get any information
about any source message from the secure condition. However, from above
theorem, the sum $\sum_{\sigma_{i}\in I_{C}}\mathbf{M}_{i}$ can be obtained
from truncated messages $\\{\widehat{g}_{e}|_{I_{C}}\>e\in C\\}$, which
indicates that the messages in the min-cut from $J_{C}$ to $C$ are served as
random keys to protect the sum from the wiretapper.

##  V Upper Bound under User Secure

In this section, we consider the network function computation problem under
the user secure condition (2). Li et al. referred this kind of security as
secrete sum when the target function is arithmetic sum over finite field [11].
In their model, each edge of the network has unlimited transmission capacity,
which means each edge can transmit a message over $\mathbb{F}_{q}$ with
unlimited length once a time. Therefore, it is meaningless to bound the
capacity under their model. In [11], the sufficient and necessary condition
for a user secure network function computation problem is that after deleting
all wiretap edges, there exists at least one source having a path to the sink
node $\rho$.

Now, we assume the transmission capacity of each edge is unit, i.e. each edge
transmits one symbol over $\mathbb{F}_{q}$ at one time. What is the relation
between network topology and computation capacity under a given security level
$r$? Here, we will use $\widehat{C}_{us}(\mathcal{N},f,r)$ to denote the
capacity of the network $\mathcal{N}$ computing $f$ with security level $r$.
We first address a sufficient and necessary condition for the existence of
user secure codes and then provide an upper bound on the capacity based on
network topology. We begin with the following illustrative examples.

Figure 2: The network has 2 sources and the target function is
$f=(x_{1}+y_{1},x_{2}+y_{2})$.

###### Example V.1

Consider the user secure network function computation problem shown in $Fig.\
\ref{F2}$. When the security level $r=1$, i.e. the wiretapper has access to
exactly one edge of the network, there exists a (2,1) network code over
$\mathbb{F}_{2}$ defined as follows:
$U_{e_{1}}=x_{1}+x_{2},U_{e_{2}}=x_{2},U_{e_{3}}=y_{1},U_{e_{4}}=y_{1}+y_{2},$
and $U_{e_{5}}=x_{2}+y_{1}$. The sink node $\rho$ can decode $x_{1}+y_{1}$ and
$x_{2}+y_{2}$ from $U_{e_{1}},U_{e_{4}},U_{e_{5}}$, and any one of
$U_{e_{1}},\cdots,U_{e_{5}}$ cannot leakage any information about
$(x_{1}+y_{1},x_{2}+y_{2})$. This example shows that
$\widehat{C}_{us}(\mathcal{N},f,r)\geq 2$. On the other hand, for sum function
computation task over network, the capacity cannot be greater than $C_{min}$.
Otherwise, we will have a code with rate larger than $C_{min}$ which
contradicts with the result in [3]. Thus, in this example,
$\widehat{C}_{us}(\mathcal{N},f,r)=2$ is tight.

The fundamental reason why random keys are not needed is that the user secure
condition (2) means the leakage messages $\mathbf{Y}_{W}$ should not be a
function of target result $\mathbf{X}_{1}+\cdots+\mathbf{X}_{s}$. In above
example, even the wiretapper knows $x_{2}$, he cannot get any information
about $x_{2}+y_{2}$ since $y_{2}$ is uniformly distributed on
$\mathbb{F}_{q}$. Therefore, we focus on the capacity without random keys. In
fact, if we allow random keys, we may have larger capacity since if a code is
secure then it is also user secure.

###### Example V.2

In Example V.1, we claim that when the security level $r=2$, there doesn’t
exist any user secure network code such that $\rho$ can compute
$\mathbf{X}+\mathbf{Y}$ without error. Suppose there exists an $(l,n)$ user
secure code, i.e. source messages
$\mathbf{X},\mathbf{Y}\in\mathbb{F}_{q}^{l}$, edge $e$ transmits a message
$U_{e}\in\mathbb{F}_{q}^{n}$, and from solvability and user security, we have

$\displaystyle\mathbf{H}(\mathbf{X}+\mathbf{Y}|U_{e_{1}},U_{e_{4}},U_{e_{5}})$
$\displaystyle=0,$
$\displaystyle\mathbf{I}(\mathbf{X}+\mathbf{Y};U_{e_{1}},U_{e_{4}})$
$\displaystyle=0,$
$\displaystyle\mathbf{I}(\mathbf{X}+\mathbf{Y};U_{e_{1}},U_{e_{5}})$
$\displaystyle=0,$

where $U_{e_{1}}$ is a function of $\mathbf{X}$, and $U_{e_{4}}$ is a function
of $\mathbf{Y}$. Then we will have

$\displaystyle\mathbf{I}(U_{e_{1}},U_{e_{5}};\mathbf{X}+\mathbf{Y})$
$\displaystyle\geq\mathbf{I}(U_{e_{1}},U_{e_{5}};\mathbf{X}+\mathbf{Y}|\mathbf{Y})$
$\displaystyle=\mathbf{H}(\mathbf{X}+\mathbf{Y}|\mathbf{Y})-\mathbf{H}(\mathbf{X}+\mathbf{Y}|U_{e_{1}},U_{e_{5}},\mathbf{Y})$
$\displaystyle=\mathbf{H}(\mathbf{X})-\mathbf{H}(\mathbf{X}+\mathbf{Y}|U_{e_{1}},U_{e_{5}},U_{e_{4}},\mathbf{Y})$
$\displaystyle=\mathbf{H}(\mathbf{X})-0>0,$

which contradicts the user security. The first equation is from the definition
of mutual information, and the second equation holds since $\mathbf{X}$ and
$\mathbf{Y}$ are independent and uniformly distributed over
$\mathbb{F}_{q}^{l}$ and $U_{e_{4}}$ is a function of $\mathbf{Y}$. From
another view, consider
$\mathbf{I}(\mathbf{X}+\mathbf{Y};U_{e_{1}},U_{e_{4}})$, we can prove

$\displaystyle\mathbf{I}(\mathbf{X}+\mathbf{Y};U_{e_{1}},U_{e_{4}})$
$\displaystyle\geq\mathbf{I}(\mathbf{X}+\mathbf{Y};U_{e_{1}},U_{e_{4}}|\mathbf{Y})$
$\displaystyle=\mathbf{H}(U_{e_{1}},U_{e_{4}}|\mathbf{Y})+\mathbf{H}(\mathbf{X}+\mathbf{Y}|\mathbf{Y})-\mathbf{H}(\mathbf{X}+\mathbf{Y},U_{e_{1}},U_{e_{4}}|\mathbf{Y})$
$\displaystyle=\mathbf{H}(U_{e_{1}})+\mathbf{H}(\mathbf{X})-\mathbf{H}(\mathbf{X}+\mathbf{Y},U_{e_{1}}|\mathbf{Y})$
$\displaystyle=\mathbf{H}(U_{e_{1}})+\mathbf{H}(\mathbf{X})-\mathbf{H}(\mathbf{X},U_{e_{1}})$
$\displaystyle=\mathbf{I}(\mathbf{X};U_{e_{1}})=\mathbf{H}(U_{e_{1}})>0,$

which also contradicts with user security. The second equation holds since
$U_{e_{4}}$ is determined by $\mathbf{Y}$.

From the above examples, we can conclude a sufficient and necessary condition
for the existence of user secure network codes.

###### Theorem V.3

Let $\mathcal{N}$ be a network and $f$ be a sum function over
$\mathbb{F}_{q}$. Suppose the security level is $r$, then there exists a user
secure network code if and only if $r<\min\\{C_{min},s\\}$, where $s$ is the
number of source nodes.

###### Proof:

We first prove the only if part. Denote the source messages as
$\mathbf{X}_{1},\cdots,\mathbf{X}_{s}$, the sink node $\rho$ wants
$\mathbf{X}_{1}+\cdots+\mathbf{X}_{s}$, while the wiretapper has access to any
$r$ edges and cannot get any information about the sum. We prove this part in
two steps.

First, suppose $r\geq C_{min}$ and let $C$ be a cut with $|C|=C_{min}$.
Without loss of generality, assume $I_{C}=\\{\sigma_{1}\\}$, let
$C^{\prime}=\cup_{i=2}^{s}Out(\sigma_{i})$. Note that $G=C\cup C^{\prime}$ is
a global cut of the network, thus the sum can be decoded from messages
transmitted by $G$, i.e.

$\mathbf{H}(\mathbf{X}_{1}+\cdots+\mathbf{X}_{s}|\\{U_{e},e\in G\\})=0.$

If there exists a user secure code with security level $r\geq C_{min}$, then
the sum is protected from the wiretapper who has all messages in cut $C$,
which indicates

$I(\mathbf{X}_{1}+\cdots+\mathbf{X}_{s};\\{U_{e},e\in C\\})=0.$

Similar with the process in Example V.2,

$\displaystyle\mathbf{I}(\\{U_{e},e\in
C\\};\mathbf{X}_{1}+\cdots+\mathbf{X}_{s})$
$\displaystyle\geq\mathbf{I}(\\{U_{e},e\in
C\\};\mathbf{X}_{1}+\cdots+\mathbf{X}_{s}|\\{\mathbf{X}_{2},\cdots,\mathbf{X}_{s}\\})$
$\displaystyle=\mathbf{H}(\mathbf{X}_{1}+\cdots+\mathbf{X}_{s}|\\{\mathbf{X}_{2},\cdots,\mathbf{X}_{s}\\})-\mathbf{H}(\mathbf{X}_{1}+\cdots+\mathbf{X}_{s}|\\{U_{e},e\in
C\\},\\{\mathbf{X}_{2},\cdots,\mathbf{X}_{s}\\})$
$\displaystyle=\mathbf{H}(\mathbf{X}_{1})-\mathbf{H}(\mathbf{X}_{1}+\cdots+\mathbf{X}_{s}|\\{U_{e},e\in
C\\},\\{U_{e},e\in C^{\prime}\\},\\{\mathbf{X}_{2},\cdots,\mathbf{X}_{s}\\})$
$\displaystyle=\mathbf{H}(\mathbf{X}_{1})-0>0,$

which contradicts with the secure condition above. The third equation holds
since $\\{U_{e},e\in C^{\prime}\\}$ is determined by
$\\{\mathbf{X}_{2},\cdots,\mathbf{X}_{s}\\}$. And the last equation follows
from that any global cut must carry all messages about
$\mathbf{X}_{1}+\cdots+\mathbf{X}_{s}$.

Similarly, suppose there is a user secure code with security level $r\geq s$,
then for the edge set $E^{\prime}=\\{e_{i}:i\in[s],e_{i}\in
Out(\sigma_{i})\\}$ with size $s$, the follow equation must be satisfied,

$\mathbf{I}(\mathbf{X}_{1}+\cdots+\mathbf{X}_{s};\\{U_{e_{i}},e_{i}\in
E^{\prime}\\})=0.$

Consider the conditional mutual information,

$\displaystyle\mathbf{I}(\\{U_{e_{i}},e_{i}\in
E^{\prime}\\};\sum\limits_{i=1}^{s}\mathbf{X}_{i})$
$\displaystyle\geq\mathbf{I}(\\{U_{e_{i}},e_{i}\in
E^{\prime}\\};\sum\limits_{i=1}^{s}\mathbf{X}_{i}|\\{\mathbf{X}_{2},\cdots,\mathbf{X}_{s}\\})$
$\displaystyle=\mathbf{H}(\sum\limits_{i=1}^{s}\mathbf{X}_{i}|\\{\mathbf{X}_{2},\cdots,\mathbf{X}_{s}\\})+\mathbf{H}(\\{U_{e_{i}},e_{i}\in
E^{\prime}\\}|\\{\mathbf{X}_{2},\cdots,\mathbf{X}_{s}\\})$ $\displaystyle\ \ \
-\mathbf{H}(\sum\limits_{i=1}^{s}\mathbf{X}_{i},\\{U_{e_{i}},e_{i}\in
E^{\prime}\\}|\\{\mathbf{X}_{2},\cdots,\mathbf{X}_{s}\\})$
$\displaystyle=\mathbf{H}(\mathbf{X}_{1})+\mathbf{H}(U_{e_{1}})-\mathbf{H}(\mathbf{X}_{1},U_{e_{1}})$
$\displaystyle=\mathbf{I}(\mathbf{X};U_{e_{1}})=\mathbf{H}(U_{e_{1}})>0,$

which is also a contradiction. Therefore, when $r\geq s$ or $r\geq C_{min}$,
there doesn’t exist any user secure code.

For the if part, we claim that if $r<\min\\{C_{min},s\\}$, then there exists a
user secure code with rate 1. The construction is as follows. For each source
node $\sigma_{i}$, we select one path from $\sigma_{i}$ to $\rho$. Each source
node sends its message $x_{i}$ directly and other nodes send the sum of
messages they get. This network code has rate 1 and is user secure since
$r<C_{min}$ and $r<s$, there exists at least one source and corresponding
message cannot be observed by the wiretapper. ∎

From Theorem V.3, we know that there always exists a user secure network code
when $r<\min\\{C_{min},s\\}$. The following example shows $C_{min}$ is not
always achievable, which means the study of user secure capacity is not
trivial.

Figure 3: The network has 2 sources and the target function is $f=x+y$

###### Example V.4

Consider the reverse butterfly network shown in $Fig.\ref{F3}$. We claim that
there doesn’t exist a rate 2 network code for security level $r=1$. Suppose
there exists a user secure network code with rate 2. Consider the global cut
$\\{e_{8},e_{9}\\}$, and let the wiretap edge $W=\\{e_{8}\\}$. By user secure
condition (2),

$\mathbf{H}(\mathbf{M}_{1}+\mathbf{M}_{2}|\mathbf{Y}_{e_{8}})=\mathbf{H}(\mathbf{M}_{1}+\mathbf{M}_{2}).$

By the solvability of the code, we have

$\mathbf{H}(\mathbf{M}_{1}+\mathbf{M}_{2}|\mathbf{Y}_{e_{8}},\mathbf{Y}_{e_{9}})=0.$

Combining the above equations,

$\mathbf{I}(\mathbf{M}_{1}+\mathbf{M}_{2};\mathbf{Y}_{e_{9}}|\mathbf{Y}_{e_{8}})=\mathbf{H}(\mathbf{M}_{1}+\mathbf{M}_{2}|\mathbf{Y}_{e_{8}})-\mathbf{H}(\mathbf{M}_{1}+\mathbf{M}_{2}|\mathbf{Y}_{e_{8}},\mathbf{Y}_{e_{9}})=\mathbf{H}(\mathbf{M}_{1}+\mathbf{M}_{2})>0,$

which means $\mathbf{I}(\mathbf{M}_{1}+\mathbf{M}_{2};\mathbf{Y}_{e_{9}})>0$.
This means if wiretap edge $W=\\{e_{9}\\}$, the wiretapper will get some
information about $\mathbf{M}_{1}+\mathbf{M}_{2}$, which is a contradiction.

Let $G$ be a global cut of the network, and $G_{min}$ be the smallest size of
a global cut. From Example V.4 we can conclude the following theorem.

###### Theorem V.5

Let $\mathcal{N}$ be a network and $f$ be an algebraic sum over a finite field
$\mathbb{F}_{q}$. If the security level $r<\min\\{C_{min},s\\}$, then

$\widehat{C}_{us}(\mathcal{N},f,r)\leq\min\\{C_{min},G_{min}-r\\},$ (17)

and $\widehat{C}_{us}(\mathcal{N},f,r)=0$ otherwise.

###### Proof:

We only prove $\widehat{C}_{us}(\mathcal{N},f,r)\leq G_{min}-r$, since
$\widehat{C}_{us}(\mathcal{N},f,r)\leq C_{min}$ can be obtained from [3]. In
fact, there doesn’t exist a network code which can compute arithmetic sum on a
network with rate larger than $C_{min}$ [3]. Similar to Example V.4, assume
$G$ is a global cut with size $G_{min}$, and $W\subset G$ is a wiretap set.
Suppose there exists an $(l,n)$ user secure code. Since source messages are
uniformly and independently distributed,

$\mathbf{H}(\mathbf{M}_{1}+\mathbf{M}_{2}+\cdots+\mathbf{M}_{s})=l\cdot\log
q.$

By user secure condition (2),

$\mathbf{H}(\mathbf{M}_{1}+\cdots+\mathbf{M}_{s}|\mathbf{Y}_{W})=\mathbf{H}(\mathbf{M}_{1}+\cdots+\mathbf{M}_{s}).$

By the solvability of the code, we have

$\mathbf{H}(\mathbf{M}_{1}\cdots+\mathbf{M}_{s}|\mathbf{Y}_{G})=0.$

Combining the above equations,

$\displaystyle(|G|-r)\cdot n\cdot\log q$
$\displaystyle\geq\mathbf{H}(\mathbf{Y}_{G\setminus W})$
$\displaystyle\geq\mathbf{I}(\mathbf{M}_{1}+\mathbf{M}_{2};\mathbf{Y}_{G\setminus
W}|\mathbf{Y}_{W})$
$\displaystyle=\mathbf{H}(\mathbf{M}_{1}+\mathbf{M}_{2}|\mathbf{Y}_{W})-\mathbf{H}(\mathbf{M}_{1}+\mathbf{M}_{2}|\mathbf{Y}_{G})$
$\displaystyle=\mathbf{H}(\mathbf{M}_{1}+\mathbf{M}_{2})=l\cdot\log q,$

which shows $l/n\leq G_{min}-r$. ∎

##  VI Conclusions

In this paper, we first present a new upper bound of the network computation
capacity under the secure condition. The new upper bound is strictly tighter
than the previous one. When the network is a multi-edge tree, we can prove
that the new upper bound is tight. Meanwhile, we give a necessary condition
for the existence of linear secure network codes for computing a sum function
over network, which provides some insight of the construction of achievable
network codes.

On the other hand, we consider the capacity problem under another new secure
condition defined as user secure in this paper. We first give a sufficient and
necessary condition for the existence of user secure network codes.
Furthermore, an upper bound of the user secure computation capacity is
addressed. However, whether the bound is tight or not remains unknown yet.

## References

  * [1] A. Giridhar and P. Kumar, “Computing and communicating functions over sensor networks”, _IEEE Journal on Selected Areas in Communications_ , vol. 23, no. 4, pp. 755-764, 2005
  * [2] A. Destounis, G. S. Paschos, and I. Koutsopoulos, “Streaming big data meets backpressure in distributed network computation”, _in Proceeding of the 37th Annual IEEE Symposium on Foundations of Computer Science_ , pp. 1-9, 2016.
  * [3] B. Rai and B. K. Dey, “On network coding for sum-networks”, _IEEE Transactions on Information Theory_ , vol. 58, no. 1, pp 50-63, 2012.
  * [4] R. Appuswamy and M. Franceschetti, “Computing linear functions by linear coding over networks”, _IEEE transactions on Information Theory_ , vol. 60, no. 1, pp. 422-431, 2013.
  * [5] R. Appuswamy, M. Franceschetti, and N. Karamchandani, “Network coding for computing: Cut-set bounds”, _IEEE Transactions on Information Theory_ , vol. 57, no. 2, pp. 1015-1030, 2011.
  * [6] C. Huang, Z. Tan, S. Yang, and X. Guang, “Comments on cut-set bounds on network function computation”, _IEEE Transactions on Information Theory_ , vol. 64, no. 9, pp. 6454-6459, 2018.
  * [7] X. Guang, R. W. Yeung, S. Yang, and C. Li, “Improved upper bound on the network function computing capacity”, _IEEE Transactions on Information Theory_ , vol. 65, no. 6, pp. 3790-3811, 2019.
  * [8] N. Cai and T. Chan, “Theory of secure network coding”, _Proceedings of the IEEE_ , vol. 99, no. 3, pp. 421-437, 2011.
  * [9] K. Bhattad and K. R. Narayanan, “Weakly secure network coding”, _NetCod_ , 104, 2005.
  * [10] K. Harada and H. Yamamoto, “Strongly secure linear network coding”, _IEICE transactions on Fundamentals of Electronics, Communications and Computer Sciences_ , vol. 91, no. 10, pp. 2720-2728, 2008.
  * [11] S. Li and C. T. Li, “Arithmetic network coding for secret sum computation”, _arXiv preprint_ , arXiv:2201.03032, 2022.
  * [12] N. Cai and R. W. Yeung, “Secure network coding”, _IEEE International Symposium on Information Theory (ISIT), IEEE_ , pp. 323, 2002
  * [13] X. Guang, Y. Bai, and R. W. Yeung, “Secure network function computation”, _IEEE International Symposium on Information Theory (ISIT), IEEE_ , pp. 66-71, 2021.
  * [14] R. Koetter, M. Effros, and T. Ho, “Network codes as codes on graphs”, _Proceeding of CISS_ , 2004.


$\displaystyle\text{ on }\Gamma_{h}\cup((\partial B_{r_{0}})\cap K),$ (149)
$\displaystyle D_{\mathbb{n}}w\leq 0\ \ $ $\displaystyle\text{ on
}\Gamma_{v}.$ (150)

There exists $\epsilon_{A1}$ depends on $C_{E},\ \alpha,\ \lambda,$ if
$r_{0}<\epsilon_{A1}(C_{E},\alpha,\lambda)$ , then in $\Omega$, $w\leq 0.$

###### Proof.

Like in section 9.1 of [10], we define upper contact set $\Gamma^{+}$ and
normal map $\chi$, with more restriction:

$\displaystyle\Gamma^{+}=$ $\displaystyle\\{(x,y)\in B_{1}(0,H)|\exists
L:\text{linear function, graph of $L$ upper contacts with}$
$\displaystyle\text{graph of $w^{+}$ at $(x,y)$},\nabla
L\cdot(\cos\sigma,\sin\sigma)\leq 0\\}$ $\displaystyle\chi(x,y)=$
$\displaystyle\\{\nabla L\mid\text{graph of $L$ upper contacts with graph of
$w^{+}$ at $(x,y)$},\nabla L\cdot(\cos\sigma,\sin\sigma)<0\\}$

It means $\Gamma^{+}\cap\Gamma_{v}=\O$. We have:

$\displaystyle\sup w^{+}\leq
2r_{0}k\left(\exp^{\frac{4\int_{\Omega}|\vec{b}|^{2}+\frac{c^{2}(w^{+})^{2}}{k^{2}}}{\lambda^{2}\pi}}-1\right)^{1\over
2},$ (151)

in above we denote:

$k=(2\int_{\Omega}c^{2}(w^{+})^{2})^{1\over 2}.$

Then if

$2r_{0}\left(\exp^{\frac{(4\int_{\Omega}|\vec{b}|^{2})+2}{\lambda^{2}\pi}}-1\right)^{1\over
2}(2\int_{\Omega}c^{2})^{1\over 2}<{1\over 2},$

we have $w\leq 0$.

So we can choose:

$\epsilon_{A1}=\min\left\\{\frac{\sqrt{\alpha}}{8C_{E}\sqrt{\pi}}\left(\exp^{\frac{4}{\pi\lambda^{2}}\left(1+\frac{\pi}{\alpha}C_{E}^{2}\right)}-1\right)^{-\frac{1}{2}},{1\over
e^{4}}\right\\}.$

∎

###  A.2 Gradient Estimates near the Corner

######  Lemma A.2.

There exists $\epsilon_{A2}$ depends on $C_{E},\Lambda,\lambda,\alpha$. Given
$r_{0}<\min\\{\epsilon_{A1},\epsilon_{A2}\\}$, and $h$ satisfies:

$\displaystyle h\in C^{0}(\overline{\Omega})\cap
C^{1}(\Omega\cup\Gamma_{v}\setminus(0,0))\cap C^{2}(\Omega),$ (152)
$\displaystyle a_{ij}h_{ij}+b_{1}h_{x}+b_{2}h_{y}+b_{3}h=0,\text{ in }\Omega,$
(153) $\displaystyle h=0,\text{ on }\Gamma_{h},$ (154) $\displaystyle
h_{\mathbb{n}}=0,\text{ on }\Gamma_{v}.$ (155)

Then there exists an $r_{A2}<r_{0}$, which depends on
$C_{E},\Lambda,\lambda,r_{0},\alpha$, s.t. on $\\{\eta=0\\}\cap B_{r_{A2}}$

$|h_{y}|\leq C(C_{E},\alpha,\lambda,\Lambda,r_{0})\cdot
r^{\frac{\alpha}{2}-1}|h|_{0;B_{r_{0}}}$ (156)

###### Proof.

Figure 20: Desingularization

Conformally map original wedge to a narrow wedge with top angle $\Theta$(to be
determined), in new cone, we use coordinate
$(\xi,\eta)=\rho(\cos\theta,\sin\theta)$.

######  Remark 2.

It’s convenient to consider $a,r,\theta,\rho,a_{ij},b_{k}$ as functions on
both sides, it means, for example on right-hand side $r(\xi,\eta)\triangleq
r(\Phi^{-1}(\xi,\eta))$, and on left-hand side
$\theta(x,y)\triangleq\theta(\Phi(x,y))$. So on right-hand side we can still
say $|b_{i}|\leq C_{E}r^{\alpha-1}$ and we have
$r(\xi,\eta)=\rho^{A\over\Theta}(\xi,\eta)$.

Under new coordinate, on right-hand side (we still denote $\Phi_{*}h$ by $h$)
$h$ satisfies:

$\displaystyle\tilde{a}_{ij}h_{ij}+\tilde{b}_{1}h_{\xi}+\tilde{b}_{2}h_{\eta}+\tilde{b}_{3}h=0,\text{
in }\Phi_{*}(\Omega),$ (157) $\displaystyle h_{\mathbb{n}}=0,\text{ on
}\\{\theta=\Theta\\}\cap\overline{\Phi_{*}(\Omega)},$ (158) $\displaystyle
h=0,\text{ on }\\{\eta=0\\}\cap\overline{\Phi_{*}(\Omega)}.$ (159)

To describe $\tilde{a}_{ij}$, $\tilde{b}_{k}$ we define:

$P=\left(\begin{array}[]{cc}\cos[a({\Theta\over A}-1)]&\sin[a({\Theta\over
A}-1)]\\\ -\sin[a({\Theta\over A}-1)]&\cos[a({\Theta\over
A}-1)]\end{array}\right)$

then:

$\displaystyle(\tilde{a}_{ij})=({\Theta\over A})^{2}P^{T}(a_{ij})P$ (160)
$\displaystyle\tilde{b}_{1}={\Theta\over A}({\Theta\over
A}-1)\\{\cos[a({\Theta\over A}-2)]a_{11}-2\sin[a({\Theta\over
A}-2)]a_{12}-\cos[a({\Theta\over A}-2)]a_{22}\\}r^{-\frac{\Theta}{A}}$
$\displaystyle+{\Theta\over A}r^{1-{\Theta\over A}}(b_{1}\cos[a({\Theta\over
A}-1)]-b_{2}\sin[a({\Theta\over A}-1)])$ (161)
$\displaystyle\tilde{b}_{2}={\Theta\over A}({\Theta\over
A}-1)\\{\sin[a({\Theta\over A}-2)]a_{11}+2\cos[a({\Theta\over
A}-2)]a_{12}-\sin[a({\Theta\over A}-2)]a_{22}\\}r^{-\frac{\Theta}{A}}$
$\displaystyle+{\Theta\over A}r^{1-{\Theta\over A}}(b_{1}\sin[a({\Theta\over
A}-1)]+b_{2}\cos[a({\Theta\over A}-1)])$ (162)
$\displaystyle\tilde{b}_{3}=b_{3}\cdot r^{2-{2\Theta\over A}}.$ (163)

So if we choose $\Theta={\alpha\over 2}A$, then $\tilde{b}_{k}$ are bounded,
specifically:

$\displaystyle{\lambda\alpha^{2}\over
4}\leq(\tilde{a}_{ij})\leq{\Lambda\alpha^{2}\over 4},$ (164)
$\displaystyle|\tilde{b}_{i}|\leq C(C_{E},\alpha).$ (165)

For any $0<t<{\rho_{0}\over 2}$, construct:

$w^{t}=M[1-e^{-\gamma{[(\xi-t)^{2}+(\eta+1)^{2}-1}]}]\cdot\sup|h|$

In $\Phi(\Omega)$:

$\displaystyle\tilde{a}_{ij}w^{t}_{ij}+\tilde{b}_{1}w^{t}_{\xi}+\tilde{b}_{2}w^{t}_{\eta}+\tilde{b}_{3}w^{t}$
$\displaystyle\leq$ $\displaystyle
M\sup|h|e^{-\gamma[((\xi-t)^{2}+(\eta+1)^{2})-1]}[-4\gamma^{2}\lambda+4\Lambda\gamma+4\gamma
C(C_{E},\alpha)+12\gamma C(C_{E},\alpha)e^{9\gamma}r_{0}]$ $\displaystyle\leq$
$\displaystyle 0,$

if we choose $r_{0}\leq\frac{e^{-9\gamma}}{12\gamma
C(C_{E},\alpha)}\triangleq\epsilon_{A2},$ and $\lambda$ large enough s.t.
$-4\gamma^{2}\lambda+4\Lambda\gamma+4C(C_{E},\alpha)\gamma+1<0$.

So if $M,\ \gamma$ big enough(depending on $C_{E},\ \Lambda,\ \lambda,\
\rho_{0}$ and $\alpha$) :

$\displaystyle\tilde{a}_{ij}w^{t}_{ij}+\tilde{b}_{1}w^{t}_{x}+\tilde{b}_{2}w^{t}_{y}+\tilde{b}_{3}w^{t}\leq
0\text{ in }\Phi(\Omega),$ (166) $\displaystyle\partial_{\mathbb{n}}w^{t}\geq
0\text{, on }\\{\theta=\Theta\\}$ (167) $\displaystyle w^{t}\geq h\text{, on
}\partial B_{\rho_{0}}\cup\\{\eta=0\\}.$ (168)

And,

$|\nabla w^{t}|(t,0)\leq
C(C_{E},\lambda,\Lambda,\alpha,\rho_{0})|h|_{0;\Phi(\Omega)},\,\,\text{for
$0<t<{\rho_{0}\over 2}$}.$

Transforming above back to original domain $\Omega$, gives

$|\partial_{y}\Phi^{*}(w^{t})|(t,0)\leq t^{{\Theta\over
A}-1}C(C_{E},\lambda,\Lambda,\alpha,r_{0})|h|_{0;\Omega},\,\,\text{for
$0<t<{2^{-{A\over\Theta}}r_{0}}$}.$

Then by Lemma A.1, $h\leq\Phi^{*}(w^{t})$ for any $t$($\
0<t<{2^{-{A\over\Theta}}r_{0}}$), on
$\\{0<x<{2^{-{A\over\Theta}}r_{0}},y=0\\}$:

$h_{y}(t,0)\leq t^{{\Theta\over
A}-1}C(C_{E},\lambda,\Lambda,\alpha,r_{0})|h|_{0;\Omega}.$ (169)

Apply process above to $-h$, we get Lemma A.2 ∎

###  A.3 Singularity Estimates

######  Lemma A.3.

Suppose $r_{0}\leq\epsilon_{A1}(\lambda,C_{E},\alpha)$, and given $h\in
C^{1}(\overline{\Omega})\cap C^{2}(\Omega\cup\Gamma_{v}\setminus(0,0)),$

$\displaystyle a_{ij}h_{ij}+b_{1}h_{x}+b_{2}h_{y}+b_{3}h=0,$
$\displaystyle\text{ in }\Omega{},$ (170) $\displaystyle h=0,$
$\displaystyle\text{ on }\Gamma_{h},{}$ (171) $\displaystyle
h_{\mathbb{n}}=0,$ $\displaystyle\text{ on }\Gamma_{v},{}$ (172)
$\displaystyle h\geq y-\varepsilon,$ $\displaystyle\text{ on }\partial
B_{r_{0}}\cap K{},$ (173)

then exists $\epsilon_{A3}(r_{0},\lambda,\Lambda,C_{E},\alpha)$, if
$\varepsilon\leq\epsilon_{A3}$, $h$ cannot be in
$C^{1,\alpha}(\Omega\cup(0,0))$.

###### Proof.

In the following, we construct a subsolution, $w$, to system (170) (171) (172)
and (173), which has growth rate $\frac{r}{(-\log r)^{\gamma}}$ along some
direction near corner of wedge.

Since $h$ satisfies $h=\nabla h=0$ at corner of wedge, so if $h\in
C^{1,\alpha}(\Omega\cup(0,0))$, we have in $\Omega$,

$|\nabla h|\leq|h|_{1,\alpha}r^{\alpha},\
|h|\leq\frac{1}{\alpha}|h|_{1,\alpha}r^{\alpha+1},$

which contradicts with $h\geq w$.

We define

$w\triangleq\frac{y}{(-\log y)^{\gamma}}-\mu x^{2}.$

In $\Omega$,

$\displaystyle a_{ij}w_{ij}+b_{1}w_{x}+b_{2}w_{y}+b_{3}w$ $\displaystyle\geq$
$\displaystyle\lambda\left(\frac{y}{(-\log
y)^{\gamma}}\right)_{yy}-2\Lambda\mu-2C_{E}r^{\alpha-1}\mu|x|-C_{E}r^{\alpha-1}\left(\frac{y}{(-\log
y)^{\gamma}}\right)_{y}-C_{E}r^{\alpha-1}\left(\frac{y}{(-\log
y)^{\gamma}}+\mu x^{2}\right).$

Plug in the following

$\left(\frac{y}{(-\log y)^{\gamma}}\right)_{y}=\frac{1}{(-\log
y)^{\gamma}}+\frac{\gamma}{(-\log y)^{\gamma+1}},$ $\left(\frac{y}{(-\log
y)^{\gamma}}\right)_{yy}=\frac{\gamma}{y(-\log
y)^{\gamma+1}}+\frac{\gamma(\gamma+1)}{y(-\log y)^{\gamma+2}},$
$-r^{\alpha-1}\geq-y^{\alpha-1},\ -r^{\alpha-1}\geq-|x|^{\alpha-1},\ |x|\leq
r_{0},y\leq r_{0},$

we get

$\displaystyle a_{ij}w_{ij}+b_{1}w_{x}+b_{2}w_{y}+b_{3}w$ $\displaystyle\geq$
$\displaystyle\frac{\lambda\gamma}{y(-\log
y)^{\gamma+1}}-2\Lambda\mu-2C_{E}r^{\alpha}_{0}\mu-C_{E}\mu r_{0}^{\alpha+1}$
$\displaystyle+\frac{1}{y(-\log
y)^{\gamma+2}}\left(\lambda\gamma(\gamma+1)-C_{E}y^{\alpha}(-\log
y)^{2}-C_{E}\gamma y^{\alpha}(-\log y)-C_{E}y^{\alpha+1}(-\log y)^{2}\right).$

Define

$C_{1}={1\over\lambda}\sup\\{{2C_{E}y^{\alpha}(-\log y)}\mid 0<y<r_{0}\\},$
$C_{2}={1\over\lambda}\sup\\{C_{E}(y^{\alpha}(-\log y)^{2}+y^{\alpha+1}(-\log
y)^{2})\mid 0<y<r_{0}\\}.$

And let

$\gamma=\max\\{C_{1},C_{2}\\}+1,$
$\mu=\frac{1}{2\Lambda+3C_{E}+1}\inf\\{\frac{\lambda\gamma}{y(-\log
y)^{\gamma+1}}\mid 0<y<r_{0}\\}.$

Then

$a_{ij}w_{ij}+b_{1}w_{x}+b_{2}w_{y}+b_{3}w\geq 0.$

Recall that $r_{0}\leq e^{1\over 4}$, and note that $\gamma>1$, so

$\frac{1}{(-\log r_{0})^{\gamma}}\leq{1\over 4}.$

On $\\{\xi\geq\frac{r_{0}}{2}\\},$

$w\leq y-\mu\xi^{2}\leq y-\frac{r_{0}^{2}}{4}\mu,$

if $\varepsilon\leq\frac{r_{0}^{2}}{4}\mu$, then $w\leq y-\varepsilon$.

On $\\{\xi\leq\frac{r_{0}}{2}\\},$

$w\leq{y\over 2}-\mu\xi^{2}\leq{y\over 2}=y-{y\over 2}\leq y-\frac{r_{0}}{4},$

if $\varepsilon\leq\frac{r_{0}}{4}$, then $w\leq y-\varepsilon$.

And since $\frac{y}{(-\log y)^{\gamma}}$ is an increasing function of $y$ and
note that $\mathbb{n}$ is outer normal direction of $\Omega$, we have

$w_{\mathbb{n}}\leq 0\text{, on }\Gamma_{v}.$

So, we define $\epsilon_{3}=\min\\{\frac{r_{0}^{2}\mu}{4},\frac{r_{0}}{2}\\}$.
When $\varepsilon\leq\epsilon_{3}$, $w<h$, which gives a contradiction.

∎

##  Appendix B Boundary Krylov-Safonov Estimates

In this section we prove the following generalization of Krylov-Safonov
estimates:

######  Lemma B.1.

Consider part of a ball $\Omega=B_{2}((0,0))\cap\\{y>f(x)\\}$, where $f$ is a
Lipschitz function of $x$, and $|f|_{Lip}\leq\epsilon$ (we denote
$\overline{\Omega}\cap\\{f(x)=y\\}$ as $L$).Given $h\in C^{1}(\Omega\cup
L)\cap C^{2}(\Omega)$, satisfying

  * •

$a_{ij}h_{ij}+b_{1}h_{x}+b_{2}h_{y}+b_{3}h=0\text{, in }\Omega,\text{where,
}\lambda\leq(a_{ij})\leq\Lambda,|b_{i}|\leq C_{E};$

  * •

$\int_{\Omega}{h^{+}}^{2}\leq\delta^{2};$

  * •

and $\exists\,C_{\beta}\geq 1$, at every point of $L$, one of the following
two things happens:
1)$h\leq\delta$;
2)$\exists{\boldsymbol{\beta}}=(\beta_{1},\beta_{2})$, $|\beta_{1}|\leq
C_{\beta}$, $\beta_{2}\geq{1\over C_{\beta}}$, $-D_{\beta}h+h\leq\delta$.

Then we have, there exist $\epsilon_{K}(C_{\beta})$ and $r_{K}(C_{\beta})$, if
$\epsilon\leq\epsilon_{K}$ :

$h\leq C(\lambda,\Lambda,C_{E},C_{\beta})\delta\text{ in }B_{r_{K}}.$

Figure 21: Local Maximum Principle

###### Proof.

Consider $g=1-x^{2}-(y-H)^{2}$, $w=(h-\delta)^{+}g^{\gamma}$, $H,\gamma$ to be
determined later. Then, on $L$,

$\displaystyle D_{\boldsymbol{\beta}}g$
$\displaystyle=D_{\boldsymbol{\beta}}(-x^{2}-(y-H)^{2})$
$\displaystyle=-2x\beta_{1}+2(H-y)\beta_{2}$
$\displaystyle\geq-2|x|C_{\beta}+2(H-y){1\over C_{\beta}}$
$\displaystyle\geq{1\over 2C_{\beta}}-2|x|C_{\beta}\ \ \ \ (\text{here we need
}H>{1\over 2},\epsilon<{1\over 4})$ $\displaystyle\geq 0\ (\text{ choose
}H=1-{1\over 64C^{4}_{\beta}},\,\epsilon_{K}={1\over 64C_{\beta}^{4}})$

So on $\\{h>\delta\\}\cap L$,

$\displaystyle w-D_{\boldsymbol{\beta}}w$
$\displaystyle=(h-\delta)g^{\gamma}-D_{\boldsymbol{\beta}}hg^{\gamma}-\gamma
g^{\gamma-1}D_{\boldsymbol{\beta}}g(h-\delta)$
$\displaystyle=(h-D_{\boldsymbol{\beta}}h-\delta)g^{\gamma}-\gamma
g^{\gamma-1}D_{\boldsymbol{\beta}}g(h-\delta)$ $\displaystyle=-\gamma
g^{\gamma-1}D_{\boldsymbol{\beta}}g(h-\delta)$ $\displaystyle\leq 0$

Like section 9.1 of [10] we define upper contact set $\Gamma^{+}$ and normal
map $\chi$, with more restriction:

$\displaystyle\Gamma^{+}=$ $\displaystyle\\{(x,y)\in B_{1}(0,H)|\exists
L:\text{linear function, graph of $L$ upper contacts with graph of $w^{+}$ at
$(x,y)$},$ $\displaystyle\nabla L\cdot(C_{\beta},{1\over C_{\beta}})\leq
0,\nabla L\cdot(-C_{\beta},{1\over C_{\beta}})\leq 0\\},$
$\displaystyle\chi(x,y)=$ $\displaystyle\\{\nabla L\mid\text{graph of $L$
upper contacts with graph of $w^{+}$ at $(x,y)$},$ $\displaystyle\nabla
L\cdot(C_{\beta},{1\over C_{\beta}})\leq 0,\nabla L\cdot(-C_{\beta},{1\over
C_{\beta}})\leq 0\\}.$

So at $p\in\Gamma^{+}\cap L$ if $w(p)>0$ by computation above,
$D_{\boldsymbol{\beta}}w>0$, $p\notin\Gamma^{+}$. It means if $w$ does not
identically equal to zero, $\Gamma^{+}\cap L=\O$. Then we have:

$\displaystyle\left(\arctan{1\over C_{\beta}^{2}}\right){(\sup w^{+})^{2}\over
2}\leq|\chi_{w^{+}}(\Gamma^{+})|\leq\int_{\Gamma^{+}}\det
D^{2}w\leq\int_{\Gamma^{+}}\frac{(a_{ij}w_{ij})^{2}}{\lambda^{2}}.$ (174)

On $\Gamma^{+},$

$\displaystyle a_{ij}w_{ij}=$ $\displaystyle
a_{ij}h_{ij}g^{\gamma}+a_{ij}(g^{\gamma})_{ij}(h-\delta)+a_{ij}h_{i}(g^{\gamma})_{j}+a_{ij}h_{j}(g^{\gamma})_{i}$
$\displaystyle+\sum_{k=1,2}(b_{k}h_{k}g^{\gamma}+b_{k}(g^{\gamma})_{k}(h-\delta)-b_{k}w_{k})$
$\displaystyle\geq$
$\displaystyle-C(C_{E},\Lambda,\gamma)(h^{+}+\delta)-\Lambda\gamma|\nabla
h|g^{\gamma-1}|\nabla g|-C_{E}|\nabla w|$

and

$|\nabla
w|\leq\frac{w}{1-\sqrt{|x|^{2}+(y-H)^{2}}}\leq\frac{2w}{1-x^{2}-(y-H)^{2}}\leq
2hg^{\gamma-1},$

which implies:

$|\nabla h|\leq\frac{2hg^{\gamma-1}+(h-\delta)\gamma g^{\gamma-1}|\nabla
g|}{g^{\gamma}},$

so,

$|\nabla h||\nabla g|g^{\gamma-1}\leq 2h|\nabla
g|g^{\gamma-2}+(h-\delta)\gamma g^{\gamma-2}|\nabla g|^{2}.$

Take $\gamma=2$ we get:

$a_{ij}w_{ij}\geq-C(C_{E},\Lambda)(h^{+}+\delta),\text{ on }\Gamma^{+}.$

Plug above into (174) we get:

$(\sup w^{+})^{2}\leq
C(\lambda,\Lambda,C_{E},C_{\beta})\left(\int_{\Omega}h^{2}+\delta^{2}\right),$

so,

$\sup_{B_{r_{K}}}h\leq C(\lambda,\Lambda,C_{E},C_{\beta})\delta,$

where we can take $r_{K}=\frac{1}{4C_{\beta}^{2}}$. ∎

## Acknowledgements

The author would like to thank Mikhail Feldman for his patient tutorship in
the past many years. He is also grateful to Guiqiang Chen, Xiuxiong Chen, Wei
Xiang, Bin Xu, Bing Wang, Guohuan Qiu, Jiyuan Han, Jingrui Cheng for the
supports and very helpful discussions.

## References

  * [1] S.Axler, P. Bourdon, W Ramey Harmonic Function Theory GTM137, Springer-Verlag 1992.
  * [2] M. Bae, G. Chen, M. Feldman Regularity of solution to regular shock reflection for potential flow. Invent. Math. 175, 505-543.
  * [3] L.Caffarelli, S.Salsa A Geometric Approach to Free Boundary Problem 2005 American Mathematical Society
  * [4] G.Chen, M.Feldman, J.Hu, W.Xiang Loss of Regularity of Solutions of the Lighthill Problem for Shock Diffraction for Potential Flow  SIAM J. Math. Anal., 52(2), 1096–1114.
  * [5] G. Chen, M. Feldman Global solution of shock reflection by large angle wedge for potential flow. Ann. of Math. (2), 71, 1067-1182.
  * [6] G. Chen, M. Feldman The Mathematics of Shock Reflection-Diffraction and von Neumann’s Conjectures. Research Monograph, Princeton University Press: Princeton, 2017.
  * [7] G. Chen, M. Feldman Comparison principles for self-similar potential flow Proc. of AMS 140(2012), no.2 651-663
  * [8] F. Chorlton Textbook of Fluid Dynamics 1976 D. Van Nostrand Company LTD
  * [9] R. Courant and K. O. Friedrichs Supersonic Flow and Shock Waves 1948 , Springer-Verlag
  * [10] D. Gilbarg and N.Trudinger Elliptic Partial Differential Equations of Second Order. Springer-Verlag, Berlin, 2001.
  * [11] Stefan Hilderbrandt and Friedrich Sauvigny Minimal surfaces in a wedge II.The edge-creeping phenomenon Arch.Math.(1997)164-176.
  * [12] D. Kinderlehrer, G. Stampacchia An Introduction to Variational Inequalities and Their Applications 1980 Academic Press.
  * [13] G. Lieberman Oblique Derivative Problems for Elliptic Equations 2013 World Scientific
  * [14] V. Maz’ya, E. Nazarow, B. Plamenevskij Asymptotic Theory of Elliptic Boundary Value Problems in Singularly Perturbed Domains 2000, Birkhäuser Verlag
  * [15] Nirenberg,L On nonlinear elliptic partial differential equations and Hölder continuity. Comm.Pure.Appl.Math. 6.(1953)103-156.
  * [16] B.Gidas, Wei-Ming Ni and L. Nirenberg Symmetry and Related Properties via the Maximum Principle. Commun. Math. Phys. 68, 209—243 (1979)
  * [17] M. Protter, H. Weinberger Maximum Principle in Differential Equations 1967 Prentice-Hall
  * [18] J. Serrin A Symmetry Problem in Potential Theory Arch. Ration. Mech. Anal. 43(1971), 304-318
  * [19] E.Stein, R.Shakarchi Real Analysis 2005 Princeton University Press
  * [20] M. Sun and K. Takayama Vorticity production in shock diffraction J.Fluid Mech.(2003),vol. 478, pp. 237-256.
  * [21] L.Tartar An Introduction to Sobolev Spaces and Interpolation Spaces 2007 Springer