An independent set of a graph is a subset of pairwise non-adjacent vertices. A complete bipartite set B is a subset of vertices admitting a bipartition B=X[union or logical sum]Y, such that both X and Y are independent sets, and all vertices of X are adjacent to those of Y. If both X,Y[not equal to][empty set], then B is called proper. A biclique is a maximal proper complete bipartite set of a graph. We present an algorithm that generates all bicliques of a graph in lexicographic order, with polynomial-time delay between the output of two successive bicliques. We also show that there is no polynomial-time delay algorithm for generating all bicliques in reverse lexicographic order, unless P=NP. The methods are based on those by Johnson, Papadimitriou and Yannakakis, in the solution of these two problems for independent sets, instead of bicliques.

@article{Dias2005240, author = {Dias, Vânia M.F. and de Figueiredo, Celina M.H. and Szwarcfiter, Jayme L.}, title = {Generating bicliques of a graph in lexicographic order}, journal = {Theoretical Computer Science}, year = {2005}, volume = {337}, number = {1-3}, pages = {240 - 248}, url = {http://www.sciencedirect.com/science/article/B6V1G-4FD0HTT-3/2/7efa1ee4d7b4823c7315a58b94f2f280}, doi = {DOI: 10.1016/j.tcs.2005.01.014}, issn = {0304-3975}, keywords = {conp, graph, independent, set, theory}, abstract = {An independent set of a graph is a subset of pairwise non-adjacent vertices. A complete bipartite set B is a subset of vertices admitting a bipartition B=X[union or logical sum]Y, such that both X and Y are independent sets, and all vertices of X are adjacent to those of Y. If both X,Y[not equal to][empty set], then B is called proper. A biclique is a maximal proper complete bipartite set of a graph. We present an algorithm that generates all bicliques of a graph in lexicographic order, with polynomial-time delay between the output of two successive bicliques. We also show that there is no polynomial-time delay algorithm for generating all bicliques in reverse lexicographic order, unless P=NP. The methods are based on those by Johnson, Papadimitriou and Yannakakis, in the solution of these two problems for independent sets, instead of bicliques.} }

%0 = article %A = Dias, Vânia M.F. and de Figueiredo, Celina M.H. and Szwarcfiter, Jayme L. %D = 2005 %T = Generating bicliques of a graph in lexicographic order %U = http://www.sciencedirect.com/science/article/B6V1G-4FD0HTT-3/2/7efa1ee4d7b4823c7315a58b94f2f280

The paper considers two decision problems on hypergraphs, hypergraph saturation and recognition of the transversal hypergraph, and discusses their significance for several search problems in applied computer science. Hypergraph saturation (i.e., given a hypergraph $l H$, decide if every subset of vertices is contained in or contains some edge of $l H$) is shown to be co-NP-complete. A certain subproblem of hypergraph saturation, the saturation of simple hypergraphs (i.e., Sperner families), is shown to be under polynomial transformation equivalent to transversal hypergraph recognition; i.e., given two hypergraphs $l H_1, l H_2$, decide if the sets in $l H_2$ are all the minimal transversals of $l H_1$. The complexity of the search problem related to the recognition of the transversal hypergraph, the computation of the transversal hypergraph, is an open problem. This task needs time exponential in the input size; it is unknown whether an output-polynomial algorithm exists. For several important subcases, for instance if an upper or lower bound is imposed on the edge size or for acyclic hypergraphs, output-polynomial algorithms are presented. Computing or recognizing the minimal transversals of a hypergraph is a frequent problem in practice, which is pointed out by identifying important applications in database theory, Boolean switching theory, logic, and artificial intelligence (AI), particularly in model-based diagnosis.

@article{219403, author = {Eiter, Thomas and Gottlob, Georg}, title = {Identifying the Minimal Transversals of a Hypergraph and Related Problems}, journal = {SIAM J. Comput.}, publisher = {Society for Industrial and Applied Mathematics}, address = {Philadelphia, PA, USA}, year = {1995}, volume = {24}, number = {6}, pages = {1278--1304}, url = {http://portal.acm.org/citation.cfm?id=219403}, doi = {http://dx.doi.org/10.1137/S0097539793250299}, issn = {0097-5397}, keywords = {complexity, conp, hypergraph, theory}, abstract = {The paper considers two decision problems on hypergraphs, hypergraph saturation and recognition of the transversal hypergraph, and discusses their significance for several search problems in applied computer science. Hypergraph saturation (i.e., given a hypergraph $l H$, decide if every subset of vertices is contained in or contains some edge of $l H$) is shown to be co-NP-complete. A certain subproblem of hypergraph saturation, the saturation of simple hypergraphs (i.e., Sperner families), is shown to be under polynomial transformation equivalent to transversal hypergraph recognition; i.e., given two hypergraphs $l H_1, l H_2$, decide if the sets in $l H_2$ are all the minimal transversals of $l H_1$. The complexity of the search problem related to the recognition of the transversal hypergraph, the computation of the transversal hypergraph, is an open problem. This task needs time exponential in the input size; it is unknown whether an output-polynomial algorithm exists. For several important subcases, for instance if an upper or lower bound is imposed on the edge size or for acyclic hypergraphs, output-polynomial algorithms are presented. Computing or recognizing the minimal transversals of a hypergraph is a frequent problem in practice, which is pointed out by identifying important applications in database theory, Boolean switching theory, logic, and artificial intelligence (AI), particularly in model-based diagnosis.} }

%0 = article %A = Eiter, Thomas and Gottlob, Georg %C = Philadelphia, PA, USA %D = 1995 %I = Society for Industrial and Applied Mathematics %T = Identifying the Minimal Transversals of a Hypergraph and Related Problems %U = http://portal.acm.org/citation.cfm?id=219403