Clique in 3-track interval graphs is APX-hard

2012/04/10 by Minghui Jiang, Jiang, Minghui
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Formal Methods in Verification

paper · pdf · doi:10.48550/arxiv.1204.2202

openalex publication_date 2012/04/10 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Butman, Hermelin, Lewenstein, and Rawitz proved that Clique in t-interval graphs is NP-hard for t >= 3. We strengthen this result to show that Clique in 3-track interval graphs is APX-hard.

Related

• The Maximum Clique Problem in Multiple Interval Graphs
• Parameterized complexity in multiple-interval graphs: domination, partition, separation, irredundancy
• Recognizing unit multiple intervals is hard
• Maximum Cut on Interval Graphs of Interval Count Two is NP-complete
• Complexity of Maximum Cut on Interval Graphs