Minimum Consistent Subset in Trees and Interval Graphs
<|reference_start|>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,\ldots, c\}$. The objective is to determine a subset $V' \subseteq V$ with minimum possible cardinality, such that for every vertex $v \in 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^{6c}n^6)$ time, significantly improving the currently best-known algorithm whose running time is $O(2^{4c}n^{2c+3})$.   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.<|reference_end|>
@article{banik2024minimum,
    title={Minimum Consistent Subset in Trees and Interval Graphs},
    author={Aritra Banik, Sayani Das, Anil Maheshwari, Bubai Manna, Subhas C
  Nandy, Krishna Priya K M, Bodhayan Roy, Sasanka Roy, Abhishek Sahu},
    journal={arXiv preprint arXiv:2404.15487},
    year={2024},
    archivePrefix={arXiv},
    eprint={2404.15487},
    primaryClass={cs.CG cs.DS}
}