BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Hai-Jun Zhou

Hai-Jun Zhou appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
cond-mat.dis-nnphysics.soc-phcond-mat.stat-mechComputational ComplexityComputer Science and Game TheoryNeurons and CognitionBiological Physicscs.CYSocial and Information NetworksArtificial IntelligenceComputation and LanguageComputer VisionData Structures and AlgorithmsDiscrete MathematicsInformation RetrievalInformation TheoryMachine Learningmath.ITnlin.AOphysics.comp-phPopulations and Evolution

Catalog footprint

What is connected

27works
21topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

27 published item(s)

preprint2022arXiv

Cycle-tree guided attack of random K-core: Spin glass model and efficient message-passing algorithm

The K-core of a graph is the maximal subgraph within which each vertex is connected to at least K other vertices. It is a fundamental network concept for understanding threshold cascading processes with a discontinuous percolation transition. A minimum attack set contains the smallest number of vertices whose removal induces complete collapse of the K-core. Here we tackle this prototypical optimal initial-condition problem from the spin-glass perspective of cycle-tree maximum packing and propose a cycle-tree guided attack (CTGA) message-passing algorithm. The good performance and time efficiency of CTGA are verified on the regular random and Erdös-Rényi random graph ensembles. Our central idea of transforming a long-range correlated dynamical process to static structural patterns may also be instructive to other hard optimization and control problems.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Lateral predictive coding revisited: Internal model, symmetry breaking, and response time

Predictive coding is a promising theoretical framework in neuroscience for understanding information transmission and perception. It posits that the brain perceives the external world through internal models and updates these models under the guidance of prediction errors. Previous studies on predictive coding emphasized top-down feedback interactions in hierarchical multi-layered networks but largely ignored lateral recurrent interactions. We perform analytical and numerical investigations in this work on the effects of single-layer lateral interactions. We consider a simple predictive response dynamics and run it on the MNIST dataset of hand-written digits. We find that learning will generally break the interaction symmetry between peer neurons, and that high input correlation between two neurons does not necessarily bring strong direct interactions between them. The optimized network responds to familiar input signals much faster than to novel or random inputs, and it significantly reduces the correlations between the output states of pairs of neurons.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Hysteresis in anesthesia and recovery: Experimental observation and dynamical mechanism

The dynamical mechanism underlying the processes of anesthesia-induced loss of consciousness and recovery is key to gaining insights into the working of the nervous system. Previous experiments revealed an asymmetry between neural signals during the anesthesia and recovery processes. Here we obtain experimental evidence for the hysteresis loop and articulate the dynamical mechanism based on percolation on multilayer complex networks with self-similarity. Model analysis reveals that, during anesthesia, the network is able to maintain its neural pathways despite the loss of a substantial fraction of the edges. A predictive and potentially testable result is that, in the forward process of anesthesia, the average shortest path and the clustering coefficient of the neural network are markedly smaller than those associated with the recovery process. This suggests that the network strives to maintain certain neurological functions by adapting to a relatively more compact structure in response to anesthesia.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Maximally flexible solutions of a random $K$-satisfiability formula

Random $K$-satisfiability ($K$-SAT) is a paradigmatic model system for studying phase transitions in constraint satisfaction problems and for developing empirical algorithms. The statistical properties of the random $K$-SAT solution space have been extensively investigated, but most earlier efforts focused on solutions that are typical. Here we consider maximally flexible solutions which satisfy all the constraints only using the minimum number of variables. Such atypical solutions have high internal entropy because they contain a maximum number of null variables which are completely free to choose their states. Each maximally flexible solution indicates a dense region of the solution space. We estimate the maximum fraction of null variables by the replica-symmetric cavity method, and implement message-passing algorithms to construct maximally flexible solutions for single $K$-SAT instances.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Solving Statistical Mechanics on Sparse Graphs with Feedback Set Variational Autoregressive Networks

