English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools annual

Global: Zendy Free Plan

Global: Zendy Tools monthly

Global: Zendy Plus monthly

A feedback vertex set (FVS) of an undirected graph contains vertices fromevery cycle of this graph. Constructing a FVS of sufficiently small cardinalityis very difficult in the worst cases, but for random graphs this problem can beefficiently solved after converting it into an appropriate spin glass model[H.-J. Zhou, Eur. Phys. J. B 86 (2013) 455]. In the present work we study thelocal stability and the phase transition properties of this spin glass model onrandom graphs. For both regular random graphs and Erd\"os-R\'enyi graphs wedetermine the inverse temperature $\beta_l$ at which the replica-symmetric meanfield theory loses its local stability, the inverse temperature $\beta_d$ ofthe dynamical (clustering) phase transition, and the inverse temperature$\beta_c$ of the static (condensation) phase transition. We find that$\beta_{l}$, $\beta_{d}$, and $\beta_c$ change with the (mean) vertex degree ina non-monotonic way; $\beta_d$ is distinct from $\beta_c$ for regular randomgraphs of vertex degrees $K\geq 64$, while $\beta_d$ are always identical to$\beta_c$ for Erd\"os-R\'enyi graphs (at least up to mean vertex degree$c=512$). We also compute the minimum FVS size of regular random graphs throughthe zero-temperature first-step replica-symmetry-breaking mean field theory andreach good agreement with the results obtained on single graph instances by thebelief propagation-guided decimation algorithm. Taking together, this paperpresents a systematic theoretical study on the energy landscape property of aspin glass system with global cycle constraints.

Spin glass phase transitions in the random feedback vertex set problem