The Minimum Consistent Spanning Subset Problem on Trees

Abstract

Given a vertex-colored edge-weighted graph, the minimum consistent subset (MCS) problem asks for a minimum subset $S$ of vertices such that every vertex $v\notin S$ has the same color as its nearest neighbor in $S$.
This problem is NP-complete. A recent result of Dey, Maheshwari, and Nandy (2021) gives a polynomial-time algorithm for the MCS problem on two-colored trees. A block is a maximal connected set of vertices of the same color.
We introduce a variant of the MCS problem, namely the minimum consistent spanning subset problem, for which we require the set $S$ to contain a vertex from every block of the graph such that every vertex $v\notin S$ has a nearest neighbor in $S$ that is in the same block as $v$.
We observe that this problem is NP-hard on general graphs. We present a polynomial-time algorithm for this problem on trees.