Maximum cliques in graphs with small intersection number and random intersection graphs

DOI10.1007/978-3-642-32589-2_63zbMATH Open1487.05198arXiv1204.4054OpenAlexW3115081644MaRDI QIDQ826323FDOQ826323

Authors: Christoforos L. Raptopoulos, Sotiris E. Nikoletseas, P. G. Spirakis 

Publication date: 20 December 2021

Published in: Computer Science Review, Mathematical Foundations of Computer Science 2012 (Search for Journal in Brave)

Abstract: In this paper, we relate the problem of finding a maximum clique to the intersection number of the input graph (i.e. the minimum number of cliques needed to edge cover the graph). In particular, we consider the maximum clique problem for graphs with small intersection number and random intersection graphs (a model in which each one of $m$ labels is chosen independently with probability $p$ by each one of $n$ vertices, and there are edges between any vertices with overlaps in the labels chosen). We first present a simple algorithm which, on input $G$ finds a maximum clique in $O(2^{2^m+O(m)}+n^{2}min{2}^m,n)$ time steps, where $m$ is an upper bound on the intersection number and $n$ is the number of vertices. Consequently, when $mleqlnlnn$ the running time of this algorithm is polynomial. We then consider random instances of the random intersection graphs model as input graphs. As our main contribution, we prove that, when the number of labels is not too large ($m=n^{alpha},0<alpha<1$), we can use the label choices of the vertices to find a maximum clique in polynomial time whp. The proof of correctness for this algorithm relies on our Single Label Clique Theorem, which roughly states that whp a "large enough" clique cannot be formed by more than one label. This theorem generalizes and strengthens other related results in the state of the art, but also broadens the range of values considered. As an important consequence of our Single Label Clique Theorem, we prove that the problem of inferring the complete information of label choices for each vertex from the resulting random intersection graph (i.e. the emph{label representation of the graph}) is emph{solvable} whp. Finding efficient algorithms for constructing such a label representation is left as an interesting open problem for future research.

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

Recommendations

• Maximum cliques in graphs with small intersection number and random intersection graphs
• Large cliques in sparse random intersection graphs
• On Some Combinatorial Properties of Random Intersection Graphs
• Large independent sets in general random intersection graphs
• Colouring Non-sparse Random Intersection Graphs

zbMATH Keywords

maximum cliqueintersection numberrandom intersection graph

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Extremal problems in graph theory (05C35) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cites Work

• Title not available (Why is that?)
• Reducibility among Combinatorial Problems
• On Random Intersection Graphs: The Subgraph Problem
• Clique is hard to approximate within \(n^{1-\epsilon}\)
• Approximating Maximum Clique by Removing Subgraphs
• A spectral heuristic for bisecting random graphs
• Large Cliques Elude the Metropolis Process
• On colouring random graphs
• Strong computational lower bounds via parameterized complexity
• Equivalence of a random intersection graph and G (n ,p )
• Random intersection graphs whenm=?(n): An equivalence theorem relating the evolution of theG(n,m,p) andG(n,p) models
• Coloring Random Intersection Graphs and Complex Networks
• Large cliques in sparse random intersection graphs
• Bounds on the max and min bisection of random cubic and random 4-regular graphs
• Bounds on the bisection width for random \(d\)-regular graphs
• Algorithms for maximum independent sets
• Properly colored subgraphs and rainbow subgraphs in edge‐colorings with local constraints
• Approximating the independence number via the \(\vartheta\)-function
• On the independence number and Hamiltonicity of uniform random intersection graphs
• Efficiently covering complex networks with cliques of similar vertices
• Maximum cliques in graphs with small intersection number and random intersection graphs
• The chromatic and clique numbers of random scaled sector graphs
• Finding Planted Partitions in Random Graphs with General Degree Distributions
• Approximating layout problems on random graphs

Cited In (7)

• On Some Combinatorial Properties of Random Intersection Graphs
• Paired threshold graphs
• Large cliques in sparse random intersection graphs
• Selected combinatorial problems through the prism of random intersection graphs models
• A spectral algorithm for finding maximum cliques in dense random intersection graphs
• On the chromatic number of non-sparse random intersection graphs
• Maximum cliques in graphs with small intersection number and random intersection graphs

This page was built for publication: Maximum cliques in graphs with small intersection number and random intersection graphs

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