On the independent set problem in random graphs

References

• F.N. Abu-Khzam, N.F. Samatova, M.A. Rizk, and M.A. Langston, The Maximum Common Subgraph Problem: Faster Solutions via Vertex Cover, Proceedings of 2007 IEEE/ACS International Conference on Computer Systems and Applications (AICCSA 2007), IEEE Computer Society, Washington, DC, 2007, pp. 367–373.
   Google Scholar
• R. Battiti and M. Protasi, Reactive local search for the maximum clique problem, Algorithmica 29(4) (2001), pp. 610–637. doi: 10.1007/s004530010074
   Web of Science ®Google Scholar
• R. Boppana and M. Halldórson, Approximating maximum independent sets by excluding subgraphs, BIT Comput. Sci. Numer. Math. 32(2) (1994), pp. 180–196. doi: 10.1007/BF01994876
   Web of Science ®Google Scholar
• J. Chen, X. Huang, I.A. Kanj, and G. Xia, Linear FPT Reductions and Computational Lower Bounds, Proceedings of the 36th ACM Symposium on Theory of Computing (STOC 2004), ACM, New York, 2004, pp. 212–221.
   Google Scholar
• J. Chen, X. Huang, I.A. Kanj, and G. Xia, Strong computational lower bounds via parameterized complexity, J. Comput. Syst. Sci. 72(8) (2006), pp. 1346–1367. doi: 10.1016/j.jcss.2006.04.007
   Web of Science ®Google Scholar
• I. Dinur and S. Safra, The Importance of Being Biased, Proceedings of the 34th ACM Symposium on Theory of Computing (STOC 2002), ACM, New York, 2002, pp. 33–42.
   Google Scholar
• R.G. Downey and M.R. Fellows, Parameterized Complexity, Springer, New York, 1998.
   Google Scholar
• R.G. Downey and M.R. Fellows, Fixed parameter tractability and completeness I: basic theory, SIAM J. Comput. 24 (1995), pp. 873–921. doi: 10.1137/S0097539792228228
   Web of Science ®Google Scholar
• R.G. Downey and M.R. Fellows, Fixed parameter tractability and completeness II: completeness for W[1], Theor. Comput. Sci. A 141 (1995), pp. 109–131. doi: 10.1016/0304-3975(94)00097-3
   Web of Science ®Google Scholar
• P. Erds and A. Rényi, On random graphs, Publ. Math. 6 (1959), pp. 290–297.
   Google Scholar
• U. Fiege, Approximating maximum clique by removing subgraphs, SIAM J. Discrete Math. 18(2) (2004), pp. 219–225. doi: 10.1137/S089548010240415X
   Web of Science ®Google Scholar
• U. Fiege and E. Ofek, Finding a maximum independent set in a sparse random graph, SIAM J. Discrete Math. 22(2) (2008), pp. 693–718. doi: 10.1137/060661090
   Web of Science ®Google Scholar
• F.V. Fomin, F. Grandoni, and D. Kratsch, Measure and Conquer: A Simple O(20.288n) Independent Set Problem, Proceedings of the 17th ACM-SIAM Symposium on Discrete Algorithms (SODA 2006), ACM, New York, 2006, pp. 18–25.
   Google Scholar
• M.R. Garey and D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness $($A Series of Books in the Mathematical Sciences$)$, W.H. Freeman, San Francisco, CA, 1979.
   Google Scholar
• G.R. Grimmett and C.J.H. Mcdiarmid, On colouring random graphs, Math. Proc. Camb. Philos. Soc. 77(2) (1975), pp. 313–324. doi: 10.1017/S0305004100051124
   Web of Science ®Google Scholar
• A. Grosso, M. Locatelli, and F.D. Croce, Combining swaps and node weights in an adaptive greedy approach for the maximum clique problem, J. Heuristics 10(2) (2004), pp. 135–152. doi: 10.1023/B:HEUR.0000026264.51747.7f
   Web of Science ®Google Scholar
• J. Håstad, Clique is Hard to Approximate within n1−ϵ, Proceedings of the 37th Annual Symposium on Foundations of Computer Science (STOC 1996), ACM, New York, 1996, pp. 627–636.
   Google Scholar
• S. Homer and M. Peinado, On the performance of polynomial-time CLIQUE approximation algorithms on very large graphs, in Cliques, Coloring, and Satisfiability: Second DIMACS Implementation Challenge, D.S. Johnson, ed., Amer. Mathematical Society, Providence, RI, 1993, pp. 103–124.
   Google Scholar
• T. Jian, An O(20.308n) algorithm for solving maximum independent set problem, IEEE Trans. Comput. 35(9) (1986), pp. 847–851. doi: 10.1109/TC.1986.1676847
   Google Scholar
• D.S. Johnson, Approximate algorithms for combinatorial problems, J. Comput. Syst. Sci. 9 (1974), pp. 256–278. doi: 10.1016/S0022-0000(74)80044-9
   Web of Science ®Google Scholar
• R.M. Karp, The probability analysis of some combinatorial search problems, in Algorithms and Complexity: New Directions and Recent Results, J.F. Traub, ed., Vols. 1–19, Academic Press, New York, 1976.
   Google Scholar
• K. Katayama, A. Hamamoto, and H. Narihisa, An effective local search for the maximum clique problem, Inf. Process. Lett. 95(5) (2005), pp. 503–511. doi: 10.1016/j.ipl.2005.05.010
   Web of Science ®Google Scholar
• J. Konc and D. Janežič, An improved branch and bound algorithm for the maximum clique problem, MATCH Commun. Math. Comput. Chem. 58(3) (2007), pp. 569–590.
   Web of Science ®Google Scholar
• A. Coja-Oghlan and C. Efthymiou, On Independent Sets in Random Graphs, Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2011), ACM, New York, 2011, pp. 136–144.
   Google Scholar
• J.M. Robson, Finding a maximum independent set in time O(2n/4), Tech. Rep. 1251-01, LaBRI Université de Bordeaux I, 2001.
   Google Scholar