TY - JOUR
AU - Biniaz, Ahmad
AU - Khamsepour, Parham
PY - 2024/05/16
Y2 - 2024/11/08
TI - The Minimum Consistent Spanning Subset Problem on Trees
JF - Journal of Graph Algorithms and Applications
JA - JGAA
VL - 28
IS - 1
SE -
DO - 10.7155/jgaa.v28i1.2929
UR - https://jgaa.info/index.php/jgaa/article/view/2929
SP - 81-93
AB - <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>
ER -