{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T04:00:34Z","timestamp":1760241634106,"version":"build-2065373602"},"reference-count":20,"publisher":"MDPI AG","issue":"6","license":[{"start":{"date-parts":[[2018,6,12]],"date-time":"2018-06-12T00:00:00Z","timestamp":1528761600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100000930","name":"NSF","doi-asserted-by":"publisher","award":["1247581"],"award-info":[{"award-number":["1247581"]}],"id":[{"id":"10.13039\/501100000930","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>Covering the edges of a bipartite graph by a minimum set of bipartite complete graphs (bicliques) is a basic graph theoretic problem, with numerous applications. In particular, it is used to characterize parsimonious models of a set of observations (each biclique corresponds to a factor or feature that relates the observations in the two sets of nodes connected by the biclique). The decision version of the minimum biclique cover problem is NP-Complete, and unless P=NP, the cover size cannot be approximated in general within less than a sub-linear factor of the number of nodes (or edges) in the graph. In this work, we consider two natural restrictions to the problem, motivated by practical applications. In the first case, we restrict the number of bicliques a node can belong to. We show that when this number is at least 5, the problem is still NP-hard. In contrast, we show that when nodes belong to no more than two bicliques, the problem has efficient approximations. The second model we consider corresponds to observing a set of independent samples from an unknown model, governed by a possibly large number of factors. The model is defined by a bipartite graph G=(L,R,E), where each node in L is assigned to an arbitrary subset of up to a constant f factors, while the nodes in R (the independent observations) are assigned to random subsets of the set of k factors where k can grow with size of the graph. We show that this practical version of the biclique cover problem is amenable to efficient approximations.<\/jats:p>","DOI":"10.3390\/a11060084","type":"journal-article","created":{"date-parts":[[2018,6,12]],"date-time":"2018-06-12T10:58:32Z","timestamp":1528801112000},"page":"84","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Efficient Approximation for Restricted Biclique Cover Problems"],"prefix":"10.3390","volume":"11","author":[{"given":"Alessandro","family":"Epasto","sequence":"first","affiliation":[{"name":"Google Research, New York, NY 10011, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9321-9460","authenticated-orcid":false,"given":"Eli","family":"Upfal","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Brown University, Providence, RI 02912, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2018,6,12]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","unstructured":"Chalermsook, P., Heydrich, S., Holm, E., and Karrenbauer, A. (2014). Nearly Tight Approximability Results for Minimum Biclique Cover and Partition. Algorithms-ESA 2014, Springer.","DOI":"10.1007\/978-3-662-44777-2_20"},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"2045","DOI":"10.1016\/j.tcs.2008.12.059","article-title":"Covering graphs with few complete bipartite subgraphs","volume":"410","author":"Fleischner","year":"2009","journal-title":"Theor. Comput. Sci."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"294","DOI":"10.1137\/0403025","article-title":"On approximate solutions for combinatorial optimization problems","volume":"3","author":"Simon","year":"1990","journal-title":"SIAM J. Discret. Math."},{"key":"ref_4","doi-asserted-by":"crossref","unstructured":"Gruber, H., and Holzer, M. (2007). Inapproximability of nondeterministic state and transition complexity assuming P \u2260 NP. Developments in Language Theory, Springer.","DOI":"10.1007\/978-3-540-73208-2_21"},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"406","DOI":"10.1016\/1385-7258(77)90055-5","article-title":"Contentment in graph theory: Covering graphs with cliques","volume":"Volume 80","author":"Orlin","year":"1977","journal-title":"Indagationes Mathematicae (Proceedings)"},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"3399","DOI":"10.1016\/j.disc.2008.09.036","article-title":"On covering graphs by complete bipartite subgraphs","volume":"309","author":"Jukna","year":"2009","journal-title":"Discret. Math."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1016\/j.ic.2011.03.008","article-title":"Mod\/Resc parsimony inference: Theory and application","volume":"213","author":"Nor","year":"2012","journal-title":"Inf. Comput."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"E15","DOI":"10.1086\/670612","article-title":"On the genetic architecture of cytoplasmic incompatibility: Inference from phenotypic data","volume":"182","author":"Nor","year":"2013","journal-title":"Am. Nat."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"243","DOI":"10.1016\/0025-5564(78)90088-3","article-title":"A mathematical analysis of human leukocyte antigen serology","volume":"40","author":"Nau","year":"1978","journal-title":"Math. Biosci."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"1348","DOI":"10.1109\/TKDE.2008.53","article-title":"The discrete basis problem","volume":"20","author":"Miettinen","year":"2008","journal-title":"IEEE Trans. Knowl. Data Eng."},{"key":"ref_11","unstructured":"Mishra, N., Ron, D., and Swaminathan, R. (2003, January 24\u201327). Learning Theory and Kernel Machines. Proceedings of the 16th Annual Conference on Learning Theory and 7th Kernel Workshop COLT\/Kernel 2003, Washington, DC, USA."},{"key":"ref_12","unstructured":"Hirsch, M., Meijer, H., and Rappaport, D. (2006). Biclique edge cover graphs and confluent drawings. Graph Drawing, Springer."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"159","DOI":"10.1016\/0012-365X(94)00350-R","article-title":"On edge perfectness and classes of bipartite graphs","volume":"149","year":"1996","journal-title":"Discret. Math."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"125","DOI":"10.1016\/S0166-218X(98)00039-0","article-title":"Complexity of minimum biclique cover and minimum biclique decomposition for bipartite domino-free graphs","volume":"86","author":"Amilhastre","year":"1998","journal-title":"Discret. Appl. Math."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"388","DOI":"10.1006\/jagm.2001.1199","article-title":"On bipartite and multipartite clique problems","volume":"41","author":"Dawande","year":"2001","journal-title":"J. Algorithms"},{"key":"ref_16","unstructured":"Javadi, R., Maleki, Z., and Omoomi, B. (arXiv, 2012). Local Clique Covering of Graphs, arXiv."},{"key":"ref_17","doi-asserted-by":"crossref","unstructured":"Arora, S., Ge, R., Sachdeva, S., and Schoenebeck, G. (2012, January 4\u20138). Finding overlapping communities in social networks: Toward a rigorous approach. Proceedings of the 13th ACM Conference on Electronic Commerce, Valencia, Spain.","DOI":"10.1145\/2229012.2229020"},{"key":"ref_18","unstructured":"Cheng, Y., and Church, G.M. (2000). Biclustering of Expression Data, ISMB."},{"key":"ref_19","doi-asserted-by":"crossref","unstructured":"Kr\u00e1l\u2019, D., Kratochv\u00edl, J., Tuza, Z., and Woeginger, G. (2001). Complexity of coloring graphs without forbidden induced subgraphs. Graph-Theoretic Concepts in Computer Science, Springer.","DOI":"10.1007\/3-540-45477-2_23"},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"266","DOI":"10.1007\/BF01190507","article-title":"The complexity of induced minors and related problems","volume":"13","author":"Fellows","year":"1995","journal-title":"Algorithmica"}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/11\/6\/84\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T15:08:19Z","timestamp":1760195299000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/11\/6\/84"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,6,12]]},"references-count":20,"journal-issue":{"issue":"6","published-online":{"date-parts":[[2018,6]]}},"alternative-id":["a11060084"],"URL":"https:\/\/doi.org\/10.3390\/a11060084","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2018,6,12]]}}}