Computing A Near-Maximum Independent Set in Linear Time by Reducing-Peeling

ABSTRACT

This paper studies the problem of efficiently computing a maximum independent set from a large graph, a fundamental problem in graph analysis. Due to the hardness results of computing an exact maximum independent set or an approximate maximum independent set with accuracy guarantee, the existing algorithms resort to heuristic techniques for approximately computing a maximum independent set with good performance in practice but no accuracy guarantee theoretically. Observing that the existing techniques have various limits, in this paper, we aim to develop efficient algorithms (with linear or near-linear time complexity) that can generate a high-quality (large-size) independent set from a graph in practice. In particular, firstly we develop a Reducing-Peeling framework which iteratively reduces the graph size by applying reduction rules on vertices with very low degrees (Reducing) and temporarily removing the vertex with the highest degree (Peeling) if the reduction rules cannot be applied. Secondly, based on our framework we design two baseline algorithms, BDOne and BDTwo, by utilizing the existing reduction rules for handling degree-one and degree-two vertices, respectively. Both algorithms can generate higher-quality (larger-size) independent sets than the existing algorithms. Thirdly, we propose a linear-time algorithm, LinearTime, and a near-linear time algorithm, NearLinear, by designing new reduction rules and developing techniques for efficiently and incrementally applying reduction rules. In practice, LinearTime takes similar time and space to BDOne but computes a higher quality independent set, similar in size to that of an independent set generated by BDTwo. Moreover, in practice NearLinear has a good chance to generate a maximum independent set and it often generates near-maximum independent sets. Fourthly, we extend our techniques to accelerate the existing iterated local search algorithms. Extensive empirical studies show that all our algorithms output much larger independent sets than the existing linear-time algorithms while having a similar running time, as well as achieve significant speedup against the existing iterated local search algorithms.

References

