The Minimum Consistent Spanning Subset Problem on Trees - Biniaz, Ahmad; Khamsepour, Parham (Journal of Graph Algorithms and Applications, 2024)
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 otin 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 otin 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.