Minimum Strict Consistent Subset in Paths, Spiders, Combs and Trees
<|reference_start|>Minimum Strict Consistent Subset in Paths, Spiders, Combs and Trees: Let G be a simple connected graph with vertex set V(G) and edge set E(G. Each vertex of V(G) is colored by a color from the set of colors {c_1, c_2,\dots, c_{\alpha}}. We take a subset S of V(G), such that for every vertex v in V(G)\S, at least one vertex of the same color is present in its set of nearest neighbors in S. We refer to such an S as a consistent subset (CS). The Minimum Consistent Subset (MCS) problem is the computation of a consistent subset of the minimum cardinality. It is established that MCS is NP-complete for general graphs, including planar graphs. The strict consistent subset is a variant of consistent subset problems. We take a subset S^{\prime} of V(G), such that for every vertex v in V(G)\S^{\prime}, all the vertices in its set of nearest neighbors in S^{\prime} have the same color as that of v. We refer to such an S^{\prime} as a strict consistent subset (SCS). The Minimum Strict Consistent Subset (MSCS) problem is the computation of a strict consistent subset of the minimum cardinality.   We demonstrate that MSCS is NP-hard for general graphs using a reduction from dominating set problems. We construct a 2-approximation algorithm and a polynomial-time algorithm in trees. Lastly, we conclude the faster polynomial-time algorithms in paths, spiders, and combs.<|reference_end|>
@article{manna2024minimum,
    title={Minimum Strict Consistent Subset in Paths, Spiders, Combs and Trees},
    author={Bubai Manna},
    journal={arXiv preprint arXiv:2405.18569},
    year={2024},
    archivePrefix={arXiv},
    eprint={2405.18569},
    primaryClass={cs.CG}
}