Problems and invariants connected with bicliques and multicliques of graphs

V. V. Lepin ; O. I. Duginov

Trudy Instituta matematiki, Tome 21 (2013) no. 2, pp. 103-127.

Résumé

It is given a survey the selected results on graph problems and invariants related to bicliques (complete biparite subgraphs) and multicliques (complete multipartite subgraphs) of graphs. Besides, new euristics for solving the minimum biclique cover problem are given.

Bibliographie

[1] Lepin V. V., “Algoritmy dlya nakhozhdeniya multiklikovoi i biklikovoi stepeni posledovatelno-parallelnogo grafa”, Trudy Instituta matematiki, 18:2 (2010), 60–78 | MR | Zbl

[2] Lepin V. V., Duginov O. I., “Algoritmy dlya nakhozhdeniya pokrytii biklikami grafa s ogranichennoi putevoi shirinoi”, Trudy Instituta matematiki, 19:2 (2011), 69–81 | MR | Zbl

[3] Lepin V. V., Duginov O. I., “Vychislenie chisla biklikovogo razbieniya grafa so spetsialnymi blokami”, Trudy Instituta matematiki, 20:1 (2012), 60–73 | MR

[4] Lepin V. V., “Lineinyi algoritm dlya vychisleniya chisla biklikovogo pokrytiya posledovatelno-parallelnogo grafa”, Trudy Instituta matematiki, 16:2 (2008), 63–75 | MR | Zbl

[5] Lepin V. V., “Lineinyi algoritm dlya vychisleniya chisla multiklikovogo pokrytiya posledovatelno-parallelnogo grafa”, Trudy Instituta matematiki, 17:1 (2009), 90–102 | Zbl

[6] Lepin V. V., Duginov O. I., “O biklikovom razbienii korony i soedineniya grafov”, Dokl. NAN Belarusi, 56:3 (2012), 10–15

[7] Lepin V. V., Duginov O. I., “O chisle biklikovogo pokrytiya dekartova proizvedeniya grafov”, Trudy Instituta matematiki, 21:1 (2013), 78–87

[8] Acuña V., Ferreira C., Freire A., Moreno E., “Solving the maximum edge biclique packing problem on unbalanced bipartite graphs”, Disc. App. Math., 2013 (to appear)

[9] Alexe G., Alexe S., Crama Y., Foldes S., Hammer P., Simeone B., “Consensus algorithms for the generation of all maximal bicliques”, Discrete Applied Mathematics, 145 (2004), 11–21 | DOI | MR | Zbl

[10] Alon N., Caro Y., Yuster R., “Packing and Covering Dense Graphs”, Journal of Combinatorial Designs, 6:6 (1998), 451–472 | 3.0.CO;2-E class='badge bg-secondary rounded-pill ref-badge extid-badge'>DOI | MR | Zbl

[11] Amiliastre J., Vilarem M., Janssen P., “Complexity of minimum biclique cover and minimum biclique decomposition for bipartite domino-free graphs”, Discrete Appl. Math., 86 (1998), 125–144 | DOI | MR

[12] Bein D., Morales L., Bein W., Shields C. O. (Jr.), Meng Z., Sudborough I. H., “Clustering and the Biclique Partition Problem”, Hawaii International Conference on System Sciences (2008), 475 | Zbl

[13] Binkele-Raiblea D., Fernaua H., Gaspersb S., Liedloffc M., “Exact exponential-time algorithms for finding bicliques”, Information Processing Letters, 111:2 (2010), 64–67 | DOI | MR

[14] Bollobas B., “On Complete Subgraphs of Different Orders”, Mathematical Proceedings of the Cambridge Philosophical Society, 79:1 (1976), 19–24 | DOI | MR | Zbl

[15] Blundo S., De Santis A., Stinson D., Vaccaro U., “Graph decompositions and secret sharing schemes”, Journal of Cryptology, 8 (1995), 39–64 | DOI | MR | Zbl

[16] Brickell E., Stinson D., “Some Improved Bounds on the Information Rate of Perfect Secret Sharing Schemes”, J. Cryptology, 5 (1992), 153–166 | DOI | MR | Zbl

[17] Caro Y., Yuster R., “Covering Graphs: The Covering Problem Solved”, Journal of Combinatorial Theory. Series A, 83 (1998), 273–282 | DOI | MR | Zbl

[18] Caro Y., Yuster R., “Packing Graphs: The packing problem solved”, Electr. J. Comb., 4:1 (1997) | MR

