Publication Date:
2015-05-07
Description:
We prove that given a bipartite graph G with vertex set V and an integer k , 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}}\) .
Print ISSN:
0178-4617
Electronic ISSN:
1432-0541
Topics:
Computer Science
,
Mathematics