Hitting all maximal independent sets of a bipartite graph (Q2354017)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Hitting all maximal independent sets of a bipartite graph |
scientific article |
Statements
Hitting all maximal independent sets of a bipartite graph (English)
0 references
10 July 2015
0 references
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\).
0 references
maximal independent set
0 references
clique transversal
0 references
fiber in posets
0 references