2017/11/29 by Sounaka Mishra, Mishra, Sounaka, Shijin Rajakrishnan +1
Computer Science · Mathematics · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.1712.02870
openalex publication_date 2017/11/29 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Given a graph G=(V, E) and a positive integer k, in Maximum k-Order Bounded Component Set (Max-k-OBCS), it is required to find a vertex set S ⊆ V of maximum size such that each component in the induced graph G[S] has at most k vertices. We prove that for constant k, Max-k-OBCS is hard to approximate within a factor of n1 -ε, for any ε> 0, unless P = NP. This is an improvement on the previous lower bound of √(n) for Max-2-OBCS due to Orlovich et al. We provide lower bounds on the approximability when k is not a constant as well. Max-k-OBCS can be seen as a generalization of Maximum Independent Set (Max-IS). We generalize Turán's greedy algorithm for Max-IS and prove that it approximates Max-k-OBCS within a factor of (2k - 1)d + k, where d is the average degree of the input graph G. This approximation factor is a generalization of Turán's approximation factor for Max-IS.