text:
# Dynamics of heuristic optimization algorithms on random graphs

## I Introduction

Many questions of practical or scientific interest are based on combinatorial optimization problems whose numerical solution requires time resources growing exponentially with the system size, or more precisely, with the number of binary variables needed to encode the problem. These include examples like planning and scheduling problems in various real-world applications, optimization of chip design, cryptografic systems in computer science, or glassy systems and random structures in physics. All these problems are characterized by a non-trivial cost function, or energy, which has to be minimized over a large set of discrete degrees of freedom.

The hardest of these optimization problems are collected in a class called NP-hard GaJo . Hardness refers in this context to the exponential growth of the computational resolution time which is observed for all known numerical algorithms. Despite an extremely large number of known NP-hard problems, and numerous approaches to solve them, no algorithms could be constructed by now which are able to solve such a problem in a time growing only polynomially with the system size. This point supports the widespread conjecture, that no such effective algorithms are constructible.

The numerical search for globally optimal solutions is thus restricted to relatively small systems. Once one has to solve larger systems, good polynomial-time algorithms are needed which construct low-cost configurations. These are not guaranteed to be optimal, but in many cases they can serve as reasonable approximations note:ptas . Many of these algorithms are based on heuristic considerations, e.g. on expected correlations between local structures of the specific problem instance and its optimal solutions. Exploiting these correlations can largely improve the performance of a heuristic procedure.

Here we are using the example of vertex covers (VC) on random graphs. It belongs to the basic NP-hard problems GaJo  and can be considered as a prototype optimization problem over a random structure. In every step of the presented heuristic algorithms, a vertex and possibly some environment is chosen randomly and covered locally optimal. The local structure of the graph, in particular its vertex-degree distribution (distribution of co-ordination numbers), can be exploited: Vertices of high degree are more likely to be covered, those of small degree are more likely to remain uncovered. We are using random graphs in order to get some information about the typical-case behaviour of the algorithm. This is to be contrasted with the worst-case picture used in the traditional theory of computational complexity GaJo .

The study of heuristic algorithms is also interesting from a more theoretical point of view. Many randomized optimization or decision problems show characteristic phase transition, when the parameters of the randomness are tuned, see e.g. the special issues AI ; TCS  for an overview. The analysis of algorithms is frequently used in theoretical computer science to construct bounds for these phase transitions, for some examples see e.g. Ga ; Wo ; PiSpWo ; Fra ; Ac  and references therein. A different approach to these transitions is given by applying techniques from equilibrium statistical mechanics, as was done successfully for some of the fundamental combinatorial problems like 3-satisfiability MoZe ; nature , number partitioning Me , or also vertex cover WeHa1 ; WeHa2 .

This paper is organized as follows: In section II, we introduce the definition of vertex covers and independent sets, present the algorithms and review some important facts on random graphs. The general dynamical equations for the graph evolution process are developed in section III, and they are solved for some cases in section IV. Section V is dedicated to approximations of the dynamical behaviour of cases which could not be solved exactly. In section VI, we present how the leaf-removal algorithm of Bauer and Golinelli BaGo1 ; BaGo2  fits into the presented scheme. It is also generalized to cases where the original algorithm fails to construct a vertex cover. The last section finally summarizes the results and gives an outlook to possible extensions.

## II Model and algorithms

### II.1 Vertex cover and related problems

Let us start with the definition of vertex covers GaJo :

Take any graph $`G=(V,E)`$ with $`N`$ vertices $`i\{1,\mathrm{},N\}`$ and $`M`$ undirected edges $`\{i,j\}EV\times V`$. A vertex cover (VC) is a subset $`UV`$ of vertices such that for every edge $`\{i,j\}E`$ there is at least one of its endpoints $`i`$ or $`j`$ in $`U`$:

$$UV\text{ is VC}\{i,j\}E:iUjU$$
(1)
We call the vertices in $`U`$ covered (cov), whereas the vertices in its complement $`VU`$ are called uncovered (uncov). The definition of a vertex cover implies therefore that every edge has at least one covered end-point.

The full vertex set $`V`$ is of course a trivial vertex cover of any graph $`G`$. In this case, all edges have two covered end-points, and at least some of the vertices can be set uncov without uncovering any edge. The corresponding optimization problem consists in finding a vertex cover of smallest cardinality. This problem belongs, according to the standard book by Garey and Johnson GaJo , to the basic NP-hard optimization problems. Therefore, it is expected to require a solution time growing exponentially in $`N`$ and $`M`$. The numerical solvability is consequently restricted to relatively small graphs.

VC is related to other well-known and widely used NP-hard problems. The first one is the independent set (IS) problem. An IS is a subset $`SV`$ of vertices such that for all $`i,jS`$ we have $`\{i,j\}E`$. So $`VS`$ is obviously a VC for every IS $`S`$, and every maximal IS is the complement of a minimal VC. The independence number, defined as the maximal cardinality max$`(|S|)`$ of all ISs, is consequently given by $`N\mathrm{min}_{\text{VC }U}|U|`$.

A clique is a fully connected subgraph. So, if the vertex subset $`SV`$ is an IS in $`G=(V,E)`$, it is a clique in the complementary graph $`\overline{G}=(V,V\times VE)`$. Finding the largest clique in one graph is equivalent to finding the largest independent set in the complementary graph.

There is also a physical problem which is equivalent to vertex cover, or more obviously to the independent set problem. Imagine the graph $`G`$ to be a lattice, and pack hard spheres of chemical radius 1 onto the vertices. Then, once a vertex is occupied by such a particle, all neighbouring vertices have to be empty. This is exactly what defines an IS. The vertices which are not occupied by spheres thus form a VC. This equivalence provides the basis of the statistical mechanics’ approach to minimal vertex covers on random graphs WeHa3 .

### II.2 Heuristic algorithms for constructing small vertex covers

As already mentioned, the construction of a minimal vertex cover is NP-hard, thus requiring exponential time resources. It is therefore reasonable to develop good approximation algorithms running in polynomial time. Here we describe a class of linear time heuristic algorithms which are able to produce small, but in general suboptimal VCs.

In this algorithm, vertices are sequentially assigned the values cov and uncov until the full graph is covered. An assigned value is not changed any more. This can be interpreted as a graph reduction process: Once a vertex is covered, it can be removed from the graph, together with all incident edges. If a vertex is set uncov, all its neighbours have to be covered in order to cover the graph. The central vertex, its neighbours and all covered edges can again be removed from the graph. The graph thus becomes smaller and smaller, until no edges are left. The size of the resulting vertex cover crucially depends on the order of the vertex selection and the decision to cover/uncover the selected vertex. The main heuristic idea is simple: A vertex of high degree is more likely to be covered, a vertex of small degree is more likely to be uncovered WeHa2 ; WeHa3 . The simplest local information, namely the vertex degree, is thus correlated to the structure of small vertex covers, and can be exploited algorithmically.

This is done in the following way: Given an initially uncovered graph $`G=(V,E)`$ and a non-negative integer $`k`$, which we call the depth of the algorithm. In every algorithmic step a vertex $`i`$ is chosen randomly, and its nearest, 2nd-nearest… and $`k`$th-nearest neighbours are selected. All these vertices, together with all edges connecting two of it, form the induced subgraph $`G^{(k)}(i)=(V^{(k)}(i),E^{(k)}(i))`$. This subgraph can be efficiently covered such that all $`k`$th nearest neighbours are set to cov. For details see the algorithm presented below. The full subgraphs, together with all edges connecting it to other vertices, is deleted from $`G`$.

For locally tree-like graphs, as e.g. random graphs or Bethe lattices, the vertex covers of $`G^{(k)}(i)`$ are especially simple: The $`k`$th neighbours of $`i`$ are covered, the $`(k1)`$st are uncovered, the $`(k2)`$nd are covered again, and so on, until $`i`$ itself is covered (uncovered) for even (odd) depth $`k`$ of the algorithm.

The main heuristic concerns now the question, how the central vertex $`i`$ is selected. It exploits the above-mentioned correlation between vertex degree and covering state of an arbitrary vertex. For even depth $`k`$, the central vertex is covered by the above procedure note1 . So it is useful to choose more frequently vertices of high degree in the subgraph remaining after elimination of already considered vertices. We therefore select a vertex of degree $`d`$ with some weight $`w_d`$ which is a monotonously growing function of $`d`$.

In the case of odd $`k`$, the central vertex is uncovered note1 . Here, the selection weight $`w_d`$ for vertices has to be a monotonously decreasing function of the vertex degree $`d`$.

The algorithm is summarized as follows, inputs are the graph $`G=(V,E)`$, the non-negative integer depth $`k`$, a mapping $`m:\{1,\mathrm{},N\}\{free,cov,uncov\}`$, which is constantly set to $`m(i)free`$ initially, and the positive weight function $`w:_+`$:

| procedure heuristic-VC($`G,k,m,w`$) |
| --- |
| begin |
|  | if $`E=\mathrm{}`$ then |
|  |  | stop; {all edges are covered by vertices with $`m(i)=cov`$} |
|  | Select a vertex $`iV`$ of current degree $`d(i)`$ randomly with weight $`w_{d(i)}`$; |
|  | if $`d(i)=0`$ |
|  |  | begin |
|  |  |  | $`m(i):=uncov`$; |
|  |  |  | $`V:=V\{i\}`$; |
|  |  |  | heuristic-VC($`G,k,m,w`$); |
|  |  | end; |
|  | else |
|  |  | begin |
|  |  |  | $`V^{(0)}(i):=\{i\}`$; |
|  |  |  | for $`\kappa `$ from $`1`$ to $`k`$ |
|  |  |  |  | $`V^{(\kappa )}(i):=V^{(\kappa 1)}(i)\{\kappa \text{th nearest neighbours of }i\}`$; |
|  |  |  | $`E^{(k+1)}(i):=\{\{i,j\}E|iV^{(k)}(i)jV^{(k)}(i)\}`$; |
|  |  |  | $`V:=VV^{(k)}(i)`$; |
|  |  |  | $`E:=EE^{(k+1)}(i)`$; |
|  |  |  | $`m(j):=cov`$ for all $`k`$th neighbours of $`i`$; |
|  |  |  | while $`V^{(\kappa 1)}(i)\mathrm{}`$ |
|  |  |  |  | begin |
|  |  |  |  |  | Select a vertex $`jV^{(\kappa 1)}(i)`$ of maximal distance from $`i`$; |
|  |  |  |  |  | $`m(j):=uncov`$; |
|  |  |  |  |  | $`m(l):=cov`$ for all neighbours $`lV^{(\kappa 1)}(i)`$ of $`j`$; |
|  |  |  |  |  | $`V^{(\kappa 1)}(i):=V^{(\kappa 1)}(i)\{j,\text{neighbours of }j\}`$; |
|  |  |  |  | end; {subgraph covered and removed from $`G`$} |
|  |  |  | heuristic-VC($`G,k,m,w`$); |
|  |  | end; |
| end; |

Please note that the degree of free vertices may change whenever $`G`$ is reduced. The algorithm always considers the current degree in the reduced subgraph, which equals the number of uncovered incident edges. The algorithm therefore defines a Markov process.

Some special cases of the algorithm where already considered for finite connectivity random graphs: In WeHa4 , the case $`k=0`$ and $`w_d=1`$ was included into a complete backtracking algorithm. The upper bound for the minimal vertex covers constructed in this way was rather poor, but it will be improved in sections IV and V by using better $`w_d`$. The case of $`k=1,w_d=1`$ was analyzed in Ga  using a different technique. Whereas being also quite unsatisfactory for small and intermediate average graph connectivities $`c_0=2M/N`$, this algorithm correctly reproduces the leading asymptotic behaviour for large $`c_0`$. In BaGo2 , very surprising results where obtained for $`k=1,w_d=\delta _{d,1}`$, where only vertices of degree 1 (leafs) are selected and uncovered, their neighbour is covered, and both are removed from the graph. This algorithm is able to cover almost all edges for $`c<e`$, thus producing a minimal vertex cover, but it stops for higher connectivities if no vertices of degree 1 are left, even if an extensive number of edges remains uncovered. These two results suggest a promising generalization for the case $`k=1`$: If we choose $`w_1w_d>0`$ for all $`d>1`$, this algorithm will work nearly as well as the leaf removal procedure for small connectivities, but it will also give the correct asymptotic behaviour for large $`c_0`$. The extreme case of choosing always a vertex of smallest current degree will work best on random graphs, but it goes beyond the analysis presented in this paper.

### II.3 Random graphs of arbitrary degree distribution

In order to gain some insight into the typical behaviour of this algorithm, we apply it to random graphs. This subsection is dedicated to summarizing some interesting known results about these graphs, as far as they are important for our analysis. As can be expected from the algorithm presented above, we will concentrate our attention to the distribution of vertex degrees. For a complete presentation see Bo .

The original idea ErRe  is to assign an equal probability to all graphs having the same numbers $`N`$ of vertices and $`M`$ of edges. A random graph $`G_{N,p}`$, with $`0p1`$, is constructed in the following way: The vertex set is chosen to be $`V=\{1,2,\mathrm{},N\}`$. For all vertex pairs $`i,jV,i<j,`$ an edges is included into $`E`$ with probability $`p`$. The two vertices remain disconnected by a direct edge with probability $`1p`$. This graph has on average $`M=p\left(\genfrac{}{}{0pt}{}{N}{2}\right)`$ edges, its mean vertex degree equals $`c_0=(N1)p`$.

The most interesting case for vertex covers are graphs of finite average connectivity, i.e. the average vertex degree $`c_0=2M/N`$ stays finite in the thermodynamic limit $`N\mathrm{}`$. In the above language, we have to fix $`p=\frac{c_0}{N1}`$. The resulting degree distribution is far from uniform. For $`N1`$, a randomly chosen vertex has degree $`d`$ with probability

$$p_d=e^{c_0}\frac{c_0^d}{d!},$$
(2)
i.e. the degree distribution approaches a Poissonian in the thermodynamic limit. In our analysis we also need the probability of finding a vertex of degree $`d`$ by following an arbitrary edge. It is obviously proportional to $`dp_d`$, due to normalization we have

$$p_d^{(1)}=e^{c_0}\frac{c_0^{d1}}{(d1)!}.$$
(3)
We thus find a Poissonian distribution of $`d1`$. The average degree of vertices reached by following an edge equals $`c_0+1`$, so there are on average $`c_0`$ additional edges.

Random graphs undergo a percolation transition at average vertex degree $`c_0=1`$. Below this threshold, the graph consists of an extensive number of small connected components, each containing up to $`O(\mathrm{ln}N)`$ vertices. For $`c_0>1`$, the number of small connected components of $`G_{N,c/(N1)}`$ is still extensive, but there is also one macroscopic connected component of $`O(N)`$ vertices. This giant component grows with increasing $`c_0`$, and exponentially approaches size $`N`$ when $`c_0`$ becomes large.