[19] Caro Y., Yuster R., “Efficient covering designs of the complete graph”, Electr. J. Comb., 4:1 (1997) | MR

[20] Caro Y., Yuster R., “Graph decomposition of slim graphs”, Graphs Comb., 15:1 (1999), 5–19 | MR | Zbl

[21] De Caen D., Hoffman D., “Impossibility of decomposing the complete graph on $n$ points into $n-1$ isomorphic complete bipartite graphs”, SIAM J. Disc. Math., 2 (1989), 48–50 | DOI | MR

[22] De Caen D., Gregory D., Pullman N., “The Boolean rank of zero-one matrices”, Proceedings of the Third Caribbean Conference on Combinatorics and Computing (1981), 169–173 | MR | Zbl

[23] Chakrabarti D., Papadimitriou S., Modha D., Falautsos C., “Fully automatic cross-association”, Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining (2004), 79–88

[24] Chung F., “On the coverings of graphs”, Discr. Math., 30 (1980), 89–93 | DOI | MR | Zbl

[25] Chung F., Erdös P., Spencer J., “On the decomposition of graphs into complete bipartite subgraphs”, Studies in Pure Mathematics, 1983, 95–101 | DOI | MR | Zbl

[26] Chung F., Graham R., “Recent results in graph decomposition”, Proc. of the 8th British Comb. Conf. (1981), 103–123 | MR | Zbl

[27] Cioaba S. M., Tait M., “More Counterexamples to the Alon–Saks–Seymour and Rank-Coloring Conjectures”, The electronic journal of combinatorics, 18 (2011), 9 pp. | MR | Zbl

[28] Cornaz D., Fonplut J., “Chromatic characterization of biclique covers”, Discr. Math., 306 (2006), 495–507 | DOI | MR | Zbl

[29] Dawande M., Keskinocak P., Swaminathan J. M., Tayur S., “On bipartite and multipartite clique problems”, Journal of Algorithms, 41 (2001), 388–403 | DOI | MR | Zbl

[30] Dias V., de Figueiredo C., Szwarcfiter J., “On the generation of bicliques of a graph”, Discrete Applied Mathematics, 155 (2007), 1826–1832 | DOI | MR | Zbl

[31] Dias V., de Figueiredo C., Szwarcfiter J., “Generating bicliques of a graph in lexicographic order”, Theoretical Computer Science, 337 (2005), 240–248 | DOI | MR | Zbl

[32] Dong L., Liu Y., “On the decomposition of graphs into complete bipartite graphs”, Graphs and Combinatorics, 23 (2007), 255–262 | DOI | MR | Zbl

[33] Dor D., Tarsi M., “Graph decomposition is NPC — A complete proof of Holyer's conjecture”, Proc. 20th ACM STOC (1992), 252–263

[34] Eppstein D., “Arboricity and bipartite subgraph listing algorithms”, Information Processing Letters, 51 (1994), 207–211 | DOI | MR | Zbl

[35] Erdös P., Goodman A. W., Pósa L., “The Representation of a Graph by Set Intersections”, Canadian Journal of Mathematics, 18 (1966), 106–112 | DOI | MR | Zbl

[36] Fernau H., Niedermeier R., “An efficient exact algorithm for constraint bipartite vertex cover”, Journal of Algorithms, 38:2 (2001), 374–410 | DOI | MR | Zbl

[37] Fishburn P., Hammer P., “Bipartite dimensions and bipartite degrees of graphs”, Discr. Math., 160 (1996), 127–148 | DOI | MR | Zbl

[38] Fleischner H., Mujuni E., Paulusma D., Szeider S., “Covering graphs with few complete bipartite subgraphs”, Theor. Comput. Sci., 410 (2009), 2045–2053 | DOI | MR | Zbl

[39] Froidure V., Rangs des relations binaires, semigroupes de relations non ambigues, Phd thesis, Univ. Paris VI, 1995

[40] Gao Z., McKay B. D., Naserasr R., Stevens B., “On Alon–Saks–Seymour Conjecture”, J. graph theory, 2010 (to appear)

[41] Gaspers S., Kratsch D., Liedloff M., “On Independent Sets and Bicliques in Graphs”, Graph-Theoretic Concepts in Computer Science, 2008, 171–182 | Zbl

[42] Gillis N., Glineur F., “A Continuous Characterization of the Maximum-Edge Biclique Problem”, Journal of Global Optimization, 2012 (to appear)