1. T. Akiba and Y. Iwata. Branch-and-reduce exponential/fpt algorithms in practice: A case study of vertex cover. Theor. Comput. Sci., 609, 2016.
2. D. V. Andrade, M. G. Resende, and R. F. Werneck. Fast local search for the maximum independent set problem. J. Heuristics, 18(4), 2012.
3. F. Araujo, J. Farinha, P. Domingues, G. C. Silaghi, and D. Kondo. A maximum independent set approach for collusion detection in voting pools. J. Parallel and Distributed Computing, 71(10), 2011.
4. A.-L. Barabasi and R. Albert. Emergence of scaling in random networks. Science, 286, 1999.
5. S. Basagni. Finding a maximal weighted independent set in wireless networks. Telecommunication Systems, 18(1--3), 2001.
6. U. Benlic and J.-K. Hao. Breakout local search for maximum clique problems. Computers & Operations Research, 40(1), 2013.
7. P. Berman and T. Fujito. On approximation properties of the independent set problem for low degree graphs. Theor. Comput. Sys., 32(2), 1999.
8. F. Bi, L. Chang, X. Lin, L. Qin, and W. Zhang. Efficient subgraph matching by postponing cartesian products. In Proc. of SIGMOD'16, 2016.
9. S. Butenko. Maximum independent set and related problems with applications. PhD thesis, University of Florida, 2003.
10. J. M. Byskov. Enumerating maximal independent sets with applications to graph colouring. Oper. Res. Lett., 32(6), 2004.
11. S. Cai. Balance between complexity and quality: local search for minimum vertex cover in massive graphs. In Proc. of IJCAI'15, 2015.
12. L. Chang, J. X. Yu, and L. Qin. Fast maximal cliques enumeration in sparse graphs. Algorithmica, 2012.
13. L. Chang, J. X. Yu, L. Qin, X. Lin, C. Liu, and W. Liang. Efficiently computing k-edge connected components via graph decomposition. In Proc. of SIGMOD'13, 2013.
14. J. Cheng, Y. Ke, S. Chu, and C. Cheng. Efficient processing of distance queries in large graphs: a vertex cover approach. In Proc. of SIGMOD'12, 2012.
15. J. Cheng, Y. Ke, A. W.-C. Fu, J. X. Yu, and L. Zhu. Finding maximal cliques in massive networks by h*-graph. In Proc. of SIGMOD'10, 2010.
16. N. Chiba and T. Nishizeki. Arboricity and subgraph listing algorithms. SIAM J. Comput., 14(1), 1985.
17. R. H. Chitnis, G. Cormode, M. T. Hajiaghayi, and M. Monemizadeh. Parameterized streaming: Maximal matching and vertex cover. In Proc. of SODA'15, 2015.
18. T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein. Introduction to Algorithms. McGraw-Hill Higher Education, 2001.
19. J. Dahlum, S. Lamm, P. Sanders, C. Schulz, D. Strash, and R. F. Werneck. Accelerating local search for the maximum independent set problem. In Proc. of SEA'16, 2016.
20. U. Feige. Approximating maximum clique by removing subgraphs. SIAM J. Discrete Math., 18(2), 2004.
21. F. V. Fomin, F. Grandoni, and D. Kratsch. A measure & conquer approach for the analysis of exact algorithms. J. ACM, 56(5), 2009.
22. A. W.-C. Fu, H. Wu, J. Cheng, and R. C.-W. Wong. Is-label: an independent-set based labeling scheme for point-to-point distance querying. PVLDB, 6(6), 2013.
23. M. R. Garey and D. S. Johnson. Computers and Intractability; A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., New York, NY, USA, 1990.
24. A. Gibbons. Algorithmic Graph Theory. Cambridge University Press, 1985.
25. M. M. Halldórsson and J. Radhakrishnan. Greed is good: Approximating independent sets in sparse and bounded-degree graphs. Algorithmica, 18(1), 1997.
26. J. Håstad. Clique is hard to approximate within n ^1ε. In Proc. of FOCS'96, 1996.
27. S. Lamm, P. Sanders, and C. Schulz. Graph partitioning for independent sets. In Proc. of SEA'15, 2015.
28. S. Lamm, P. Sanders, C. Schulz, D. Strash, and R. F. Werneck. Finding near-optimal independent sets at scale. In Proc. of ALENEX'16, 2016.
29. Y. Lim, U. Kang, and C. Faloutsos. Slashburn: Graph compression and mining beyond caveman communities. IEEE Trans. Knowl. Data Eng., 26(12), 2014.
30. Y. Liu, J. Lu, H. Yang, X. Xiao, and Z. Wei. Towards maximum independent sets on massive graphs. PVLDB, 8(13), 2015.
31. P. M. Pardalos and J. Xue. The maximum clique problem. J. global Optimization, 4(3), 1994.
32. D. Puthal, S. Nepal, C. Paris, R. Ranjan, and J. Chen. Efficient algorithms for social network coverage and reach. In 2015 IEEE International Congress on Big Data, 2015.
33. P. S. Segundo, A. Lopez, and P. M. Pardalos. A new exact maximum clique algorithm for large and massive sparse graphs. Computers & Operations Research, 66, 2016.
34. S. S. Skiena. The Algorithm Design Manual. Springer Publishing Company, Incorporated, 2nd edition, 2008.
35. E. Tomita, Y. Sutani, T. Higashi, S. Takahashi, and M. Wakatsuki. A simple and faster branch-and-bound algorithm for finding a maximum clique. In Proc. of WALCOM'10, 2010.
36. P.-J. Wan, B. Xu, L. Wang, S. Ji, and O. Frieder. A new paradigm for multiflow in wireless networks: Theory and applications. In Proc. of INFOCOM'15, 2015.
37. J. Xiang, C. Guo, and A. Aboulnaga. Scalable maximum clique computation using mapreduce. In Proc. of ICDE'13, 2013.
38. M. Xiao and H. Nagamochi. Confining sets and avoiding bottleneck cases: A simple maximum independent set algorithm in degree-3 graphs. Theor. Comput. Sci., 469, 2013.
39. Z. Zhang, L. Qin, and J. X. Yu. Contract & expand: I/O efficient sccs computing. In Proc. of ICDE'14, 2014.
40. Y. Zhu, L. Qin, J. X. Yu, Y. Ke, and X. Lin. High efficiency and quality: large graphs matching. VLDB J., 22(3), 2013.

Index Terms

• Information systems

  • World Wide Web

    • Web applications

      • Social networks

• Mathematics of computing

  • Discrete mathematics

    • Graph theory

      • Graph algorithms