MINIMUM CONSISTENT SUBSET IN TREES AND INTERVAL GRAPHS

作     者：Banik, Aritra Das, Sayani Maheshwari, Anil Manna, Bubai Nandy, Subhas C. Krishna Priya, K.M. Roy, Bodhayan Roy, Sasanka Sahu, Abhishek 

作者机构：National Institute of Science Education and Research An OCC of Homi Bhabha National Institute Odisha Bhubaneswar752050 India Theoretical Computer Science The Institute of Mathematical Sciences India School of Computer Science Carleton University Canada Department of Mathematics Indian Institute of Technology Kharagpur India Advanced Computing and Microelectronics Unit Indian Statistical Institute Kolkata India 

出 版 物：《arXiv》 (arXiv)

年 卷 期：2024年

核心收录：

主　　题：Color 

摘      要：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-complete10. We propose a fixed-parameter tractable (FPT) algorithm for MCS on trees running in O(26cn6) time, significantly improving the currently best-known algorithm whose running time is O(24cn2c+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. Copyright © 2024, The Authors. All rights reserved.