×

Consensus algorithms for the generation of all maximal bicliques. (English) Zbl 1056.05132

Summary: We describe a new algorithm for generating all maximal bicliques (i.e. complete bipartite, not necessarily induced subgraphs) of a graph. The algorithm is inspired by, and is quite similar to, the consensus method used in propositional logic. We show that some variants of the algorithm are totally polynomial, and even incrementally polynomial. The total complexity of the most efficient variant of the algorithms presented here is polynomial in the input size, and only linear in the output size. Computational experiments demonstrate its high efficiency on randomly generated graphs with up to 2000 vertices and 20,000 edges.

MSC:

05C85 Graph algorithms (graph-theoretic aspects)
68R10 Graph theory (including graph drawing) in computer science
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] P. Agarwal, N. Alon, B. Aronov, S. Suri, Can visibility graphs be represented compactly? in: Proceedings of the Ninth ACM Symposium on Computational Geometry, 1993, pp. 338-347.; P. Agarwal, N. Alon, B. Aronov, S. Suri, Can visibility graphs be represented compactly? in: Proceedings of the Ninth ACM Symposium on Computational Geometry, 1993, pp. 338-347. · Zbl 0819.68134
[2] Aho, A. V.; Hopcroft, J. E.; Ullman, J. D., The Design and Analysis of Computer Algorithms (1974), Addison-Wesley Publishing Company: Addison-Wesley Publishing Company Reading · Zbl 0286.68029
[3] Benzaken, Cl.; Boyd, S.; Hammer, P. L.; Simeone, B., Adjoints of pure bidirected graphs, Congress. Numer, 39, 123-144 (1983) · Zbl 0537.05024
[4] Benzaken, Cl.; Hammer, P. L.; Simeone, B., Some remarks on conflict graphs of quadratic pseudo-Boolean functions, Internat. Ser. Numer. Math, 55, 9-30 (1980) · Zbl 0455.90063
[5] J.-C. Bermond, Couvertures des arrêtes d’un graphe par des graphes bipartis complets, Preprint, Univ. De Paris Sud, Centre d’Orsay, Rapport de Recherche No. 10, 1978.; J.-C. Bermond, Couvertures des arrêtes d’un graphe par des graphes bipartis complets, Preprint, Univ. De Paris Sud, Centre d’Orsay, Rapport de Recherche No. 10, 1978.
[6] A. Blake, Canonical expressions in Boolean algebra, Ph. D. Thesis, University of Chicago, 1937.; A. Blake, Canonical expressions in Boolean algebra, Ph. D. Thesis, University of Chicago, 1937. · Zbl 0018.38601
[7] Boros, E.; Crama, Y.; Hammer, P. L., Polynomial-time inference of all valid implications for Horn and related formulae, Ann. Math. Artif. Intell, 1, 21-32 (1990) · Zbl 0878.68105
[8] Bylka, S.; Idzik, A.; Komar, J., Bipartite subgraphs of graphs with maximum degree three, Graphs Combin, 15, 129-136 (1999) · Zbl 0931.05040
[9] Chang, C. L.; Lee, R. C., Symbolic Logic and Mechanical Theorem Proving (1973), Academic Press: Academic Press New York, San Francisco, London · Zbl 0263.68046
[10] Chung, F. R.K., On the coverings of graphs, Discrete Math, 30, 89-93 (1980) · Zbl 0451.05037
[11] Chung, F. R.K., On the decomposition of graphs, SIAM J. Algebraic Discrete Methods, 2, 1-12 (1981) · Zbl 0499.05046
[12] Chung, F. R.K.; Erdös, P.; Spencer, J., On the decomposition of graphs into complete bipartite subgraphs, Stud. Pure Math, 95-101 (1983)
[13] Crama, Y.; Hammer, P. L., Recognition of quadratic graphs and adjoints of bidirected graphs, Ann. New York Acad. Sci, 555, 140-149 (1989) · Zbl 0744.05060
[14] Dawande, M.; Keskinocak, P.; Swaminathan, J.; Tayur, S., On the biclique and multi-partite clique problems, J. Algorithms, 41, 2, 388-403 (2001) · Zbl 1017.68088
[15] Doherty, F. C.C.; Lundgren, J. R.; Siewert, D. J., Biclique covers and partitions of bipartite graphs and digraphs and related matrix ranks of {0,1}-matrices, Congress. Numer, 136, 73-96 (1999) · Zbl 0965.05082
[16] Dulmage, A. L.; Mendelsohn, N. S., Coverings of bipartite graphs, Canad. J. Math, 10, 517-534 (1958) · Zbl 0091.37404
[17] Ebenegger, Ch.; Hammer, P. L.; de Werra, D., Pseudo-Boolean functions and stability of graphs, Ann. Discrete Math, 19, 83-97 (1984) · Zbl 0567.05031
[18] Eppstein, D., Arboricity and bipartite subgraph listing algorithms, Inform. Process. Lett, 51, 207-211 (1994) · Zbl 0813.68115
[19] Foldes, S.; Hammer, P. L., Disjunctive and conjunctive normal forms of pseudo-Boolean functions, Discrete Appl. Math, 107, 1-26 (2000) · Zbl 0965.06015
[20] Garey, M. R.; Johnson, D. S., Computers and Intractability, A guide to the theory of NP-completeness (1979), Freeman: Freeman San Francisco · Zbl 0411.68039
[21] Glover, F., Maximum matching in a convex bipartite graph, Naval Res. Logistics Q, 14, 313-316 (1967) · Zbl 0183.24501
[22] Golumbic, M. C.; Hammer, P. L., Stability in circular arc graphs, J. Algorithms, 9, 314-320 (1988) · Zbl 0651.68083
[23] W.H. Haemers, Bicliques and eigenvalues, Research Memorandum FEW 783, Tilburg University, 1999.; W.H. Haemers, Bicliques and eigenvalues, Research Memorandum FEW 783, Tilburg University, 1999.
[24] P.L. Hammer, The conflict graph of a pseudo-Boolean function, Technical Report, Bell Laboratories, West Long Branch, NJ, 1978.; P.L. Hammer, The conflict graph of a pseudo-Boolean function, Technical Report, Bell Laboratories, West Long Branch, NJ, 1978.
[25] Hammer, P. L.; Mahadev, N. V.R.; de Werra, D., The struction of a graphapplication to CN-free graphs, Combinatorica, 5, 141-147 (1985) · Zbl 0582.05051
[26] Hammer, P. L.; Mahadev, N. V.R.; de Werra, D., Stability in CAN-free graphs, J. Combin. Theory Ser. B, 38, 23-30 (1985) · Zbl 0558.05053
[27] Hammer, P. L.; Simeone, B., Quasimonotone Boolean functions and bistellar graphs, Ann. Discrete Math, 9, 107-119 (1980) · Zbl 0455.05049
[28] Hochbaum, D. S., Approximating clique and biclique problems, J. Algorithms, 29, 174-200 (1998) · Zbl 0919.68056
[29] Johnson, D. S., The NP-completeness columnan ongoing guide, J. Algorithms, 8, 438-448 (1987) · Zbl 0633.68022
[30] Johnson, D. S.; Yannakakis, M.; Papadimitriou, C. H., On generating all maximal independent sets, Inform. Process. Lett, 27, 119-123 (1988) · Zbl 0654.68086
[31] A. Kaufmann, E. Pichat, Méthodes mathématiques non numériques et leurs algorithmes, Algorithmes de Recherche des Eléments Maximaux, Tome I, Masson, Paris, 1977.; A. Kaufmann, E. Pichat, Méthodes mathématiques non numériques et leurs algorithmes, Algorithmes de Recherche des Eléments Maximaux, Tome I, Masson, Paris, 1977. · Zbl 0361.05047
[32] Lawler, E. L.; Lenstra, J. K.; Rinnooy Kan, A. H.G., Generating all maximal independent setsNP-hardness and polynomial-time algorithms, SIAM J. Comput, 9, 558-565 (1980) · Zbl 0445.68054
[33] Y. Malgrange, Recherche des sous-matrices premières d’une matrice à coefficients binaries, Applications à certains problèmes de graphe, in: Deuxième Congrès de l’AFCALTI, October 1961, Gauthier-Villars, Paris, 1962, pp. 231-242.; Y. Malgrange, Recherche des sous-matrices premières d’une matrice à coefficients binaries, Applications à certains problèmes de graphe, in: Deuxième Congrès de l’AFCALTI, October 1961, Gauthier-Villars, Paris, 1962, pp. 231-242.
[34] Mehlhorn, K., Data Structures and Algorithms 2: Graph Algorithms and NP-Completeness (1984), Springer: Springer Berlin · Zbl 0556.68002
[35] Papadimitriou, C. H., Computational Complexity (1994), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0557.68033
[36] D.V. Pasechnik, Bipartite sandwiches: bounding the size of a maximum biclique, preprint, 1999.; D.V. Pasechnik, Bipartite sandwiches: bounding the size of a maximum biclique, preprint, 1999.
[37] Paull, M. C.; Unger, S. H., Minimizing the number of states in incompletely specified sequential switching functions, IRE Trans. Electron. Comput, EC-8, 356-367 (1959)
[38] Peeters, R., The maximum edge biclique problem is NP-complete, Discrete Appl. Math, 131, 651-654 (2003) · Zbl 1026.68068
[39] Pichat, E., The disangagement algorithm or a new generalization of the exclusion algorithm, Discrete Math, 17, 95-106 (1977) · Zbl 0381.06024
[40] Quine, W., A way to simplify truth functions, Amer. Math. Monthly, 62, 627-631 (1955) · Zbl 0068.24209
[41] Tsukiyama, S.; Ide, M.; Ariyoshi, H.; Shirakawa, I., A new algorithm for generating all the maximal independent sets, SIAM J. Comput, 6, 505-517 (1977) · Zbl 0364.05027
[42] Tuza, Z., Covering of graphs by complete bipartite subgraphscomplexity of 0-1 matrices, Combinatorica, 4, 111-116 (1984) · Zbl 0559.05050
[43] M. Yannakakis, Node- and edge-deletion NP-complete problems, Proceedings of the 10th Annual ACM Symposium on Theory of Computing, Association for Computing Machinery, New York, 1978, pp. 253-264.; M. Yannakakis, Node- and edge-deletion NP-complete problems, Proceedings of the 10th Annual ACM Symposium on Theory of Computing, Association for Computing Machinery, New York, 1978, pp. 253-264. · Zbl 1282.68131
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.