The concept of random graphs was recently generalized to random graphs of arbitrary degree distribution MoRe ; Ne . There, every graph of a given distribution $`p_d`$ (not necessarily a Poissonian) is assigned the same probability. These graphs can be easily generated: For all vertices $`i=1,\mathrm{},N`$, a degree $`d(i)`$ is drawn randomly from $`p_d`$. If $`_id(i)`$ is even, we continue, if not, we repeat the above procedure. Then a large vertex set is created, containing every vertex $`i`$ exactly $`d(i)`$ times. Now we sequentially select pairs of vertices and add these to the edge set $`E`$, excluding only self-connections. Following again an edge, the reached vertex has degree $`d`$ with probability $`p_d^{(1)}=dp_d/c_0`$, with $`c_0=_kkp_k`$ denoting the average degree.

### II.4 Minimal vertex covers on random graphs

Before analysing the behaviour of the presented heuristics, we will give a short overview over known properties of minimal vertex covers on random graphs, see WeHa3  for the original presentation.

The analysis there was carried out for random graphs $`G_{N,c_0/(N1)}`$, using the mapping to a hard-sphere lattice gas described in subsection II.1. Using the replica method, a grand-canonical approach was taken, including a chemical potential $`\mu `$ controlling the number of hard spheres. In the limit $`\mu \mathrm{}`$, the system tends to the closest packings, or, equivalently, to the minimal vertex covers. Assuming the validity of replica symmetry, it was found that minimal VCs contain a fraction of vertices given by

$`x_c(c_0)`$ $`=`$ $`\underset{N\mathrm{}}{lim}N^1\underset{\text{VC }U}{\mathrm{min}}|U|`$ (4)
$`=`$ $`1{\displaystyle \frac{W(c_0)^2+2W(c_0)}{2c_0}}`$
with $`W(c_0)`$ being the real branch of the Lambert-W function defined as the inverse of $`We^W=c_0`$. It was also shown, that replica symmetry is locally stable for $`c_0e`$, whereas it is unstable for larger average connectivities, leading to broken replica symmetry. The correctness of (4) was recently shown to be exact in BaGo2  based on a leaf-removal algorithm, which, as mentioned above, can be understood as a variant of heuristic-VC.

An interesting insight into the structural properties of minimal vertex covers was given by identifying a covered and an uncovered backbone. The first one is defined as the set of all vertices which are covered in all minimal VCs, the uncovered backbone unifies all vertices being uncov in all minimal VCs. Denoting their relative sizes by $`b_{cov/uncov}(c_0)`$, the replica symmetric analysis leads to

$`b_{cov}(c_0)`$ $`=`$ $`1{\displaystyle \frac{W(c_0)^2+W(c_0)}{c_0}}`$
$`b_{uncov}(c_0)`$ $`=`$ $`{\displaystyle \frac{W(c_0)}{c_0}}.`$ (5)
The remaining $`NW(c_0)^2/c`$ vertices belong neither to the covered nor the uncovered backbone, they change the covering state from one minimal VC to the next. A strong correlation between degree distribution and backbone was observed: Vertices of small degree tend to be more frequently in the uncovered backbone, whereas vertices of high degree can be found more likely in the covered backbone. As mentioned in subsection II.2, this can be exploited in the heuristic algorithm by adapting the selection weights.

## III Rate equations for the degree distribution

### III.1 Graph reduction dynamics

We assume that the input to the algorithm heuristic-VC is a random graph $`G=(V,E)`$ with $`N`$ vertices and degree distribution $`p_d`$, and we concentrate on the graph reduction process for a moment. The size of the constructed vertex cover will be calculated in subsection III.2.

In every algorithmic step, a vertex is selected with weight $`w_d`$ depending only on its current degree $`d`$. Then, this vertex and all its nearest neighbours, 2nd nearest neighbours,… $`k`$th nearest neighbours are removed from the graph. The edges incident to these vertices are removed, too. Following this procedure, a smaller graph is defined, and the algorithm is iterated. This graph reduction process is Markovian, because the action of each algorithmic steps depends only on the properties of the current reduced graph, more precisely on the current vertex degrees and neighbourhood relations.

Let us further assume, that we start at (algorithmic) time $`t=0`$, and every iteration step is counted as $`\mathrm{\Delta }t`$. The dynamics will be described by rate equations for the vertex-degree distribution $`p_d(t)`$, or the number of vertices $`N_d(t)=p_d(t)N(t)`$ of degree $`d`$, where $`N(t)`$ denotes the remaining vertex number at time $`t`$. Their dynamics can be decomposed into the following elementary processes (where $`_t=_{d=0}^{\mathrm{}}()p_d(t)`$ denotes the average over the current degree distribution $`p_d(t)`$):

* Removal of the central vertex: A central vertex of degree $`d`$ is selected with weight $`w_d`$, i.e. with probability $`w_dp_d(t)/w_d_t`$. $`N_d(t)`$ is thus reduced by one with this probability.
* Removal of the 1st, 2nd,…, $`k`$th nearest neighbours: According to the last item, the central vertex has on average $`w_dp_d(t)_t/w_d_t`$ neighbours. As the degrees of neighbouring sites are uncorrelated in random graphs, each of these has degree $`d`$ with independent probabilities $`p_d^{(1)}(t)=dp_d(t)/d_t`$. Random graphs are locally tree-like, $`d1`$ of the $`d`$ edges of a 1st neighbour lead to 2nd nearest neighbours, i.e. the average number of 2nd neighbours equals $`\frac{dw_d_t}{w_d_t}\frac{d(d1)_t}{d_t}`$. This argument can easily extended to 3rd neighbours etc.
* Update of the connectivity of $`(k+1)`$st neighbours: The edges connecting $`k`$th and $`(k+1)`$st neighbours are removed from the graph, too. The degree of every $`(k+1)`$st neighbour is thus reduced by one.

These processes are combined to evolution equations for the expected numbers $`N_d(t)`$ of vertices with degree $`d`$ at time $`t`$:

$`N_d(t+\mathrm{\Delta }t)`$ $`=`$ $`N_d(t){\displaystyle \frac{w_dp_d(t)}{w_d_t}}{\displaystyle \frac{dw_d_t}{w_d_t}}{\displaystyle \underset{m=1}{\overset{k}{}}}\left({\displaystyle \frac{d(d1)_t}{d_t}}\right)^{m1}{\displaystyle \frac{dp_d(t)}{d_t}}`$ (6)
$`+{\displaystyle \frac{dw_d_t}{w_d_t}}\left({\displaystyle \frac{d(d1)_t}{d_t}}\right)^k{\displaystyle \frac{(d+1)p_{d+1}(t)dp_d(t)}{d_t}}`$
The first line describes the deletion of vertices, the second the update of the degrees of all $`(k+1)`$st neighbours. These equations are valid for the average trajectory, which is, however, followed with probability approaching 1 for $`N=N(t=0)\mathrm{}`$. Macroscopic deviations appear only with exponentially small probability and are thus important for small $`N`$ only. The quality of using the average trajectory is demonstrated in the inset of fig. 1. There the trajectory of a single graph with $`N=310^4`$ vertices is found to excellently follow the analytical prediction.

Using equations (6), we can calculate also the evolution of the total numbers of remaining vertices, $`N(t)=_dN_d(t)`$, and edges, $`M(t)=\frac{1}{2}_ddN_d(t)`$:

$`N(t+\mathrm{\Delta }t)`$ $`=`$ $`N(t)1{\displaystyle \frac{dw_d_t}{w_d_t}}{\displaystyle \underset{m=1}{\overset{k}{}}}\left({\displaystyle \frac{d(d1)_t}{d_t}}\right)^{m1}`$
$`M(t+\mathrm{\Delta }t)`$ $`=`$ $`M(t){\displaystyle \frac{1}{2}}{\displaystyle \frac{dw_d_t}{w_d_t}}\left(1+{\displaystyle \frac{d^2_t}{d_t}}{\displaystyle \underset{m=1}{\overset{k+1}{}}}\left[{\displaystyle \frac{d(d1)_t}{d_t}}\right]^{m1}\left[{\displaystyle \frac{d(d1)_t}{d_t}}\right]^{k+1}\right).`$ (7)
As we are mainly interested in the behaviour of large graphs, $`N1`$, we may change to intensive quantities by writing $`N(t)=n(t)N,N_d(t)=p_d(t)n(t)N`$. Setting further $`\mathrm{\Delta }t=\frac{1}{N}`$, and replacing differences by derivatives in the thermodynamic limit, we find

$`\dot{n}(t)`$ $`=`$ $`1{\displaystyle \frac{dw_d_t}{w_d_t}}{\displaystyle \underset{m=1}{\overset{k}{}}}\left({\displaystyle \frac{d(d1)_t}{d_t}}\right)^{m1}`$
$`\dot{n}(t)p_d(t)+n(t)\dot{p}_d(t)`$ $`=`$ $`{\displaystyle \frac{w_dp_d(t)}{w_d_t}}{\displaystyle \frac{dw_d_t}{w_d_t}}{\displaystyle \underset{m=1}{\overset{k}{}}}\left({\displaystyle \frac{d(d1)_t}{d_t}}\right)^{m1}{\displaystyle \frac{dp_d(t)}{d_t}}`$ (8)
$`+{\displaystyle \frac{dw_d_t}{w_d_t}}\left({\displaystyle \frac{d(d1)_t}{d_t}}\right)^k{\displaystyle \frac{(d+1)p_{d+1}(t)dp_d(t)}{d_t}}.`$
The graph reduction process is thus described by an infinite set of non-linear differential equations, where the non-linearity enters only through the time-dependent averages $`_t`$. As we were starting with an ordinary random graph, these equations have to be solved under the initial condition

$`n(0)`$ $`=`$ $`1`$
$`p_d(0)`$ $`=`$ $`e^{c_0}{\displaystyle \frac{c_0^d}{d!}}`$ (9)
where $`c_0`$ equals the initial average vertex degree.

In section V we also need the dynamical equations for the moments $`d^n_t`$ of $`p_d(t)`$. Multiplying the second of eqs. (III.1) with $`d^n`$ and summing over all degrees yields

$`n(t){\displaystyle \frac{d}{dt}}d^n_t`$ $`=`$ $`{\displaystyle \frac{w_d_td^n_td^nw_d_t}{w_d_t}}+{\displaystyle \frac{dw_d_t}{w_d_t}}{\displaystyle \frac{d_td^n_td^{n+1}_t}{d_t}}{\displaystyle \underset{m=1}{\overset{k}{}}}\left({\displaystyle \frac{d(d1)_t}{d_t}}\right)^{m1}`$ (10)
$`+{\displaystyle \frac{dw_d_t}{w_d_t}}{\displaystyle \frac{d(d1)^n_td^{n+1}_t}{d_t}}\left({\displaystyle \frac{d(d1)_t}{d_t}}\right)^k`$
Please note that these equations do not contain any finite and closed subset of equations, because the evolution of any moment depends also on higher moments.

A similar approach was chosen in PiSpWo  to analyze an algorithm constructing the maximal sub-graph having minimal degree $`K`$, i.e. the so-called $`K`$-core. Pittel et al. rigorously derived and solved a closed set of equations for $`N_0(t),\mathrm{},N_{K1}(t)`$ and $`M(t)`$. An analogous reduction to a finite number of equations will be constructed in section VI for the generalized leaf-removal algorithm, but it cannot be achieved for the general case.

Our approach resembles also the rate equation approach used in the area of growing networks AlBa ; KrRe ; DoMe . Note, however, that there the evolution of the number $`N_d(t)`$ of vertices of degree $`d`$ depends only on the vertices having smaller degree, because edges are always added and never deleted. So, in principle, the evolution equations can be solved by calculating first $`N_0(t)`$, then $`N_1(t)`$ and so on. In the graph reduction process the problem becomes more complicated since the evolution of $`N_d`$ depends also on $`N_{d+1}`$, for arbitrary $`d`$, but there is no maximal degree $`d`$ in the Poissonian initial condition.

### III.2 The cardinality of constructed vertex covers

Before trying to solve equations (III.1,III.1) for specific choices of $`w_d`$ and $`k`$, we will give general expressions for the number $`X(t)`$ of vertices which are covered by the algorithm.

For the locally tree-like case of random graphs, the $`k`$th neighbours of the selected vertex are covered, the $`(k1)`$st are uncovered etc. So the covering state of the central vertex depends on the depth $`k`$: For even $`k`$, it will be covered (if $`d0`$), for odd $`k`$, it will be uncovered. We therefore consider these two cases independently.

#### III.2.1 Odd depth $`k`$

For odd $`k`$, the central vertex is almost always uncovered. Denoting the expected number of covered vertices at time t with $`X(t)=x(t)N`$, we thus find

$$X(t+\mathrm{\Delta }t)=X(t)+\frac{dw_d_t}{w_d_t}\underset{m=0}{\overset{(k1)/2}{}}\left(\frac{d(d1)_t}{d_t}\right)^{2m},$$
(11)
cf. the first of equations (III.1). Going again to the limit of large graphs, $`N\mathrm{}`$, this can be written as a differential equation for $`x(t)`$:

$$\dot{x}(t)=\frac{dw_d_t}{w_d_t}\underset{m=0}{\overset{(k1)/2}{}}\left(\frac{d(d1)_t}{d_t}\right)^{2m}.$$
(12)
Once we know the solution of the graph dynamical equation (III.1), we can calculate the time $`t_f`$ where all edges are covered, $`d_{t_f}=0`$, and integrate the last equation over the time interval $`[0,t_f]`$. As all removed edges were covered by our algorithm, we thus have constructed a vertex cover of relative size $`x(t_f)`$. As the described average trajectory is followed with probability one for $`N\mathrm{}`$, this $`x(t_f)`$ gives an upper bound for the true minimal vertex cover size of the random graph under consideration.

#### III.2.2 Even depth $`k`$

For even $`k`$, the central vertex is covered in general. Only if it is disconnected, i.e. if its degree equals zero, it is set to uncov, see the algorithm heuristic-VC. The last case happens with probability $`\frac{w_0p_0(t)}{w_d_t}`$. We thus conclude for $`X(t)`$

$$X(t+\mathrm{\Delta }t)=X(t)+1\frac{w_0p_0(t)}{w_d_t}+\frac{dw_d_t}{w_d_t}\underset{m=0}{\overset{k/21}{}}\left(\frac{d(d1)_t}{d_t}\right)^{2m+1},$$
(13)
or, in the limit $`N\mathrm{}`$,

$$\dot{x}(t)=+1\frac{w_0p_0(t)}{w_d_t}+\frac{dw_d_t}{w_d_t}\underset{m=0}{\overset{k/21}{}}\left(\frac{d(d1)_t}{d_t}\right)^{2m+1}.$$
(14)
This equation can be integrated, once we know the solution of equations (III.1), and an upper bound to $`x_c(c_0)`$ can be read off.