We propose a method for solving statistical mechanics problems defined on sparse graphs. It extracts a small Feedback Vertex Set (FVS) from the sparse graph, converting the sparse system to a much smaller system with many-body and dense interactions with an effective energy on every configuration of the FVS, then learns a variational distribution parameterized using neural networks to approximate the original Boltzmann distribution. The method is able to estimate free energy, compute observables, and generate unbiased samples via direct sampling without auto-correlation. Extensive experiments show that our approach is more accurate than existing approaches for sparse spin glasses. On random graphs and real-world networks, our approach significantly outperforms the standard methods for sparse systems such as the belief-propagation algorithm; on structured sparse systems such as two-dimensional lattices our approach is significantly faster and more accurate than recently proposed variational autoregressive networks using convolution neural networks.

0 citations0 reviewsNo code linkedOpen access
preprint2019arXiv

Covering Problems and Core Percolations on Hypergraphs

Covering problems are classical computational problems concerning whether a certain combinatorial structure 'covers' another. For example, the minimum vertex covering problem aims to find the smallest set of vertices in a graph so that each edge is incident to at least one vertex in that set. Interestingly, the computational complexity of the minimum vertex covering problem in graphs is closely related to the core percolation problem, where the core is a special subgraph obtained by the greedy leaf removal procedure. Here, by generalizing the greedy leaf removal procedure in graphs to hypergraphs, we introduce two generalizations of core percolation in graphs to hypergraphs, related to the minimum hyperedge cover problem and the minimum vertex cover problem on hypergraphs, respectively. We offer analytical solutions of these two core percolations for random hypergraphs with arbitrary vertex degree and hyperedge cardinality distributions. We also compute these two cores in several real-world hypergraphs, finding that they tend to be much smaller than their randomized counterparts. This result suggests that both the minimum hyperedge cover problem and the minimum vertex cover problem in those real-world hypergraphs can actually be solved in polynomial time. Finally, we map the minimum dominating set problem in graphs to the minimum hyperedge cover problem in hypergraphs. We show that our generalized greedy leaf removel procedure significantly outperforms the state-of-the-art method in solving the minimum dominating set problem.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

A spin glass approach to the directed feedback vertex set problem

A directed graph (digraph) is formed by vertices and arcs (directed edges) from one vertex to another. A feedback vertex set (FVS) is a set of vertices that contains at least one vertex of every directed cycle in this digraph. The directed feedback vertex set problem aims at constructing a FVS of minimum cardinality. This is a fundamental cycle-constrained hard combinatorial optimization problem with wide practical applications. In this paper we construct a spin glass model for the directed FVS problem by converting the global cycle constraints into local arc constraints, and study this model through the replica-symmetric (RS) mean field theory of statistical physics. We then implement a belief propagation-guided decimation (BPD) algorithm for single digraph instances. The BPD algorithm slightly outperforms the simulated annealing algorithm on large random graph instances. The predictions of the RS mean field theory are noticeably lower than the BPD results, possibly due to its neglect of cycle-caused long range correlations.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Generalized minimum dominating set and application in automatic text summarization

For a graph formed by vertices and weighted edges, a generalized minimum dominating set (MDS) is a vertex set of smallest cardinality such that the summed weight of edges from each outside vertex to vertices in this set is equal to or larger than certain threshold value. This generalized MDS problem reduces to the conventional MDS problem in the limiting case of all the edge weights being equal to the threshold value. We treat the generalized MDS problem in the present paper by a replica-symmetric spin glass theory and derive a set of belief-propagation equations. As a practical application we consider the problem of extracting a set of sentences that best summarize a given input text document. We carry out a preliminary test of the statistical physics-inspired method to this automatic text summarization problem.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Identifying optimal targets of network attack by belief propagation

For a network formed by nodes and undirected links between pairs of nodes, the network optimal attack problem aims at deleting a minimum number of target nodes to break the network down into many small components. This problem is intrinsically related to the feedback vertex set problem that was successfully tackled by spin glass theory and an associated belief propagation-guided decimation (BPD) algorithm [H.-J. Zhou, Eur. Phys. J. B 86 (2013) 455]. In the present work we apply the BPD alrogithm (which has approximately linear time complexity) to the network optimal attack problem, and demonstrate that it has much better performance than a recently proposed Collective Information algorithm [F. Morone and H. A. Makse, Nature 524 (2015) 63--68] for different types of random networks and real-world network instances. The BPD-guided attack scheme often induces an abrupt collapse of the whole network, which may make it very difficult to defend.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Loop-corrected belief propagation for lattice spin models

