1. Introduction
A graph or a network [1, 2] is a simple language to describe the structure of interacted systems, which consists of vertices as their constituents and edges as interaction among constituents. A typical combinatorial optimization problem defined on a graph [3] focuses on finding a set of vertices or edges with a minimal or maximal cardinality, in which certain constraints on the set are satisfied. From the perspective of theoretical computer science, many combinatorial optimization problems are computationally hard [4, 5], whose optimal solutions are buried in an exceedingly large solution space and it takes an unreasonable time (for example, to the order of an exponential function of a problem size) to find them in the worst case. For these hard optimization problems, both developing fast algorithms for their solution configurations on problem instances and constructing an analytical theory for their ground-state properties prove to be difficult tasks. A combinatorial optimization problem can be easily mapped to a statistical mechanics problem on a graph with discrete vertex states. Statistical physics-based methods, especially the spin-glass theory, provide analytical and algorithmic tools, such as the replica trick and the cavity method [6-9]. These approaches clarify the relation between the computational behavior of algorithms and the structural properties of solution space of underlying problems, and also develop fast message-passing algorithms on given graph instances.
An undirected graph $G = \{V, E\}$ has a vertex set $V$ with $|V| = N$ and an edge set $E$ with $|E| = M$. For any vertex $i \in V$, its degree $k_i$ is the size of the set of its nearest neighbors $\partial i$. The mean degree of $G$ is $c \equiv 2M /N$. The degree distribution $P(k)$ is defined as the probability of a randomly chosen vertex having a degree $k \unicode{x2A7E} 0$. Another degree distribution important in analytical theories in the context of graphs is the excess degree distribution $Q(k)$. Following a randomly chosen edge $(i, j)$ between vertices $i$ and $j$, from $i$ to $j$, $Q(k)$ is defined as the probability that $j$ has a degree $k$. By definition, we have $Q(k) = k P(k) / c$. As a classical model for random graphs, the Erdös-Rényi (ER) random graphs [10, 11] with a mean degree $c$ show a Poissonian degree distribution as
$equation$
with $k \unicode{x2A7E} 0$.A vertex cover on a graph $G = \{V, E\}$ is a set of vertices as $S$, such that each edge in the graph, say $(i, j) \in E$ between vertices $i$ and $j$, has at least one end-node in the set, say $i \in S$, or $j \in S$, or both $i, j \in S$. A binary state for a vertex $i \in V$ can be defined as $s_i \in \{1, 0\}$, in which $s_i = 1$ denotes $i$ as being covered (in a vertex cover) and $s_i = 0$ as being uncovered (not in a vertex cover). A microscopic configuration of vertex cover is $\vec{s} = \{s_i\}$ for all $i \in V$. The constraint for $\vec{s}$ as a proper vertex cover can be stated as: for any edge $(i, j) \in E$, we have $(s_i, s_j) = (1, 0)$, or $(0, 1)$, or $(1, 1)$. The energy density or the fraction $x$ of a proper vertex cover configuration $\vec{s}$ is
$align$
The minimal vertex cover (MVC) problem is to find vertex covers $S$ with the smallest cardinality, equivalently, those configurations with the lowest $x$.The MVC problem can be further formulated as a statistical mechanics problem. We first introduce $\beta$ as the inverse temperature. The partition function of the MVC problem on $G = \{V, E\}$ is
$align$
In the above equation, the first product is the Boltzmann factor of a covering configuration $\vec{s}$, and the second product selects these vertex cover configurations which satisfy the topological constraint. $Z(\beta)$ simply sums all the proper vertex configurations and reweighs them with Boltzmann factors. In the zero-temperature limit ($\beta \to + \infty$), only those $\vec{s}$ with the lowest energy contribute to the partition function.In the mathematical literature, an upper bound of the minimal energy density $x_0$ on a general graph $G = \{V, E\}$ based on vertex degrees is established in [14] as
$align}x_0 \unicode{x2A7D} 1 - \frac {1}{|V|} \frac {\left( \sum _{i \in V} \frac {1}{k_i + 1} \right)^2$
On ER random graphs, upper and lower bounds for $x_0$ are derived in [15] as $x_l \lt x_0 \lt 1 - \ln c/c$, while $x_l$ is the root of $align$
In [16], an asymptotic behavior of $x_0$ on ER random graphs with large $c$ is derived as $align$
As a typical method inspired by statistical physics, the spin glass theory is also adopted for the MVC problem. In [17, 18], the replica trick is adopted and its energy density on ER random graphs under the assumption of replica symmetry (RS) is analytically calculated as
$align$
while the Lambert-W-function $W(c)$ is defined as $W(c) \exp W(c) = c$. This prediction of $x_0$ is exact when $c \unicode{x2A7D} {\mathrm{e}} = 2.71828 \cdots$, yet it underestimates true ground-state energy density when $c \gt {\mathrm{e}}$. When a RS solution fails, the picture of RS breaking (RSB) can be introduced for a more refined illustration of hierarchical structure of solution space. In [19], the survey propagation algorithm is developed to characterize the properties of ground-state solutions at the first-step RSB level. Yet whether the first-step RSB solution is enough or more steps of RSB are needed for the MVC problem on general random graphs is still an open question [20, 21].In this paper, we focus on analytical frameworks for the MVC problem, which explicitly connect its ground-state properties with the structural parameters of underlying graphs. These frameworks provide an explainable description to its ground-state properties, and act as a complimentary approach to those methods with a more algorithmic origin. Yet constructing such frameworks is generally much more difficult than developing algorithms. A frequently adopted approach is to explore the geometrical properties of solution configurations of optimization problems. Below we briefly introduce two analytical frameworks: the first one can be considered as a baseline method for the analytical prediction of energy density of the MVC problem, and the second one is the framework we will correct and extend in this paper.
The first framework is based on the greedy leaf removal (GLR) procedure. On an undirected graph, any vertex with a degree one is a leaf, and its only nearest neighbor is correspondingly a root. The GLR procedure is the iterative removal of any root with all its adjacent edges, and leaves the residual subgraph as a core. This procedure is originally adopted as a local algorithm to reduce problem size for the maximum matching (MM) problem [22, 23], which finds matchings (a set of edges without shared vertices) with the maximal cardinality. It is easy to verify that the roots constitute a part of a solution of MVC, and those edges connecting roots and their leaves belong to a part of a solution of MM. The analytical theory of cores is developed on ER random graphs [24] and further on general random graphs [25]. With the analytical theory of both core and roots from the GLR procedure, the energy densities of the MVC and MM problems on general random graphs are further estimated [26]. As it is shown for the MVC problem in [26], when a core is absent, this theory gives a correct calculation of energy density. When there is a core, the trivial fixed point of the core percolation theory leads to an underestimation of energy density. In [26], equation (7 ) can be easily reproduced on ER random graphs with a simple geometrical interpretation. A similar framework is also applied on the MM problem on the undirected bipartite representation of directed graphs [27]. Generalized versions of the GLR procedure and their percolation analysis can also be found in other combinatorial optimization problems, such as $k$-XORSAT problem [28, 29], Boolean networks [30], maximum independent set problem [31], minimum dominating set problem [32, 33], covering problems on hypergraphs [34], and $z$-matching problem on bipartite graphs [35].
The second framework is based on the theory of long-range frustration (LRF) [36, 37]. The LRF effect among MVC configurations is based on an intuition that some combinations of states of distant vertex pairs are forbidden due to long paths between them. Vertices whose states fluctuate among MVC configurations are further classified into two types, depending on how their state fixing triggers an extensive or a local state fixing of their neighboring vertices. This framework provides a refined quantitative picture on how vertices in different coarse-grained states contribute to the energy density of the MVC problem. Analytical result [37] shows that the LRF theory on ER random graphs achieves estimations very close to those from survey propagation-guided decimation (SPD) algorithm, which is basically at the first-step RSB level. The LRF framework is further applied on the satisfiability problems [38, 39].
In this paper, we follow the concept and the framework of LRF in [9, 36, 37] and focus on the analytical theory of the energy density of the MVC problem on general random graphs. Our contributions here are in three parts: (1) we remove inconsistency and clarify some derivation steps in the LRF framework of [36, 37] which can lead to a significant deviation in the prediction of energy densities on random graphs with non-Poissonian degree distributions; (2) we extend the corrected LRF framework on the MVC problem from the specific case of ER random graphs [36, 37] to sparse random graphs with arbitrary degree distributions; (3) we test our LRF theory of the MVC problem on some random graph models, and it achieves predictions on energy densities close to the SPD algorithm, and proves to be better than an analytical theory based on the GLR procedure [26] which basically ignores LRF effect.
Here is the layout of the paper. In section 2 , we present the concept of LRF for the MVC problem. In section 3 , we lay down our analytical framework of LRF on sparse random graphs. In section 4 , we test our theory on some random graph models, and compare the results with three other algorithms. In section 5 , we conclude the paper with some discussion.
2. Model
In this paper, we basically follow the concepts in [36, 37], such as the classification of vertices based on MVC configurations, the notation of LRF, the distinction of type-I and type-II unfrozen vertices, and the definition of order parameter of LRF. As shown in sections 3 and 4 , we will make a substantial correction to the theoretical framework of LRF in [36, 37]. For the self-consistency of the paper, we simply lay down an intuitive picture and core ideas of LRF from [36, 37].
As we mentioned, a MVC configuration on a graph $G = \{V, E\}$ can be denoted as $\vec{s} = \{s_i\}$ with $i \in V$ and $s_i \in \{0, 1\}$. For all the MVC configurations on $G$, there are simply three possibilities for the state of any vertex $i \in V$: $s_i = 0$ for all configurations; $s_i = 0$ for some (not all) configurations, while $s_i = 1$ for the other configurations; and $s_i = 1$ for all configurations. We define a coarse-grained state $C = \{0, \ast, 1\}$ for the above three possibilities, respectively. Correspondingly, we can classify all vertices into three categories: those frozen as being uncovered, those with an unfrozen state, and those frozen as being covered. See figure 1 for an example.
Figure 1. A diagram of the MVC configurations and the vertex categories. (a) shows a small graph with $7$ vertices and $7$ edges. (b) and (c) show two MVC configurations, in which covered vertices are denoted as shaded circles, and uncovered vertices are in empty circles. (d) shows the categories of vertices based on the two MVC configurations, in which a vertex with $0$ inside is frozen as being uncovered, a vertex with $\ast$ inside is in an unfrozen state, and a vertex with $1$ inside is frozen as being covered. |
On a large graph, we denote the relative sizes of vertices with coarse-grained states $\{0, \ast, 1\}$ as $(R_0, R_{\ast}, R_1)$, respectively. We simply have
$equation$
We can see that, vertices with the three coarse-grained states contribute to the energy of MVCs by $0$, a number $\in (0, 1)$, and $1$, respectively. A quantitative description of $(R_0, R_{\ast}, R_1)$ helps to characterize energy density and other ground-state properties of the MVC problem.The basic intuition of the LRF effect in the MVC problem is to further categorize those unfrozen vertices. In figure 1, the four vertices $\{l, m, n, o\}$ are all unfrozen vertices. For the non-neighboring vertex pairs $(l, n)$ and $(m, o)$, there is no combination for their states as $(1, 0)$ nor $(0, 1)$. Such a case of forbidden state combinations can exist for two unfrozen vertices far apart on graphs, considering the typical distance $\propto \ln N$ between two vertices on a sparse graph with $N$ vertices. To quantify the LRF effect, [36, 37] considers a simple question: when an unfrozen vertex $i$ is fixed with $s_i = 1$, how many unfrozen vertices must fix their states consequently. Two simple scenarios are considered in [36, 37]: a size of unfrozen vertices linear with $N$ fix their states correspondingly, thus the vertex $i$ is a type-I unfrozen vertex; a finite size $\sim \mathcal{O}(1)$ of unfrozen vertices fix their states correspondingly, thus $i$ is a type-II unfrozen vertex. On a large graph, the fraction $R$ of type-I unfrozen vertices among all unfrozen vertices is defined as the order parameter of the LRF effect [36, 37].
In this paper, with a slightly different notation from the one in [36, 37], we define the fraction of type-I unfrozen vertices among all vertices as $R_{\mathrm{g}}$. In the following LRF theory for the MVC problem on random graphs, we develop an analytical framework to calculate $(R_0, R_{\ast}, R_{\mathrm{g}}, R_1)$ and finally the energy density $x$ of the MVC problem.
3. Theory
3.1. Derivation of basic equations
Our theory generally follows the one in [36, 37]. As we will show, some inconsistencies of the theoretical framework in [36, 37] are removed to reach the current one in this paper. We further extends the theory onto general random graphs with arbitrary degree distributions. The framework here is basically the cavity method of spin glass theory, which is frequently applied on combinatorial optimization problems and satisfiability problems [8, 9], and also on percolation models on graphs [40, 41]. Despite drastically different equations of the cavity method for specific problems on graphs, the cavity method has a probabilistic formalism. Some basic quantities of problems, such as the ground-state energy density, can be interpreted as marginal probabilities on a graph. Under a given anzatz of RS or levels of RSB, these marginal probabilities can be derived with a set of cavity probabilities and those cavity probabilities form self-consistent equations with each other.
On a sparse random graph $G = \{V, E\}$, the relative sizes of vertices $(R_0, R_{\ast}, R_{\mathrm{g}}, R_1)$ can be understood as marginal probabilities when a randomly chosen vertex in $V$ is frozen as being uncovered, unfrozen, type-I unfrozen, and frozen as being covered, respectively. These marginal probabilities can be calculated with pertinent cavity probabilities. On a randomly chosen edge $(i, j) \in E$ and from vertex $i$ to vertex $j$, we define two cavity probabilities $(r_{0}, r_{\mathrm{g}})$: $r_{0}$ as the probability of $j$ frozen as being uncovered and $r_{\mathrm{g}}$ as the probability of $j$ being a type-I unfrozen vertex, both when $(i, j)$ is not considered. For a randomly chosen vertex $i \in V$, its category depends on these categories of its nearest neighbors. We consider here a cavity graph $G \backslash i$ when $i$ and its adjacent edges are all removed from $G$. Under the Bethe-Peierls approximation [8] at the RS level in cavity method, the categories of $i$'s nearest neighbors in $G \backslash i$ are independent with each other due to long distances between them. We then can establish equations connecting marginal probabilities $(R_0, R_{\ast}, R_{\mathrm{g}}, R_1)$ and cavity probabilities $(r_0, r_{\mathrm{g}})$.
In figure 2, we show a schematics to summarize the main notations and the flowchart in our theoretical framework. A detailed explanation is laid down in the following paragraphs.
Figure 2. A diagram of the main notations of probabilities and the flowchart of calculation in the LRF theory. (a)-(e) shows a vertex $i$ and the five different cases of the states of its nearest neighbors. All of the frozen neighbors in the uncovered state, the type-I unfrozen neighbors, the type-II unfrozen neighbors, and the frozen neighbors in the covered states are denoted collectively with an empty circle, a dark shaded circle, a light shaded circle, and a filled circle, respectively. Notations of $\# r_0$, $\# r_{\mathrm{g}}$, $\# (r_{\ast} - r_{\mathrm{g}})$, and $\# r_1$ respectively denote the size of the four types of neighboring vertices. A cross on an edge reiterates the absence of neighbors of a certain type. The five subfigures gives us a guide to the derivation of $P_1$ in equation ( |
We first consider $R_0$. For a randomly chosen vertex $i \in V$ to be frozen as being uncovered, we consider two cases for the nearest neighbors $\partial i$ in $G \backslash i$ as Case I and Case II. In Case I, among $\partial i$ there is no vertex frozen as being uncovered, nor type-I unfrozen vertex. The probability of this case is
$\begin{align} P_1 & = \sum _{k = 0}^{+ \infty} P\left(k\right) \left(1 - r_0 - r_{\mathrm{g}}\right)^{k}.\end{align}$
In Case II, among $\partial i$ there is no vertex frozen as being uncovered, yet with at least one type-I unfrozen vertex. Yet there is a possibility that all these type-I unfrozen vertices are not frustrated in $G \backslash i$, thus they can be in the covered state in certain MVC configurations. For any two type-I unfrozen vertices in $\partial i$ in $G \backslash i$, we assume an equal chance for them to be frustrated and be not frustrated, neglecting their local structural properties. Then the probability for Case II is 10 ) to (11 ), we simply substitute the summation sign $\sum _{s = 1}^{k}$ with $\sum _{s = 0}^{k}$, and further rearrange the equation into concise summations on degree distributions. The form of summations in equation (11 ) is suitable for short-hand notations as we will show later.
$align$
$align$
From equations (In both Cases I and II, when a vertex $i$ is added into $G \backslash i$, $i$ becomes a vertex frozen as being uncovered in $G$. Thus we have $R_0$ as 9 ) and (11 ), we have $R_0$ equivalently as
$align$
With equations ($align}R_0= 2 \sum _{k = 0}^{+\infty} P\left(k\right) \left( 1 - r_0 - \frac {r_{\mathrm{g}}}{2} \right)^{k$
Beware that, even though in both Case I and Case II $i$ becomes a vertex frozen as being uncovered, their influence on $i$'s neighbors are significantly different. In Case I, since there is no type-I unfrozen vertex among $\partial i$ in $G \backslash i$, after $i$ is assigned as being uncovered in $G$, there is only a limited number of unfrozen neighbors which are assigned with a certain state in the subsequent state fixing. Yet in Case II, a state fixing from $i$ can propagate until a macroscopic fraction of unfrozen vertices is assigned with certain states. We can see that a drastic change happens in the configurations of the MVC problem.
Then we consider $R_{\ast}$. For a randomly chosen vertex $i \in G$, we consider three cases, Case III, Case IV, and Case V, for $\partial i$ in $G \backslash i$. In Case III, among $\partial i$ there is only one vertex frozen as being uncovered and no type-I unfrozen vertex. We have the probability term as
$align$
In Case IV, among $\partial i$ there is only one vertex frozen as being uncovered and at least one type-I unfrozen vertex. Yet there is a possibility that these type-I unfrozen neighbors are not frustrated in $G \backslash i$, thus they can be all in the covered state, like the situation in Case II. We have the probability term as 15 ) to (16 ), we substitute the second summation sign $\sum _{s = 1}^{k - 1}$ with $\sum _{s = 0}^{k - 1}$ and rearrange the equation into simple summations forms.
$align}P_4& = \sum _{k = 2}^{+ \infty} P\left(k\right) k r_0 \sum _{s = 1}^{k - 1$
$align}& = 2 r_0 \sum _{k = 1}^{+ \infty} P\left(k\right) k\left[ \left( 1 - r_0 - \frac {r_{\mathrm{g}}}{2} \right)^{k - 1$
From equations (In Case V, among $\partial i$ there is no vertex frozen as being uncovered and at least two type-I unfrozen vertices. Suppose here we have $s (\unicode{x2A7E} 2)$ type-I unfrozen vertices in $\partial i$ in $G \backslash i$. There is a possibility that a frustration shows between one vertex and all the other $s - 1$ vertices while these $s - 1$ vertices are not frustrated, thus at most $s - 1$ neighbors can be in the covered state. Following the logic in Cases II and IV, we have the probability term as 17 ), the Kronecker delta $\delta _{s, t}$ is defined as $1$ only when $s = t$ and $0$ in other cases. From equations (17 ) to (18 ), we leave the details of simplification in appendix A .
$\begin{align} P_5& = \sum _{k = 2}^{+ \infty} P\left(k\right) \sum _{s = 2}^{k} {k \choose s} r_{\mathrm{g}}^{s} \left(1 - r_0 - r_{\mathrm{g}}\right)^{k - s}\nonumber\\ & \quad \times \left[ \delta _{s,2} \frac {1}{2} + \left(1 - \delta _{s,2}\right) \frac {s}{2^{s - 1}} \right], \end{align}$
$\begin{align} & = cr_{\mathrm{g}} \sum _{k = 1}^{+\infty} Q\left(k\right) \left[ \left( 1 - r_0 - \frac {r_{\mathrm{g}}}{2} \right)^{k - 1} - \left(1 - r_0 - r_{\mathrm{g}}\right)^{k - 1} \right]\nonumber\\ & \quad - \frac {c r_{\mathrm{g}}^2}{4} \sum _{k = 2}^{+\infty} Q\left(k\right) \left(k - 1\right) \left(1 - r_0 - r_{\mathrm{g}}\right)^{k - 2}.\end{align}$
In equation (In all the Cases III, IV, and V, a vertex $i$ becomes an unfrozen vertex in $G$. Thus we have 14 ), (16 ), and (18 ), we correspondingly have A .
$align$
With equations ($\begin{align} R_{\ast} & = \left(2 c r_0 + c r_{\mathrm{g}}\right) \sum _{k = 1}^{+\infty} Q\left(k\right) \left( 1 - r_0 - \frac {r_{\mathrm{g}}}{2} \right)^{k - 1} \nonumber\\ & \quad- \left(c r_0 + c r_{\mathrm{g}}\right) \sum _{k = 1}^{+\infty} Q\left(k\right) \left(1 - r_0 - r_{\mathrm{g}}\right)^{k - 1} \nonumber \\ & \quad - \frac {c r_{\mathrm{g}}^2}{4} \sum _{k = 2}^{+\infty} Q\left(k\right) \left(k - 1\right) \left(1 - r_0 - r_{\mathrm{g}}\right)^{k - 2}.\end{align}$
Details of above equation are also left in appendix Then we consider $R_{\mathrm{g}}$. We can see that only in Cases III and IV, the vertex $i$ can be type-I unfrozen in $G$, yet an extra constraint should be satisfied. Here we denote a vertex $j \in \partial i$ as the only vertex which is frozen as being uncovered in $G \backslash i$. After the addition of $i$ into $G \backslash i$, $j$ correspondingly becomes an unfrozen vertex in $G$. If $i$ is assigned as $s_i = 1$ in $G$, we have a state fixing as $s_j = 0$ to achieve a low energy. For the vertex $j$ per se, there are Cases I and II for the nearest neighbors $\partial j \backslash i$, which lead to $j$ as frozen as being uncovered before the addition of $i$. If the nearest neighbors $\partial j \backslash i$ is in Case II, a propagation of state fixing happens and a macroscopic fraction of unfrozen vertices are assigned with certain states. For a randomly chosen edge $(i, j) \in E$ between vertices $i$ and $j$, we define $Q_1$ and $Q_2$ as the probability of Case I and Case II, respectively, for the states of $\partial j \backslash i$. We consider them as the cavity counterpart of marginal probabilities $P_1$ and $P_2$, respectively. Following equations (9 )-(11 ) for the derivation of $P_1$ and $P_2$, we lay down expressions for $Q_1$ and $Q_2$ as 21 ) and (23 ), we have
$\begin{align} Q_1 & = \sum _{k = 1}^{+ \infty} Q\left(k\right) \left(1 - r_0 - r_{\mathrm{g}}\right)^{k - 1},\end{align}$
$\begin{align} Q_2 & = \sum _{k = 2}^{+ \infty} Q\left(k\right) \sum _{s = 1}^{k - 1} {k - 1 \choose s} r_{\mathrm{g}}^{s} \left(1 - r_0 - r_{\mathrm{g}}\right)^{k - 1 - s} \frac {1}{2^{s - 1}},\end{align}$
$align}& = 2 \sum _{k = 1}^{+ \infty} Q\left(k\right)\left[ \left( 1 - r_0 - \frac {r_{\mathrm{g}}}{2} \right)^{k - 1}- \left(1 - r_0 - r_{\mathrm{g}}\right)^{k - 1$
We thus have $align$
Combining equations ($align}r_0 = 2 \sum _{k = 1}^{+ \infty} Q\left(k\right) \left(1 - r_0 - \frac {r_{\mathrm{g}}}{2} \right)^{k - 1$
For $R_{\mathrm{g}}$, we have 14 ), (16 ), and (21 ), we finally have
$align}R_{\mathrm{g}}= \left(P_3 + P_4\right) \frac {Q_2}{Q_1 + Q_2$
After inserting equations ($align}R_{\mathrm{g}}& = \left[ 2 \sum _{k = 1}^{+ \infty} P\left(k\right) k \left(1 - r_0 - \frac {r_{\mathrm{g}}}{2} \right)^{k - 1}\right.\nonumber\\&\quad \left.- \sum _{k = 1}^{+ \infty} P\left(k\right) k \left(1 - r_0 - r_{\mathrm{g}} \right)^{k - 1}\right] \nonumber\\&\quad \times \left[ r_0 - \sum _{k = 1}^{+ \infty} Q\left(k\right) \left(1 - r_0 - r_{\mathrm{g}}\right)^{k - 1$
We finally consider $r_{\mathrm{g}}$. For a randomly chosen edge $(i, j) \in E$ between vertices $i$ and $j$, we consider Case III and Case IV for the states of $\partial j \backslash i$. Their probabilities are defined as $Q_3$ and $Q_4$, respectively, which can be viewed as the cavity counterpart of marginal probabilities $P_3$ and $P_4$, respectively. Following equations (14 )-(16 ) for the derivation of $P_3$ and $P_4$, we lay down expressions for $Q_3$ and $Q_4$ as
$\begin{align} Q_3 & = \sum _{k = 2}^{+ \infty} Q\left(k\right) \left(k - 1\right) r_0 \left(1 - r_0 - r_{\mathrm{g}}\right)^{k - 2},\end{align}$
$align}Q_4& = \sum _{k = 3}^{+ \infty} Q\left(k\right) \left(k - 1\right) r_0 \sum _{s = 1}^{k - 2$
$align}& = 2 r_0 \sum _{k = 2}^{+ \infty} Q\left(k\right) \left(k - 1\right) \left[ \left( 1 - r_0 - \frac {r_{\mathrm{g}}}{2} \right)^{k - 2$
Following equation (26 ) for the derivation of $R_{\mathrm{g}}$, we have the expression for $r_{\mathrm{g}}$ as 21 ), (28 ), and (30 ), we have
$align}r_{\mathrm{g}}= \left(Q_3 + Q_4\right) \frac {Q_2}{Q_1 + Q_2$
Combining equations ($\begin{align} r_{\mathrm{g}} & = \left[2 \sum _{k = 2}^{+ \infty} Q\left(k\right) \left(k - 1\right) \left(1 - r_0 - \frac {r_{\mathrm{g}}}{2} \right)^{k - 2}\right.\nonumber\\ &\quad \left. - \sum _{k = 2}^{+ \infty} Q\left(k\right) \left(k - 1\right) \left(1 - r_0 - r_{\mathrm{g}} \right)^{k - 2} \right] \nonumber\\ &\quad \times \left[r_0 - \sum _{k = 1}^{+ \infty} Q\left(k\right) \left(1 - r_0 - r_{\mathrm{g}}\right)^{k - 1} \right].\end{align}$
Equations (13 ), (20 ), (27 ), (25 ), and (32 ) consist of the basis of our analytical theory. For a graph ensemble or instance with $P(k)$, with equations (25 ) and (32 ) we first calculate stable fixed $(r_0, r_{\mathrm{g}})$, then with equations (13 ), (20 ) and (27 ) we calculate corresponding $(R_{0}, R_{\ast}, R_{\mathrm{g}})$, respectively.
Here is a numerical procedure to solve the stable fixed points of equations (25 ) and (32 ). We define the right-hand side of equations (25 ) and (32 ) as $f(r_{0}, r_{\mathrm{g}})$ and $g(r_{0}, r_{\mathrm{g}})$, respectively. We have 33 ) as $r_{0}^{\ast}$. Then we can calculate $g(r_{0}^{\ast}, r_{\mathrm{g}})$. Finally, we can check whether $r_{\mathrm{g}} = g(r_{0}^{\ast}, r_{\mathrm{g}})$ satisfies. In such a way, we can calculate stable fixed $r_{\mathrm{g}}$ for equation (34 ) as $r_{\mathrm{g}}^{\ast}$. Then we again calculate corresponding $r_{0}^{\ast}$ with given $r_{\mathrm{g}}^{\ast}$ with equation (33 ). Finally, we have the pair of fixed points as $(r_{0}^{\ast}, r_{\mathrm{g}}^{\ast})$.
$align$
$align$
We then adopt a numerical method to calculate stable fixed points of $r_{0}$ and $r_{\mathrm{g}}$. For any given $r_{\mathrm{g}} \in [0, 1]$, we calculate the stable fixed point of $r_{0}$ with equation (With the solution of $(R_0, R_{\ast}, R_{\mathrm{g}})$, we can further estimate ground-state properties of the MVC problem. We focus on its energy density $x$. Consider here a vertex $i$ is added into a cavity graph $G \backslash i$. If $i$ becomes a vertex frozen as being uncovered in $G$, the addition of $i$ contributes by no energy to MVC on $G$. If $i$ becomes an unfrozen vertex in $G$, its sole uncovered nearest neighbor (say, $j$) also becomes an unfrozen vertex in $G$. Then either $i$ or $j$ is covered in the MVC on $G$. Thus the addition of $i$ contributes by one to the energy of MVC on $G$. If $i$ becomes a frozen vertex as being covered in $G$, there is no state change in $G \backslash i$, and the addition of $i$ also contributes by one to the energy of MVC on $G$. Summing the above three cases, $x$ can be estimated as [37]
$align$
To calculate $x$ for a given $c$, we first discretize $c$ as $c = N_c \Delta c$ into $N_c (\gg 1)$ steps with a step length $\Delta c$. Thus we have a long sequence of mean degrees $c^{^{\prime}}$ as $c^{^{\prime}} = n \Delta c$ with $1 \unicode{x2A7D} n \unicode{x2A7D} N_c$. We should mention that, for each $c^{^{\prime}}$, the corresponding $R_0$ is calculated from our framework. We calculate $R_0$ for each $c^{^{\prime}}$, and add up $1 - R_0$ as the energy contribution from $c^{^{\prime}} - \Delta c$ to $c^{^{\prime}}$. Beware that, the above procedure takes an incremental approach to calculate the energy density on large graphs with a mean degree $c$, which effectively calculates all the energy densities of MVC with $c^{^{\prime}} \lt c$. It is easy to see that, with a larger $N_c$, we can have a more accurate $x$.Here we discuss the time complexity of our analytical theory to estimate energy density $x$ for a graph ensemble or instance with a degree distribution $P(k)$ and a corresponding mean degree $c$. To calculate the stable fixed $(r_{0}^{\ast}, r_{\mathrm{g}}^{\ast})$, we adopt a simple bisection method to find all fixed points of $(r_{0}, r_{\mathrm{g}})$ in a greedy way. In the search for fixed points, we discretize $[0, 1]$ (the range of $r_0$ and $r_{\mathrm{g}}$) into $N_0$ equal intervals for $r_0$ and $N_{\mathrm{g}}$ equal intervals for $r_{\mathrm{g}}$. Thus the time complexity to find the stable fixed $(r_{0}^{\ast}, r_{\mathrm{g}}^{\ast})$ is $\mathcal{O} (N_0 N_{\mathrm{g}})$. Considering the discretization scheme in estimating energy density in equation (35 ), the final time complexity of our framework to calculate the energy density at mean degree $c$, along with those at each mean degree $c^{^{\prime}} (\unicode{x2A7D} c)$ in the discretization step, is $\mathcal {O}(N_c N_0 N_{\mathrm{g}})$. In section 4 , we set $N_c = 10^3$ for ER random graphs and $10^4$ for the other graph models, and $N_0 = N_{\mathrm{g}} = 10^3$ uniformly.
3.2. Comparison with the theory based on the GLR procedure
We then compare our framework with the theory based on the GLR procedure for the MVC problem in [26]. We first make a very crude assumption that there is no LRF among unfrozen vertices, and we see where our analytical framework will lead us. In this context, we have $r_{\mathrm{g}} = R_{\mathrm{g}} = 0$. Our framework reduces to 36 ) we first calculate stable fixed $r_0$, and then with equation (40 ) we can estimate $x$. On the other hand, in [26] to estimate the energy density of the MVC problem, the branch of trivial fixed points of $\alpha$ and $\beta$ with $1 - \alpha - \beta = 0$ is chosen no matter there is a core or not on a graph. It is easy to find some correspondence of notations and equations between our work and [26]: the cavity probability $r_0$ to the cavity probability $\alpha$, equation (36 ) to equations (1 ) and (2 ) when $1 - \alpha - \beta = 0$, and equations (40 ) to (5 ). Taken the above messages together, the theory based on the GLR procedure simply corresponds to the LRF theory with no LRF effect. When a macroscopic LRF effect sets in and $R \gt 0$, this theory deviates from a proper prediction and underestimates the energy density of MVCs.
$align$
$align$
$\begin{align} R_{\ast} & = cr_0 \sum _{k = 1}^{+\infty} Q\left(k\right) \left(1 - r_0\right)^{k - 1} \nonumber \\ & = cr_0^2,\end{align}$
$\begin{align} R_1 & = 1 - R_0 - R_{\ast} \nonumber \\ & = 1 - \sum _{k = 0}^{+\infty} P\left(k\right) \left(1 - r_0\right)^{k} - cr_0^2.\end{align}$
We further assume that each type-II vertex contributes by exactly one half to the energy of the MVC problem, neglecting details of local graph structure. As there are only type-II vertices in unfrozen vertices here, their total contribution to the energy density is simply $R_{\ast} / 2$. We have the energy density as $align$
Given a degree distribution $P(k)$, with equation (3.3. Simplified equations of our theory
Our basic equations can be further reformulated in a more compact form. We first define two short-hand summations on degree distributions as 13 ), (20 ), (27 ), (25 ), and (32 ) can be rewritten as
$\begin{align} P^{\left(s\right)} \left(x\right) & = \sum _{k = s}^{+ \infty} P\left(k\right) {k \choose s} x^{k - s},\end{align}$
$\begin{align} Q^{\left(s\right)}\left(x\right) & = \sum _{k = s + 1}^{+ \infty} Q\left(k\right) {k - 1 \choose s} x^{k - 1 - s},\end{align}$
in which $x \in [0, 1]$ is a real variable and $s \unicode{x2A7E} 0$ is an integer. Equations ($align$
$\begin{align} R_{\ast} & = \left(2 c r_0 + cr_{\mathrm{g}}\right) Q^{\left(0\right)} \left(1 - r_0 - \frac {r_{\mathrm{g}}}{2} \right) \nonumber \\ & \quad - \left(c r_0 + cr_{\mathrm{g}}\right) Q^{\left(0\right)}\left(1 - r_0 - r_{\mathrm{g}}\right) - \frac {c r_{\mathrm{g}}^2}{4} Q^{\left(1\right)}\left(1 - r_0 - r_{\mathrm{g}}\right),\end{align}$
$\begin{align} R_{\mathrm{g}} & = \left[ 2 P^{\left(1\right)} \left(1 - r_{0} - \frac {r_{\mathrm{g}}}{2} \right) - P^{\left(1\right)} \left(1 - r_{0} - r_{\mathrm{g}} \right) \right] \nonumber \\ & \quad \times \left[ r_{0} - Q^{\left(0\right)} \left( 1 - r_{0} - r_{\mathrm{g}} \right) \right],\end{align}$
$align$
$\begin{align} r_{\mathrm{g}} & = \left[ 2 Q^{\left(1\right)} \left(1 - r_{0} - \frac {r_{\mathrm{g}}}{2} \right) - Q^{\left(1\right)} \left(1 - r_{0} - r_{\mathrm{g}} \right) \right] \nonumber \\ & \quad \times \left[ r_{0} - Q^{\left(0\right)} \left( 1 - r_{0} - r_{\mathrm{g}} \right) \right].\end{align}$
4. Result
4.1. Methods for comparison
To further ascertain the correctness of energy density prediction from our framework, we also calculate energy densities of the MVC problem with other three methods.
The first method is the theory based on the GLR procedure [26]. We leave a simple explanation of this analytical method in appendix B
The second method is the belief propagation-guided decimation (BPD) algorithm [13] combined with the GLR procedure, which outputs approximate MVC configurations on graph instances. We simply name it as the GLR+BPD algorithm for short. The belief propagation (BP) algorithm works at the RS level, assuming that all the solutions are organized in a single cluster (a macroscopic state) which has no inner structure. The inverse temperature $\beta$ is the reweighting parameter in the BP algorithm. The basic procedure of this hybrid algorithm is as follows: (1) on a graph instance, we first apply the GLR procedure to cover roots as local optimal steps until there is a core; (2) we iterate cavity messages on all edges of the residual core, until a convergence of messages or a maximal number of message updating; (3) we adopt a BPD step on the core to cover a fraction of vertices with the largest marginal probability to be in the covered state; (4) the above three steps are iteratively carried out, until all the edges of the initial graph are covered. Basic parameters of message updating and vertex decimation in the algorithm are as follows: the maximal iteration number $N_{\mathrm{iter}}$ in a single step of message updating, the criterion $\varepsilon$ of message convergence for the maximal difference between messages between two consecutive updating steps, and the size of covered vertices $N_{1}$ in a single decimation step of BPD on a core with a vertex size $N_{\mathrm{core}}$. In our result here, we set $N_{\mathrm{iter}} = 200$, $\varepsilon = 10^{-8}$, $N_{1} = \max \{N_{\mathrm{core}}/ N_{\mathrm{d}}, N_{\mathrm{min}}\}$ with $N_{\mathrm{d}} = 200$ and $N_{\mathrm{min}} = 1$.
The third method is the SPD algorithm [19] combined with the GLR procedure, which also outputs approximate MVC configurations on graph instances. We name it as the GLR+SPD algorithm for short. The survey propagation (SP) algorithm [42] works at the first-step RSB level, assuming that the solutions are organized in a large number of well separated clusters, in each of which there is no inner structure. In each macroscopic state, we set $\beta \to +\infty$, and reweigh different macroscopic states by their energy densities with a parameter $y$. The procedure of the GLR+SPD algorithm is much like the one in the GLR+BPD algorithm, in which we iterate messages based on equations in SP algorithm rather than those based on equations in BP algorithm. In our result here, we adopt the same parameters of $N_{\mathrm{iter}}$, $\varepsilon$, $N_{1}$, $N_{\mathrm{d}}$, and $N_{\mathrm{min}} $ with the GLR+BPD algorithm.
4.2. Results on random graph models
Then we test our analytical framework on some representative random graph models.
We first consider the ER random graphs [10, 11]. For Poissonian degree distributions, the summations in equations (41 ) and (42 ) reduce to 48 ) specifically on ER random graphs, which is not a universal property for general random graphs.
$align$
for any $x \in [0, 1]$ and $s \unicode{x2A7E} 0$. We have simplified formulae for $(R_{0}, R_{\ast}, R_{\mathrm{g}}, r_{0}, r_{\mathrm{g}})$ as $align}R_{0$
$\begin{align} R_{\ast} & = \left(2 c r_0 + c r_{\mathrm{g}}\right) {\mathrm{e}}^{- c \left( r_0 + r_{\mathrm{g}} / 2 \right)} \nonumber \\ & \quad - \left[ cr_0 + cr_{\mathrm{g}} + \frac {\left(cr_{\mathrm{g}}\right)^2}{4} \right] {\mathrm{e}}^{- c \left(r_0 + r_{\mathrm{g}}\right)},\end{align}$
$\begin{align} R_{\mathrm{g}} & = \left[ 2 c {\mathrm{e}}^{- c\left(r_0 + r_{\mathrm{g}} / 2\right)} - c {\mathrm{e}}^{- c \left(r_{0} + r_{\mathrm{g}}\right)} \right] \left[ r_0 - {\mathrm{e}}^{- c \left(r_{0} + r_{\mathrm{g}}\right)} \right],\end{align}$
$align}r_{0$
$\begin{align} r_{\mathrm{g}} & = \left[ 2 c {\mathrm{e}}^{- c \left(r_0 + r_{\mathrm{g}} / 2\right)} - c {\mathrm{e}}^{- c \left(r_{0} + r_{\mathrm{g}}\right)} \right] \left[ r_0 - {\mathrm{e}}^{- c \left(r_{0} + r_{\mathrm{g}}\right)} \right].\end{align}$
We can easily find that $align$
This equivalence is simply a natural result of equation (We then discuss connections and difference between our framework and Zhou's in [36, 37]. In [36], equation (2 ) shows 3 ) shows 55 ), (56 ), and (57 ) is equivalent to equations (49 ), (50 ), and (51 ), respectively. This means that our framework naturally reproduces those main results in [36, 37]. Yet there is a fundamental difference between these two frameworks. Considering the forms of degree distributions, the right-hand side of both equation (2) in [36] and the first equation in [37] are meant for marginal probabilities (say $R_0$ and $R_{\mathrm{g}}$ in our notations here), not for cavity probabilities (say $r_0$ and $r_{\mathrm{g}}$). That is to say, Zhou's theory establishes its framework only with marginal probabilities. Our theory reproduces Zhou's one only when equation (54 ) holds on ER random graphs, and Zhou's theory can suffer from severe deviation on predictions on graphs with non-Poissonian degree distributions. In summary, our framework takes the LRF effect as intrinsically a percolation model and follows a formal construction process for its analytical theory with both marginal and cavity probabilities, thus we can root out the intrinsic inconsistencies in Zhou's theory.
$align$
and equation ($\begin{align} q_0 & = \left(2 c q_{+} + c q_0 R\right) {\mathrm{e}}^{- c q_{+} - c q_0 R / 2} \nonumber \\ &\quad - \left[ c q_{+} + c q_0 R + \frac{\left(c q_0 R\right)^2}{4} \right] {\mathrm{e}}^{- c q_{+} - c q_0 R}.\end{align}$
The first equation in [37] shows $align$
Considering a correspondence between probabilities as $\{q_{+}, q_{0}R\} \leftrightarrow \{r_0, r_{\mathrm{g}}\}$, we can easily find that the right-hand side of equations (In figure 3(a), we can see that with an increasing $c$, $R_0$ decreases and $R_1$ increases monotonously. $R_{\ast}$ gradually increases from $0$, reaches a maximum at $c \approx {\mathrm{e}}$, and then decreases. $R_{\mathrm{g}}$ follows a similar pattern with $R_{\ast}$, yet a nontrivial $R_{\mathrm{g}} ( \gt 0)$ emerges continuously at $c = c^{\ast} = {\mathrm{e}}$, while $c^{\ast}$ is the critical mean degree. The behavior of $R_{\mathrm{g}}$ can be explained by the birth of a nontrivial stable $r_{\mathrm{g}}$ from equations (52 ) and (53 ). In a simple schematic explanation, we can plot $y = g(r_0, r_{\mathrm{g}})$ and $y = r_{\mathrm{g}}$ in the same coordinates, and all the fixed points can be read from the intersection between them. When $c \unicode{x2A7D} c^{\ast} = {\mathrm{e}}$, there is only one fixed point as $r_{\mathrm{g}}^{\ast} = 0$. When $c \gt c^{\ast} = {\mathrm{e}}$, a nontrival stable point $r_{\mathrm{g}}^{\ast} ( \gt 0)$ emerges continuously. In a general case, the critical point $c^{\ast}$ can be determined from the set of equations as
$align$
$align$
Figure 3. Marginals of the LRF theory and energy densities of the MVC problem on ER random graphs. (a) shows marginal probabilities $(R_0, R_{\ast}, R_{\mathrm{g}}, R_1)$ from the LRF theory on infinitely large ER random graphs. (b) shows energy densities of the MVC problem on ER random graphs. Results are from four methods: the GLR+BPD algorithm on graph instances with a vertex size $N = 10^5$ with $\beta = 10$, the GLR+SPD algorithm on graph instances with a vertex size $N = 10^5$ with $y = 3.1$, the framework of the LRF theory on infinitely large graphs with $\Delta c = 0.001$, and the theory based on the GLR procedure (GLR-based) on infinitely large graphs. |
In figure 3(b), we show energy densities of the MVC problem from four methods. When $c \unicode{x2A7D} {\mathrm{e}}$, there is no percolation of type-I unfrozen vertices, equivalently no LRF effect among unfrozen vertices, and all the four methods achieve energy densities with an indistinguishable difference. When $c \gt {\mathrm{e}}$, there is a percolation of LRF effect among unfrozen vertices, and we have the following three observations. The first one is that, the GLR+SPD algorithm achieves consistently lower energy densities than the GLR+BPD algorithm. Thus we take the GLR+SPD results as a convenient reference of true ground-state energy density of the MVC problem. The second one is that, the LRF predictions are higher than the GLR+SPD results, and the GLR-based predictions are lower than the GLR+SPD results. An intuitive explanation is that the effect of LRF forbids some covering configurations which have lower energies yet violate the structural constraint for a proper vertex cover. Ignoring the LRF effect simply leads to an underestimation of true ground-state energy density of the MVC problem. The third one is that, with the GLR+SPD results as a reference, the LRF predictions are much more closer to them than the GLR-based predictions. The three complementary observations confirm that the idea of LRF captures a proper mechanism leading to the highly complicated energy landscape of the MVC problem, and our theoretical framework on LRF delivers a reasonable prediction of its ground-state energy densities.
We then test our framework on diluted regular random (RR) graphs. A RR graph has a uniform degree distribution as each vertex has a degree $K (\unicode{x2A7E} 2)$. In order to generate graph instances with a heterogeneous degree profile, we randomly dilute a RR graph, in which a fraction $1 - \rho \in [0, 1]$ of edges is randomly chosen and removed. The residual diluted RR graph shows a degree distribution $P(k)$ as
$align$
with $0 \unicode{x2A7D} k \unicode{x2A7D} K$.In figure 4, the four marginal probabilities for diluted RR graphs follow the similar pattern as the case on ER random graphs. We find that when a percolation happens, the LRF predictions of energy densities are only slightly higher than the GLR+SPD results, and they are much closer to the GLR+SPD results than the GLR-based predictions.
Figure 4. Marginals of the LRF theory and energy densities of the MVC problem on diluted RR graphs. (a) and (b) show marginal probabilities $(R_0, R_{\ast}, R_{\mathrm{g}}, R_1)$ from the LRF theory on infinitely large diluted RR graphs in the case of $K = 10$ and $K = 6$, respectively. (c)-(f) show energy densities of the MVC problem on diluted RR graphs from four methods in the case of $K = \{10, 8, 6, 4\}$, respectively. Each subgraph in (c)-(f) generally follows the format and the algorithm parameters in figure 3(b). For the GLR+SPD algorithm, we set $y = 3$. For the LRF theory, we set $\Delta \rho = 0.001$. |
We finally consider networks with scale-free property in degree distributions [43], which show a degree distribution $P(k) \propto k^{- \gamma}$ with $\gamma$ as a degree exponent. This property exists abundantly in real-world networks due to their intricate evolution mechanisms, which lead to structural heterogeneity at many different levels.
Here we consider two models to generate scale-free network instances. The first model is the configurational model [40], which can generate graph instances with any given proper degree distribution. A typical procedure of the configurational model follows as: for a degree distribution $P(k)$ and a vertex size $N$, we have a list of degrees $k$ and corresponding vertex size $NP(k)$; we generate a sequence of degrees with a size of $N$, in which a vertex with a degree $k$ has $k$ half-edges; two half-edges from two different vertices can be connected into a proper edge if there is no edge between them; after all half-edges are turned into proper edges, we finally generate a graph instance. In the configurational model for scale-free networks, we define four parameters: a vertex size $N$, a degree exponent $\gamma$, a maximal degree $k_{\mathrm{max}}$, and a minimal degree $k_{\mathrm{min}}$. To eliminate the degree-degree correlation in networks, we usually set $k_{\mathrm{max}} = \sqrt N$. Like the case in diluted RR graphs, we consider the diluted version of scale-free network instances, in which a fraction $1 - \rho \in [0, 1]$ of edges is randomly chosen and removed. For a scale-free network instance with an initial degree distribution $P^{i}(k)$ with $k_{\mathrm{min}} \unicode{x2A7D} k \unicode{x2A7D} k_{\mathrm{max}}$, after a dilution process with a fraction $\rho$, we have the degree distribution of the diluted graph as
$align$
with $0 \unicode{x2A7D} k \unicode{x2A7D} k_{\mathrm{max}}$.In figure 5, the four marginal probabilities of LRF theory on a scale-free network instance follow a pattern quite similar to those in the case of ER random graphs. We find that when there is a percolation, the LRF predictions of energy densities are always higher than the GLR+SPD results. We further notice that, with the GLR+SPD results as a reference, even the overestimation from LRF theory is comparable with the underestimation from the GLR-based theory, the LRF predictions are still closer to the GLR+SPD results.
Figure 5. Marginals of the LRF theory and energy densities of the MVC problem on scale-free networks generated with configurational model. We here focus on network instances generated with $N = 10^5$, $\gamma = 2.5$, and $k_{\mathrm{max}} = \sqrt {N}$. (a) and (b) show marginal probabilities $(R_0, R_{\ast}, R_{\mathrm{g}}, R_1)$ from the LRF theory on a single graph instance in the case of $k_{\mathrm{min}} = 12$ and $k_{\mathrm{min}} = 8$, respectively. (c)-(f) show energy densities of the MVC problem from four methods on diluted graph instances in the case of $k_{\mathrm{min}} = \{12, 10, 8, 6\}$, respectively. Each subgraph in (c)-(f) generally follows the format and the algorithm parameters in figure 3(b). For the LRF and the GLR-based theoretical frameworks, the empirical degree distribution of diluted graph instances is the input. For the LRF theory, we set $\Delta \rho = 0.001$. |
We then consider scale-free networks generated with static model [44, 45]. The graph construction process in static model is a process of independent edge addition based on weights of vertices, which is much like the generation of ER random graphs. Basic parameters of the model are a vertex size $N$, a degree exponent $\gamma$, and a mean degree $c$. We first define an intermediary parameter $\xi \equiv 1 / (\gamma - 1)$. We initially construct a null graph with only $N$ vertices and no edge. For each vertex $i$ with an index $i \in \{1, 2,\ldots, N\}$, a relative weight $w_i = i^{- \xi} / \sum _{i = 1}^{N} i^{- \xi}$ is assigned. In a single step of edge addition, two vertices, say $i$ and $j$, are selected with probabilities of their respective weights $w_i$ and $w_j$. If there is no connection between them, a proper edge between them can be established as $(i, j)$. In such a way, a sequence of edges with a size $M = c N / 2$ is added into the null graph. Such a large graph instance has a degree distribution as
$eqnarray$
with $k \unicode{x2A7E} 0$. The special function ${\mathrm{E}}_{a}(x)$ is a general exponential integral function defined as ${\mathrm{E}}_{a}(x) \equiv \int _{1}^{\infty} \mathrm{d}t e^{-xt} t^{- a}$ with $a,$ $x \gt 0$. For large $k$, we have $P (k) \propto k^{- \gamma}$.In figure 6, we find that the pattern of the four marginals is also quite similar to the case of ER random graphs. We also find that when a percolation happens, the LRF predictions of energy densities are slightly higher than the GLR+SPD results except the case of $\gamma = 2.8 ( \lt 3.0)$, and the GLR-based predictions are lower than the GLR+SPD results. Besides, the LRF predictions are always closer to the GLR+SPD results than the GLR-based predictions.
Figure 6. Marginals of the LRF theory and energy densities of the MVC problem on scale-free networks generated with static model. (a) and (b) show marginal probabilities $(R_0, R_{\ast}, R_{\mathrm{g}}, R_1)$ from the LRF theory on inifitely large scale-free networks in the case of $\gamma = 3.5$ and $\gamma = 3$, respectively. (c)-(f) show energy densities of the MVC problem from four methods on scale-free networks in the case of $\gamma = \{3.5, 3.2, 3, 2.8\}$, respectively. Each subgraph in (c)-(f) generally follows the format and the algorithm parameters in figure 3(b). For the LRF theory, we set $\Delta c = 0.01$. |
5. Conclusion
In this paper, we focus on an analytical method for the MVC problem, which predicts its energy density as an explicit function of the topological properties of graph ensembles. This methodology is complementary to those powerful methods, such as SP algorithm, which mainly apply on graph instances or are in a formalism of population dynamics.
Our theoretical framework is based on the effect of LRF between unfrozen vertices in MVC configurations. We correct the LRF theory in [36, 37] and extend it from ER random graphs onto general random graphs. An analytical theory on LRF is finally developed to account for the relative size of vertices in the four coarse-grained states, thus leads to a theoretical prediction on the energy density of MVC only with degree distribution of graphs as inputs. We test our analytical framework on some random graph models. We show that, when a percolation of LRF effect happens on a graph, the performance of our framework is rather close to a hybrid algorithm combining the GLR procedure and the SPD algorithm, and is significantly better than a theory based on the GLR procedure. That is to say, our analytical framework of LRF at the RS level can achieve predictions of energy densities very close to the message passing algorithms at the first-step RSB level. Our framework shows that a refined picture of the structure of solution configurations helps us to develop a precise theory for ground-state properties of hard combinatorial optimizations.
We should mention that our binary classification of unfrozen vertices is only an approximation on the path to an exact theory, if possible, of the energy density of the MVC problem on general random graphs. More detailed information on the structure of unfrozen vertices can further improve our prediction. For example, we can incorporate the size distribution of state fixing from an unfrozen vertex into our current framework. Potential improvement on our theory will be carried out in a future work.
The concept of LRF is based on the long-range interaction among vertex states in the ground-state configurations of optimization problems, and the LRF effect is not limited to the context of the MVC problem. [38] introduces the LRF framework into $K$-satisfiability problems to discuss the percolation thresholds of the LRF effect with the SAT-UNSAT transition points. [39] calculates the residual order parameter of LRF in the first-step RSB solutions for the MVC and the maximal $2$-satisfiability problems. Both are examples of a new way to elucidate the phase transition behaviors in the solution spaces of combinatorial optimization problems from the perspective of the spin glass theory. An integration of the LRF effect into other hard optimization problems can be considered in a following work.