Paper Info
Title
The maximum clique problem in multiple interval graphs (extended abstract)
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≥3 and polynomial-time solvable when t=1. The problem is also known to be NP-complete in t-track graphs when t≥4 and polynomial-time solvable when t≤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.
Year
DOI
Venue
2012
10.1007/978-3-642-34611-8_9
WG
Keywords
Field
DocType
maximum clique problem,weighted maximum clique,polynomial-time solvable,interval graph,t-interval graph,multiple interval graph,unit 2-interval graph,t-circular interval graph,single interval,maximum clique
Discrete mathematics,Indifference graph,Combinatorics,Chordal graph,Clique-sum,Treewidth,Clique problem,Trapezoid graph,Mathematics,Maximal independent set,Split graph
Conference
Volume
ISSN
Citations 
7551
0302-9743
0
PageRank 
References 
Authors
0.34
27
3
Name
Order
Citations
PageRank
Mathew C. Francis110714.90
Daniel Gonçalves27611.47
Pascal Ochem325836.91