Hitting all maximal independent sets of a bipartite graph (Q2354017): Difference between revisions

A maximal independent set in a graph is a subset of pairwise nonadjacent vertices that is maximal with respect to inclusion. A vertex subset of a graph \(G\) meeting all maximal independent sets of \(G\) is called a transversal of \(G\). The main result of this paper is: Given a bipartite graph \(G\) and a positive integer \(k\), it is \(\sum_{2}^P\)-complete to decide whether \(G\) has a transversal of size at most \(k\).