[43] Goerdt A., Lanka A., “An approximation hardness result for bipartite Clique”, Electronic Colloquium on Computational Complexity, 2004, 48, 15 pp.

[44] Graham R., Pollak H., “On embedding graphs in squashed cubes”, Graph Theory and Applications, Proc. 2nd Internat. Conf. Graph Theory (Kalamazoo, 1972), Lecture Notes in Math., 303, 1973, 99–110 | DOI | MR

[45] Graham R., Pollak H., “On the addressing problem for loop switching”, Bell. System Tech., 50 (1971), 2495–2519 | DOI | MR | Zbl

[46] Gregory D., Shader B., Watts V., “Biclique decompositions and Hermitian rank”, Linear Algebra Appl., 292 (1999), 267–280 | DOI | MR | Zbl

[47] Gregory D., “Expressing graphs in terms of complete bipartite graphs”, Queen's-R.M.C. Discrete Mathematics Seminar http://www.mast.queensu.ca/g̃regoryd/Notes/ExpressGraphBicliques.pdf

[48] Gregory D., Heyink B., Vander Meulen K., “Inertia and biclique decompositions of joins of graphs”, Journal of Combinatorial Theory, Series B, 88 (2003), 135–151 | DOI | MR | Zbl

[49] Groshaus M., Szwarcfiter J. L., “Biclique-Helly Graphs”, Graphs and Combinatorics, 23 (2007), 633–645 | DOI | MR | Zbl

[50] Groshaus M., Szwarcfiter J. L., “Biclique graphs and biclique matrices”, Journal of Graph Theory, 63 (2010), 1–16 | DOI | MR | Zbl

[51] Günlück O., “A New Min-Cut Max-Flow Ratio for Multicommodity Flows”, Integer Programming and Combinatorial Optimization, 9th International IPCO Conference (Cambridge, MA, USA, 2002), 54–66 | MR

[52] Haemers W. H., “Bicliques and Eigenvalues”, J. Comb. Theory (B), 82:1 (2001), 56–66 | DOI | MR | Zbl

[53] Harary F., Hsu D., Miller Z., “The biparticity of a graph”, J. Graph Theory, 1 (1977), 131–133 | DOI | MR | Zbl

[54] Heydari M., Morales L., Shields C., Sudborough L., “Computing cross associations for attack graphs and other applications”, Proceedings of the 40th Hawaii International Conference on Systems Science (2007), 270

[55] Hochbaum D., “Approximating clique and biclique problems”, Journal of Algorithms, 29 (1998), 174–200 | DOI | MR | Zbl

[56] Hochbaum D., Levin A., “Covering the edges of bipartite graphs using $K_{2,2}$ graphs”, Theor. Comput. Sci., 411:1 (2010), 1–9 | DOI | MR | Zbl

[57] Hoffman A., “Eigenvalues and partitionings of the edges of a graph”, Linear Algebra Appl., 5 (1972), 137–146 | DOI | MR | Zbl

[58] Holyer I., “The NP-completeness of some edge-partition problems”, SIAM J. Comput., 10 (1981), 713–717 | DOI | MR | Zbl

[59] Huang C., “On the existence of balanced bipartite designs, II”, Discrete Mathematics, 9 (1974), 147–159 | DOI | MR | Zbl

[60] Huang C., Rosa A., “On the existence of balanced bipartite designs”, Utilitas Math., 4 (1973), 55–75 | MR | Zbl

[61] Huang H., Sudakov B., “A counterexample to the Alon–Saks–Seymour conjecture and related problems”, Combinatorica, 32 (2012), 205–219 | DOI | MR | Zbl

[62] Schonheim J., Bialostocki A., “Packing and covering of the complete graph with 4-cycles”, Canadian Math. Bull., 18 (1975), 703–708 | DOI | MR | Zbl

[63] Jiang T., Ravikumar B., “Minimal NFA Problems are hard”, SIAM J. Comput., 22 (1993), 1117–1141 | DOI | MR | Zbl

[64] Jukna S., Kulikov A., “On covering graphs by complete bipartite subgraphs”, Discrete Mathematics, 309 (2009), 3399–3403 | DOI | MR | Zbl

[65] Kahn J., “Recent results on some not-so-recent hypergraph matching and covering problems”, Extremal problems for finite sets (1991), Bolyai Soc. Math. Stud. Janos Bolyai Math. Soc., Budapest, 1994, 305–353 | MR | Zbl

