Hitting all maximal independent sets of a bipartite graph (Q2354017): Difference between revisions
From MaRDI portal
Set OpenAlex properties. |
Changed an Item |
||
Property / arXiv ID | |||
Property / arXiv ID: 1208.5589 / rank | |||
Normal rank |
Revision as of 05:46, 19 April 2024
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