## IV The solvable case of linear selection weights $`w_d`$

The problem in solving differential equations (III.1) with initial conditions (III.1) is, that the Poissonian shape of the degree distribution is, in general, not conserved under the dynamics. In such cases one has to keep track of all the individual probabilities $`p_d(t)`$ for each possible degree $`d`$. As the dynamics of $`p_d(t)`$ depends on $`p_{d+1}(t)`$ for all $`d`$, and $`d`$ is not bound from above for the Poissonian initial condition, it is not obvious how to construct a finite and closed subset of equations which can be solved separately, opening the door to the solution for all $`p_d`$.

There exist, however, some cases where the Poissonian shape of the degree distribution is conserved, as can be shown explicitly by plugging a Poissonian Ansatz

$$p_d(t)=e^{c(t)}\frac{c(t)^d}{d!}$$
(15)
into (III.1) and verifying, that the same equation for the average vertex degree $`c(t)`$ is reproduced for arbitrary $`d`$. The most general case for this behaviour is found for linear selection weights

$$w_d=Ad+B$$
(16)
where $`A,B`$ are arbitrary non-negative real numbers. In this case, the graph can be totally specified by calculating $`n(t)=\frac{N(t)}{N}`$ and $`c(t)=\frac{2M(t)}{N(t)}`$. Their evolution can be read off from equations (III.1), where the averages $`_t`$ can be expressed via $`c(t)`$:

$`d_t`$ $`=`$ $`c(t)`$
$`d(d1)_t`$ $`=`$ $`c(t)^2`$
$`w_d_t`$ $`=`$ $`Ac(t)+B`$
$`dw_d_t`$ $`=`$ $`Ac(t)^2+(A+B)c(t)`$ (17)
In the limit $`N\mathrm{}`$ the graph reduction dynamics is thus completely determined by the differential equations

$`\dot{n}(t)`$ $`=`$ $`1{\displaystyle \frac{Ac(t)^2+(A+B)c(t)}{Ac(t)+B}}{\displaystyle \underset{m=0}{\overset{k1}{}}}c(t)^m`$
$`\dot{n}(t)c(t)+n(t)\dot{c}(t)`$ $`=`$ $`2{\displaystyle \frac{Ac(t)^2+(A+B)c(t)}{Ac(t)+B}}{\displaystyle \underset{m=0}{\overset{k}{}}}c(t)^m`$ (18)
Eliminating $`\dot{n}(t)`$ from the second equation, we end up with

$$n(t)\dot{c}(t)=\frac{Ac(t)^2+(2A+B)c(t)}{Ac(t)+B}\frac{Ac(t)^2+(A+B)c(t)}{Ac(t)+B}\underset{m=1}{\overset{k}{}}c(t)^m.$$
(19)
These equations have to be solved under the initial conditions $`n(t=0)=1`$ and $`c(t=0)=c_0`$

### IV.1 Constant selection weights: $`A=0,B=1`$

Equations (IV,19) simplify further if we restrict it for a while to constant selection weights $`w_d1`$, i.e. $`A=0,B=1`$. There we find

$`\dot{n}(t)`$ $`=`$ $`{\displaystyle \underset{m=0}{\overset{k}{}}}c(t)^m`$
$`n(t)\dot{c}(t)`$ $`=`$ $`c(t)\dot{n}(t).`$ (20)
In the second line, the equation for $`\dot{n}(t)`$ was already used to eliminate the complicated sum of powers of $`c(t)`$. Using the initial conditions $`n(t=0)=1`$ and $`c(t=0)=c_0`$, the second line results in

$$c(t)=c_0n(t),$$
(21)
and one of the two functions can be eliminated from the first of equations (IV.1). We consequently find

$$\dot{c}(t)=c_0\underset{m=0}{\overset{k}{}}c(t)^m$$
(22)
which is solved implicitly by

$$t=\frac{1}{c_0}_{c(t)}^{c_0}\frac{d\stackrel{~}{c}}{_{m=0}^k\stackrel{~}{c}^m}.$$
(23)
The algorithm stops when all edges are covered, i.e. for $`c(t_f)=0`$. This final time $`t_f`$ corresponds, in the original algorithmic language, to $`t_fN`$ iterations of heuristic-VC, and is given by

$$t_f=\frac{1}{c_0}_0^{c_0}\frac{d\stackrel{~}{c}}{_{m=0}^k\stackrel{~}{c}^m}.$$
(24)
These results can be used in order to determine the relative size $`x_f(c_0)=x(t_f)`$ using the results of section III.2. There we observed a difference between even and odd values $`k`$ of the depth of heuristic-VC according to the fact that the central vertex in one case is almost always covered, in the other case uncovered. We therefore continue discussing these cases separately, starting with $`k=0`$, going then to arbitrary odd $`k`$, and discussing general even $`k`$ at the end of this section.

#### IV.1.1 The simplest algorithm

The simplest possible algorithm has depth $`k=0`$: In every algorithmic step an arbitrary vertex is chosen and covered if its degree is non-zero, uncovered else. The vertex and all incident edges are removed from the graph. This simple algorithm was already analysed in WeHa4  as the heuristic underlying a complete backtracking algorithm. The results given there can be easily reproduced, for $`k=0`$ the integration in eq. (23) can be trivially carried out. We find a simple linear decrease of the average vertex degree,

$$c(t)=(1t)c_0,$$
(25)
and the final time becomes $`t_f=1`$ as one vertex is removed in every algorithmic step. The resulting size of the constructed vertex cover follows easily by integrating equation (14), with $`p_0(t)=e^{c(t)}`$:

$$x_f^{(0,0)}(c_0)=1\frac{1e^{c_0}}{c_0},$$
(26)
cf. WeHa4 . This gives the very first and simplest upper bound on the true size of minimal vertex covers which is, however, not very good: For, e.g., $`c_0=2`$, we find $`x_f(2)=0.5677`$ compared to the true value $`x_c(c)=0.3919`$, cf. eq. (4). Also the asymptotic behaviour for large average vertex degrees, $`x_f(c_0>>1)1\frac{1}{c_0}`$, does not meet the exact asymptotic behaviour, which was evaluated by Frieze Fr  to be $`x_c(c_0>>1)1\frac{\mathrm{ln}c_0}{c_0}`$ to leading order.

#### IV.1.2 Gazmuri’s algorithm and odd depths

This asymptotics is found to hold also for a slightly more complicated case: It is valid for all non-zero values of the depth, i.e. for $`k>0`$. Let us, for simplicity, start with arbitrary odd values of the depth $`k`$ of the algorithm. For $`k=1`$, the algorithm is equivalent to the one proposed by Gazmuri Ga : In every time step, an arbitrary vertex is chosen and set to uncov, all its neighbours are covered, and the whole cluster including all incident edges are removed from the graph. Gazmuri has already characterized the performance of this algorithm, using a different technique.

Please remember that, according to equation (22), the time dependency of the mean vertex degree is given by

$$\dot{c}(t)=c_0\underset{m=0}{\overset{k}{}}c(t)^m.$$
(27)
This can be used to solve equation (12) for the evolution of the number of covered vertices, which, using the Poissonian distribution (15), and integrating over $`t`$ reads

$$x(t)=_0^t𝑑t^{}\underset{m=0}{\overset{(k1)/2}{}}c(t^{})^{2m+1}.$$
(28)
Changing variables from $`t`$ to $`c`$, and plugging in equation (27), we find

$`x(c)`$ $`=`$ $`{\displaystyle \frac{1}{c_0}}{\displaystyle _c^{c_0}}𝑑\stackrel{~}{c}{\displaystyle \frac{_{m=0}^{(k1)/2}\stackrel{~}{c}^{2m+1}}{_{n=0}^k\stackrel{~}{c}^n}}`$ (29)
$`=`$ $`{\displaystyle \frac{1}{c_0}}{\displaystyle _c^{c_0}}𝑑\stackrel{~}{c}{\displaystyle \frac{\stackrel{~}{c}}{1+\stackrel{~}{c}}}`$
$`=`$ $`{\displaystyle \frac{c_0c}{c_0}}{\displaystyle \frac{1}{c_0}}\mathrm{ln}{\displaystyle \frac{1+c_0}{1+c}}.`$
This expression gives the $`x`$-$`c`$-trajectory which is interestingly independent on the depth $`k`$ (as long as $`k`$ is odd). The only difference is given by the time dependencies $`x(t)=x(c(t))`$ as $`c(t)`$ is $`k`$-dependent, cf. equation (23).

The graph is completely covered when $`c(t)`$ reaches zero. The cardinality of this vertex cover is almost surely given by $`x_f(c_0)=x(c=0)`$, i.e.

$$x_f^{(k,0)}(c_0)=1\frac{\mathrm{ln}(1+c_0)}{c_0}$$
(30)
independently on the (odd) depth $`k`$ of the algorithm. For $`k=1`$, Gazmuri’s bound is thus reproduced, and the leading order of the behaviour for large initial connectivities $`c_0`$ is correctly found. The algorithm is, however, less successful for small and intermediate connectivities, as we will see in the following sections.

#### IV.1.3 The case of even depth $`k2`$

The case of even depth leads to more complicated expressions, which cannot be evaluated explicitly. The main problem is induced by the $`p_0(t)`$-contribution in the evolution of $`x(t)`$, as given in equation (14). After having applied the Poissonian ansatz (15), the latter reads

$$x(t)=_0^t𝑑t^{}\left(\underset{m=0}{\overset{k/2}{}}c(t^{})^{2m}e^{c(t)}\right),$$
(31)
hence we find for the relative vertex-cover size, and arbitrary even depth $`k`$

$$x_f^{(k,0)}(c_0)=\frac{1}{c_0}_0^{c_0}𝑑\stackrel{~}{c}\frac{_{m=0}^{k/2}\stackrel{~}{c}^{2m}e^{\stackrel{~}{c}}}{_{n=0}^k\stackrel{~}{c}^n}.$$
(32)
This integral cannot be evaluated explicitly for arbitrary even $`k`$. We can, however, extract the asymptotic behaviour for $`c_01`$. In this limit, the terms of $`O(e^{\stackrel{~}{c}})`$ and $`O(\stackrel{~}{c}^0)`$ can be neglected in both the numerator and the denominator in the last integral. The corrections from the integration interval $`(0,O((c_0)^0))`$ are of order 1 and thus suppressed by the prefactor $`\frac{1}{c_0}`$, compared to the leading terms

$$x_f^{(k,0)}(c_01)1\frac{\mathrm{ln}(1+c_0)}{c_0}$$
(33)
which coincide with the case of odd depth.

### IV.2 Linear selection weights: $`A=1,B=0`$

After having discussed in great detail algorithms with $`w_d=const.`$, i.e. simple algorithms selecting central vertices completely at random, without regarding its degree, we now turn to the case of linear $`w_d`$. In this case, as already mentioned at the beginning of this section, the degree distribution still stays Poissonian. This can be understood intuitively in the following way: The case $`w_d=d`$ is equivalent to choosing an arbitrary edge with constant probability, and selecting one of the end-vertices. According to section II.3, the chosen vertex will have degree $`d`$ with probability $`p_d^{(1)}dp_d`$. The more general case $`w_d=Ad+B`$, cf. eq. (16), corresponds to mixing this selection procedure (weight $`A`$) with the uniform selection of vertices (weight $`B`$).

Fixing $`A`$ to a non-zero value is sensible only for even depth values $`k`$ since these correspond to covering the central vertex of the cluster of radius $`k`$. As mentioned above, the vertex degree is correlated to the covering state in small vertex covers, so it does not make sense to preferentially select vertices of high degree and to uncover it subsequently. The performance of the algorithm is thus only improved for even $`k`$. The strongest improvement is obtained for $`w_d=d`$, i.e. for $`B=0`$.

Whereas eqs. (IV,19) lead to complicated coupled non-linear differential equations for $`c(t)`$ and $`n(t)`$, which have to be solved numerically for general even $`k`$, the case $`k=0`$ becomes very simple. There, the equations read

$`\dot{n}(t)`$ $`=`$ $`1`$
$`n(t)\dot{c}(t)`$ $`=`$ $`c(t)2`$
$`\dot{x}(t)`$ $`=`$ $`1`$ (34)
and are solved by

$`n(t)`$ $`=`$ $`1t`$
$`c(t)`$ $`=`$ $`c_0(2+c_0)t`$
$`x(t)`$ $`=`$ $`t`$ (35)
The graph is covered for $`c(t_f)=0`$, which leads to vertex covers of size

$$x_f^{(0,1)}(c_0)=1\frac{2}{2+c_0}.$$
(36)
This size is always smaller than the one found for the very simplest algorithm ($`w_d=1,k=0`$), but stays worse than Gazmuri’s algorithm ($`w_d=1,k=1`$). Also the asymptotic behaviour is not correctly reproduced.

## V An approximation for depth-zero algorithms with non-linear selection weights

If we choose non-linear selection weights $`w_d=d^\alpha ,\alpha 0,1`$, the graph reduction dynamics deviates from the unrestricted ensemble of random graphs, and the degree distribution becomes non-Poissonian. The new distribution thus cannot be described by the evolution of its mean value alone, and we have to solve all equations from (III.1) simultaneously. In general, this cannot be achieved analytically. To approximate the solution numerically, we may cut the tail of $`p_d(t)`$, and solve only a finite number of equations. This works fine for small initial values of $`c_0=c(t=0)`$ because of the rapid decrease of the Poissonian distribution. For larger values of $`c_0`$ however, the number of remaining equations becomes large, too. So it would be better to find an approximation of $`p_d(t)`$ depending only on a small number of parameters. The dynamics of these parameters can be determined from the lowest moments $`d^m_t,`$ with $`m`$ ranging from 1 to the number of parameters.

This section is dedicated to algorithms of depth $`k=0`$, but non-linear selection weights $`w_d=d^\alpha ,\alpha 0,1`$. Every algorithmic step thus removes one vertex from the graph. No vertices of degree 0 are selected ($`w_0=0`$); all selected vertices thus have to be covered according to heuristic-VC. We thus trivially have

$`n(t)`$ $`=`$ $`1t`$
$`x(t)`$ $`=`$ $`t`$ (37)
and the size of the constructed vertex cover is given by $`x_f^{(0,\alpha )}(c_0)=t_f`$ with $`c(t_f)=0`$. Note that this does not necessarily imply $`n(t_f)=0`$ as only vertices of non-vanishing degree are selected. At time $`t_f`$, the remaining graph consists of $`(1t_f)N`$ completely disconnected vertices.

