Optimal vertex cover for the small-world Hanoi networks

The vertex-cover problem on the Hanoi networks HN3 and HN5 is analyzed with an exact renormalization group and parallel-tempering Monte Carlo simulations. The grand canonical partition function of the equivalent hard-core repulsive lattice-gas problem is recast first as an Ising-like canonical partition function, which allows for a closed set of renormalization-group equations. The flow of these equations is analyzed for the limit of infinite chemical potential, at which the vertex-cover problem is attained. The relevant fixed point and its neighborhood are analyzed and nontrivial results are obtained both for the coverage as well as for the ground-state entropy density, which indicates the complex structure of the solution space. Using special hierarchy-dependent operators in the renormalization group and Monte Carlo simulations, structural details of optimal configurations are revealed. These studies indicate that the optimal coverages (or packings) are not related by a simple symmetry. Using a clustering analysis of the solutions obtained in the Monte Carlo simulations, a complex solution space structure is revealed for each system size. Nevertheless, in the thermodynamic limit, the solution landscape is dominated by one huge set of very similar solutions.

Figure 1

Vertex covering for (a) a triangular lattice and (b) a Sierpinski gasket. In both cases, the optimal coverage (large dots) is imperfect (i.e., some edges possess double coverings). Yet these solutions either are unique, as for the Sierpinski gasket, or possess a finite symmetry, such as the possible translations on the triangular lattice, both cases leading to a vanishing entropy density. For both lattices it is easily seen that the asymptotic coverage is $\frac{2}{3}$. In the case of the triangular lattice, the unit cell (dashed red box) contains two vertices completely and shares half of eight vertices with other cells, i.e., it has effectively $2+\frac{8}{2}=6$ vertices of which $1+\frac{6}{2}=4$ are covered. The unit cell in the Sierpinski gasket contains $3+\frac{3}{2}$ vertices of which the three fully contained ones must be covered.

Figure 2

Depiction of the three-regular network HN3 on a semi-infinite line. Note that HN3 is planar.

Figure 3

Depiction of the planar network HN5, consisting of an HN3 core (black lines) with the addition of farther-reaching long-range edges (shaded lines). Note that sites on the lowest level of the hierarchy have degree 3, then degree 5, 7, etc, comprising a fraction of $1/2,$$1/4$, $1/8$, etc., of all sites, which makes for an average degree of 5 in this network. (There is no distinction made between black and shaded lines in our studies here.)

Figure 4

Plot of the value of ${\kappa }_i$ after the $i$th RG step for $m={10}^{-2},{10}^{-4},{10}^{-6},$ and ${10}^{-8}$ (left to right). At a length scale $\xi \left(m\right)=2^i$ with $i=-\frac{3}{4}\log {}_{2}m$, the behavior of ${\kappa }_i$ crosses over from the value at the unstable $m=0$ fixed point, ${\kappa }^{*}=1/(2^{2/3}-1)\approx 1.70$, to the stable $m=1$ ($\mu =0$) fixed point at which ${\kappa }^{*}=1$.

Figure 5

Plot of (a) the packing fraction ${\nu }_{\text{VC}}$ and (b) its entropy density $s_{\text{VC}}$ for the lattice gas problem for HN3 for the first few system sizes $N=2^k+1$ with $k=2,\dots ,5$ (top to bottom at $m=1$) as a function of $m$.

Figure 6

Plot of the packing fraction per level $2^i{\nu }_i$ on HN3 for various system sizes $N=2^k+1$ with $k=7,12,17,22$, and 26, plotted also on a relative level-scale $i/k$ at $m\to 0$. Asymptotically, in large systems, all vertices in higher levels $i$ appear to be just 50$\%$ packed (or covered), which is minimally necessary to cover the one small-world edge connecting such vertices. (Of course, each level contains half as many vertices as any preceding level and thus contributes ever less to the overall coverage.) This packing may well be random as such vertices are far separated between the higher levels. A significantly lower packing (higher coverage) is attained only at an ever small fraction of the lowest levels to account for the overall packing fraction of $\frac{3}{8}$ (coverage $\frac{5}{8}$).

