Hitting All Maximal Independent Sets of a Bipartite Graph

Hitting All Maximal Independent Sets of a Bipartite Graph

0.00 Avg rating0 Votes
Article ID: iaor201526341
Volume: 72
Issue: 2
Start Page Number: 359
End Page Number: 368
Publication Date: Jun 2015
Journal: Algorithmica
Authors: ,
Keywords: graphs
Abstract:

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 Σ 2 P equ1 .

Reviews

Required fields are marked *. Your email address will not be published.