Article ID: | iaor20112712 |
Volume: | 8 |
Issue: | 1 |
Start Page Number: | 18 |
End Page Number: | 24 |
Publication Date: | Feb 2011 |
Journal: | Discrete Optimization |
Authors: | Damaschke Peter |
Keywords: | combinatorial optimization, biology |
Motivated by the need for succinct representations of all ‘small’ transversals (or hitting sets) of a hypergraph of fixed rank, we study the complexity of computing such a representation. Next, the existence of a minimal hitting set of at least a given size arises as a subproblem. We give one algorithm for hypergraphs of any fixed rank, and we largely improve an earlier algorithm (by H. Fernau, 2005, ) for the rank‐2 case, i.e., for computing a minimal vertex cover of at least a given size in a graph. We were led to these questions by combinatorial aspects of the protein inference problem in shotgun proteomics.