- input is undirected graph $G$ - outputs a set of vertices that covers (touch) every edge - optimization goal is to minimize the size of this set - special case of [[Set Cover Problem]]