Approximation Algorithms
	l Computing FAIL(p) is #P complete [V] l Exact algorithm seems unlikely l Approximation scheme » Given G, p, e, outputs e-approximation » May be randomized: – succeed with high probability » Fully polynomial (FPRAS) if runtime is polynomial in n, 1/e