As the initial condition $`p_d(t=0)`$ of the graph reduction dynamics is given by a Poissonian of mean $`c_0`$, we are looking for a deformation of the Poissonian distribution which allows to independently vary mean and variance, and thus to approximate the true $`p_d(t)`$. A simple possibility is given by the generalized binomial expression

$$\pi _d(t)=\frac{\mathrm{\Gamma }(1+\mu (t)^1)}{\mathrm{\Gamma }(1+\mu (t)^1d)\mathrm{\Gamma }(1+d)}\left[1c(t)\mu (t)\right]^{(\mu (t)^1d)}\left[c(t)\mu (t)\right]^d.$$
(38)
For $`\mu (t)0`$, this expression approaches a Poissonian distribution of mean $`c(t)`$, the initial condition is thus characterized by $`c(t=0)=c_0`$ and $`\mu (t=0)=0`$. Please note, however, that (38) does not necessarily describe a probability distribution, because $`\pi _d(t)`$ becomes negative for certain $`d`$ if $`1/\mu (t)`$ is not a positive integer. We do not expect this to produce serious problems for the calculated averages, as long as the absolute value of these negative $`\pi _d(t)`$ stays neglectable compared to the total normalization 1. This is exactly what happens in our case, as we will see below.

The moments of $`\pi _d(t)`$ are given by

$$\mathrm{\Pi }^{(n+1)}(t):=\underset{d=0}{\overset{\mathrm{}}{}}d(d1)\mathrm{}(dn)\pi _d(t)=c(t)^{n+1}[1\mu (t)][12\mu (t)]\mathrm{}[1n\mu (t)].$$
(39)
The product $`d(d1)\mathrm{}(dn)`$ can be expanded into a sum of pure powers, their mean values are determined by inverting this sum:

$$\stackrel{~}{\mathrm{\Pi }}^{(n)}(t):=\underset{d=0}{\overset{\mathrm{}}{}}d^n\pi _d(t)=\underset{m=1}{\overset{n}{}}a_m^{(n)}\mathrm{\Pi }^{(n)}(t).$$
(40)
The coefficients are given iteratively by $`a_m^{(n)}=ma_m^{(n1)}+a_{m1}^{(n1)}`$, using the trivial identity $`a_m^{(1)}=\delta _{m,1}`$ and the convention $`a_0^{(n)}0`$ for all $`n`$.

Given two non-trivial moments, e.g. $`n=1,2`$, $`c(t)`$ and $`\mu (t)`$ can be calculated, and all other moments are determined. We can thus approximate the dynamics of the degree distribution by considering of the dynamics of the first two moments of $`p_d(t)`$ only. The exact equations for $`d_t`$ and $`d(d1)_t`$ follow from eq. (10) by fixing $`k=0`$ and $`w_d=d^\alpha `$,

$`(1t){\displaystyle \frac{d}{dt}}d_t`$ $`=`$ $`d_t2{\displaystyle \frac{d^{\alpha +1}_t}{d^\alpha _t}}`$
$`(1t){\displaystyle \frac{d}{dt}}d(d1)_t`$ $`=`$ $`d(d1)_t{\displaystyle \frac{d^{\alpha +2}_t}{d^\alpha _t}}+{\displaystyle \frac{d^{\alpha +1}_t}{d^\alpha _t}}\left(12{\displaystyle \frac{d(d1)_t}{d_t}}\right).`$ (41)
They contain higher moments of $`p_d(t)`$, but are closed approximately by using (39,40):

$`(1t){\displaystyle \frac{d}{dt}}c(t)`$ $`=`$ $`c(t)2{\displaystyle \frac{\stackrel{~}{\mathrm{\Pi }}^{(\alpha +1)}(t)}{\stackrel{~}{\mathrm{\Pi }}^{(\alpha )}(t)}}`$
$`(1t){\displaystyle \frac{d}{dt}}\left(c(t)^2[1\mu (t)]\right)`$ $`=`$ $`c(t)^2[1\mu (t)]{\displaystyle \frac{\stackrel{~}{\mathrm{\Pi }}^{(\alpha +2)}(t)}{\stackrel{~}{\mathrm{\Pi }}^{(\alpha )}(t)}}+{\displaystyle \frac{\stackrel{~}{\mathrm{\Pi }}^{(\alpha +1)}(t)}{\stackrel{~}{\mathrm{\Pi }}^{(\alpha )}(t)}}\left(12c(t)[1\mu (t)]\right)`$ (42)
These two equations can be easily converted to ordinary differential equations $`\dot{c}(t)=F_c(c(t),\mu (t),t)`$ and $`\dot{\mu }(t)=F_\mu (c(t),\mu (t),t)`$ which are, however, not analytically solvable for general values of $`\alpha `$. They can instead be solved efficiently using numerical standard techniques. The results are displayed in fig. 1 together with numerical simulations obtain for large graphs. We find that the binomial approximation works extremely well for small values of $`\alpha `$, systematically growing deviations appear for larger $`\alpha `$, cf. fig. 2. We also find that heuristic-VC is able to approximate the true minimal vertex-cover size up to a few percent, performing better for larger $`\alpha `$. We observe, however, that even the vertex covers constructed for very large $`\alpha `$ remain suboptimal, i.e. extensively larger than the minimal VCs.

The behaviour of eqs. (V) for large $`c(t=0)=c_0`$ can be extracted analytically by expanding the equations for $`\dot{c}(t)`$ ($`\dot{\mu }(t)`$) to $`O(1/c)`$ ($`O(1/c^2)`$). $`F_\mu `$ is a sum of terms of $`O(\mu ^2)`$, $`O(\mu /c)`$ and $`O(1/c^2)`$, and $`\mu (t)`$ stays of $`O(1/c^2)`$ due to its initial condition $`\mu (0)=0`$. We thus find $`(1t)\dot{c}=c2\alpha O(1/c)`$ which is solved to leading orders by $`c(t)c_0t(c_0+2\alpha )`$. From the vanishing of these leading orders we can read of the dominant contributions to the constructed vertex covers, which we conjecture to be exact also for the true dynamics:

$$x_f^{(0,\alpha )}(c_01)1\frac{2\alpha }{c_0+2\alpha }.$$
(43)
For larger $`\alpha `$, the asymptotics becomes better and better, but still does not reach the correct behaviour $`x_c1\mathrm{ln}(c_0)/c_0`$ of the minimal VCs. Note that, for sufficiently large $`c_0`$, Gazmuri’s depth-one algorithm outperforms the depth-zero algorithm for arbitrary $`\alpha `$. We expect, however, that the correct asymptotic behaviour is reached by exponential selection weights $`w_d`$, and hence in particular for the heuristic where always a vertex of maximal degree is chosen.

## VI Generalizing the leaf removal procedure: Depth-one algorithms

The best performance can be achieved using a generalization of the leaf-removal algorithm (LR) proposed by Bauer and Golinelli BaGo1 . Their algorithm is based on the following observation: Consider a vertex of degree one, i.e. a vertex which has a single neighbour. One of these two vertices has to be covered in order to cover also the connecting edge. It is obviously better to cover the neighbour than the vertex of degree one. Iterating this procedure, there are two possible final situations:
(i) All edges are covered, and the constructed vertex cover is a minimal one.
(ii) There are uncovered edges, but no vertices of current degree one are left. The algorithm stops without having constructed a vertex cover.
This algorithm can be understood as a special case of heuristic-VC with depth $`k=1`$ and $`w_d=\delta _{d,1}`$. Following a completely different route, Bauer and Golinelli have found a surprising result: For random graphs of average degree $`c_0<e`$, their algorithm is able to cover almost all edges, and the predicted minimal vertex cover size coincides with the replica symmetric one found in WeHa1 . For larger average degrees, $`c_0>e`$, case (ii) is valid, and a finite fraction of edges remains uncovered. We re-derive this result below using our dynamical rate equations.

In order to construct a small vertex cover also for higher-connectivity graphs, the algorithm has to be modified to $`w_d>0`$ for all $`d>0`$. The case $`w_d=A\delta _{d,1}+1`$, with $`A>0`$, will therefore be analysed in sec. VI.2. For $`A1`$, this algorithm performs nearly as well as pure leaf-removal for small average vertex degrees. For large $`c_0`$ it finally becomes more and more similar to Gazmuri’s algorithm, being still better for any finite $`c_0`$. We will call this algorithm generalized leaf removal (GLR).

The best performance is, of course, obtained for $`w_d=e^{\alpha d}`$, with $`\alpha \mathrm{}`$. There always a vertex of minimal degree is selected and uncovered, all neighbours are covered. As long as the fraction $`p_1(t)`$ of vertices of degree one is non-zero, the algorithm is equivalent to the leaf-removal procedure. This is valid in particular also for $`c_0<e`$, where (almost) minimal VCs are constructed. The analysis of this algorithm goes, however, beyond the analysis presented here.

### VI.1 Leaf removal

Let us first concentrate on the leaf-removal algorithm (LR) in its original version, i.e. on depth $`k=1`$ and selection weights $`w_d=\delta _{d,1}`$. In every algorithmic step, exactly two vertices are removed from the graph $`G`$, and exactly one vertex is covered. We therefore conclude

$`n(t)`$ $`=`$ $`12t`$
$`x(t)`$ $`=`$ $`t`$ (44)
The degree distribution follows, according to (III.1), from the dynamical equations

$$(12t)\dot{p}_d(t)=2p_d(t)\delta _{d,1}\frac{d^2_t}{d_t^2}dp_d(t)+\frac{d(d1)_t}{d_t^2}(d+1)p_{d+1}(t).$$
(45)
Vertices of degree $`d>1`$ are only touched if they are first or second neighbours of a vertex of degree one, in which cases they are either covered and removed, or their vertex degree is reduced by one. The degrees of neighbouring vertices are statistically independent, we thus expect $`p_d(t)`$ to keep its Poissonian shape for all $`d>1`$. In fact, the ansatz

$`p_d(t)=\gamma (t)e^{\kappa (t)}{\displaystyle \frac{\kappa (t)^d}{d!}}d>1`$ (46)
together with the global normalization

$$1=p_0(t)+p_1(t)+\gamma (t)\left(1e^{\kappa (t)}[1\kappa (t)]\right)$$
(47)
can be plugged into eqs. (45) and leads to uniquely determined equations for $`\gamma (t),\kappa (t)`$ and $`p_1(t)`$. The latter is, for technical reasons, replaced by an equation for $`c(t)`$. Using

$`d_t`$ $`=`$ $`c(t)`$
$`=`$ $`p_1(t)+\gamma (t)\kappa (t)\left[1e^{\kappa (t)}\right]`$
$`d(d1)_t`$ $`=`$ $`\gamma (t)\kappa (t)^2,`$ (48)
these read

$`(12t)\dot{c}(t)`$ $`=`$ $`2c(t)2{\displaystyle \frac{\gamma (t)\kappa (t)^2+c(t)}{c(t)}}`$
$`(12t)\dot{\kappa }(t)`$ $`=`$ $`\kappa (t){\displaystyle \frac{\gamma (t)\kappa (t)^2+c(t)}{c(t)}}`$
$`(12t)\dot{\gamma }(t)`$ $`=`$ $`\gamma (t){\displaystyle \frac{2c(t)\kappa (t)}{c(t)}}.`$ (49)
The initial conditions are $`c(0)=\kappa (0)=c_0,\gamma (0)=1`$. The equation for the average vertex degree $`c(t)`$ can be removed by observing

$$(12t)\frac{d}{dt}\left(\frac{\kappa (t)^2}{c(t)}\right)=(12t)\frac{\kappa (t)^2}{c(t)}\left(2\frac{\dot{\kappa }(t)}{\kappa (t)}\frac{\dot{c}(t)}{c(t)}\right)=2\frac{\kappa (t)^2}{c(t)}$$
(50)
which is solved by

$$c(t)=\frac{\kappa (t)^2}{(12t)c_0}.$$
(51)
The solution of the two remaining equations is given implicitly by

$`t`$ $`=`$ $`1{\displaystyle \frac{1}{2c_0}}\left([\kappa (t)W(c_0e^{\kappa (t)})]^2+2W(c_0e^{\kappa (t)})\right)`$
$`\gamma (t)`$ $`=`$ $`{\displaystyle \frac{W(c_0e^{\kappa (t)})}{(12t)c_0}}`$ (52)
as can be checked explicitly using eqs. (VI.1). $`W`$ denotes again the Lambert-W function, cf. sec. II.4. The graph is covered if this trajectory reaches $`c(t_f)=0`$, i.e. for $`\kappa (t_f)=0`$. From the first of eqs. (VI.1) we thus find the final time

$$t_f=1\frac{W(c_0)^2+2W(c_0)}{2c_0}.$$
(53)
This result is only valid, if $`p_d(t)0`$ for all $`d`$ and all $`0<t<t_f`$. Using eq. (VI.1), we find

$`p_1(t)`$ $`=`$ $`c(t)\gamma (t)\kappa (t)\left[1e^{\kappa (t)}\right]`$ (54)
$`=`$ $`{\displaystyle \frac{\kappa (t)}{(12t)c_0}}\left(\kappa (t)W(c_0e^{\kappa (t)})[1e^{\kappa (t)}]\right)`$
$`=:`$ $`{\displaystyle \frac{\kappa (t)}{(12t)c_0}}\mathrm{\Phi }(\kappa (t)).`$
The prefactor of $`\mathrm{\Phi }(\kappa )`$ is non-negative, it is thus sufficient to investigate $`\mathrm{\Phi }(\kappa )`$ for $`\kappa 0`$. We have $`\mathrm{\Phi }(0)=0`$, and

$$\frac{d\mathrm{\Phi }}{d\kappa }=1\frac{W(c_0e^\kappa )}{1+W(c_0e^\kappa )}[1e^\kappa ]e^\kappa W(c_0e^\kappa ),$$
(55)
i.e. $`\mathrm{\Phi }^{}(0)=1W(c_0)`$. The monotonous function $`W(c_0)`$ becomes larger than 1 for $`c_0>e`$, i.e. in this case $`p_1(t)`$ would approach zero from negative values. This is a contradiction. We therefore conclude

$$c_0<e:x_{LR}(c_0)=1\frac{W(c_0)^2+2W(c_0)}{2c_0},$$
(56)
and this value coincides with the relative size of a minimal vertex cover. For $`c_0>e`$ the algorithm gets stuck if $`p_1(t)=0`$ is reached, no vertices of degree one are left, and a finite fraction of all edges remains uncovered.

### VI.2 Generalized leaf removal

In order to overcome this problem, we generalize the leaf-removal algorithm by modifying the selection weights to $`w_d=1+A\delta _{d,1}`$. This algorithm interpolates between the algorithms of Bauer and Golinelli ($`A\mathrm{}`$, exact minimal VCs for $`c_0<e`$) and the one of Gazmuri ($`A=0`$, correct leading asymptotic behaviour for $`c_01`$). We thus expect that this algorithm shows a very good performance in the whole finite-connectivity region for large, but finite $`A`$.

