On the independent set problem in random graphs

DOI10.1080/00207160.2014.976210zbMATH Open1334.05108arXiv1308.1556OpenAlexW2168519036WikidataQ56210439 ScholiaQ56210439MaRDI QIDQ2804023FDOQ2804023

Authors: Yinglei Song 

Publication date: 27 April 2016

Published in: International Journal of Computer Mathematics (Search for Journal in Brave)

Abstract: In this paper, we develop efficient exact and approximate algorithms for computing a maximum independent set in random graphs. In a random graph $G$, each pair of vertices are joined by an edge with a probability $p$, where $p$ is a constant between $0$ and $1$. We show that, a maximum independent set in a random graph that contains $n$ vertices can be computed in expected computation time $2^{O(lo{g}_2^{2}n)}$. Using techniques based on enumeration, we develop an algorithm that can find a largest common subgraph in two random graphs in $n$ and $m$ vertices ($mleqn$) in expected computation time $2^{O(n^{frac12}lo{g}_2^{frac53}n)}$. In addition, we show that, with high probability, the parameterized independent set problem is fixed parameter tractable in random graphs and the maximum independent set in a random graph in $n$ vertices can be approximated within a ratio of $frac2n{2}^{sqrtlo{g}_{2}n}$ in expected polynomial time.

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

Recommendations

• Finding a Maximum Independent Set in a Sparse Random Graph
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• Independent sets in random sparse graphs
• Finding Large Independent Sets in Polynomial Expected Time

zbMATH Keywords

exact algorithmindependent setrandom graphsparameterized algorithm

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Cites Work

• Title not available (Why is that?)
• Approximation algorithms for combinatorial problems
• Approximating Maximum Clique by Removing Subgraphs
• Title not available (Why is that?)
• Fixed-Parameter Tractability and Completeness I: Basic Results
• Fixed-parameter tractability and completeness II: On completeness for W[1]
• On colouring random graphs
• Reactive local search for the maximum clique problem
• Strong computational lower bounds via parameterized complexity
• An effective local search for the maximum clique problem
• Linear FPT reductions and computational lower bounds
• Approximating maximum independent sets by excluding subgraphs
• Measure and conquer
• The importance of being biased
• An O(2^0.304n) Algorithm for Solving Maximum Independent Set Problem
• Finding a Maximum Independent Set in a Sparse Random Graph

Cited In (13)

• Randomly finding independent sets in locally sparse graphs
• On threshold probability for the stability of independent sets in distance graphs
• Title not available (Why is that?)
• Independent sets in random sparse graphs
• Simulating independence
• Hard graphs for randomized subgraph exclusion algorithms
• On the Maximal Number of Strongly Independent Vertices in a Random Acyclic Directed Graph
• Finding a Maximum Independent Set in a Sparse Random Graph
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• Random maximal independent sets and the unfriendly theater seating arrangement problem
• The resolution complexity of independent sets and vertex covers in random graphs
• Approximating independent set in perturbed graphs
• Experimental and Efficient Algorithms

Uses Software

• DIMACS

This page was built for publication: On the independent set problem in random graphs

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