A note on the fine-grained complexity of MIS on regular graphs

DOI10.1016/j.ipl.2021.106123OpenAlexW3153425020MaRDI QIDQ2032165

Saeed Akhoondian Amiri

Publication date: 16 June 2021

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2008.09008

zbMATH Keywords

computational complexityplanar graphsindependent setNP-completeETH

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Maximum independent sets in 3- and 4-regular Hamiltonian graphs
• Some simplified NP-complete graph problems
• Which problems have strongly exponential complexity?
• Subexponential-time algorithms for maximum independent set in \(P_t\)-free and broom-free graphs
• Face covers and the genus problem for apex graphs
• Exact algorithms for maximum independent set
• A subexponential-time algorithm for the maximum independent set problem in \(P_t\)-free graphs
• Fast algorithms for max independent set
• Linear degree extractors and the inapproximability of max clique and chromatic number
• A measure & conquer approach for the analysis of exact algorithms
• An improved exponential-time algorithm for k -SAT
• Algorithms for maximum independent sets
• Unnamed Item
• Unnamed Item
• Unnamed Item