On the independent set problem in random graphs

DOI10.1080/00207160.2014.976210MaRDI QIDQ2804023zbMATHOpenAlexWikidataFDO

Authors Yinglei Song

Publication date 27 April 2016

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

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

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)

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.

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

Cites work

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

Cited in

(13)

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

Describes a project that uses

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)