Equality of domination and transversal numbers in hypergraphs

A subset SS of the vertex set of a hypergraph HH is called a dominating set of HH if for every vertex vv not in SS there exists u∈Su∈S such that uu and vv are contained in an edge in HH. The minimum cardinality of a dominating set in HH is called the domination number of HH and is denoted by γ(H)γ(H). A transversal of a hypergraph HH is defined to be a subset TT of the vertex set such that T∩E≠0̸T∩E≠0̸ for every edge EE of HH. The transversal number of HH, denoted by τ(H)τ(H), is the minimum number of vertices in a transversal. A hypergraph is of rank kk if each of its edges contains at most kk vertices.The inequality τ(H)≥γ(H)τ(H)≥γ(H) is valid for every hypergraph HH without isolated vertices. In this paper, we investigate the hypergraphs satisfying τ(H)=γ(H)τ(H)=γ(H), and prove that their recognition problem is NP-hard already on the class of linear hypergraphs of rank 3, while on unrestricted problem instances it lies inside the complexity class Θ2p.Structurally we focus our attention on hypergraphs in which each subhypergraph H′H′ without isolated vertices fulfills the equality τ(H′)=γ(H′)τ(H′)=γ(H′). We show that if each induced subhypergraph satisfies the equality then it holds for the non-induced ones as well. Moreover, we prove that for every positive integer kk, there are only a finite number of forbidden subhypergraphs of rank kk, and each of them has domination number at most kk.