Also in this case, the Poissonian shape of $`p_d(t)`$ remains correct for all degrees $`d>1`$, and ansatz (46) together with the normalization constraint (47) remains valid. Plugging everything into the dynamical equations (III.1), we directly arrive at

$`\dot{n}(t)`$ $`=`$ $`{\displaystyle \frac{1+c(t)+2Ap_1(t)}{1+Ap_1(t)}}`$
$`n(t)\dot{c}(t)`$ $`=`$ $`c(t){\displaystyle \frac{1+c(t)+2Ap_1(t)}{1+Ap_1(t)}}2{\displaystyle \frac{[\gamma (t)\kappa (t)^2+c(t)][c(t)+Ap_1(t)]}{[1+Ap_1(t)]c(t)}}`$
$`n(t)\dot{\kappa }(t)`$ $`=`$ $`\kappa (t){\displaystyle \frac{[\gamma (t)\kappa (t)^2+c(t)][c(t)+Ap_1(t)]}{[1+Ap_1(t)]c(t)^2}}`$
$`n(t)\dot{\gamma }(t)`$ $`=`$ $`\gamma (t){\displaystyle \frac{c(t)+2Ap_1(t)}{1+Ap_1(t)}}\kappa (t)\gamma (t){\displaystyle \frac{c(t)+Ap_1(t)}{1+Ap_1(t)}}`$ (57)
with $`p_1(t)=c(t)\gamma (t)\kappa (t)[1e^{\kappa (t)}]`$. These equations determine the exact graph reduction dynamics for generalized leaf removal, and can be solved numerically. Due to the non-zero selection weights for all degrees, these equations do not suffer from the appearance of negative values for certain $`p_d(t)`$, and the algorithm always constructs a vertex cover. The number of covered vertices at algorithmic time $`t`$ can be calculated from eq. (12), which for our special choices of $`k`$ and $`w_d`$ reads

$$\dot{x}(t)=\frac{c(t)+Ap_1(t)}{1+Ap_1(t)}$$
(58)
The relative size of the finally constructed vertex cover is, with probability one, given by $`x(t_f)`$, with $`t_f`$ following from $`c(t_f)=0`$. In figure 3, the results are presented for several values of $`A`$ and compared with Gazmuri’s resp. Bauer and Golinelli’s algorithms.

## VII Summary and outlook

The solution of many combinatorial optimization problems requires exponential time resources and is thus restricted to relatively small system sizes. For larger systems, good and fast approximation algorithms are needed, which are frequently based on heuristic considerations concerning correlations between local problem structure and optimal problem solutions.

Constructing a minimal vertex cover of a given graph belongs to the basic NP-hard problems, and can be understood as a prototype combinatorial optimization problem. In this paper, we have therefore analysed linear-time algorithms for constructing small vertex covers of finite-connectivity random graphs. The applied heuristic exploits the observation that vertices of high vertex degree are more likely to be covered in minimal VCs, whereas those of small degree remain more frequently uncovered.

We have introduced and analysed mainly two types of algorithms, namely depth-zero and depth-one algorithms. In the first case, vertices are selected randomly and (if connected to any other vertex) they are covered. We found that the performance of the algorithm can be largely improved by preferentially selecting vertices of high degree.

We also observed that depth-zero algorithms were outperformed by depth-one algorithms. These select a vertex in every algorithmic step and uncover it. All neighbours of the selected vertex must be covered consequently. The best performance is achieved if the algorithm always selects a vertex of smallest degree. As was already found by Bauer and Golinelli BaGo2 , this procedure even outputs an (almost) minimal VC if it is applied to random graphs of average connectivity $`c_0<e`$. The algorithm constructs good approximations also for higher connectivities.

Both types of algorithms can be interpreted as Markovian graph reduction processes. They are analytically characterized by the evolution of the degree distribution of the remaining uncovered subgraphs. The dynamical equations were solved in some cases, in other cases approximations were necessary.

The presented approach can be extended into several directions:

* The applied heuristic was restricted to considering the simplest local structure, namely the degree of the selected vertex. Depth-one algorithms can be improved by e.g. selecting a vertex of minimal degree but with maximal number of next-nearest neighbours. Covering the nearest neighbours thus results in a higher number of covered edges. It would be interesting to extend the rate equations to this case.
* VC is used as a prototype optimization problem, but the approach can be generalized to other combinatorial problems defined over random structures, e.g. to graph coloring or satisfiability problems. For random 3-satisfiability, lower bounds for the SAT/UNSAT threshold are usually obtained using algorithms in the so-called card-game representation Fra ; Ac , which corresponds to $`w_d=const`$ in our analysis.
* Our analysis was restricted to the typical time evolution of the degree distribution. Deviations appear with exponentially small probability - and are thus important for small systems. These rare events can be systematically exploited by exponentially frequent restarts of the algorithm. If a minimal VC is found with probability $`p=e^{\tau N}`$, we need $`e^{(\tau +\epsilon )N}`$ restarts to almost surely construct a VC (for all $`\epsilon >0`$). As observed recently for simple heuristics of vertex cover MonZe  and 3-satisfiability CoMo , this random restart algorithm can be exponentially faster than exact standard procedures (like backtracking). The performance can be improved further by using a more sophisticated heuristics.
* Also sophisticated complete algorithms, i.e. those that find an optimal solution for sure, use heuristic arguments for accelerating the combinatorial search. The presented ideas may hence contribute to the analysis of such algorithms, and the insight may be used to exponentially speed up the numerical search.


format: text

text:
# 1 Introduction

## 1 Introduction

Fiber bundles with connection are the standard mathematical arena for the gauge theories of condensed matter and particle physics. Indeed, pointlike excitations carry information along paths in space-time and this process is well described by the operation of parallel transport. However, in a strongly coupled regime, the dynamics of non-Abelian gauge fields allows the appearance of extended objects such as loops or membranes and we need a new geometrical setting to describe the transport of information on surfaces and higher dimensional manifolds. It is known that the correct extension of parallel transport to surfaces should be defined in gerbes (, , , ) but the theory is still in development.

In order to develop our intuition of gerbes, we restrict our approach to a discrete setting and use a simplicial complex instead of the $`\stackrel{ˇ}{\mathrm{C}}`$ech-de Rahm complex of a covering of a smooth manifold. We extract differential information by considering infinitesimal simplexes. Thus we set a simplicial complex $`X`$ and a Lie group $`G`$ which is our local symmetry group. (In the discrete topology, we can use any topological group, but when we consider infinitesimal simplexes, we will need a smooth symmetry group). The word ”bundle” will always mean ”combinatorial $`G`$-bundle with connection” and ”gerbes” will in fact mean ”combinatorial $`G`$-gerbes with 1-connection (connective structure) and 2-connection (curving)”. We will use informally infinitesimal simplexes and combinatorial differential forms  but without diving into non-standard analysis  or synthetic differential geometry (, ), where we can handle consistently infinitesimal quantities in a broader context than set theory.

## 2 Categorical preliminaries

### 2.1 Basic concepts

