Given on graph $G = (V, E)$ and an integer $N \ge 0$, $N-MVC$ is a minimal set of vertices such that each edge can be reached from some vertex in $N-MVC$ via at most $N$ edges.
An article named "Approximation algorithms for the L-distance vertex cover problem" by Chen Qiaoyun and Zhao Liang suggested that this problem can be somehow reduced to Set Covering problem. I'm asking for general advice on how such reductions can be performed and what's the theory behind them.
Any advice would be appreciated.
Best Answer
The idea is the same as in the $N=1$ case. You want to cover the edge set of the graph. For $N=1$, the covering sets are the stars in the graph; that is, for each vertex, you take the set of outgoing edges from that vertex. A vertex cover in the graph is essentially the same thing as a cover of the edge set using these sets.
What sets should you take instead if $N > 1$?