2023/03/04 by Bubai Manna, Manna, Bubai, Bodhayan Roy +1
Computer Science · #Advanced Graph Theory Research #Computational Geometry (cs.CG) #FOS: Computer and information sciences
paper · pdf · doi:10.48550/arxiv.2303.02337
openalex publication_date 2023/03/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
For a graph G = (V,E) where each vertex is coloured by one of k colours, consider a subset C of V such that for each vertex v in V\C, its set of nearest neighbours in C contains at least one vertex of the same colour as v. Such a C is called a consistent subset (CS). Computing a consistent subset of the minimum size is called the Minimum Consistent Subset problem (MCS). MCS is known to be NP-complete for planar graphs. We propose a polynomial-time algorithm for finding a minimum consistent subset of a k-chromatic spider graph when k is a constant. We also show MCS remains NP-complete on trees.