We recall here some basic definitions  in order to set our notations. A category $`𝐂`$ is defined by two kinds of data : a class of objects, $`\mathrm{Ob}(𝐂)`$, and, for any pair of objects $`x`$ and $`y`$, a set of arrows $`𝐂_{xy}`$ (or $`𝐂(x,y))`$. These sets are equipped with associative composition laws $`𝐂_{xy}\times 𝐂_{yz}𝐂_{xz}`$ and identities $`1_x𝐂_{xx}`$, so that the sets $`𝐂_{xx}`$ are monoids. When $`\mathrm{Ob}(𝐂)`$ is a set, $`𝐂`$ is called a small category. For any category $`𝐂`$, its opposite category, $`𝐂^{\mathrm{op}}`$, has the same class of objects but the arrows are reversed. A groupoid is a category in which all the arrows are invertible. The monoids $`𝐂_{xx}`$ are then groups.

A weak 2-category $`𝒞`$ is defined by three kinds of data : a class of objects, $`\mathrm{Ob}(𝒞)`$, and, for any pair of objects $`X`$ and $`Y`$, a category of 1-arrows $`𝒞_{XY}`$. The arrows of $`𝒞_{XY}`$ are called the 2-arrows of $`𝒞`$. We have maps $`s_0,t_0,s_1`$ and $`t_1`$, called, respectively, 0-source, 0-target, 1-source and 1-target, and defined as follows. If $`X,Y\mathrm{Ob}(𝒞),u,v\mathrm{Ob}(𝒞_{XY})`$ and $`\alpha :uv`$, then $`s_0(u)=s_0(v)X,t_0(u)=t_0(v)Y,s_1(\alpha )u`$ and $`t_1(\alpha )v`$. The composition of these maps thus satisfy the identities $`s_0s_1=s_0t_1`$ and $`t_0s_1=t_0t_1`$ The composition of 1-arrows in $`𝒞`$ is simply their concatenation, and denoted by $`\times `$. The 2-arrows can be composed either horizontally, if the 0-target of the first one coincides with the 0-source of the second one, or vertically, if the 1-target of the first one coincides with the 1-source of the second one. When all the 1-arrows and 2-arrows of a 2-category are invertible, it is called a 2-groupoid. The invertibility of a 1-arrow $`u:XY`$ asserts the existence of another 1-arrow $`v:YX`$ and of invertible 2-arrows $`\alpha :uv1_X`$ and $`\beta :vu1_Y`$. $`u`$ and $`v`$ are said to be quasi-inverses of each other.

A category $`𝐂`$ is said monoidal when it is endowed with a bifunctor $`𝐂\times 𝐂𝐂`$, with associativity isomorphisms $`a_{x,y,z}:x(yz)(xy)z`$ satisfying the pentagon axiom

$$a_{x,y,zw}a_{xy,z,w}=(1_x\times a_{y,z,w})a_{x,yz,w}(a_{x,y,z}\times 1_w)$$

with an identity object $`I`$ and with left and right identity isomorphisms $`L_x:Ixx`$ and $`R_x:xIx`$ such that

$$a_{x,I,y}(1_x\times L_x)=(R_x\times 1_y)$$

for any $`x,y\mathrm{Ob}(𝐂)`$. If, moreover, for any $`x`$ of $`𝐂`$ there exists an object $`x^{}`$ and invertible arrows $`\epsilon _x:xx^{}I`$ and $`\eta _x:x^{}xI`$ then the monoidal category $`𝐂`$ is termed compact. A compact, monoidal groupoid is called a gr-category .

### 2.2 Torsors and bitorsors

Let $`G`$ be a fixed Lie group. The topological spaces endowed with a left (resp. right), continuous, free and transitive action of $`G`$ are called left (resp. right) $`G`$-torsors. $`\mathrm{},r,\lambda ,\rho ,\mathrm{}`$ will denote generically such actions. A morphism $`f:(\mathrm{},X)(\mathrm{}^{},X^{})`$ between two left $`G`$-torsors is a continuous $`G`$-equivariant map : $`\mathrm{}_gf=f\mathrm{}_{}^{}{}_{g}{}^{}`$. These morphisms are in fact homeomorphisms so that the left (resp. right) $`G`$-torsors and their morphisms form a groupoid $`𝒯_L(G)`$ (resp. $`𝒯_R(G)`$). With $`𝒯_L(G)`$ and $`𝒯_R(G)`$, we can build a group-like category $``$ in the following way . If we want to define a product of two torsors, a one sided action of $`G`$ isn’t enough. However, the left action on $`(\mathrm{},Y)\mathrm{Ob}(𝒯_L(G))`$ can be contracted with the right action on $`(X,r)\mathrm{Ob}(𝒯_R(G))`$ to give a space $`X\times _GY`$ (contracted product) defined by

$`X\times _GY`$ $`=`$ $`X\times Y/`$
$`(x,\mathrm{}_g(y))`$ $``$ $`(r_g(x),y)`$
For $`X\times _GY`$ to be in the same category as $`X`$ and $`Y`$, they must all carry a left action and a right action of $`G`$. A manifold endowed with such actions is called a $`G`$-bitorsor. A morphism $`f:(\mathrm{},X,r)(\mathrm{}^{},X^{},r^{})`$ between two bitorsors is a continuous map which commutes with both actions on $`X`$ and $`X^{}`$. Since $`\mathrm{}_g(x)`$, the image of $`xX`$ under the left action of $`gG`$, can be reached by the right action of a unique $`hG`$, the correspondance $`gh=\phi (g)`$ defines a map $`\phi :GG`$, which is actually an automorphism of $`G`$. Conversely, any $`\phi \mathrm{Aut}(G)`$ determines a unique bitorsor from a left $`G`$-torsor $`(\mathrm{},X)`$, by defining the right action of $`gG`$ as follows :

$$r_g(x)=\mathrm{}_{\phi ^1(g)}(x)xX,gG$$

$``$ will denote the gr-category of $`G`$-bitorsors and $`𝒯_L()`$ the weak 2-groupoid of $``$-torsors. A $``$-torsor is a category $`𝒞`$ on which $``$ acts by equivalences, that is to say each $`G`$-bitorsor $`\beta `$ is mapped to a functor $`F_\beta :𝒞𝒞`$ which admits a quasi-inverse. The simplest $``$-torsors are $`𝒯_L(G)`$ and $`𝒯_R(G)`$, where the action of $`(\lambda ,\beta ,\rho )`$ on $`(\mathrm{},T)𝒯_L(G)`$ twists $`\mathrm{}`$ to give the left $`G`$-torsor $`B\times _GT(\lambda ,T)`$. The importance of bitorsors in non-Abelian cohomology comes from the fact that they compare different torsors and can thus act homogeneously as automorphisms on categories which are equivalent to $`𝒯_L(G)`$ or $`𝒯_R(G)`$.

## 3 Bundles as representations of a groupoid of paths

### 3.1 Combinatorial Bundles

If $`X`$ is a simplicial complex, we can define the groupoid $`\mathrm{\Pi }_1(X)`$ as the category whose objects are its vertices and whose arrows are its edge-paths, i.e. families $`(x_0,x_1,\mathrm{},x_n)`$ of successive neighbour vertices ($`n1`$). We identify neither the paths describing the same curve at different speeds, nor the paths which differ by ”backtrackings” (called ”thin homotopies” in ). In other words, if $`yx`$ then

$`(\mathrm{},x,y,y,z,\mathrm{})`$ $``$ $`(\mathrm{},x,y,z,\mathrm{})`$
$`(\mathrm{},x,y,x,z,\mathrm{})`$ $``$ $`(\mathrm{},x,z,\mathrm{})`$
The insertion or deletion of identical successive vertices is a discrete analogue of a local diffeomorphism and the invariance of physical quantities under backtracking is the ”zigzag symmetry” invoked by A. Polyakov  in the search of a string theory adapted to the description of the confined phase of Yang-Mills theory. Both symmetries must be represented in any quantum theory of loops.

A left bundle with connection over $`X`$ is defined as a presheaf of left $`G`$-torsors on $`\mathrm{\Pi }_1(X)`$, that is to say a contravariant functor $`f:\mathrm{\Pi }_1(X)^{\mathrm{op}}𝒯_L(G)`$ which represents the groupoid of paths into the groupoid of left $`G`$-torsors. The fibers are the objects $`f_x,f_y,f_z,\mathrm{}`$ associated to the vertices $`x,y,z,\mathrm{}`$. The connection is determined by the images of the edges, $`f_{xy}:f_yf_x`$, which are morphisms of left $`G`$-torsors. Its curvature, $`c`$ , is the 2-form defined by the holonomies along elementary loops :

$`c`$ $`=`$ $`{\displaystyle \underset{[xyzx]}{}}[xyzx]c_{xyzx}`$
$`c_{xyzx}`$ $`=`$ $`f_{xy}f_{yz}f_{zx}:f_xf_x`$
Each $`c_{xyzx}`$ is an automorphism of $`G`$-torsor, i.e. an element of $`G`$, and $`c`$ is a $`G`$-valued 2-form, since $`c_{xzyx}=c_{xyzx}^1`$, and $`c_{xyzx}=1G`$ when $`[xyzx]`$ is degenerate.

Two bundles $`f,f^{}`$ are decreted to be isomorphic iff. there exists an invertible natural transformation $`g:f^{}f`$. In components, we have an arrow $`g_x:f_{}^{}{}_{x}{}^{}f_x`$ in $`𝒯_L(G)`$ for each $`x`$, such that $`f_{xy}g_y=g_xf_{}^{}{}_{xy}{}^{}`$, i.e. the following square commutes :

$`f`$ and $`f^{}`$ have therefore the same curvature. When $`f=f^{}`$, $`g_x`$ and $`g_y`$ are elements of $`G`$ and we recover the usual expression of gauge transformations.

### 3.2 The Bianchi Identity

We recall here the homotopical interpretation of the Bianchi identity satisfied by the connection 1-form, $`A`$, and its curvature 2-form, $`F`$, in order to extend it to the case of gerbes. Let $`w,x,y`$ and $`z`$ be four pairwise neighbour points, i.e. an infinitesimal tetrahedron, with $`w`$ as base point. The homotopy $`(wxyw)(wyzw)(wzxw)(wx)(xyzx)(xw)`$, which takes place in the 1-skeleton of $`X`$, implies the multiplicative Bianchi identity

$`\overline{)c_{wxyw}c_{wyzw}c_{wzxw}=f_{wx}c_{xyzx}f_{xw}}`$ (1)
If we choose an origin in each fiber, $`f_{xy}`$ is mapped to an element of $`G`$ and, near the identity, we can write $`f_{xy}=1+A_{xy}`$, $`A`$ being a $`𝔤`$-valued 1-form, i.e. an antisymmetric map ($`A_{yx}=A_{xy}`$) from the set of oriented edges of $`X`$ to $`𝔤`$. We can also write this 1-form as a linear combination of the oriented edges, $`A=_{(xy)}(xy)A_{xy}`$. The curvature of $`A`$ is the $`𝔤`$-valued 2-form $`F=_{[xyzx]}[xyzx]F_{xyzx}`$ defined by

$`F_{xyzx}`$ $`=`$ $`c_{xyzx}1`$
$`=`$ $`(1+A_{xy})(1+A_{yz})(1+A_{zx})1`$
$`=`$ $`(A_{xy}+A_{yz}+A_{zx})+(A_{xy}A_{yz}+A_{yz}A_{zx}+A_{xy}A_{zx})`$
$`F`$ $`=`$ $`dA+{\displaystyle \frac{1}{2}}[A,A]`$
Expanding each member of the equation (3) to the second order, we obtain

$`c_{wxyw}c_{wyzw}c_{wzxw}`$ $`=`$ $`1+F_{wxyw}+F_{wyzw}+F_{wzxw}`$
$`f_{wx}c_{xyzx}f_{xw}`$ $`=`$ $`1+A_{wx}+A_{xw}+F_{xyzx}+A_{wx}F_{xyzx}+F_{xyzx}A_{xw}`$
$`=`$ $`1+F_{xyzx}+[A_{wx},F_{xyzx}]`$
and (3) implies the Bianchi identity

$`F_{xyzx}F_{wxyw}F_{wyzw}F_{wzxw}+[A_{wx},F_{xyzx}]=0`$
usually written in terms of differential forms :

$`\overline{)dF+[A,F]=0}`$ (2)
## 4 Gerbes as representations of a 2-groupoid of surfaces

### 4.1 Combinatorial gerbes

We know from algebraic topology that the second homotopy group of any space $`X`$ is always abelian. A better object to study is in fact the space of parametrized surfaces. This is a 2-groupoid and it is the basic object in our construction of combinatorial gerbes. So let’s define the 2-groupoid $`\mathrm{\Pi }_2(X)`$ as follows. The objects and arrows of $`\mathrm{\Pi }_2(X)`$ are the same as in $`\mathrm{\Pi }_1(X)`$ but $`\mathrm{\Pi }_2(X)`$ also has 2-arrows generated by the elementary homotopies along the oriented 2-cells of $`X`$. More precisely, two paths with the same boundary points, say $`\gamma =(x_0,x_1,\mathrm{},x_n)`$ and $`\gamma ^{}=(x_0,x_1,\mathrm{},x_p,y,x_{p+1},\mathrm{},x_n)`$, form an elementary 2-arrow of $`\mathrm{\Pi }_2(X)`$ if they differ only by the insertion of a vertex $`y`$ which is a common neighbour to $`x_p`$ and $`x_{p+1}`$. If the vertex inserted is already present, i.e. if $`y=x_p`$ or $`y=x_{p+1}`$, then the path does not change and this 2-arrow is considered as equal to the identity 2-arrow of this path. These prescriptions define the generating 2-arrows of $`\mathrm{\Pi }_2(X)`$. All 2-arrows of $`\mathrm{\Pi }_2(X)`$ are then obtained by glueing these generators, either horizontally ($`\times `$) or vertically ($``$). Thus, a 2-arrow from $`\gamma _0`$ to $`\gamma _n`$ is a family of paths $`(\gamma _0,\mathrm{},\gamma _n)`$ such that, for all $`i\{0,\mathrm{},n1\}`$, $`(\gamma _i,\gamma _{i+1})`$ be an elementary 2-arrow of $`\mathrm{\Pi }_2(X)`$. As with paths, we don’t identify a priori the 2-arrows with different speeds or with backtrackings. If $`\gamma `$ is a neighbour of $`\gamma _i`$, then

$`(\mathrm{},\gamma _{i1},\gamma _i,\gamma _i,\gamma _{i+1},\mathrm{})`$ $``$ $`(\mathrm{},\gamma _{i1},\gamma _i,\gamma _{i+1},\mathrm{})`$
$`(\mathrm{},\gamma _{i1},\gamma _i,\gamma ,\gamma _i,\gamma _{i+1},\mathrm{})`$ $``$ $`(\mathrm{},\gamma _{i1},\gamma _i,\gamma _{i+1},\mathrm{})`$
The generating 2-arrows of $`\mathrm{\Pi }_2(X)`$ will be written with brackets :

$`[xzy]=(xy,xzy)`$ $`=`$ $`\mathrm{insertion}\mathrm{of}z\mathrm{between}x\mathrm{and}y`$
$`[xzy]^{}=(xzy,xy)`$ $`=`$ $`\mathrm{deletion}\mathrm{of}z\mathrm{between}x\mathrm{and}y`$
$`[xzyx]=(xx,xzyx)`$ $`=`$ $`\mathrm{insertion}\mathrm{of}(zy)\mathrm{between}x\mathrm{and}x`$
$`[xzyx]^{}=(xzyx,xx)`$ $`=`$ $`\mathrm{deletion}\mathrm{of}(zy)\mathrm{between}x\mathrm{and}x`$
We now have the tools to define the combinatorial $`G`$-gerbes with connection as the contravariant 2-functors (prestacks in groupoids)

$$\varphi :\mathrm{\Pi }_2(X)^{\mathrm{op}}𝒯_L()$$

which represent the groupoid of surfaces, $`\mathrm{\Pi }_2(X)`$, in the 2-groupoid of $``$-torsors, $`𝒯_L()`$. The choice of $`𝒯_L()`$ as a target 2-category is a natural one, because its 2-arrows are mapped to elements of $`G`$, once we have chosen an equivalence between its objects and the gauge gr-category $``$. This compact definition hides much combinatorial geometry. For example, we will explore in the following section the cocycle relations satisfied by the curvature of $`\varphi `$. Since the fibers are categories $`\varphi _x,\varphi _y,\mathrm{}`$ and the edges are mapped to the 1-connection functors $`\varphi _{xy}:\varphi _y\varphi _x`$, we can define its (functor valued) curvature 2-form $`C=_{[xyzx]}[xyzx]C_{xyzx}`$ by

$$C_{xyzx}=\varphi _{xy}\varphi _{yz}\varphi _{zx}$$

It is important not to confuse $`C_{xyzx}`$, which is given by the usual composition of functors, and the horizontal compostion $`\varphi _{xyzx}=\varphi _{xy}\times \varphi _{yz}\times \varphi _{zx}`$ which is their concatenation, i.e. a fibered category with 1-connection over the path $`(xyzx)`$. The functor $`C_{xyzx}`$, associated to the 2-cell $`[xyzx]`$, is an equivalence of the $``$-torsor $`\varphi _x`$, therefore it is naturally equivalent to the functorial action of some bitorsor $`\beta _{xyzx}\mathrm{Ob}()`$ satisfying

$`\beta _{xyzx}\beta _{xzyx}`$ $`=`$ $`1_{}`$
$`\varphi _{xy}\beta _{yzxy}`$ $`=`$ $`\beta _{xyzx}\varphi _{xy}`$
We will keep the same notation for this bitorsor, its functorial action on $`\varphi _x`$, and the corresponding element of $`\mathrm{Aut}(G)`$. But $`\varphi `$ provides us with natural equivalences which represent in $`𝒯_L()`$ the corresponding elementary homotopies. More precisely, the 2-arrows

$`\varphi _{[xzy]}`$ $`:`$ $`\varphi _{xz}\times \varphi _{zy}\varphi _{xy}`$
$`\varphi _{[xzy]^{}}`$ $`:`$ $`\varphi _{xy}\varphi _{xz}\times \varphi _{zy}`$
$`\varphi _{[xyzx]}`$ $`:`$ $`\varphi _{xy}\times \varphi _{yz}\times \varphi _{zx}\varphi _{xx}`$
$`\varphi _{[xyzx]^{}}`$ $`:`$ $`\varphi _{xx}\varphi _{xy}\times \varphi _{yz}\times \varphi _{zx}`$
induce natural transformations between the compositions of 1-connection functors

$`K_{[xzy]}`$ $`:`$ $`\varphi _{xz}\varphi _{zy}\beta _{yzxy}\varphi _{xy}`$
$`K_{[xzy]^{}}`$ $`:`$ $`\varphi _{xy}\varphi _{xz}\varphi _{zy}\beta _{yzxy}`$
$`K_{[xzyx]}`$ $`:`$ $`C_{xzyx}\beta _{xyzx}1_{\varphi _x}`$
$`K_{[xzyx]^{}}`$ $`:`$ $`1_{\varphi _x}C_{xzyx}\beta _{xyzx}`$
such that, for any $`a\mathrm{Ob}(\varphi _y)`$, we have

$`K_{[\mathrm{}]^{}}`$ $`=`$ $`(K_{[\mathrm{}]})^1`$
$`K_{[xzy]}(a)`$ $`=`$ $`\varphi _{xy}(K_{[yxzy]}(a))`$
$`=`$ $`K_{[xzyx]}(\varphi _{xy}(a))`$
Similarly, $`\varphi `$ induces natural transformations

$`\overline{K}_{[xzy]}`$ $`:`$ $`\beta _{xyzx}\varphi _{xz}\varphi _{zy}\varphi _{xy}`$
$`\overline{K}_{[xzy]^{}}`$ $`:`$ $`\varphi _{xy}\beta _{xyzx}\varphi _{xz}\varphi _{zy}`$
$`\overline{K}_{[xzyx]}`$ $`:`$ $`\beta _{xyzx}C_{xzyx}1_{\varphi _x}`$
$`\overline{K}_{[xzyx]^{}}`$ $`:`$ $`1_{\varphi _x}\beta _{xyzx}C_{xzyx}`$
satisfying identical conditions. (Thus it seems possible to break the chiral symmetry by giving to the variables $`K`$ and $`\overline{K}`$ different dynamics.) For example, $`K_{[xzy]}`$ represents the elementary homotopy from $`(xy)`$ to $`(xzy)`$ as a 2-arrow in the reversed direction ($`\varphi `$ being contravariant) and whose component at $`a`$ is the arrow

$$K_{[xzy]}(a):\varphi _{xz}\varphi _{zy}\beta _{yzxy}(a)\varphi _{xy}(a)$$

The 2-functoriality of $`\varphi `$ implies the naturality of $`K_{[xzy]}`$, i.e. for each arrow $`u:ab`$ in $`\varphi _y`$ we have a commutative diagram

i.e. the relation

$`\overline{)\varphi _{xy}(u)K_{[xzy]}(a)=K_{[xzy]}(b)\varphi _{xz}\varphi _{zy}\beta _{yzxy}(u)}`$ (3)
Analogously, for $`[xzyx]`$ :

$`\overline{)uK_{[xzyx]}(a)=K_{[xzyx]}(b)C_{xzyx}\beta _{xyzx}(u)}`$ (4)
We have to consider the paths with and without backtrackings as different because the degenerate 2-cell $`[xyx]`$ is mapped to a 2-arrow

$$\varphi _{[xyx]}:\varphi _{xy}\times \varphi _{yx}\varphi _{xx}$$

which is a part of the combinatorial data of the 2-functor $`\varphi `$ and amounts to the choice of a quasi-inverse of the 1-connection (see , §(7.4)). Indeed, if we choose $`\beta _{xyyx}=1_{\varphi _x}`$, then $`K_{[xyx]}`$ is precisely the arrow we need to invert $`\varphi _{xy}`$, since

$$K_{[xyx]}:\varphi _{xy}\varphi _{yx}\beta _{xyyx}=\varphi _{xy}\varphi _{yx}1_{\varphi _x}$$

A local gauge fixing is obtained by choosing an object $`\alpha _x`$ in $`\varphi _x`$ for each vertex $`x`$ of an infinitesimal tetrahedron. Then, each object $`a`$ of $`\varphi _x`$ defines (the isomorphy class of) a bitorsor $`b_{xa}`$ by

$$b_{xa}(\alpha _x)a$$

Let $`(𝔤)`$ be the Lie algebra of $`\mathrm{Aut}(G)`$, i.e. the set of derivations of $`𝔤`$. We can define the $`(𝔤)`$-valued 1-form $`\mu =_{(xy)}(xy)\mu _{xy}`$ by

$$b_{y,\varphi _{xy}(\alpha _x)}=1_{\mathrm{Aut}(G)}+\mu _{xy}$$

and the $`𝔤`$-valued 2-form $`B=_{[xyzx]}[xyzx]B_{xyzx}`$ by

$$K_{[xyzx]}=1_G+B_{xyzx}$$

Moreover, the expansion of $`\beta `$ near the identity provides the ”fake curvature” , which is the $`(𝔤)`$-valued 2-form $`\nu =_{[xyzx]}[xyzx]\nu _{xyzx}`$ defined by

$$\beta _{xyzx}=1_{\mathrm{Aut}(G)}+\nu _{xyzx}$$

The naturality condition (3 or 4) induces the following identity in $`\mathrm{Aut}(G)`$ :

$$(\mathrm{Ad}_{1+B_{yxzy}})(1+\mu _{xy})=(1+\mu _{xz})(1+\mu _{zy})(1+\nu _{yzxy})$$

Expanding it to the second order, we obtain an identity in $`(𝔤)`$ :

$`\mu _{xz}+\mu _{zy}+\mu _{yx}+\mu _{xz}\mu _{zy}=\nu _{yxzy}+[B_{yxzy},\mathrm{}]`$
the limit of which is

$`\overline{)\nu =d\mu +\mu ^2[B,\mathrm{}]}`$ (5)
($`[X,\mathrm{}](𝔤)`$ denotes the adjoint action of $`X𝔤`$). This identity can also be taken as the definition of $`\nu `$.

### 4.2 The fibered categories induced by a gerbe over the space of paths

In this section, we are going to define two fibered categories over the space of paths of $`X`$, $`\mathrm{\Phi }`$ and $`\overline{\mathrm{\Phi }}`$, each one equipped with a functorial 1-connection ($`\mathrm{\Phi }`$ and $`\overline{\mathrm{\Phi }}`$ are related by a reversion of arrows). From the 2-groupoid $`\mathrm{\Pi }_2(X)`$, we first define the groupoid $`𝒫(X)`$ whose objects are the 1-arrows of $`\mathrm{\Pi }_2(X)`$ and whose arrows are the 2-arrows of $`\mathrm{\Pi }_2(X)`$. The fiber of $`\mathrm{\Phi }`$ above $`\gamma =(x_0,\mathrm{},x_n)`$, is defined as the category $`\mathrm{\Phi }_\gamma `$ whose objects are the sections of $`\varphi `$ above $`\gamma `$ :

$`\mathrm{Ob}(\mathrm{\Phi }_\gamma )`$ $`=`$ $`\{(a,u)=(a_0,u_{01},a_1,\mathrm{},a_{n1},u_{n1,n},a_n)|`$
$`a_i\mathrm{Ob}(\varphi _{x_i})\mathrm{and}u_{j,j+1}:\varphi _{x_j,x_{j+1}}(a_{j+1})a_j\}`$
and whose arrows are the homotopies between such sections :

$$\mathrm{\Phi }_\gamma ((a,u);(b,v))=\{(\alpha _i:a_ib_i)_{0in}|\alpha _iu_{i,i+1}=v_{i,i+1}\varphi _{x_i,x_{i+1}}(\alpha _{i+1})\}$$

The 1- and 2-connection of $`\varphi `$ combine to induce a functorial connection on $`\mathrm{\Phi }`$. Indeed, if $`(\gamma ,\gamma ^{})`$ is an oriented edge of $`𝒫(X)`$, and if $`\gamma `$ and $`\gamma ^{}`$ differ by the 2-cell $`[xzy]`$, we define $`\mathrm{\Phi }_{\gamma \gamma ^{}}:\mathrm{\Phi }_\gamma ^{}\mathrm{\Phi }_\gamma `$ by the following action on the objects of $`\mathrm{\Phi }_\gamma ^{}`$ :

$`\mathrm{\Phi }_{\gamma \gamma ^{}}(\mathrm{},a_x,u_{xz},a_z,u_{zy},a_y,\mathrm{})`$
$`=(\mathrm{},a_x,u_{xz}\varphi _{xz}(u_{zy})K_{[xzy]^{}}(a_y),\beta _{yxzy}(a_y),\beta _{yxzy}(\mathrm{}))`$
where the dots on the left of $`a_x`$ denote the unchanged entries and all the entries on the right of $`a_y`$ are twisted by $`\beta _{yzxy}`$ acting on the corresponding fiber. The functor $`\mathrm{\Phi }_{\gamma ^{}\gamma }:\mathrm{\Phi }_\gamma \mathrm{\Phi }_\gamma ^{}`$ acts as follows :

$`\mathrm{\Phi }_{\gamma ^{}\gamma }(\mathrm{},b_x,v_{xy},b_y,\mathrm{})`$
$`=(\mathrm{},b_x,v_{xy}K_{[xzy]}(C_{yxzy}\beta _{yzxy}(b_y)),\varphi _{zy}\beta _{yzxy}(b_y),\varphi _{zy}\beta _{yzxy}(1_{b_y}),\beta _{yzxy}(b_y),\beta _{yzxy}(\mathrm{}))`$
The initial entries $`v_{xy}`$ and $`b_y`$ are deleted and the entries on the right of $`b_y`$ are twisted by $`\beta _{yxzy}`$ acting on the corresponding fiber. One can check easily that $`\mathrm{\Phi }_{\gamma ^{}\gamma }`$ and $`\mathrm{\Phi }_{\gamma \gamma ^{}}`$ are quasi-inverses one of another. In the definition of the 3-curvature of $`\varphi `$, given below, we will also need the expression of the connection functor $`\mathrm{\Phi }_{(xx,xyzx)}`$ which maps the category of sections of $`\varphi _{xyzx}`$ into that of sections of $`\varphi _{xx}`$. The image of $`(a_{0x},u_{xy},a_y,u_{yz},a_z,u_{zx},a_{1x})\mathrm{Ob}(\mathrm{\Phi }_{xyzx})`$ via $`\mathrm{\Phi }_{(xx,xyzx)}`$ is

$`\mathrm{\Phi }_{(xx,xyzx)}(a_{0x},u_{xy},a_y,u_{yz},a_z,u_{zx},a_{1x})`$
$`=(a_{0x},u_{xy}\varphi _{xy}(u_{yz})\varphi _{xy}\varphi _{yz}(u_{zx})K_{[xyzx]^{}}(a_{1x}),\beta _{xyzx}(a_{1x}))`$
Conversely, $`\mathrm{\Phi }_{(xyzx,xx)}`$ maps $`(b_{0x},v_{xx},b_{1x})`$ to

$`\mathrm{\Phi }_{(xyzx,xx)}(b_{0x},v_{xx},b_{1x})=`$
$`(b_{0x},v_{xx}K_{[xyzx]}(b_{1x}),\varphi _{yz}\varphi _{zx}\beta _{xzyx}(b_{1x}),\varphi _{yz}\varphi _{zx}\beta _{xzyx}(1_{b_{1x}}),`$
$`\varphi _{zx}\beta _{xzyx}(b_{1x}),\varphi _{zx}\beta _{xzyx}(1_{b_{1x}}),\beta _{xzyx}(b_{1x}))`$
When we move the path $`\gamma =(x_0,\mathrm{},x_n)`$ at an end point, to the neighbour path $`\gamma ^{}=(x_0,\mathrm{},x_{n1},y)`$, $`y`$ being a neighbour of $`x_n`$ and of $`x_{n1}`$, the sweeping functor $`\mathrm{\Phi }_{\gamma ^{}\gamma }`$ acts on $`(\mathrm{},a_{n1},u_{n1},a_n)`$ as follows :

$$\mathrm{\Phi }_{\gamma ^{}\gamma }(\mathrm{},a_{n1},u_{n1},a_n)=(\mathrm{},a_{n1},u_{n1}K_{[x_{n1}yx_n]^{}}(a_n),\varphi _{yx_n}\beta _{x_nyx_{n1}x_n}(a_n))$$

The objects of $`\overline{\mathrm{\Phi }}`$ are defined like those of $`\mathrm{\Phi }`$ but with reversed arrows :

$`\mathrm{Ob}(\overline{\mathrm{\Phi }})`$ $`=`$ $`\{(a,u)=(a_0,u_{01},a_1,\mathrm{},a_{n1},u_{n1,n},a_n)|`$
$`a_i\mathrm{Ob}(\varphi _{x_i})\mathrm{and}u_{j,j+1}:a_j\varphi _{x_jx_{j+1}}(a_{j+1})\}`$
The elements of $`\overline{\mathrm{\Phi }}((a,u);(b,v))`$ are defined as homotopies between the objects $`(a,u)`$ and $`(b,v)`$ and the connection $`\overline{\mathrm{\Phi }}_{\gamma \gamma ^{}}`$ is defined by formulas similar to those for $`\mathrm{\Phi }`$ but using $`\overline{K}:\beta C1`$ and $`\overline{K}^1:1\beta C`$ instead of $`K`$ and $`K^1`$.

We define the 3-curvature of $`\varphi `$ as the 3-form $`\mathrm{\Omega }`$ which, to each oriented 3-cell $`\sigma =vwxyv`$ such that $`v=s_0(\sigma )=t_0(\sigma )`$ and $`(vv)=s_1(\sigma )=t_1(\sigma )`$, associates the 2-arrow $`\mathrm{\Omega }_\sigma :\varphi _{vv}\varphi _{vv}`$ obtained by composition of the sweeping functors associated to the four oriented faces of this 3-cell. Let’s now compute $`\mathrm{\Omega }_\sigma `$ when the boundary of $`\sigma `$ is represented by the following pasting scheme, swept from top to bottom :

Let $`(b\stackrel{𝛼}{}a)\mathrm{Ob}(\mathrm{\Phi }_{vv^{}})`$ and let’s twist $`a`$ by the 1-arrows $`C\beta `$ associated to the boundaries of the 2-cells swept successively. This defines a sequence of objects $`a_i\mathrm{Ob}(\varphi _v)`$

$`a_1`$ $`=`$ $`C_{vwyv}\beta _{vywv}(a)`$
$`a_2`$ $`=`$ $`\varphi _{vy}C_{ywxy}\beta _{yxwy}\varphi _{yv}(a_1)`$
$`a_3`$ $`=`$ $`C_{vxyv}\beta _{vyxv}(a_2)`$
$`a_4`$ $`=`$ $`C_{vwxv}\beta _{vxwv}(a_3)`$
The $`K`$ arrows corresponding to these 2-cells are

$`K_{[vwyv]^{}}(a):a`$ $``$ $`a_1`$
$`\varphi _{vy}\left(K_{[ywxy]^{}}(\varphi _{yv}(a_1))\right):a_1`$ $``$ $`a_2`$
$`K_{[vxyv]}(a_2):a_2`$ $``$ $`a_3`$
$`K_{[vwxv]}(a_3):a_3`$ $``$ $`a_4`$
The composition of these four arrows defines the 3-curvature arrow $`\mathrm{\Omega }_\sigma (a)`$ :

$`\overline{)\mathrm{\Omega }_\sigma (a)=K_{[vwxv]}(a_3)K_{[vxyv]}(a_2)\varphi _{vy}\left(K_{[ywxy]^{}}(\varphi _{yv}(a_1))\right)K_{[vwyv]^{}}(a)}`$ (6)
Choosing a local section of $`\varphi `$, we can expand the 1-connection as $`\varphi _{xy}=1_{\mathrm{Aut}}(G)+\mu _{xy}`$ and the 2-connection as $`K=1_G+B`$. Since $`(1_{}C)`$ is an infinitesimal of second order, the expansion of $`\mathrm{\Omega }_\sigma (a)=1_G+\omega _{vwxyv}`$ to the third order gives

$$1+\omega _{vwxyv}=[1+B_{vwxv}][1+B_{vxyv}]\left[(1+\mu _{vy})(1B_{ywxy})\right][1B_{vwyv}]$$

where the dot denotes the action of $`(𝔤)`$ on $`𝔤`$. Using the antisymmetry of $`\omega `$ and $`B`$, we deduce

$$\omega _{vywxv}=B_{ywxy}B_{vywv}B_{vyxv}B_{vxwv}+\mu _{vy}B_{ywxy}$$

and the expression of the curvature 3-form $`\omega =_{wxyzw}wxyzw\omega _{wxyzw}`$ in terms of differential forms becomes

$`\overline{)\omega =dB+\mu B}`$ (7)
### 4.3 Cocycle identities

In the proof of the Bianchi identity, we have used a homotopy in the 1-skeleton of an infinitesimal tetrahedron. By analogy, in order to obtain the 3-cocycle identities satisfied by $`\varphi `$, we can use a homotopy in the 2-skeleton of an oriented 4-simplex of $`X`$. So let $`v,w,x,y`$ and $`z`$ be five pairwise neighbour vertices of $`X`$. Let’s choose $`v`$ as base point, let’s double it into $`v`$ and $`v^{}`$ and let’s sweep the boundary of the four tetrahedra containing $`v`$, according to the following pasting schemes, from top to bottom :

First face ($`F_1`$) :

$$F_1=\varphi _{[vwxv]}(1_{\varphi _{vwx}}\times \varphi _{[xyv]})(1_{\varphi _{vw}}\times \varphi _{[wxy]^{}}\times 1_{\varphi _{yv}})\varphi _{[vwyv]^{}}$$

Second face ($`F_2`$) :

$$F_2=\varphi _{[vwyv]^{}}(1_{\varphi _{vw}}\times \varphi _{[wzy]}\times 1_{\varphi _{yv}})(\varphi _{[vwz]^{}}\times 1_{\varphi _{[zyv]}})\varphi _{[vzyv]^{}}$$

Third face ($`F_3`$) :

$$F_3=\varphi _{[vzyv]}(1_{\varphi _{vz}}\times \varphi _{[zxy]}\times 1_{\varphi _{yv}})(1_{\varphi _{vzx}}\times \varphi _{[xyv]^{}})\varphi _{[vzxv]^{}}$$

Fourth face ($`F_4`$) :

$$F_4=\varphi _{[vzxv]}(\varphi _{[vwz]}\times 1_{\varphi _{zxv}})(1_{\varphi _{vw}}\times \varphi _{[wzx]^{}}\times 1_{\varphi _{xv}})\varphi _{[vwxv]^{}}$$

The composition of these four 2-arrows, which are loops in loop space, amounts to sweeping the boundary of the tetrahedron opposite to $`v`$ (fifth face, $`F_5`$) :

$`F_5`$ $`=`$ $`\varphi _{[vwxv]}(1_{\varphi _{vwx}}\times \varphi _{[xyv]})(1_{\varphi _{vw}}\times \varphi _{[wxy]^{}}\times 1_{\varphi _{yv}})(1_{\varphi _{vw}}\times \varphi _{[wzy]}\times 1_{\varphi _{yv}})`$
$`(\varphi _{[vwz]^{}}\times 1_{\varphi _{zyv}})(\varphi _{[vwz]}\times \varphi _{[zxy]}\times 1_{\varphi _{yv}})(1_{\varphi _{vw}}\times \varphi _{[wzx]^{}}\times \varphi _{[xyv]^{}})\varphi _{[vwxv]^{}}`$
The functors defined by these five pasting schemes map $`\mathrm{\Phi }_{vv^{}}`$ to itself. If we choose a section of $`\varphi `$ above this 4-simplex, i.e. an object of reference in each fiber, these functors are reduced to the action of an element of $`G`$ on the arrows of $`\varphi _v`$ and the identity of these 2-arrows becomes an equality in $`G`$. By expanding the product $`F_1F_2F_3F_4`$ of the first four faces to the fourth order, and equating it to $`F_5`$, we obtain a combinatorial representation of the cocycle identity satisfied by $`\omega `$, which is easier to prove directly with differential forms :

$`d\omega +\mu \omega `$ $`=`$ $`d(dB+\mu B)+\mu (dB+\mu B)`$
$`=`$ $`d\mu B\mu dB+\mu dB+\mu ^2B`$
$`=`$ $`(d\mu +\mu ^2)B`$
Since $`B`$ a $`𝔤`$-valued 2-form, we have $`[B,B]=0`$ and we obtain :

$`\overline{)d\omega +\mu \omega =\nu B}`$ (8)
### 4.4 Gauge transformations

As in the case of bundles, we need to know when two gerbes define the same gauge invariant quantities and what the automorphisms of a given gerbe are. Our functorial approach suggests to define the gauge transformations on $`\varphi `$ as its equivalences of 2-functor. Two gerbes $`\varphi `$ and $`\varphi ^{}`$ are declared isomorphic iff. there exists an invertible natural equivalence of 2-functors, $`H:\varphi ^{}\varphi `$, i.e. for each vertex $`x`$ a 1-arrow of $`𝒯_L()`$, $`H_x:\varphi _{}^{}{}_{x}{}^{}\varphi _x`$, and, for each edge $`xy`$, a 2-arrow $`H_{xy}:H_x\varphi _{}^{}{}_{xy}{}^{}\varphi _{xy}H_y`$, such that the following composition of 2-arrows be invertible

When $`\varphi =\varphi ^{}`$, the gauge transformation $`H`$ induces an equivalence of $`\mathrm{\Phi }`$ : if, for each path $`\gamma \mathrm{Ob}(𝒫(X))`$, $`H_\gamma :\mathrm{\Phi }_\gamma \mathrm{\Phi }_\gamma `$ denotes the action of $`H`$ on the category of sections of $`\varphi _\gamma `$, then $`H`$ is an equivalence of $`\mathrm{\Phi }`$ since for each edge $`(\gamma ,\gamma ^{})`$ of $`𝒫(X)`$, there exists an invertible natural transformation from $`H_\gamma ^{}\mathrm{\Phi }_{\gamma ^{}\gamma }`$ to $`\mathrm{\Phi }_{\gamma ^{}\gamma }H_\gamma `$ represented by the following diagram

In order to obtain the local expression of the gauge transformed 2-connection, let’s pick $`(b\stackrel{𝛼}{}a)\mathrm{Ob}(\mathrm{\Phi }_{(xx)})`$ and let’s compare the action of $`\mathrm{\Phi }_{(xyzx,xx)}H_{(xx)}`$

$`\mathrm{\Phi }_{(xyzx,xx)}H_{(xx)}(b\stackrel{𝛼}{}a)`$ $`=`$ $`(H_x(b),H_x(\alpha )K_{[xyzx]}(H_x(a)),`$
$`\varphi _{yz}\varphi _{zx}\beta _{xzyx}H_x(a),\varphi _{yz}\varphi _{zx}\beta _{xzyx}H_x(1_a),`$
$`\varphi _{zx}\beta _{xzyx}H_x(a),\varphi _{zx}\beta _{xzyx}H_x(1_a),\beta _{xzyx}H_x(a))`$
with the action of $`H_{(xyzx)}\mathrm{\Phi }_{(xyzx,xx)}`$ on the same initial section :

$`H_{(xyzx)}\mathrm{\Phi }_{(xyzx,xx)}(b\stackrel{𝛼}{}a)`$ $`=`$ $`(H_x^1(b),H_x^1(\alpha )H_x^1(K_{[xyzx]}(a))H_{xy}^1(\varphi _{yz}\varphi _{zx}\beta _{xzyx}(a)),`$
$`H_y^1\varphi _{yz}\varphi _{zx}\beta _{xzyx}(a),H_{yz}^1(\varphi _{zx}\beta _{xzyx}(a)),`$
$`H_z^1\varphi _{zx}\beta _{xzyx}(a),H_{zx}^1(\beta _{xzyx}(a)),H_x^1\beta _{xzyx}(a))`$
Equating the compositions of these arrows, we obtain :

$`K_{[xyzx]}(H_x(a))`$ $`=`$ $`H_x^1(K_{[xyzx]}(a))H_{xy}^1(\varphi _{yz}\varphi _{zx}\beta _{xzyx}(a))`$
$`\varphi _{xy}H_{yz}^1(\varphi _{zx}\beta _{xzyx}(a))\varphi _{xy}\varphi _{yz}H_{zx}^1(\beta _{xzyx}(a))`$
In a local chart, we have

$`K_{[xyzx]}(a)`$ $`=`$ $`1_G+B_{xyzx}`$
$`K_{[xyzx]}(H_x(a))`$ $`=`$ $`1_G+B_{}^{}{}_{xyzx}{}^{}`$
$`\varphi _{xy}`$ $`=`$ $`1_{\mathrm{Aut}(G)}+\mu _{xy}`$
$`\varphi _{}^{}{}_{xy}{}^{}`$ $`=`$ $`1_{\mathrm{Aut}(G)}+\mu _{}^{}{}_{xy}{}^{}`$
$`H_x`$ $`=`$ $`1_{\mathrm{Aut}(G)}+\xi _x`$
$`H_{xy}`$ $`=`$ $`1_G+\eta _{xy}`$
where $`\xi _x(𝔤)`$ and $`\eta _{xy}𝔤`$. The expansion of the previous identity up to first order in $`(\xi ,\eta )`$ provides us with the expression of the infinitesimal gauge transformations :

$`1+B_{}^{}{}_{xyzx}{}^{}`$ $`=`$ $`\left[(1\xi _x)(1+B_{xyzx})\right]\left[1\eta _{xy}\right]`$
$`\left[(1+\mu _{xy})(1\eta _{yz})\right]\left[(1+\mu _{xy})(1+\mu _{yz})(1\eta _{zx})\right]`$
$`B_{}^{}{}_{xyzx}{}^{}`$ $`=`$ $`B_{xyzx}\xi _xB_{xyzx}(\eta _{xy}+\eta _{yz}+\eta _{zx}+\mu _{xy}\eta _{yz}\mu _{xy}\eta _{zx}\mu _{yz}\eta _{zx})`$
Using the differential forms $`\xi =_xx\xi _x`$ and $`\eta =_{(xy)}(xy)\eta _{xy}`$ :

$`\overline{)B^{}=B\xi B(d\eta +\mu \eta )}`$ (9)
The infinitesimal effect of $`H`$ on the 1-connection is obtained by expanding up to first order in $`(\xi ,\eta )`$ the equivalence between functors :

$`\varphi _{}^{}{}_{xy}{}^{}`$ $``$ $`H_x^1\varphi _{xy}H_y`$
$`1+\mu _{}^{}{}_{xy}{}^{}`$ $`=`$ $`(1\xi _x)(1+\mu _{xy})(1+\xi _y)`$
$`\mu _{}^{}{}_{xy}{}^{}`$ $`=`$ $`\mu _{xy}+\xi _y\xi _x+\mu _{xy}\xi _y\xi _x\mu _{xy}`$
In terms of differential forms :

$`\overline{)\mu ^{}=\mu +d\xi +[\mu ,\xi ]}`$ (10)
Introducing the notation $`=d+\mu `$, we have

$`^2`$ $`=`$ $`d\mu +\mu ^2`$
$`\xi `$ $`=`$ $`d\xi +[\mu ,\xi ]`$
$`B`$ $`=`$ $`dB+\mu B=\omega `$
$`\eta `$ $`=`$ $`d\eta +\mu \eta `$
and similarly with $`^{}`$ and $`\mu ^{}`$. The action of $`H`$ on the 2-curvature $`\nu `$ is given by

$`\nu ^{}`$ $`=`$ $`d\mu ^{}+(\mu ^{})^2+[B^{},\mathrm{}]`$
$`=`$ $`d(\mu +\xi )+(\mu +\xi )^2+[B\xi B\eta ,\mathrm{}]`$
$`=`$ $`\left(d\mu +\mu ^2+[B,\mathrm{}]\right)+d\xi +\mu \xi +(\xi )\mu [\xi B+\eta ,\mathrm{}]`$
$`\overline{)\nu ^{}=\nu +^2\xi [\xi B+\eta ,\mathrm{}]}`$ (11)
Similarly, the first order gauge variation of the curvature 3-form $`\omega `$ is given by

$`\omega ^{}`$ $`=`$ $`dB^{}+\mu ^{}B^{}`$
$`=`$ $`dBd(\xi B)d(\eta )+(\mu +\xi )(B\xi B\eta )`$
$`=`$ $`\omega (\xi B)+(\xi )B^2\eta `$
$`\overline{)\omega ^{}=\omega \xi \omega ^2\eta }`$ (12)
## 5 Perspectives

In the long search of a string model of the confined phase of Yang-Mills theory , A. Polyakov emphasized a crucial difference between the metric strings, which are coupled to the background metric $`G_{\mu \nu }`$ and include gravitons in their spectrum, and the gauge strings, which don’t. The gauge symmetry of the theory formulated in terms of connection and curvature is adapted to the short distance physics. In the string picture, the gauge symmetry translates into the zizgzag symmetry : if a thin homotopy relates two surfaces with the same fixed boundary, then their actions are equal. This symmetry is precisely what is needed to project the zero mass spectrum of the string on the space generated by the vector vertex operators, thus eliminating the graviton. In our setting, the zigzag symmetry acts in the fibered category $`\mathrm{\Phi }`$. An elementary backtracking is a pair of paths, say $`\gamma =(\mathrm{},x,y,\mathrm{})`$ and $`\gamma ^{}=(\mathrm{},x,z,x,y,\mathrm{})`$, and the corresponding functor $`\mathrm{\Phi }_{\gamma \gamma ^{}}`$ acts as

$`\mathrm{\Phi }_{\gamma ^{}\gamma }(\mathrm{},a_x,u_{xz},a_z,u_{zx},a_{}^{}{}_{x}{}^{},\mathrm{})`$
$`=(\mathrm{},a_x,u_{xz}\varphi _{xz}(u_{zx})K_{[xzzx]^{}}(a_{}^{}{}_{x}{}^{}),\beta _{xzzx}(a_{}^{}{}_{x}{}^{}),\beta _{xzzx}(\mathrm{}))`$
Therefore, the requirement of the zigzag symmetry is equivalent to

$$K_{[xzzx]}=K_{[xzzx]^{}}=\overline{K}_{[xzzx]}=\overline{K}_{[xzzx]^{}}=1_{1_{\varphi _x}}1_G$$

As noted in (§4.1), this condition, which bears on $`\beta `$ and $`C`$, amounts to specifying a quasi-inverse of the connective structure : $`\varphi _{xy}^1=\varphi _{yx}`$. The action of the pure $`BF`$-theory is defined on a four-manifold $`M`$ by

$$S(\mu ,B)=_M\mathrm{tr}_{\mathrm{ad}}(\nu [B,\mathrm{}])$$

We deduce from the relations (9-12) its gauge variation :

$`S(\mu ^{},B^{})S(\mu ,B)`$ $`=`$ $`{\displaystyle _M}\mathrm{tr}_{\mathrm{ad}}\left((\xi \omega )+\nu \eta \right)`$
$`=`$ $`{\displaystyle _M}\mathrm{tr}_{\mathrm{ad}}\left(\xi \omega +{\displaystyle \frac{1}{2}}\mu \eta \right)`$
The identity (8) is a higher dimensional analogue of the Bianchi identity (2), and shows clearly the origin of the topological invariance of $`S`$.

Remarks :

$`i`$) Since our approach does not suppose the existence of a globally defined 2-form $`B`$, all integral formulas depend on the choice of a $`\stackrel{ˇ}{\mathrm{C}}`$ech 1-cocycle taking its values in $`\mathrm{Aut}(G)`$ and adapted to an open hypercover of $`M`$.

