Hitting All Maximal Independent Sets of a Bipartite Graph
We prove that given a bipartite graph G with vertex set V and an integerk, deciding whether there exists a subset of V of size at most k hitting all maximal independent sets of G is complete for the class \(\varSigma_{2}^{\mathrm{P}}\).
maximal independent set clique transversal fibre in posets