Exact combinatorial algorithms and experiments for finding maximum \(k\)-plexes. (English) Zbl 1261.90081
Summary: We propose new practical algorithms to find maximum-cardinality \(k\)-plexes in graphs. A \(k\)-plex denotes a vertex subset in a graph inducing a subgraph where every vertex has edges to all but at most \(k\) vertices in the \(k\)-plex. Cliques are 1-plexes. In analogy to the special case of finding maximum-cardinality cliques, finding maximum-cardinality \(k\)-plexes is NP-hard. Complementing previous work, we develop exact combinatorial algorithms, which are strongly based on methods from parameterized algorithmics. The experiments with our freely available implementation indicate the competitiveness of our approach, for many real-world graphs outperforming the previously used methods.
Keywords:
parameterized algorithmics; social network analysis; biological network analysis; NP-complete graph problems; dense subgraphs; \(s\)-plexes; \(k\)-dependent setsReferences:
| [1] | Abu-Khzam FN, Collins RL, Fellows MR, Langston MA, Suters WH, Symons CT (2004) Kernelization algorithms for the Vertex Cover problem: Theory and experiments. In: Proc 6th ALENEX. ACM/SIAM, New York/Philadelphia, pp 62–69 |
| [2] | Abu-Khzam FN, Fellows MR, Langston MA, Suters WH (2007) Crown structures for vertex cover kernelization. Theory Comput Syst 41(3):411–430 · Zbl 1148.68035 · doi:10.1007/s00224-007-1328-0 |
| [3] | Balasundaram B, Butenko S, Trukhanov S (2005) Novel approaches for analyzing biological networks. J Comb Optim 10(1):23–39 · Zbl 1080.90010 · doi:10.1007/s10878-005-1857-x |
| [4] | Balasundaram B, Butenko S, Hicks IV (2009) Clique relaxations in social network analysis: The maximum k-plex problem. Oper Res. doi: 10.1287/opre.1100.0851 . Available electronically · Zbl 1218.90228 |
| [5] | Balasundaram B, Chandramouli S, Trukhanov S (2010) Approximation algorithms for finding and partitioning unit-disk graphs into co-k-plexes. Optim Lett 4:311–320 · Zbl 1202.90257 · doi:10.1007/s11590-009-0146-5 |
| [6] | Batagelj V, Mrvar A (2006) Pajek datasets. http://vlado.fmf.uni-lj.si/pub/networks/data/ , accessed January 2009 · Zbl 1054.68564 |
| [7] | Beebe NH (2002) Nelson H.F. Beebe’s bibliographies page. http://www.math.utah.edu/\(\sim\)beebe/bibliographies.html |
| [8] | van Bevern R, Moser H, Niedermeier R (2011) Approximation and tidying–a problem kernel for s-plex cluster vertex deletion. Algorithmica. doi: 10.1007/s00453-011-9492-7 . Available electronically · Zbl 1236.68100 |
| [9] | Bodlaender HL (2009) Kernelization: New upper and lower bound techniques. In: Proc 4th IWPEC. LNCS, vol 5917. Springer, Berlin, pp 17–37 · Zbl 1273.68158 |
| [10] | Chen ZZ, Fellows M, Fu B, Jiang H, Liu Y, Wand L, Zhu B (2010) A linear kernel for co-path/cycle packing. In: Proc 6th AAIM. LNCS, vol 6124. Springer, Berlin, pp 90–102 · Zbl 1286.05131 |
| [11] | Chesler EJ, Lu L, Shou S, Qu Y, Gu J, Wang J, Hsu HC, Mountz JD, Baldwin NE, MA Langston, Threadgill DW, Manly KF, Williams RW (2005) Complex trait analysis of gene expression uncovers polygenic and pleiotropic networks that modulate nervous system function. Nat Genet 37(3):233–242 · doi:10.1038/ng1518 |
| [12] | Dessmark A, Jansen K, Lingas A (1993) The maximum k-dependent and f-dependent set problem. In: Proc 4th ISAAC. LNCS, vol 762. Springer, Berlin, pp 88–97 · Zbl 0925.05062 |
| [13] | DIMACS (1995) Maximum clique, graph coloring, and satisfiability. Second DIMACS implementation challenge. http://dimacs.rutgers.edu/Challenges/ , accessed November 2008 |
| [14] | Djidev H, Garrido O, Levcopoulos C, Lingas A (1992) On the maximum k-dependent set problem. Tech Rep LU-CS-TR:92-91, Department of Computer Science, Lund University, Sweden |
| [15] | Downey RG, Fellows MR (1999) Parameterized complexity. Springer, Berlin |
| [16] | Fellows MR, Guo J, Moser H, Niedermeier R (2009) A generalization of Nemhauser and Trotter’s local optimization theorem. In: Proc 26th STACS, IBFI Dagstuhl, Germany. pp 409–420 · Zbl 1236.68086 |
| [17] | Fellows MR, Guo J, Moser H, Niedermeier R (2010) A generalization of Nemhauser and Trotter’s local optimization theorem. J Comput Syst Sci. doi: 10.1016/j.jcss.2010.12.001 . Available electronically · Zbl 1236.68086 |
| [18] | Flum J, Grohe M (2006) Parameterized complexity theory. Springer, Berlin · Zbl 1143.68016 |
| [19] | Grossman J, Ion P, Castro RD (2007) The Erdos number project. http://www.oakland.edu/enp/ , accessed January 2009 |
| [20] | Guo J, Niedermeier R (2007) Invitation to data reduction and problem kernelization. SIGACT News 38(1):31–45 · doi:10.1145/1233481.1233493 |
| [21] | Guo J, Moser H, Niedermeier R (2009) Iterative compression for exactly solving NP-hard minimization problems. In: Algorithmics of large and complex networks. LNCS, vol 5515. Springer, Berlin, pp 65–80 · Zbl 1248.68380 |
| [22] | Guo J, Komusiewicz C, Niedermeier R, Uhlmann J (2010) A more relaxed model for graph-based data clustering: s-plex cluster editing. SIAM J Discrete Math 24(4):1662–1683 · Zbl 1221.05293 · doi:10.1137/090767285 |
| [23] | Hüffner F, Niedermeier R, Wernicke S (2008) Techniques for practical fixed-parameter algorithms. Comput J 51(1):7–25 · doi:10.1093/comjnl/bxm040 |
| [24] | Hüffner F, Komusiewicz C, Moser H, Niedermeier R (2009) Isolation concepts for clique enumeration: Comparison and computational experiments. Theor Comput Sci 410(52):5384–5397 · Zbl 1192.68484 · doi:10.1016/j.tcs.2009.05.008 |
| [25] | Hüffner F, Komusiewicz C, Moser H, Niedermeier R (2010) Fixed-parameter algorithms for cluster vertex deletion. Theory Comput Syst 47:196–217 · Zbl 1205.68263 · doi:10.1007/s00224-008-9150-x |
| [26] | Ito H, Iwama K (2009) Enumeration of isolated cliques and pseudo-cliques. ACM Trans Algorithms 5(4):40 :1–21 · Zbl 1298.05250 |
| [27] | Jones B (2002) Computational geometry database. http://compgeom.cs.uiuc.edu/\(\sim\)jeffe/compgeom/biblios.html |
| [28] | Komusiewicz C, Hüffner F, Moser H, Niedermeier R (2009) Isolation concepts for efficiently enumerating dense subgraphs. Theor Comput Sci 410(38-40):3640–3654 · Zbl 1171.68030 · doi:10.1016/j.tcs.2009.04.021 |
| [29] | Lewis JM, Yannakakis M (1980) The node-deletion problem for hereditary properties is NP-complete. J Comput Syst Sci 20(2):219–230 · Zbl 0436.68029 · doi:10.1016/0022-0000(80)90060-4 |
| [30] | McClosky B, Hicks IV (2010) Combinatorial algorithms for the maximum k-plex problem. J Comb Optim. doi: 10.1007/s10878-010-9338-2 . Available electronically · Zbl 1245.90109 |
| [31] | Moser H (2009) Finding optimal solutions for covering and matching problems. PhD thesis, Institut für Informatik, Friedrich-Schiller Universität, Jena |
| [32] | Nemhauser GL, Trotter LE (1975) Vertex packings: Structural properties and algorithms. Math Program 8:232–248 · Zbl 0314.90059 · doi:10.1007/BF01580444 |
| [33] | Niedermeier R (2006) Invitation to fixed-parameter algorithms. Oxford University Press, London · Zbl 1095.68038 |
| [34] | Niedermeier R, Rossmanith P (2000) A general method to speed up fixed-parameter-tractable algorithms. Inf Process Lett 73(3–4):125–129 · Zbl 1014.68064 · doi:10.1016/S0020-0190(00)00004-1 |
| [35] | Nishimura N, Ragde P, Thilikos DM (2005) Fast fixed-parameter tractable algorithms for nontrivial generalizations of Vertex Cover. Discrete Appl Math 152(1–3):229–245 · Zbl 1080.05093 · doi:10.1016/j.dam.2005.02.029 |
| [36] | Östergård PRJ (2002) A fast algorithm for the maximum clique problem. Discrete Appl Math 120(1–3):197–207 · Zbl 1019.05054 · doi:10.1016/S0166-218X(01)00290-6 |
| [37] | Sanchis LA, Jagota A (1996) Some experimental and theoretical results on test case generators for the maximum clique problem. INFORMS J Comput 8(2):103–117 · Zbl 0866.90074 · doi:10.1287/ijoc.8.2.103 |
| [38] | Seidman SB, Foster BL (1978) A graph-theoretic generalization of the clique concept. J Math Sociol 6:139–154 · Zbl 0386.92015 · doi:10.1080/0022250X.1978.9989883 |
| [39] | Trukhanov S (2008) Novel approaches for solving large-scale optimization problems on graphs. PhD thesis, A&M Universtity, Texas |
| [40] | Wu B, Pei X (2007) A parallel algorithm for enumerating all the maximal k-plexes. In: Emerging technologies in knowledge discovery and data mining. Lecture notes in artificial intelligence, vol 4819. Springer, Berlin, pp 476–483 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
