An Approximation Algorithm for Graph Label Selection

Josia John, Simon Meierhans, Maximilian Probst Gutenberg

In the graph label selection problem, one is given an $n$-vertex graph and a budget $k$, and seeks to select $k$ vertices whose labels enable accurate prediction of the labels on t…