Minimum Consistent Subset for Trees Revisited

Hiroki Arimura, Tatsuya Gima, Yasuaki Kobayashi +2

In a vertex-colored graph $G=(V,E)$, a subset $S\subseteq V$ is said to be consistent if every vertex has a nearest neighbor in $S$ with the same color. The problem of computin…