The maximum clique problem in multiple interval graphs

DOI10.1007/S00453-013-9828-6MaRDI QIDQ2350898zbMATH OpenOpenAlexFDO

Authors Mathew C. Francis, Daniel Gonçalves, Pascal Ochem

Publication date 25 June 2015

Published in Algorithmica (Search for Journal in Brave)

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

zbMATH Keywords

\(t\)-interval graphs\(t\)-track graphsapproximation hardnessmaximum cliqueNP-completenessunit \(t\)-interval graphsunit \(t\)-track graphs

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25)

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 $tgeq3$ and polynomial-time solvable when $t=1$. The problem is also known to be NP-complete in $t$-track graphs when $tgeq4$ and polynomial-time solvable when $tleq2$. 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$.

Recommendations

• The maximum clique problem in multiple interval graphs (extended abstract)
• The maximum clique interdiction problem
• scientific article; zbMATH DE number 1424314
• scientific article; zbMATH DE number 4112629
• scientific article; zbMATH DE number 4130407
• The maximum clique problem
• On the maximal clique problem
• The \(p\)-Maxian problem on interval graphs
• scientific article; zbMATH DE number 26478
• On the maximum number of cliques in a graph

Cites work

• Algorithms for a maximum clique and a maximum independent set of a circle graph
• Algorithms – ESA 2005
• Approximation algorithms for intersection graphs
• Cyclical scheduling and multi-shift scheduling: complexity and approximation algorithms
• Dotted interval graphs and high throughput genotyping
• scientific article; zbMATH DE number 4200260 (Why is no real title available?)
• Linear degree extractors and the inapproximability of max clique and chromatic number
• Maximum Weight Clique Algorithms for Circular-Arc Graphs and Circle Graphs
• Maximum weight independent sets and cliques in intersection graphs of filaments
• On approximation properties of the Independent set problem for degree 3 graphs
• On double and multiple interval graphs
• On the parameterized complexity of multiple-interval graph problems
• On the parameterized complexity of some optimization problems related to multiple-interval graphs
• Optimization problems in multiple-interval graphs
• Optimization, approximation, and complexity classes
• Parameterized complexity in multiple-interval graphs: domination, partition, separation, irredundancy
• Ramsey numbers and an approximation algorithm for the vertex cover problem
• Recognizing graphs with fixed interval number is NP-complete
• Scheduling Split Intervals
• Sorting with objectives. Graph theoretic concepts in industrial optimization
• The Clique Problem in Ray Intersection Graphs
• The Complexity of Combinatorial Optimization Problems on d‐Dimensional Boxes
• The max clique problem in classes of string-graphs
• The Rectilinear Steiner Tree Problem is NP-Complete
• Transversals of d-intervals
• Universality considerations in VLSI circuits
• Vertex Intersection Graphs of Paths on a Grid

Cited in

(29)

• Two-way and multiway partitioning of a set of intervals for clique-width maximization
• On the m-clique free interval subgraphs polytope: polyhedral analysis and applications
• Combinatorial problems on \(H\)-graphs
• Cyclic arrangements with minimum modulo \(m\) winding numbers
• On edge intersection graphs of paths with 2 bends
• Shiftable intervals
• The Clique Problem in Ray Intersection Graphs
• Optimization problems in multiple-interval graphs
• Optimization problems in multiple-interval graphs
• scientific article; zbMATH DE number 5914909 (Why is no real title available?)
• Clique Clustering Yields a PTAS for max-Coloring Interval Graphs
• scientific article; zbMATH DE number 5963787 (Why is no real title available?)
• On edge intersection graphs of paths with 2 bends
• Minimum Clique Partition Problem with Constrained Weight for Interval Graphs
• scientific article; zbMATH DE number 522858 (Why is no real title available?)
• RESTRICTED TRACK ASSIGNMENT WITH APPLICATIONS
• Complexity and polynomially solvable special cases of QUBO
• The maximum clique problem in multiple interval graphs (extended abstract)
• A parllel algorithm for finding a maximum weight clique of an interval graph
• On \(H\)-topological intersection graphs
• Temporal interval cliques and independent sets
• A graph-theoretic barcode ordering model for linked-reads
• Contact graphs of boxes with unidirectional contacts
• Recognizing unit multiple interval graphs is hard
• The simultaneous interval number: a new width parameter that measures the similarity to interval graphs
• Recognizing unit multiple intervals is hard
• Clique clustering yields a PTAS for max-coloring interval graphs
• Generalizing Roberts' characterization of unit interval graphs
• Some approximation algorithms for the clique partition problem in weighted interval graphs

This page was built for publication: The maximum clique problem in multiple interval graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2350898)