Counting and Sampling RANDOM GENERATION OF COMBINATORIAL STRUCTURES FROM A UNIFORM DISTRIBUTION LGORITHMS Mark R.JERRUM Department f Computer Science,Universiry of Edinburgh,Edinburgh EH93 Unied Kingdom Leslie G.VALIANT* Aiken Computation Laboratory,Harard Universiry,Cambridge,MA 02138,U.S.A V灯jayV.VAZIRANI* Computer Scence Department,Comell Universiry,Ithac,NY 14853,U.S.A. [Jerrum-Valiant-Vazirani86]: (For self-reducible problems) approx.counting (approx.,exact)sampling is tractable is tractableCounting and Sampling approx. counting is tractable (approx., exact) sampling is tractable (For self-reducible problems) [Jerrum-Valiant-Vazirani ’86]: