2020/08/20 by Saeed Akhoondian Amiri, Amiri, Saeed Akhoondian
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Interconnection Networks and Systems #cs.CC #cs.DS
paper · pdf · doi:10.48550/arxiv.2008.09008
openalex publication_date 2020/08/20 · arxiv created 2021/03/24 · arxiv updated 2021/03/25 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We show that there is no subexponential time algorithm for computing the exact solution of the maximum independent set problem in d-regular graphs unless ETH fails. We expand our method to show that it helps to provide lower bounds for other covering problems such as vertex cover and clique. We utilize the construction to show the NP-hardness of MIS on 5-regular planar graphs, closing the exact complexity status of the problem on regular planar graphs.