Figure 7

Depiction of perfect coverings on HN3 for $k=3$. Of all seven solutions, we omitted the three obtained by reflection from these. Light-colored sites belong to the vertex cover, dark-colored sites mark particles with hard-core repulsion that prevents nearest-neighbor occupation.

Figure 8

Depiction of perfect coverings on HN3 for $k=4$. Of all 37 solutions, we omitted the 17 obtained by reflection from these. Light-colored sites belong to the vertex cover, dark-colored sites mark particles with hard-core repulsion that prevents nearest-neighbor occupation.

Figure 9

Plot of (a) the packing fraction ${\nu }_{\text{VC}}$ and (b) its entropy density $s_{\text{VC}}$ for the lattice gas problem for HN5 for the first few system sizes $N=2^k+1$ with $k=2,\dots ,5$ (with alternating behavior) as a function of $m$. Each entropy drops noticeably in the limit $m\to 0$.

Figure 10

Plot of the packing fraction per level $2^i{\nu }_i$ on HN5 for various system sizes $N=2^k+1$ with $k=7,12,17,22$, and 26, plotted also on a relative level-scale $i/k$ for $m\to 0$. In an alternating fashion, levels attain an interlaced higher or lower relative packing (lower or higher coverage), which varies very little between the levels and seems to converge to nontrivial values. Notice that the apparent closing of the gap at the highest levels results from the numerical evaluation of the RG recursions at very small but still finite chemical activity (here $m={10}^{-9}$).

Figure 11

Highest density $\nu$ of the lattice gas on Hanoi networks found in the Monte Carlo simulation as a function of system size $N$. The main plot shows HN3, the inset shows HN5. The solid lines represent fits to powers laws according to Eq. (45) (see Table ). The dashed horizontal line in the inset marks the value $1/3$.

Figure 12

Histogram of how often each configuration of highest density is sampled during the MCMCMC simulation of a $N=33$ node graph for HN3 (main plot) and HN5 (inset). The total number of sampled configurations was ${10}^6$ in both cases.

Figure 13

Distance-distance matrices for sets of $K=200$ randomly sampled highest-density configurations. The columns and rows are labeled by configurations; the order of the configurations in the rows and columns is the same and is obtained via a clustering approach (see the text). The clustering structure is visible by way of the trees (dendrograms), which are shown below the matrices. The entries of each matrix are normalized Hamming distances between different configurations, shown in grayscale (black indicates distance 0 and white indicates distance 1).

Figure 14

Cophenetic correlations in Eq. (47) as a function of system size for HN3 (main plot) and HN5 (inset). The solid line displays the function $\mathcal{K}(N)=3.25N^{-0.68}$.

Figure 15

Depiction of the graphlets associated with the sectional partition function ${\zeta }_i^l$ in Eq. (A4) during one RG step on HN3. The step consists of (a) tracing out odd-labeled variables $x_{n\pm 1}$ (taking into account the hard-core constraint relevant at this level) and (b) expressing the renormalized couplings $({\gamma }^{\prime },{\eta }^{\prime },{\kappa }^{\prime },{\lambda }^{\prime },{\Delta }^{\prime })$ in terms of the old couplings $(\gamma ,\eta ,\kappa ,\lambda ,\Delta )$. To save space, the one-point couplings (bond magnetizations [41]) $\gamma$ and $\eta$ have been omitted. These drawings summarize the calculations in Eqs. (A4) and (A5).

Figure 16

Depiction of the (exact) RG step on HN5. This step is identical to that for HN3 in Fig. 15 aside from the additional hard-core repulsive terms (a) between $x_{n\pm 2}$ and $x_n$, which is relevant for the current RG step, and (b) between $x_{n-2}$ and $x_{n+2}$, which contributes at the next level of the RG.