The Minimum Consistent Spanning Subset Problem on Trees
Ahmad Biniaz, Parham Khamsepour · 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.