Belief propagation (BP) is a message-passing method for solving probabilistic graphical models. It is very successful in treating disordered models (such as spin glasses) on random graphs. On the other hand, finite-dimensional lattice models have an abundant number of short loops, and the BP method is still far from being satisfactory in treating the complicated loop-induced correlations in these systems. Here we propose a loop-corrected BP method to take into account the effect of short loops in lattice spin models. We demonstrate, through an application to the square-lattice Ising model, that loop-corrected BP improves over the naive BP method significantly. We also implement loop-corrected BP at the coarse-grained region graph level to further boost its performance.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

On one-step replica symmetry breaking in the Edwards-Anderson spin glass model

We consider a one-step replica symmetry breaking description of the Edwards-Anderson spin glass model in 2D. The ingredients of this description are a Kikuchi approximation to the free energy and a second-level statistical model built on the extremal points of the Kikuchi approximation, which are also fixed points of a Generalized Belief Propagation (GBP) scheme. We show that a generalized free energy can be constructed where these extremal points are exponentially weighted by their Kikuchi free energy and a Parisi parameter $y$, and that the Kikuchi approximation of this generalized free energy leads to second-level, one-step replica symmetry breaking (1RSB), GBP equations. We then proceed analogously to Bethe approximation case for tree-like graphs, where it has been shown that 1RSB Belief Propagation equations admit a Survey Propagation solution. We discuss when and how the one-step-replica symmetry breaking GBP equations that we obtain also allow a simpler class of solutions which can be interpreted as a class of Generalized Survey Propagation equations for the single instance graph case.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Optimal Disruption of Complex Networks

The collection of all the strongly connected components in a directed graph, among each cluster of which any node has a path to another node, is a typical example of the intertwining structure and dynamics in complex networks, as its relative size indicates network cohesion and it also composes of all the feedback cycles in the network. Here we consider finding an optimal strategy with minimal effort in removal arcs (for example, deactivation of directed interactions) to fragment all the strongly connected components into tree structure with no effect from feedback mechanism. We map the optimal network disruption problem to the minimal feedback arc set problem, a non-deterministically polynomial hard combinatorial optimization problem in graph theory. We solve the problem with statistical physical methods from spin glass theory, resulting in a simple numerical method to extract sub-optimal disruption arc sets with significantly better results than a local heuristic method and a simulated annealing method both in random and real networks. Our results has various implications in controlling and manipulation of real interacted systems.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Serving by local consensus in the public service location game

We discuss the issue of distributed and cooperative decision-making in a network game of public service location. Each node of the network can choose to be a provider of service which is accessible to the provider itself and also to all the neighboring nodes. A node may also choose only to be a consumer, and then it has to pay a tax, and the collected tax is evenly distributed to all the service providers to remedy their cost. If nodes do not communicate with each other but make individual best-response decisions, the system will be trapped in an inefficient situation of high tax level. In this work we investigate a decentralized local-consensus selection mechanism, according to which nodes in need of service recommend their neighbors of highest local impact as candidate servers, and a node may become a server only if all its non-server neighbors give their assent. We demonstrate that this local-consensus mechanism, although only involving information exchange among neighboring nodes, leads to socially efficient solutions with tax level approaching the lowest possible value. Our results may help in understanding and improving collective problem-solving in various networked social systems and robotic systems.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Spin glass phase transitions in the random feedback vertex set problem

