Abstract
Bicliques of graphs have been studied extensively, partially motivated by the large number of applications. In this paper we improve Prisner’s upper bound on the number of maximal bicliques (Combinatorica, 20, 109–117, 2000) and show that the maximum number of maximal bicliques in a graph on n vertices is Θ(3n/3). Our major contribution is an exact exponential-time algorithm. This branching algorithm computes the number of distinct maximal independent sets in a graph in time O(1.3642n), where n is the number of vertices of the input graph. We use this counting algorithm and previously known algorithms for various other problems related to independent sets to derive algorithms for problems related to bicliques via polynomial-time reductions.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Alber, J., Niedermeier, R.: Improved tree decomposition based algorithms for domination-like problems. In: Proc. of LATIN 2002. LNCS, vol. 2286, pp. 613–627. Springer, Berlin (2002)
Alexe, G., Alexe, S., Crama, Y., Foldes, S., Hammer, P.L., Simeone, B.: Consensus algorithms for the generation of all maximal bicliques. Discrete Appl. Math. 145, 11–21 (2004)
Amilhastre, J., Vilarem, M.C., Janssen, P.: Complexity of minimum biclique cover and minimum biclique decomposition for bipartite dominofree graphs. Discrete Appl. Math. 86, 125–144 (1998)
Björklund, A., Husfeldt, T., Koivisto, M.: Set partitioning via inclusion–exclusion. SIAM J. Comput. 39, 546–563 (2009)
Dahllöf, V., Jonsson, P.: An algorithm for counting maximum weighted independent sets and its applications. In: Proc. of SODA 2002, pp. 292–298. ACM and SIAM, Philadelphia (2002)
Dahllöf, V., Jonsson, P., Wahlström, M.: Counting models for 2SAT and 3SAT formulae. Theor. Comput. Sci. 332, 265–291 (2005)
Dawande, M., Swaminathan, J., Keskinocak, P., Tayur, S.: On bipartite and multipartite clique problems. J. Algorithms 41, 388–403 (2001)
Demaine, E.D., Gutin, G., Marx, D., Stege, U.: Open Problems—Structure Theory and FPT Algorithmcs for Graphs, Digraphs and Hypergraphs. Dagstuhl Seminar Proceedings 07281 (2007), IBFI, Schloss Dagstuhl, Germany
Dias, V.M.F., Herrera de Figueiredo, C.M., Szwarcfiter, J.L.: Generating bicliques of a graph in lexicographic order. Theor. Comput. Sci. 337, 240–248 (2005)
Dias, V.M.F., Herrera de Figueiredo, C.M., Szwarcfiter, J.L.: On the generation of bicliques of a graph. Discrete Appl. Math. 155, 1826–1832 (2007)
Fernau, H., Kneis, J., Kratsch, D., Langer, A., Liedloff, M., Raible, D., Rossmanith, P.: An exact algorithm for the maximum leaf spanning tree problem. In: Proc. of IWPEC 2009. LNCS, vol. 5917, pp. 161–172. Springer, Berlin (2009)
Fomin, F.V., Gaspers, S., Pyatkin, A.V., Razgon, I.: On the minimum feedback vertex set problem: Exact and enumeration algorithms. Algorithmica 52, 293–307 (2008)
Fomin, F.V., Grandoni, F., Kratsch, D.: A measure & conquer approach for the analysis of exact algorithms. J. ACM 56 (2009)
Fürer, M., Kasiviswanathan, S.P.: Algorithms for counting 2-SAT solutions and colorings with applications. In: Proc. of AAIM 2007. LNCS, vol. 4508, pp. 47–57. Springer, Berlin (2007)
Ganter, B., Wille, R.: Formal Concept Analysis, Mathematical Foundations. Springer, Berlin (1996)
Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-completeness. Freeman, New York (1979)
Gaspers, S., Liedloff, M.: A branch-and-reduce algorithm for finding a minimum independent dominating set. ArXiv Report 1009.1381 [CoRR abs] (2010)
Gaspers, S., Kratsch, D., Liedloff, M.: On independent sets and bicliques in graphs. In: Proc. of WG 2008. LNCS, vol. 5344, pp. 171–182. Springer, Berlin (2008)
Hochbaum, D.S.: Approximating clique and biclique problems. J. Algorithms 29, 174–200 (1998)
Kneis, J., Langer, A., Rossmanith, P.: A fine-grained analysis of a simple independent set algorithm. In: Proc. of FSTTCS 2009. LIPICS, vol. 4, pp. 287–298, Schloss Dagstuhl–Leibniz-Zentrum für Informatik, Germany
Makino, K., Uno, T.: New algorithms for enumerating all maximal cliques. In: Proc. of SWAT 2004. LNCS, vol. 3111, pp. 260–272. Springer, Berlin (2004)
Moon, J.W., Moser, L.: On cliques in graphs. Isr. J. Math. 3, 23–28 (1965)
Nourine, L., Raynaud, O.: A fast algorithm for building lattices. Inf. Process. Lett. 71, 199–204 (1999)
Nourine, L., Raynaud, O.: A fast incremental algorithm for building lattices. J. Exp. Theor. Artif. Intell. 14, 217–227 (2002)
Okamoto, Y., Uno, T., Uehara, R.: Counting the number of independent sets in chordal graphs. J. Discrete Algorithms 6, 229–242 (2008)
Peeters, R.: The maximum edge biclique problem is NP-complete. Discrete Appl. Math. 131, 651–654 (2003)
Prisner, E.: Bicliques in graphs I: Bounds on their number. Combinatorica 20, 109–117 (2000)
Robson, J.M.: Algorithms for maximum independent sets. J. Algorithms 7, 425–440 (1986)
van Rooij, J.M.M., Bodlaender, H.L.: Design by measure and conquer: a faster exact algorithm for dominating set. In: Proc. of STACS 2008. LIPIcs, pp. 657–668. Schloss Dagstuhl–Leibniz-Zentrum für Informatik, Germany
van Rooij, J.M.M., Nederlof, J., van Dijk, T.C.: Inclusion/exclusion meets measure and conquer. In: Proc. of ESA 2009. LNCS, vol. 5757, pp. 554–565. Springer, Berlin (2009)
Wahlström, M.: A tighter bound for counting max-weight solutions to 2SAT instances. In: Proc. of IWPEC 2008. LNCS, vol. 5018, pp. 202–213. Springer, Berlin (2008)
Yannakakis, M.: Node and edge deletion NP-complete problems. In: Proc. of STOC 1978, pp. 253–264. ACM, New York (1978)
Author information
Authors and Affiliations
Corresponding author
Additional information
A large part of the research was done while Serge Gaspers was visiting the University of Metz. A preliminary version of this paper appeared in the proceedings of WG 2008 [18]. Serge Gaspers acknowledges partial support of NFR and of Conicyt Chile via the project Basal-CMM.
Rights and permissions
About this article
Cite this article
Gaspers, S., Kratsch, D. & Liedloff, M. On Independent Sets and Bicliques in Graphs. Algorithmica 62, 637–658 (2012). https://doi.org/10.1007/s00453-010-9474-1
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00453-010-9474-1