Effect of constraint relaxation on the minimum vertex cover problem in random graphs

A statistical-mechanical study of the effect of constraint relaxation on the minimum vertex cover problem in Erdős-Rényi random graphs is presented. Using a penalty-method formulation for constraint relaxation, typical properties of solutions, including infeasible solutions that violate the constraints, are analyzed by means of the replica method and cavity method. The problem involves a competition between reducing the number of vertices to be covered and satisfying the edge constraints. The analysis under the replica-symmetric (RS) ansatz clarifies that the competition leads to degeneracies in the vertex and edge states, which determine the quantitative properties of the system, such as the cover and penalty ratios. A precise analysis of these effects improves the accuracy of RS approximation for the minimum cover ratio in the replica symmetry-breaking (RSB) region. Furthermore, the analysis based on the RS cavity method indicates that the RS/RSB boundary of the ground states with respect to the mean degree of the graphs is expanded, and the critical temperature is lowered by constraint relaxation.

Figure 1

Inverse-temperature $\beta$ dependence of the energy density $\varepsilon$ and the cover ratio $\rho$ for $\gamma =2.0$, 1.1, and 0.9 for $c=2.0$. For $\gamma >1$ (solid lines), both $\varepsilon$ and $\rho$ are asymptotically converged to the minimum cover ratio for large $\beta$, but for $\gamma <1$ (dashed), $\varepsilon$ and $\rho$ are converged to lower values. These calculations were obtained by the method of population dynamics with ${10}^5$ populations, where the errors are within the width of lines.

Figure 2

Penalty-coefficient $\gamma$ dependence of the energy density $\varepsilon$ and the cover ratio $\rho$ for $\beta =10$ (solid and dashed lines) and 100 (dashed and two-dotted lines) at mean degree $c=2.0$. The simulation conditions of the population dynamics are the same as in Fig. 1. Since a large amount of data was taken in the area with finely varying curves, markers are not displayed for visibility.

Figure 3

$\gamma$ dependence of the cover ratio $\rho$, penalty ratio $\nu$ and energy density $\varepsilon$ in the low-temperature limit at mean degree $c=2.0$. The simulation conditions of population dynamics are the same as in Fig. 1, and the markers are not displayed for visibility.

Figure 4

$c$ dependence of the minimum cover ratios, $x_c\left(c\right)$ and ${\tilde{x}}_c\left(c\right)$ without and with the correction field (solid and dashed lines), respectively. Small circles denote the Monte Carlo result obtained by [23]. The vertical dotted line denotes the known RS/RSB boundary of $c=e$. The inset shows $c$ dependence of the probability of nonbackbone vertices being covered, which is 1/2 without the correction field.

Figure 5

$c$ dependence of the minimum cover ratios, $x_c\left(c\right)$ and ${\tilde{x}}_c\left(c\right)$ without and with correction field (solid and dashed lines), respectively. Dotted lines denote upper and lower bounds in [38].

Figure 6

Stability bound for the self-consistent equation of Eq. (18) in the low-temperature limit as a function of mean degree $c$, above which the stability condition is satisfied. The dashed line is the limit of the RS solution that can be valid for $\gamma \to \infty$ [26], which will be discussed in the next section.

Figure 7

Stability bounds for the self-consistent equation (18) without damping at finite $\beta$ and mean degree $c$. The dashed line is the stability bound of the RS solution at $\gamma \to \infty$ obtained by the cavity method [26].

Figure 8

Mean-degree $c$ dependence of the divergence temperature $T_{\mathrm{c}}$ of ${\chi }_{\mathrm{SG}}$ for several $\gamma$, obtained by the population dynamics methods. Numerical errors are similar to the width of curves, and markers are omitted for visibility.

Figure 9

$\gamma$ dependence of the divergence temperature $T_{\mathrm{c}}$ of ${\chi }_{\mathrm{SG}}$ for $c=5.0$ (cross marker) and 15 (plus). The vertical line represents the boundary between the feasible and infeasible regions at $T=0$. Numerical errors are within the width of the curves.

Figure 10

Finite-size scaling plots of the spin-glass susceptibility at $\gamma \to \infty$ (left) and $\gamma =0.505$ (right) for ER random graph with mean degree $c=15$. The left and right plots are obtained with $T_{\mathrm{c}}=0.275$ and 0.219, and with critical exponents as $(x,y)=(1.06\left(2\right),2.19\left(4\right))$ and $(0.61\left(4\right),2.20\left(5\right))$, respectively.

Figure 11

Graph-averaged overlap distribution $P\left(q\right)$ at several $\beta \mathrm{s}$ for $N=512$ with mean degree $c=15$ and $\gamma =1.1$. $P\left(q\right)$ is ordered by $\beta$ from left to right, $\beta =0.1,0.28,0.62,1.29,2.37$, and 3.06 below ${\beta }_c=3.89$, and $3.98,5.64$, and 10.0 above ${\beta }_{\mathrm{c}}$. The results are averaged over 200 random graphs, and the error bars evaluated by the bootstrap method are plotted only at $\beta =10$ for visibility.

Figure 12

System-size $N$ dependence of the graph-averaged overlap distributions $P\left(q\right)$ for mean degree $c=15$ and $\gamma =1.1$. Temperatures are at (a) $\beta =1.05$, (b) 3.06, (c) 3.98, and (d) 10.0, and (c) and (d) are above the inverse transition temperature ${\beta }_c=3.89$. The average of the random graphs is taken at approximately 200.

Figure 13

Graph-averaged overlap distribution $P\left(q\right)$ (solid line) and $P_G\left(q\right)$ for two sample graph instances (dashed and dotted lines) for $N=512$ with mean degree $c=15$ and $\gamma =1.1$. Temperatures are at (a) $\beta =1.05$, (b) 3.06, (c) 3.98, and (d) 10.0. Temperatures in (c) and (d) are above the inverse transition temperature ${\beta }_c=3.89$.

Figure 14

Dynamical mappings for the population dynamics at the low-temperature limit in the feasible region. The (blue) thick line represents the mapping, $h^{\prime }=1-K\left(h\right)$, for $l=1$, and the (red) horizontal and vertical lines represent the paths that $h_i^{\prime }$ is generated from $\left\{h_j\right\}$. The cycles shown by the dotted lines eventually disappear because their population is not supplied by other $h_j$, and then values other than $h_j=0$ and 1 disappear in the range $0\le h\le 1$.

Figure 15

Dynamical mappings for the population dynamics at the low-temperature limit in the infeasible region. There exists a stable cycle of $\gamma \leftrightarrow 1-\gamma$ whose population is provided from other $h_j^{\prime }\mathrm{s}$. Then there are innumerable secondary $h_i^{\prime }$ derived from their sums. Any value other than $h=1-l-l^{\prime }\gamma ,l,l^{\prime }\in \mathcal{Z}$ eventually vanishes for the same reason as the dotted cycles in Fig. 14.