[66] Kloks T., Kratsch D., “Computing a perfect edge without vertex elimination ordering of a chordal bipartite graph”, Information Processing Letters, 55 (1995), 11–16 | DOI | MR | Zbl

[67] Kratzke T., Reznick B., West D., “Eigensharp Graphs: Decomposition into Complete Bipartite Subgraphs”, Transactions of the American Mathematical Society, 308 (1988), 637–653 | DOI | MR | Zbl

[68] Kushilevitz E., Nisan N., Communication Complexity, Cambridge University Press, 2006 | MR

[69] Levin A., “Approximating the Unweighted $k$-Set Cover Problem: Greedy Meets Local Search”, SIAM J. Discrete Math., 23:1 (2008), 251–264 | DOI | MR | Zbl

[70] Li W., Seshia S., A Sparse Coding Method for Specification Mining and Error Localization, Technical report, EECS Department, University of California, Berkeley, 2011

[71] Li J., Liu G., Li H., Wong L., “Maximal Biclique Subgraphs and Closed Pattern Pairs of the Adjacency Matrix: A One-to-one Correspondence and Mining Algorithms”, Journal IEEE Transactions on Knowledge and Data Engineering, 19 (2007), 1625–1637 | DOI

[72] Lin C., Lin J.-J., Shyu T.-W., “Complete bipartite decompositions of crowns, with applications to complete directed graphs”, Combinatorics and Computer Science, 8th Franco-Japanese and 4th Franco-Chinese Conference (Brest, France, 1996), Lecture Notes in Computer Science, 1120, 58–66 | DOI | MR

[73] Lubiw A., “A weighted min-max relation for intervals”, J. Combin. Theory, 53 (1991), 151–172 | DOI | MR | Zbl

[74] Lubiw A., “The boolean basis problem and how to cover some polygons by rectangles”, SIAM J. Discrete Math., 1990, 98–115 | DOI | MR | Zbl

[75] Müller H., “Alternating cycle-free matchings”, Order, 7 (1990), 11–21 | DOI | MR | Zbl

[76] Müller H., “On edge perfectness and classes of bipartite graphs”, Discr. Math., 149 (1996), 159–187 | DOI | MR | Zbl

[77] Makino T., Uno T., “New Algorithms for Enumerating All Maximal Cliques”, SWAT (2004), LNCS, 3111, 260–272 | MR | Zbl

[78] Martin B., Paulusma D., “The Computational Complexity of Disconnected Cut and $2K_2$-Partition”, Principles and Practice of Constraint Programming, 2011, 561–575

[79] Monson S., Pullman N., Rees R., “A survey of clique and biclique coverings and factorizations of $(0,1)$-matrices”, Bulletin of the I. C. A., 14 (1995), 17–86 | MR | Zbl

[80] Mubayi D., Vishwanathan S., “Bipartite Coverings and the Chromatic Number”, Electron. J. Combin., 16:1 (2009), 5 | MR | Zbl

[81] Nau D. S., Markowsky G., Woodbury M. A., Amos D. B., “A mathematical analysis of human leukocyte antigen serology”, Math. Biosci., 40 (1978), 240–270 | DOI | MR

[82] Nor I., Hermelin D., Charlat S., Engelstadter J., Reuter M., Duron O., Sagot M.-F., “Mod/Resc Parsimony Inference: Theory and application”, Information and Computation, 213 (2012), 23–32 | DOI | MR | Zbl

[83] Nussbaum D., Pu S., Sack J.-R., Uno T., Zarrabi-Zadeh H., “Finding Maximum Edge Bicliques in Convex Bipartite Graphs”, Algorithmica, 64 (2012), 311–325 | DOI | MR | Zbl

[84] Orlin J., “Containment in Graph Theory: covering graphs with cliques”, Nederl. Akad. Wetensch. Indag. Math., 39 (1977), 211–218 | MR

[85] Ozkahya L., Person Y., “Minimum $H$-Decompositions of Graphs: Edge-Critical Case”, Journal of Combinatorial Theory, Series B, 102:3 (2012), 715–725 | DOI | MR | Zbl

[86] Peck G., “A new proof of a theorem of Graham and Pollak”, Discrete Mathematics, 49 (1984), 327–328 | DOI | MR | Zbl

