Finding smallest subset of vertices - backtracking?

Question

let E - set of all edges in graph G The problem is to find the smallest subset S of vertices from G, which satisfies condition: sum of all outgoing edges from each vertex in S = E

In other words: Edges are streets and we can place street lamps on the vertices. If we place a street lamp on a vertex - all outgoing streets from this vertex are lightened. How to find the cheapes way to make all streets lightened?

Is there something better than backtracking?

Answer 1

It is an np-complete problem. But as always there are many near optimal solutions. Try this one