A feedback vertex set (FVS) of an undirected graph contains vertices from every cycle of this graph. Constructing a FVS of sufficiently small cardinality is very difficult in the worst cases, but for random graphs this problem can be efficiently 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 the local stability and the phase transition properties of this spin glass model on random graphs. For both regular random graphs and Erdös-Rényi graphs we determine the inverse temperature $β_l$ at which the replica-symmetric mean field theory loses its local stability, the inverse temperature $β_d$ of the dynamical (clustering) phase transition, and the inverse temperature $β_c$ of the static (condensation) phase transition. We find that $β_{l}$, $β_{d}$, and $β_c$ change with the (mean) vertex degree in a non-monotonic way; $β_d$ is distinct from $β_c$ for regular random graphs of vertex degrees $K\geq 64$, while $β_d$ are always identical to $β_c$ for Erdös-Rényi graphs (at least up to mean vertex degree $c=512$). We also compute the minimum FVS size of regular random graphs through the zero-temperature first-step replica-symmetry-breaking mean field theory and reach good agreement with the results obtained on single graph instances by the belief propagation-guided decimation algorithm. Taking together, this paper presents a systematic theoretical study on the energy landscape property of a spin glass system with global cycle constraints.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Spike Pattern Structure Influences Efficacy Variability under STDP and Synaptic Homeostasis

In neural systems, synaptic plasticity is usually driven by spike trains. Due to the inherent noises of neurons, synapses and networks, spike trains typically exhibit externally uncontrollable variability such as spatial heterogeneity and temporal stochasticity, resulting in variability of synapses, which we call efficacy variability. Spike patterns with the same population rate but inducing different efficacy variability may result in neuronal networks with sharply different structures and functions. However, how the variability of spike trains influences the efficacy variability remains unclear. Here, we systematically study this influence when spike patterns possess four aspects of statistical features, i.e. synchronous firing, auto-temporal structure, heterogeneity of rates and heterogeneity of cross-correlations, under spike-timing dependent plasticity (STDP) after dynamically bounding the mean strength of plastic synapses into or out of a neuron (synaptic homeostasis). We then show the functional importance of efficacy variability on the encoding and maintenance of connection patterns and on the early development of primary visual systems driven by retinal waves. We anticipate our work brings a fresh perspective to the understanding of the interaction between synaptic plasticity and dynamical spike patterns in functional processes of neural systems.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Statistical Mechanics of the Minimum Dominating Set Problem

The minimum dominating set problem has wide applications in network science and related fields. It consists of assembling a node set of global minimum size such that any node of the network is either in this set or is adjacent to at least one node of this set. Although this is a difficult optimization problem in general, we show it can be exactly solved by a generalized leaf-removal process if the network contains no core. If the network has an extensive core, we estimate the size of minimum dominating sets by a mean-field theory and implement a belief-propagation algorithm to obtain near-optimal solutions. Our algorithms also perform well on real-world network instances.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

The Directed Dominating Set Problem: Generalized Leaf Removal and Belief Propagation

A minimum dominating set for a digraph (directed graph) is a smallest set of vertices such that each vertex either belongs to this set or has at least one parent vertex in this set. We solve this hard combinatorial optimization problem approximately by a local algorithm of generalized leaf removal and by a message-passing algorithm of belief propagation. These algorithms can construct near-optimal dominating sets or even exact minimum dominating sets for random digraphs and also for real-world digraph instances. We further develop a core percolation theory and a replica-symmetric spin glass theory for this problem. Our algorithmic and theoretical results may facilitate applications of dominating sets to various network problems involving directed interactions.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Optimal cooperation-trap strategies for the iterated Rock-Paper-Scissors game

In an iterated non-cooperative game, if all the players act to maximize their individual accumulated payoff, the system as a whole usually converges to a Nash equilibrium that poorly benefits any player. Here we show that such an undesirable destiny is avoidable in an iterated Rock-Paper-Scissors (RPS) game involving two players X and Y. Player X has the option of proactively adopting a cooperation-trap strategy, which enforces complete cooperation from the rational player Y and leads to a highly beneficial as well as maximally fair situation to both players. That maximal degree of cooperation is achievable in such a competitive system with cyclic dominance of actions may stimulate creative thinking on how to resolve conflicts and enhance cooperation in human societies.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Social cycling and conditional responses in the Rock-Paper-Scissors game

