@article{Biniaz_Khamsepour_2024, title={The Minimum Consistent Spanning Subset Problem on Trees}, volume={28}, url={https://jgaa.info/index.php/jgaa/article/view/2929}, DOI={10.7155/jgaa.v28i1.2929}, abstractNote={<pre>Given a vertex-colored edge-weighted graph, the <em>minimum consistent subset</em> (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$. <br>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 <em>block</em> is a maximal connected set of vertices of the same color. <br>We introduce a variant of the MCS problem, namely the <em>minimum consistent spanning subset</em> 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$. <br>We observe that this problem is NP-hard on general graphs. We present a polynomial-time algorithm for this problem on trees.</pre>}, number={1}, journal={Journal of Graph Algorithms and Applications}, author={Biniaz, Ahmad and Khamsepour, Parham}, year={2024}, month={May}, pages={81–93} }