New Complexity and Algorithmic Bounds for Minimum Consistent Subsets

Abstract

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,\dots ,c\}$. The objective is to determine a subset $V^{\prime }\subseteq V$ with minimum possible cardinality, such that for every vertex $v\in V$, at least one of its nearest neighbors in $V^{\prime }$ (measured in terms of the hop distance) shares the same color as $v$. A variant of MCS is the minimum strict consistent subset (MSCS) in which instead of requiring at least one nearest neighbor of $v$, all the nearest neighbors of $v$ in $V^{\prime }$ must have the same color as $v$. The decision version for MCS problem as well as for MSCS problem asks whether there exists a subset $V^{\prime }$ of cardinality at most $l$ for some positive integer $l$. The MCS problem is known to be NP-complete 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. We also show that the MSCS problem is log-APX-hard on general graphs and NP-complete on planar graphs.

A preliminary version of this article appeared in the Proceedings of the 44th Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2024)