How humans make decisions in non-cooperative strategic interactions is a challenging question. For the fundamental model system of Rock-Paper-Scissors (RPS) game, classic game theory of infinite rationality predicts the Nash equilibrium (NE) state with every player randomizing her choices to avoid being exploited, while evolutionary game theory of bounded rationality in general predicts persistent cyclic motions, especially for finite populations. However, as empirical studies on human subjects have been relatively sparse, it is still a controversial issue as to which theoretical framework is more appropriate to describe decision making of human subjects. Here we observe population-level cyclic motions in a laboratory experiment of the discrete-time iterated RPS game under the traditional random pairwise-matching protocol. The cycling direction and frequency are not sensitive to the payoff parameter a. This collective behavior contradicts with the NE theory but it is quantitatively explained by a microscopic model of win-lose-tie conditional response without any adjustable parameter. Our theoretical calculations reveal that this new strategy may offer higher payoffs to individual players in comparison with the NE mixed strategy, suggesting that high social efficiency is achievable through optimized conditional response.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Solving the undirected feedback vertex set problem by local search

An undirected graph consists of a set of vertices and a set of undirected edges between vertices. Such a graph may contain an abundant number of cycles, then a feedback vertex set (FVS) is a set of vertices intersecting with each of these cycles. Constructing a FVS of cardinality approaching the global minimum value is a optimization problem in the nondeterministic polynomial-complete complexity class, therefore it might be extremely difficult for some large graph instances. In this paper we develop a simulated annealing local search algorithm for the undirected FVS problem. By defining an order for the vertices outside the FVS, we replace the global cycle constraints by a set of local vertex constraints on this order. Under these local constraints the cardinality of the focal FVS is then gradually reduced by the simulated annealing dynamical process. We test this heuristic algorithm on large instances of Erödos-Renyi random graph and regular random graph, and find that this algorithm is comparable in performance to the belief propagation-guided decimation algorithm.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Statistical physics of hard combinatorial optimization: The vertex cover problem

Typical-case computation complexity is a research topic at the boundary of computer science, applied mathematics, and statistical physics. In the last twenty years the replica-symmetry-breaking mean field theory of spin glasses and the associated message-passing algorithms have greatly deepened our understanding of typical-case computation complexity. In this paper we use the vertex cover problem, a basic nondeterministic-polynomial (NP)-complete combinatorial optimization problem of wide application, as an example to introduce the statistical physical methods and algorithms. We do not go into the technical details but emphasize mainly the intuitive physical meanings of the message-passing equations. A nonfamiliar reader shall be able to understand to a large extent the physics behind the mean field approaches and to adjust them in solving other optimization problems.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Topological invariant tensor renormalization group method for spin glasses

Tensor renormalization group method (TRG) is a real space renormalization group approach. It has been successfully applied to both classical and quantum systems. In this paper, we study a disordered and frustrated system, the two-dimensional Edward-Anderson model, by a new topological invariant TRG scheme. We propose an approach to calculate the local magnetizations and nearest pair correlations simultaneously. The Nishimori multi-critical point predicted by the topological invariant TRG agrees well with the recent Monte-Carlo results. The TRG schemes outperform the mean field methods on the calculation of the partition function. We notice that it maybe obtain a negative partition function at sufficiently low temperatures. However, the negative contribution can be neglected if the systems is large enough. This topological invariant TRG can also be used to study three-dimensional spin glass systems.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Cycle frequency in standard Rock-Paper-Scissors games: Evidence from experimental economics

The Rock-Paper-Scissors (RPS) game is a widely used model system in game theory. Evolutionary game theory predicts the existence of persistent cycles in the evolutionary trajectories of the RPS game, but experimental evidence has remained to be rather weak. In this work we performed laboratory experiments on the RPS game and analyzed the social-state evolutionary trajectories of twelve populations of N=6 players. We found strong evidence supporting the existence of persistent cycles. The mean cycling frequency was measured to be $0.029 \pm 0.009$ period per experimental round. Our experimental observations can be quantitatively explained by a simple non-equilibrium model, namely the discrete-time logit dynamical process with a noise parameter. Our work therefore favors the evolutionary game theory over the classical game theory for describing the dynamical behavior of the RPS game.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Inducing Effect on the Percolation Transition in Complex Networks

