Why Is Maximum Clique Often Easy in Practice?

References

• Abello J, Pardalos PM, Resende MGC (1999) On maximum clique problems in very large graphs. Abello JM, Vitter JS, ed. External Memory Algorithms (American Mathematical Society, Providence, RI), 119–130.Google Scholar
• Abu-Khzam FN, Collins RL, Fellows MR, Langston MA, Suters WH, Symons CT (2004) Kernelization algorithms for the vertex cover problem: Theory and experiments. Arge L, Italiano GF, Sedgewick R, eds. Proc. 6th Workshop Algorithm Engrg. Experiments (ALENEX) (SIAM, Philadelphia), 62–69.Google Scholar
• Achterberg T (2007) Constraint integer programming. PhD thesis, Technische Universität Berlin, Berlin.Google Scholar
• Akiba T, Iwata Y (2016) Branch-and-reduce exponential/FPT algorithms in practice: A case study of vertex cover. Theoret. Comput. Sci. 609(1):211–225.Crossref, Google Scholar
• Bader GD, Hogue CW (2003) An automated method for finding molecular complexes in large protein interaction networks. BMC Bioinformatics 4:Article 2.Crossref, Google Scholar
• Balasubramanian R, Fellows M, Raman V (1998) An improved fixed-parameter algorithm for vertex cover. Inform. Processing Lett. 65(3):163–168.Crossref, Google Scholar
• Barabási AL, Albert R (1999) Emergence of scaling in random networks. Science 286(5439):509–512.Crossref, Google Scholar
• Bar-Yehuda R, Even S (1985) A local-ratio theorem for approximating the weighted vertex cover problem. Ausiello G, Lucertini M, eds. Analysis and Design of Algorithms for Combinatorial Problems (North Holland Publising Co., Amsterdam),27–45.Crossref, Google Scholar
• Batagelj V, Zaversnik M (2003) An O(m) algorithm for cores decomposition of networks. Preprint, submitted October 25, https://arxiv.org/abs/cs/0310049.Google Scholar
• Björklund A, Husfeldt T, Koivisto M (2009) Set partitioning via inclusion-exclusion. SIAM J. Comput. 39(2):546–563.Crossref, Google Scholar
• Bomze IM, Budinich M, Pardalos PM, Pelillo M (1999) The maximum clique problem. Du DZ, Pardalos PM, eds. Handbook of Combinatorial Optimization (Springer-Verlag, Boston), 1–74.Crossref, Google Scholar
• Bonato A, Hadi N, Horn P, Prałat P, Wang C (2009) Models of online social networks. Internet Math. 6(3):285–313.Crossref, Google Scholar
• Borchers B (1999) CSDP, a C library for semidefinite programming. Optim. Methods Software 11(1-4):613–623.Crossref, Google Scholar
• Borchers B (2017) CSDP 6.2 user’s guide. Accessed January 20, 2020, https://github.com/coin-or/Csdp/blob/master/doc/csdpuser.pdf.Google Scholar
• Buchanan A, Walteros JL, Butenko S, Pardalos PM (2014) Solving maximum clique in sparse graphs: an O(nm+n2d/4) algorithm for d-degenerate graphs. Optim. Lett. 8(5):1611–1617.Crossref, Google Scholar
• Buss JF, Goldsmith J (1993) Nondeterminism within P. SIAM J. Comput. 22(3):560–572.Crossref, Google Scholar
• Carraghan R, Pardalos PM (1990) An exact algorithm for the maximum clique problem. Oper. Res. Lett. 9(6):375–382.Crossref, Google Scholar
• Chen J, Kanj IA, Jia W (2001) Vertex cover: Further observations and further improvements. J. Algorithms 41(2):280–301.Crossref, Google Scholar
• Chen J, Kanj IA, Xia G (2010) Improved upper bounds for vertex cover. Theoret. Comput. Sci. 411(40):3736–3756.Crossref, Google Scholar
• Chen J, Fernau H, Kanj IA, Xia G (2007) Parametric duality and kernelization: Lower bounds and upper bounds on kernel size. SIAM J. Comput. 37(4):1077–1106.Crossref, Google Scholar
• Chor B, Fellows M, Juedes D (2004) Linear kernels in linear time, or how to save k colors in O(n2) steps. Hromkovič J, Nagl M, eds. Proc. 30th Internat. Conf. Graph-Theoretic Concepts Comput. Sci. (Springer Berlin, Heidelberg), 257–269.Google Scholar
• Cohen J (2008) Trusses: Cohesive subgraphs for social network analysis. Technical Report 16 (National Security Agency, Fort Meade, MD).Google Scholar
• Csardi G, Nepusz T (2006) The igraph software package for complex network research. InterJournal Complex Systems 1695(5):1–9.Google Scholar
• Cygan M, Fomin FV, Kowalik Ł, Lokshtanov D, Marx D, Pilipczuk M, Pilipczuk M, Saurabh S (2015) Parameterized Algorithms (Springer, New York).Crossref, Google Scholar
• Dailey DP (1980) Uniqueness of colorability and colorability of planar 4-regular graphs are NP-complete. Discrete Math. 30(3):289–293.Crossref, Google Scholar
• Dell H, Van Melkebeek D (2014) Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses. J. ACM 61(4):Article 23.Crossref, Google Scholar
• Downey RG, Fellows MR (1999) Parameterized Complexity (Springer-Verlag, New York).Crossref, Google Scholar
• Eppstein D, Löffler M, Strash D (2013) Listing all maximal cliques in large sparse real-world graphs. ACM J. Experiment. Algorithmics 18(3):3.1.Google Scholar
• Erdös P, Hajnal A (1966) On chromatic number of graphs and set-systems. Acta Math. Hungar. 17(1-2):61–99.Crossref, Google Scholar
• Freuder EC (1982) A sufficient condition for backtrack-free search. J. ACM 29(1):24–32.Crossref, Google Scholar
• Garey MR, Johnson DS, Stockmeyer L (1976) Some simplified NP-complete graph problems. Theoret. Comput. Sci. 1(3):237–267.Crossref, Google Scholar
• Håstad J (1999) Clique is hard to approximate within O(n1−ɛ). Acta Math. 182(1):105–142.Crossref, Google Scholar
• Iwata Y, Oka K, Yoshida Y (2014) Linear-time FPT algorithms via network flow. Proc. 25th Annual ACM-SIAM Sympos. Discrete Algorithms (Society for Industrial and Applied Mathematics, Philadephia), 1749–1761.Google Scholar
• Kirousis LM, Thilikos DM (1996) The linkage of a graph. SIAM J. Comput. 25(3):626–647.Crossref, Google Scholar
• Knuth DE (1994) The sandwich theorem. Electron. J. Combin. 1(1):1.Crossref, Google Scholar
• Konc J, Janežič D (2007) An improved branch and bound algorithm for the maximum clique problem. MATCH Commun. Math. Comput. Chem. 58(3):569–590.Google Scholar
• Li CM, Quan Z (2010) An efficient branch-and-bound algorithm based on MaxSAT for the maximum clique problem. Proc. 24th AAAI Conf. Artificial Intelligence (AAAI Press, Palo Alto, CA), 128–133.Google Scholar
• Li W, Zhu B (2018) A 2k-kernelization algorithm for vertex cover based on crown decomposition. Theoret. Comput. Sci. 739:80–85.Crossref, Google Scholar
• Lick DR, White AT (1970) k-degenerate graphs. Canadian J. Math. 22(5):1082–1096.Crossref, Google Scholar
• Lieder F, Rad FBA, Jarre F (2015) Unifying semidefinite and set-copositive relaxations of binary problems and randomization techniques. Comput. Optim. Appl. 61(3):669–688.Crossref, Google Scholar
• Lovász L (1979) On the Shannon capacity of a graph. IEEE Trans. Inform. Theory 25(1):1–7.Crossref, Google Scholar
• Manoussakis G (2014) The clique problem on inductive k-independent graphs. Preprint, submitted October 13, https://arxiv.org/abs/1410.3302.Google Scholar
• Manoussakis G (2016) New algorithms for cliques and related structures in k-degenerate graphs. Preprint, submitted April 4, https://arxiv.org/abs/1501.01819v4.Google Scholar
• Matula DW, Beck LL (1983) Smallest-last ordering and clustering and graph coloring algorithms. J. ACM 30(3):417–427.Crossref, Google Scholar
• Mittelmann H (2018) Benchmarks for optimization software. Accessed January 20, 2020, http://plato.asu.edu/bench.html.Google Scholar
• Nagamochi H (2010) Minimum degree orderings. Algorithmica 56(1):17–34.Crossref, Google Scholar
• Nemhauser GL, Trotter LE Jr (1975) Vertex packings: structural properties and algorithms. Math. Programming 8(1):232–248.Crossref, Google Scholar
• Niedermeier R, Rossmanith P (2000) A general method to speed up fixed-parameter-tractable algorithms. Inform. Processing Lett. 73(3):125–129.Crossref, Google Scholar
• Östergård PRJ (2002) A fast algorithm for the maximum clique problem. Discrete Appl. Math. 120(1):197–207.Crossref, Google Scholar
• Pattabiraman B, Patwary MMA, Gebremedhin AH, Liao WK, Choudhary A (2013) Fast algorithms for the maximum clique problem on massive sparse graphs. Bonato A, Mitzenmacher M, Prałat P, eds. International Workshop on Algorithms and Models for the Web-Graph (Springer, Heidelberg), 156–169.Google Scholar
• Prosser P (2012) Exact algorithms for maximum clique: A computational study. Algorithms (Basel) 5(4):545–587.Crossref, Google Scholar
• Pulleyblank WR (1979) Minimum node covers and 2-bicritical graphs. Math. Programming 17(1):91–103.Crossref, Google Scholar
• Robson JM (2001) Finding a maximum independent set in time O(2n/4). Technical report, LaBRI, Université de Bordeaux I.Google Scholar
• Rossi RA (2014) Fast triangle core decomposition for mining large graphs. Tseng VS, Ho TB, Zhou Z-H, Chen ALP, Kao H-Y, eds. Pacific-Asia Conf. Knowledge Discovery Data Mining (Springer, Heidelberg), 310–322.Google Scholar
• Rossi RA, Ahmed NK (2015) The network data repository with interactive graph analytics and visualization. Proc. 29th AAAI Conf. Artificial Intelligence (AAAI Press, Palo Alto, CA), 4292–4293.Google Scholar
• Rossi RA, Gleich DF, Gebremedhin AH (2015) Parallel maximum clique algorithms with applications to network analysis. SIAM J. Sci. Comput. 37(5):C589–C616.Crossref, Google Scholar
• San Segundo P, Lopez A, Pardalos PM (2016) A new exact maximum clique algorithm for large and massive sparse graphs. Comput. Oper. Res. 66:81–94.Crossref, Google Scholar
• San Segundo P, Nikolaev A, Batsyn M (2015) Infra-chromatic bound for exact maximum clique search. Comput. Oper. Res. 64:293–303.Crossref, Google Scholar
• San Segundo P, Artieda J, Batsyn M, Pardalos PM (2017a) An enhanced bitstring encoding for exact maximum clique search in sparse graphs. Optim. Methods Software 32(2):312–335.Crossref, Google Scholar
• San Segundo P, Lopez A, Artieda J, Pardalos PM (2017b) A parallel maximum clique algorithm for large and massive sparse graphs. Optim. Lett. 11(2):343–358.Crossref, Google Scholar
• Savelsbergh MWP (1994) Preprocessing and probing techniques for mixed integer programming problems. ORSA J. Comput. 6(4):445–454.Link, Google Scholar
• Seidman SB (1983) Network structure and minimum degree. Soc. Networks 5(3):269–287.Crossref, Google Scholar
• Sloane NJA (2017) Challenge problems: Independent sets in graphs. Accessed Janary 20, 2020, https://oeis.org/A265032/a265032.html.Google Scholar
• Szekeres G, Wilf HS (1968) An inequality for the chromatic number of a graph. J. Combin. Theory 4(1):1–3.Crossref, Google Scholar
• Tomita E, Kameda T (2007) An efficient branch-and-bound algorithm for finding a maximum clique with computational experiments. J. Global Optim. 37(1):95–111.Crossref, Google Scholar
• Tomita E, Sutani Y, Higashi T, Takahashi S, Wakatsuki M (2010) A simple and faster branch-and-bound algorithm for finding a maximum clique. Rahman MS, Fujita S, eds. WALCOM: Algorithms and Computation (Springer, Berlin), 191–203.Crossref, Google Scholar
• Verma A, Buchanan A, Butenko S (2015) Solving the maximum clique and vertex coloring problems on very large sparse networks. INFORMS J. Comput. 27(1):164–177.Link, Google Scholar
• Wang J, Cheng J (2012) Truss decomposition in massive networks. Proc. VLDB Endowment 5(9):812–823.Crossref, Google Scholar
• Watts DJ (1999) Networks, dynamics, and the small-world phenomenon. Amer. J. Sociol. 105(2):493–527.Crossref, Google Scholar
• Wilson AT (2009) Applying the boundary point method to an SDP relaxation of the maximum independent set problem for a branch and bound algorithm. Master’s thesis, New Mexico Institute of Mining and Technology, Socorro, NM.Google Scholar
• Zuckerman D (2006) Linear degree extractors and the inapproximability of max clique and chromatic number. Proc. 38th Annual ACM Sympos. Theory Comput. (ACM, New York), 681–690.Google Scholar