𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On Bipartite and Multipartite Clique Problems

✍ Scribed by Milind Dawande; Pinar Keskinocak; Jayashankar M Swaminathan; Sridhar Tayur

Publisher
Elsevier Science
Year
2001
Tongue
English
Weight
131 KB
Volume
41
Category
Article
ISSN
0196-6774

No coin nor oath required. For personal study only.

✦ Synopsis

In this paper, we introduce the maximum edge biclique problem in bipartite graphs and the edge/node weighted multipartite clique problem in multipartite graphs. Our motivation for studying these problems came from abstractions of real manufacturing problems in the computer industry and from formal concept analysis. We show that the weighted version and four variants of the unweighted version of the biclique problem are NP-complete. For random bipartite graphs, we show that the size of the maximum balanced biclique is considerably smaller than the size of the maximum edge cardinality biclique, thus highlighting the difference between the two problems. For multipartite graphs, we consider three versions each for the edge and node weighted problems which differ in the structure of the multipartite clique (MPC) required. We show that all the edge weighted versions are NP-complete in general. We also provide a special case in which edge weighted versions are polynomially solvable.

πŸ“œ SIMILAR VOLUMES

Approximating Clique and Biclique Proble
Approximating Clique and Biclique Problems
✍ Dorit S. Hochbaum πŸ“‚ Article πŸ“… 1998 πŸ› Elsevier Science 🌐 English βš– 317 KB

We present here 2-approximation algorithms for several node deletion and edge deletion biclique problems and for an edge deletion clique problem. The biclique problem is to find a node induced subgraph that is bipartite and complete. The objective is to minimize the total weight of nodes or edges de

On the Ramsey Problem for Multicolor Bip
On the Ramsey Problem for Multicolor Bipartite Graphs
✍ W.A Carnielli; E.L Monte Carmelo πŸ“‚ Article πŸ“… 1999 πŸ› Elsevier Science 🌐 English βš– 85 KB

Given i, j positive integers, let K denote a bipartite complete graph and let i, j ## Ε½ . R m, n be the smallest integer a such that for any r-coloring of the edges of K r a, a one can always find a monochromatic subgraph isomorphic to K . In other m, n Ε½ . Γ„ 4 words, if a G R m, n then every mat

On cliques and bicliques
On cliques and bicliques
✍ Henning, Michael A. πŸ“‚ Article πŸ“… 2000 πŸ› John Wiley and Sons 🌐 English βš– 97 KB πŸ‘ 1 views

For integers m, n β‰₯ 2, let g(m, n) be the minimum order of a graph, where every vertex belongs to both a clique K m of order m and a biclique K(n, n). or, if m is sufficiently large and (m -1)(n -1) is not an integer.

On bipartite 2-factorizations of kn βˆ’ I
On bipartite 2-factorizations of kn βˆ’ I and the Oberwolfach problem
✍ Darryn Bryant; Peter Danziger πŸ“‚ Article πŸ“… 2010 πŸ› John Wiley and Sons 🌐 English βš– 180 KB

It is shown that if F 1 , F 2 , ...,F t are bipartite 2-regular graphs of order n and 1 , 2 , . . . , t are positive integers such that 1 + 2 +β€’ β€’ β€’+ t = (n-2) / 2, 1 β‰₯ 3 is odd, and i is even for i = 2, 3, . . . , t, then there exists a 2-factorization of K n -I in which there are exactly i 2-facto

NP completeness of the edge precoloring
NP completeness of the edge precoloring extension problem on bipartite graphs
✍ JiΕ™Γ­ Fiala πŸ“‚ Article πŸ“… 2003 πŸ› John Wiley and Sons 🌐 English βš– 63 KB πŸ‘ 1 views

## Abstract We show that the following problem is __NP__ complete: Let __G__ be a cubic bipartite graph and __f__ be a precoloring of a subset of edges of __G__ using at most three colors. Can __f__ be extended to a proper edge 3‐coloring of the entire graph __G__? This result provides a natural co