当前位置:首页 >> >>

Complexity of minimum biclique decomposition of bipartite graphs

Complexity of minimum biclique decomposition of bipartite graphs

J. Amilhastre LIRMM UMR 9928 UNIVERSITE MONTPELLIER II/CNRS 16, Rue Ada Montpellier cedex 5 France email : {amilhast}@lirmm.fr

Abstract : Many problems studied in graph theory are graph decomposition problems. The minimum
number of complete bipartite graphs needed to partition the edges of a bipartite graph. is one of these problem and it is still open. We propose a NP-completness proof for its decision version and we show that it is polynomial on bipartite C4-free graphs.

1. Introduction
This note deals with the minimum number of edge-disjoint bicliques (complete bipartite graphs) needed to partition the edges of a bipartite graph. Let us denote BICLIQUE DECOMPOSITION the decision version of this problem. Problem : BICLIQUE DECOMPOSITION Instance : Bipartite graph B = (X,Y,E) , positive integer K Question : Can the edges of B be partitionned into k ≤ K disjoints sets E1, E2, ... , Ek such that, for 1 ≤ i ≤ k, Ei induces a complete bipartite subgraph of B ? Although the covering related problem, COVERING BY COMPLETE BIPARTITE SUBGRAPHS, has been proved to be NP-Complete (J. Orlin [1]) surprisingly, the partition version is still an open problem in graph theory. But no proof for BICLIQUE DECOMPOSITION can be directly obtain from the proof for
COVERING BY COMPLETE BIPARTITE SUBGRAPHS. It is in fact not obvious how to determine a minimum

partition by biclique from a minimum covering by biclique, because the property to be a biclique is not an hereditary property with respect to edge deletion. Therefore another reduction has to be found.
BICLIQUE DECOMPOSITION is one of the many graph decomposition problems which have been

studied in graph theory. Given F a family of graphs and G a graph, the decomposition (resp. cover) parameter of a graph G for F is the minimum number of subgraphs of G that belong to F needed to partition (resp. cover) the edges of G. The decomposition parameters have been very studied for a large number of graph families ; for a survey , see [6] . Among them, the decomposition parameters of graphs for F the family of all bicliques is interesting. A minimum biclique decomposition of a graph can have many

applications ; in particular such a decomposition yields efficient encoding of the graph. But, the computation of the biclique decomposition parameter of any graph is hard (the corresponding decision problem is NP-complete [6]). Recently, T. JIANG and B. RAVIKUMAR have proposed in [3] an NP-completness result on a language problem through which a NP-completness proof for BICLIQUE DECOMPOSITION can be obtained. We propose in the following a simple and direct proof for BICLIQUE DECOMPOSITION and a polynomial class for it, namely : the bipartite C4-free graphs.

2. Definitions and notations
Throughout this paper, a bipartite graph B is a finite, simple and undirected graph defined by (X(B), Y(B), E(B)). X(B) and Y(B) partition the vertices of B into two independant sets. E(B) denotes the set of edges of B. For any vertex x of B, N(x) = { y / {x, y} ∈ B } An edge {x , y} of B with x in X(B) and y in Y(B) is noted (x, y). A biclique of a bipartite graph B is a complete bipartite subgraph of B. A star is a n vertices graph with n-1 vertices of degree 1 and 1 vertex of degree n-1, the center of the star. The C4 is the four vertices cycle (a complete bipartite graph). A H-free graph is a graph which contains no graph of type H as induced subgraph.

3. Complexity of the BICLIQUE DECOMPOSITION problem
In [3] T.JIANG and B. RAVIKUMAR have used a problem called NORMAL SET BASIS to reduce a problem of finite automatons minimisation. There is a strong link between BICLIQUE DECOMPOSITION and the problem of finding minimum non ambigous automatons [5]. Then, the proof for BICLIQUE
DECOMPOSITION presented in this section is a modified version of their proof. This proof is also from NORMAL SET BASIS.

Problem : NORMAL SET BASIS Instance : C a collection of finite sets, positive integer K ≤ |C|. Question : Is there a normal set basis of cardinal k ≤ K for C i.e. a collection R of finite sets such that ? c ∈ C, there is a pairwise disjoint subcollection of R whose union is exactly c. We can note that this problem is a variation of the SET BASIS problem, which has been shown to be NP-Complete by STOCKMEYER [4].

Theorem 1. The NORMAL SET BASIS problem is NP-complete. Proof. The proof is due to T. JIANG and B. RAVIKUMAR. Their reduction is from VERTEX COVER [4] and can be found in [3].

Theorem 2. The BICLIQUE DECOMPOSITION problem is NP-Complete. Proof. Let us show that NORMAL SET BASIS can be polynomially reduced to B I C L I Q U E

DECOMPOSITION . ? Let I = (C,K) be an instance of NORMAL SET BASIS where C = {c1, c2, ..., cn}. Then, let I' = (B,K) be an instance of BICLIQUE DECOMPOSITION , constructed from I such that X(B) = C, Y(B) = U ci and ? ci ci∈C

