Minimum Consistent Subset in Trees and Interval Graphs

In the Minimum Consistent Subset (MCS) problem, we are presented with a connected simple undirected graph $G=(V,E)$, consisting of a vertex set V of size n and an edge set E. Each vertex in V is assigned a color from the set \1,2,…, c\. The objective is to determine a subset V' ⊆ V with minimum possible cardinality, such that for every vertex v ∈ V, at least one of its nearest neighbors in $V'$ (measured in terms of the hop distance) shares the same color as v. The decision problem, indicating whether there exists a subset $V'$ of cardinality at most l for some positive integer l, is known to be NP-complete even for planar graphs. In this paper, we establish that the MCS problem for trees, when the number of colors c is considered an input parameter, is NP-complete. We propose a fixed-parameter tractable (FPT) algorithm for MCS on trees running in O(2⁶ᶜn⁶) time, significantly improving the currently best-known algorithm whose running time is O(2⁴ᶜn²ᶜ⁺³). In an effort to comprehensively understand the computational complexity of the MCS problem across different graph classes, we extend our investigation to interval graphs. We show that it remains NP-complete for interval graphs, thus enriching graph classes where MCS remains intractable.