$`ii`$) The section $`(a,u)\mathrm{Ob}(\mathrm{\Phi }_\gamma )`$, transported by the successive sweeping functors $`\mathrm{\Phi }_{\gamma \gamma ^{}}`$, provides a $`G`$-bundle with connection over the moving path and plays the same role as a fermion transported by a gauge field in Yang-Mills theory.

As suggested in (§4.4), the geometry of gerbes is already adapted to the kinematics of topological field theories of type $`BF`$. Indeed, if we compare the gauge transformations given in (§4.3) with those of the pure $`BF`$-theory , we remark that we can make the following correspondence :

$`\mathrm{gerbes}`$ $``$ $`BF\mathrm{theory}`$
$`\mu `$ $``$ $`[A,\mathrm{}]`$
$`\nu `$ $``$ $`[F_A,\mathrm{}][B,\mathrm{}]`$
This leads us to believe that the right framework for $`BF`$-type field theories is the space of gerbes and not the narrower theory of (principal or associated) bundles.

Conclusion : We have developped a simplicial approach to non-Abelian gerbes and proved, using a 2-groupoid combinatorics, that it leads to the same cohomology classes as the differential approach. The specificity of our viewpoint resides in the usage of the space of iterated edge-paths and of homotopy $`n`$-groupoids. The importance of the space of paths is suggested by gauge field theories where physical quantities are naturally associated to loops. Conversely, the developement of the theory of gerbes may open the door to the resolution of long standing problems of physics like the mathematical proof of confinement of quarks in QCD or the construction of integrable models in dimension higher than two . We hope to develop these ideas in a near future.

Acknowledgements : I wish to thank Lawrence Breen for useful discussions at the beginning of this work, Daniel Bennequin and Olivier Babelon for their encouragements, and Marc Bellon for a careful reading of the manuscript.