2025/12/14 by Aritra Banik, Banik, Aritra, Mano Prakash Parthasarathi +7
Computer Science · #Advanced Clustering Algorithms Research #Advanced Graph Neural Networks #Computational Geometry (cs.CG) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Machine Learning and Data Classification
paper · pdf · doi:10.48550/arxiv.2512.12860
openalex publication_date 2025/12/14 · openalex created_date 2025/12/17 · openalex updated_date 2026/07/28
The Minimum Consistent Subset (MCS) problem arises naturally in the context of supervised clustering and instance selection. In supervised clustering, one aims to infer a meaningful partitioning of data using a small labeled subset. However, the sheer volume of training data in modern applications poses a significant computational challenge. The MCS problem formalizes this goal: given a labeled dataset X in a metric space, the task is to compute a smallest subset S ⊆ X such that every point in X shares its label with at least one of its nearest neighbors in S. Recently, the MCS problem has been extended to graph metrics, where distances are defined by shortest paths. Prior work has shown that MCS remains NP-hard even on simple graph classes like trees, though an algorithm with runtime O(26c ⋅ n6) is known for trees, where c is the number of colors and n the number of vertices. This raises the challenge of identifying graph classes that admit algorithms efficient in both n and c. In this work, we study the Minimum Consistent Subset problem on graphs, focusing on two well-established measures: the vertex cover number (vc) and the neighborhood diversity (nd). We develop an algorithm with running time vcO(vc)\cdotPoly(n,c), and another algorithm with runtime ndO(nd)\cdotPoly(n,c). In the language of parameterized complexity, this implies that MCS is fixed-parameter tractable (FPT) parameterized by the vertex cover number and the neighborhood diversity. Notably, our algorithms remain efficient for arbitrarily many colors, as their complexity is polynomially dependent on the number of colors.