Independent transversals of hypergraph edges and bipartite bigraphs (Q1974346)

For a hypergraph \(H\), a subset \(X\subset V(H)\) is called a transversal (or a vertex covering) if \(X\cap e\neq \varnothing\) for any edge \(e\in E(H)\) and a subset \(I\subset V(H)\) is said to be independent if it contains no edge of \(H\). In this paper for two hypergraphs \(G\) and \(H\) having the same vertex set \(V(G)=V(H)=V\) the following two problems are considered: (1) Determine whether there exists a subset \(I\subset V\) which is independent in \(G\) and is a transversal in \(H\). (2) Determine whether there exists a partition \(V=X\cup Y\) such that \(X\) is independent in \(G\) and \(Y\) is independent in \(H\). It is proved that the problems (1) and (2) are NP-complete, even when \(G\) is a graph, but they become polynomially solvable, provided that both \(G\) and \(H\) are graphs.