中央研究院 資訊科學研究所

For a hypergraph $H$, the transversal is a subset of vertices whose intersection with every edge is nonempty. The cardinality of a minimum transversal is the transversal number of $H$, denoted by $[@BackSlash]tau(H)$. The Tuza constant $c_k$ is defined as $[@BackSlash]sup{[@BackSlash]tau(H)/ (m+n)}$, where $H$ ranges over all $k$-uniform hypergrpahs, with $m$ and $n$ being the number of edges and vertices, respectively. The upper bounds on $c_k$ can be obtained by a kind of linear programs, in which the numbers of variables are different. In this talk, we give an analysis of how good the bound can be achieved based on the linear programming approach.