The Maximum Clique Problem in Multiple Interval Graphs

Mathew C. Francis 1 Daniel Gonçalves 1 Pascal Ochem 1
1 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : Multiple interval graphs are variants of interval graphs where instead of a single interval, each vertex is assigned a set of intervals on the real line. We study the complexity of the MAXIMUM CLIQUE problem in several classes of multiple interval graphs. The MAXIMUM CLIQUE problem, or the problem of finding the size of the maximum clique, is known to be NP-complete for $t$-interval graphs when $t\geq 3$ and polynomial-time solvable when $t=1$. The problem is also known to be NP-complete in $t$-track graphs when $t\geq 4$ and polynomial-time solvable when $t\leq 2$. We show that MAXIMUM CLIQUE is already NP-complete for unit 2-interval graphs and unit 3-track graphs. Further, we show that the problem is APX-complete for 2-interval graphs, 3-track graphs, unit 3-interval graphs and unit 4-track graphs. We also introduce two new classes of graphs called $t$-circular interval graphs and $t$-circular track graphs and study the complexity of the MAXIMUM CLIQUE problem in them. On the positive side, we present a polynomial time $t$-approximation algorithm for WEIGHTED MAXIMUM CLIQUE on $t$-interval graphs, improving earlier work with approximation ratio $4t$.
Type de document :
Communication dans un congrès
WG'12: 38th International Workshop on Graph Theoretic Concepts in Computer Science, Jun 2012, Jerusalem, Israel. LNCS (7551), pp.57-68, 2012
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00738525
Contributeur : Daniel Gonçalves <>
Soumis le : jeudi 4 octobre 2012 - 14:58:52
Dernière modification le : jeudi 24 mai 2018 - 15:59:22

Identifiants

  • HAL Id : lirmm-00738525, version 1

Collections

Citation

Mathew C. Francis, Daniel Gonçalves, Pascal Ochem. The Maximum Clique Problem in Multiple Interval Graphs. WG'12: 38th International Workshop on Graph Theoretic Concepts in Computer Science, Jun 2012, Jerusalem, Israel. LNCS (7551), pp.57-68, 2012. 〈lirmm-00738525〉

Partager

Métriques

Consultations de la notice

101