[87] Peeters R., “The maximum edge biclique problem is NP-complete”, Discrete Applied Mathematics, 131 (2003), 651–654 | DOI | MR | Zbl

[88] Pikhurko O., Sousa T., “Minimum $H$-Decompositions of Graphs”, Journal of Combinatorial Theory B, 97 (2007), 1041–1055 | DOI | MR | Zbl

[89] Pottosina S., Pottosin Y., Sedliak B., “Finding maximal complete bipartite subgraphs in a graph”, J. Applied Mathematics, 1:1 (2008), 75–81

[90] Priesler M., Tarsi M., “Multigraph decomposition into stars and into multistars”, Discrete Mathematics, 296 (2005), 235–244 | DOI | MR | Zbl

[91] Priesler M., Tarsi M., “On some multigraph decomposition problems and their computational complexity”, Discrete Mathematics, 281 (2004), 247–254 | DOI | MR | Zbl

[92] Prisner E., “Bicliques in graphs. I: Bounds on their number”, Combinatorica, 20 (2000), 109–117 | DOI | MR | Zbl

[93] Quadras J., Vasanthika S., “Biclique Cover of Complete Graph $K_n$ and Honeycomb Network $HC(n)$”, Informatics Engineering and Information Science Communications in Computer and Information Science, 252 (2011), 151–158 | DOI

[94] Reznick B., Tiwari P., West D., “Decomposition of product graphs into complete bipartite subgraphs”, Discrete Mathematics, 57 (1985), 189–193 | DOI | MR | Zbl

[95] Rho Y., “A Note on the Alon–Saks–Seymour Coloring Conjecture”, Ars Comb., 63 (2002), 289–292 | MR | Zbl

[96] Sousa T., “Minimum weight $H$-decompositions of graphs: the bipartite case”, Electron. J. Combin., 18:1 (2011), 126–135 | MR

[97] Sousa T., “4-Cycle Decompositions of Graphs”, Open Journal of Discrete Mathematics, 2 (2012), 125–130 | DOI

[98] Sousa T., “The $H$-Decomposition Problem for Graphs”, Applied Mathematics, 3 (2012), 1719–1722 | DOI

[99] Tverberg H., “On the decomposition of $K_n$ into complete bipartite graphs”, J. Graph. Theory, 46 (1982), 493–494 | DOI | MR

[100] Vashist A., Kulikowski C. A., Muchnik I., “Ortholog Clustering on a Multipartite Graph”, IEEE/ACM Transactions on computational biology and bioinformatics, 4:1 (2007), 17–27 | DOI

[101] Watts V., Covers and Partitions of Graphs by Complete Bipartite Subgraphs, Phd thesis, Queen's University, Kingston, Ontario, Canada, 2001

[102] Wilson R. M., “Decomposition of complete graphs into subgraphs isomorphic to a given graph”, Congressus Numerantium, XV (1975), 647–659 | MR

[103] Ene A., Horne W., Milosavljevic N., Rao P., Schreiber R., Tarjan R., “Fast exact and heuristic methods for role minimization problems”, SACMAT '08 Proceedings of the 13th ACM symposium on Access control models and technologies (2008), 1–10

[104] Vaidya J., Atluri V., Guo Q., “The role mining problem: Finding a minimal descriptive set of roles”, SACMAT '07 Proceedings of the 13th ACM symposium on Access control models and technologies (2007), 175–184

[105] Vaidya J., Atluri V., Warner J., “Roleminer: Mining roles using subset enumeration”, ACM CCS '06, 144–153

[106] Zhang D., Ramamohanarao K., Ebringer T., “Role engineering using graph optimisation”, SACMAT '07 Proceedings of the 13th ACM symposium on Access control models and technologies (2007), 139–144

[107] Saenko I., Kotenko I., “Genetic Algorithms for Role Mining Problem”, Proceedings of the 2011 19th International Euromicro Conference on Parallel, Distributed and Network-Based Processing (2011), 646–650

[108] Kellerman E., “Determination of keyword conflict”, IBM Technical Disclosure Bulletin, 16 (1973), 544–546

[109] Robertson N., Sanders D., Seymour P., Thomas R., “Efficiently four-coloring planar graphs”, STOC '96 Proceedings of the twenty-eighth annual ACM symposium on Theory of computing (1996), 571–575 | MR | Zbl

[110] Müller H., “On edge perfectness and classes of bipartite graphs”, Discr. Math., 149 (1996), 159–187 | DOI | MR | Zbl