Percolation theory concerns the emergence of connected clusters that percolate through a networked system. Previous studies ignored the effect that a node outside the percolating cluster may actively induce its inside neighbours to exit the percolating cluster. Here we study this inducing effect on the classical site percolation and K-core percolation, showing that the inducing effect always causes a discontinuous percolation transition. We precisely predict the percolation threshold and core size for uncorrelated random networks with arbitrary degree distributions. For low-dimensional lattices the percolation threshold fluctuates considerably over realizations, yet we can still predict the core size once the percolation occurs. The core sizes of real-world networks can also be well predicted using degree distribution as the only input. Our work therefore provides a theoretical framework for quantitatively understanding discontinuous breakdown phenomena in various complex systems.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Simplifying Generalized Belief Propagation on Redundant Region Graphs

The cluster variation method has been developed into a general theoretical framework for treating short-range correlations in many-body systems after it was first proposed by Kikuchi in 1951. On the numerical side, a message-passing approach called generalized belief propagation (GBP) was proposed by Yedidia, Freeman and Weiss about a decade ago as a way of computing the minimal value of the cluster variational free energy and the marginal distributions of clusters of variables. However the GBP equations are often redundant, and it is quite a non-trivial task to make the GBP iteration converges to a fixed point. These drawbacks hinder the application of the GBP approach to finite-dimensional frustrated and disordered systems. In this work we report an alternative and simple derivation of the GBP equations starting from the partition function expression. Based on this derivation we propose a natural and systematic way of removing the redundance of the GBP equations. We apply the simplified generalized belief propagation (SGBP) equations to the two-dimensional and the three-dimensional ferromagnetic Ising model and Edwards-Anderson spin glass model. The numerical results confirm that the SGBP message-passing approach is able to achieve satisfactory performance on these model systems. We also suggest that a subset of the SGBP equations can be neglected in the numerical iteration process without affecting the final results.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Spin glass approach to the feedback vertex set problem

A feedback vertex set (FVS) of an undirected graph is a set of vertices that contains at least one vertex of each cycle of the graph. The feedback vertex set problem consists of constructing a FVS of size less than a certain given value. This combinatorial optimization problem has many practical applications, but it is in the nondeterministic polynomial-complete class of worst-case computational complexity. In this paper we define a spin glass model for the FVS problem and then study this model on the ensemble of finite-connectivity random graphs. In our model the global cycle constraints are represented through the local constraints on all the edges of the graph, and they are then treated by distributed message-passing procedures such as belief propagation. Our belief propagation-guided decimation algorithm can construct nearly optimal feedback vertex sets for single random graph instances and regular lattices. We also design a spin glass model for the FVS problem on a directed graph. Our work will be very useful for identifying the set of vertices that contribute most significantly to the dynamical complexity of a large networked system.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Witness of unsatisfiability for a random 3-satisfiability formula

The random 3-satisfiability (3-SAT) problem is in the unsatisfiable (UNSAT) phase when the clause density $α$ exceeds a critical value $α_s \approx 4.267$. However, rigorously proving the unsatisfiability of a given large 3-SAT instance is extremely difficult. In this paper we apply the mean-field theory of statistical physics to the unsatisfiability problem, and show that a specific type of UNSAT witnesses (Feige-Kim-Ofek witnesses) can in principle be constructed when the clause density $α> 19$. We then construct Feige-Kim-Ofek witnesses for single 3-SAT instances through a simple random sampling algorithm and a focused local search algorithm. The random sampling algorithm works only when $α$ scales at least linearly with the variable number $N$, but the focused local search algorithm works for clause densty $α> c N^{b}$ with $b \approx 0.59$ and prefactor $c \approx 8$. The exponent $b$ can be further decreased by enlarging the single parameter $S$ of the focused local search algorithm.

0 citations0 reviewsNo code linkedOpen access