∈ X, ? y ∈ Y, (ci, y) ∈ E(B) ? y ∈ ci. The building of I' from I is polynomial.
? Suppose that R = {r1, r2, ..., rk}, k ≤ K is a normal set basis for C. We can easily show that B can

be decomposed in k edge-disjoint bicliques. Let F be a function associating for each ci ∈ C, a pairwise disjoint subset of R whose union is exactly C. Then, let B(j) = {ci ∈ C /rj ∈ F(ci)} × rj , ? 1 ≤ j ≤ k. - By definition of B, ? 1 ≤ j ≤ k, B(j) induces a complete bipartite subgraph of B. - As ? ci ∈ C, F(ci) is composed of pairwise disjoint sets, ? 1 ≤ p< q ≤ k, B(p) ∩B(q) = ?
k

- By definition of R,

U B(j) = E(B).
j=1

Then, we have a biclique decomposition of B : B(1), B(2), ..., B(k).

?

Suppose that (V1 × W1), (V2 × W2), ..., (Vk × Wk), k ≤ K is a biclique decomposition of B. We can

show that W1, W2, .., Wk is a normal set basis for C directly given by this decomposition. Let F(j) = {Wi / cj ∈ Vi}, ? 1 ≤ j ≤ n. - By definition of B, ? 1 ≤ j ≤ n, ? Wi ∈ F(j), Wi ? cj . - As the bicliques of the decomposition are edge-disjoint, ? 1 ≤ j ≤ n, F(j) is composed of disjoint sets. - As {(Vi × Wi), 1 ≤ i ≤ k} is a partition of E(B), U Wi = cj, ? 1 ≤ j ≤ n
Wi∈F(j)

Then, W1, W2, ..., Wk is a normal set basis for C.

We can conclude that BICLIQUE DECOMPOSITION is NP-Complete.

3. Poynomial class
In this section, we present a class for which the BICLIQUE DECOMPOSITION problem is polynomial : the class of bipartite C4-free graphs.

Lemma 1. Let M2 ? E inducing a star of a bipartite graph B. For any M1 ? E that induces a biclique of B, M2 \ M1 induces a biclique of B or M2 ? M1.. Proof. "star" is an hereditary property for edge deletion.

Let B be a bipartite C4-free graphs. Any complete bipartite subgraph of B is a star. Then, let V be a minimum vertex cover of B i.e. a minimum subset of the vertices such that each edge has one of these endpoints in V.

Lemma 2. The minimum number of bicliques which are necessary to partition the edges of B is |V|. [6] Proof. ? Let E1, E2, ..., Ek be a biclique decomposition of B. Each Ei, 1 ≤ i ≤ k, induces a star of B whose center covers Ei. Then, the set of these centers is a vertex cover of B.

? Let V = {x1, x2, ..., xk} be a vertex cover of B. For each xi, S(xi) = {xi} × N(xi) induces a star of B
i?1

centered on xi. As lemma 1, for each xi in V, S(xi) \
k ?1

U S(xj) is a star. Then, the non nul sets among S(x1),
j=1

S(x2) \ S(x1), ...., S(xk) \

U S(xj) form a biclique decomposition of B in no more than k stars.
j=1

Property 1. For any graph, a minimum vertex cover is the complement of a maximal stable.

Theorem 3. Computing a minimum biclique decomposition of a bipartite C4-free graph is polynomial. Proof. From lemma 2, we can deduce a polynomial algorithm to compute a minimum biclique

decomposition of a bipartite C4-free graph B. Step 1 : compute S a maximum stable of B. This step is polynomial [7]. Step 2 : compute the set V of vertices of B not in S. By property 1, V is a minimum vertex cover of B. Step 3 : compute a minimum set of pairwise edge-disjoint stars centered on vertices in V that cover the edges of B.

4. Further work
We are interested in the complexity of BICLIQUE DECOMPOSITION for two graph classes : the distance hereditary bipartite graphs and the chordal bipartite graphs.

References
[1] J. Orlin (1977), "Containment in graph Theory : Covering graphs with cliques", Nederl. Akad. Wetensch. ndag. Math. , 39, 147-172 [2] Hans Urich Simon (1990), "On approximate solutions for combinatorial optimization problems", SIAM jourmal of dicrete mathematics, Vol 3, No 2, 294 - 310 Tao Jiang, B. Ravikumar (1993), "Minimal NFA problems are hard", SIAM jourmal of computation, Vol 22, No 6, 1117-1141 M. R. Garey, D. S. Johnson, "Computers and intractibility : A guide to the theory of NPCompletness", W. H. Freeman, San Francisco, 1979. Amilhastre J. (1994) ; "Représentation par automates de l'ensemble des solutions d'un CSP", Rapport de Recherche LIRMM, 94056, Univerité Montpellier II. T. Kratzke, B.Reznick and D. West (1988) , "Eigensharp graphs : decomposition into complete bipartite subgraphs", Transaction of the American Mathematical Society, V.308, N.2 [7] M. C. Golumbic ; "Algorithmic Graph Theory and Perfect Graphs", Academic Press, INC, New York, 1980.

[3]

[4]

[5]

[6]


更多相关标签: