×

On co-bicliques. (English) Zbl 1227.90043

Summary: A co-biclique of a simple undirected graph \(G=(V,E)\) is the edge-set of two disjoint complete subgraphs of \(G\). (A co-biclique is the complement of a biclique.) A subset \(F\subseteq E\) is an independent of \(G\) if there is a co-biclique \(B\) such that \(F\subseteq B\), otherwise \(F\) is a dependent of \(G\). This paper describes the minimal dependents of \(G\). (A minimal dependent is a dependent \(C\) such that any proper subset of \(C\) is an independent.) It is shown that a minimum-cost dependent set of \(G\) can be determined in polynomial time for any nonnegative cost vector \(x\in\mathbb Q_+^E\). Based on this, we obtain a branch-and-cut algorithm for the maximum co-biclique problem which is, given a weight vector \(w\in\mathbb Q_+^E\), to find a co-biclique \(B\) of \(G\) maximizing \(w(B)=\sum_{e\in B}w_e\).

MSC:

90C35 Programming involving graphs or networks
90C09 Boolean programming
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
05C85 Graph algorithms (graph-theoretic aspects)
PDFBibTeX XMLCite
Full Text: DOI EuDML Link

References:

[1] D. Cornaz, A linear programming formulation for the maximum complete multipartite subgraph problem. Math. Program. B105 (2006) 329-344. Zbl1079.05093 · Zbl 1079.05093 · doi:10.1007/s10107-005-0656-6
[2] D. Cornaz and J. Fonlupt, Chromatic characterization of biclique cover. Discrete Math.306 (2006) 495-507. · Zbl 1087.05043 · doi:10.1016/j.disc.2006.01.010
[3] D. Cornaz and A.R. Mahjoub, The maximum induced bipartite subgraph problem with edge weights. SIAM J. on Discrete Math. to appear. Zbl1141.05076 · Zbl 1141.05076 · doi:10.1137/060650015
[4] D. Cornaz, On forests, stable sets and polyhedra associated with clique partitions. Manuscript available on Optimization Online. · Zbl 1221.05132
[5] V. Jost, Ordonnancement chromatique : polyèdres, complexité et classification. Thèse de l’Université Joseph Fourier, Grenoble (2006).
[6] M. Grötschel, L. Lovàsz and A. Schrijver, The ellipsoid method and its consequences in combinatorial optimization. Combinatorica1 (1981) 169-197. Zbl0539.90078 · Zbl 0539.90078
[7] D. Monson, N.J. Pullman and R. Rees, A survey of clique and biclique coverings and factorizations of (0,1)-matrices. Bull. I.C.A.14 (1995) 17-86. Zbl0832.05088 · Zbl 0832.05088
[8] A. Schrijver, Combinatorial Optimization. Springer-Verlag, Berlin Heidelberg (2003). · Zbl 1041.90001
[9] A. Sebő, private communication.
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.