Learning graph structures in discrete Markov random fields

We present a general algorithm for learning the structure of discrete Markov random fields from i.i.d. samples. The algorithm either achieves the same computational complexity or lowers the computational complexity of earlier algorithms for several cases, and provides a new low-computational complexity algorithm for the case of Ising models where the underlying graph is the Erdos-Rényi random graph G ~ G(p, c/p).