An independent set of a graph $G$ is a subset of pairwise non-adjacent vertices. The parameter maximum independent set of graph $G$ is the size of a largest independent set in $G$.
Minimal/maximal is with respect to the contents of ISGCI. Only references for direct bounds are given. Where no reference is given, check equivalent parameters.
Problems in italics have no summary page and are only listed when ISGCI contains a result for the current parameter.
3-Colourability
[?]
|
FPT-Linear | [+]Details | |||||
Clique
[?]
|
Unknown to ISGCI | [+]Details | |||||
Clique cover
[?]
|
Unknown to ISGCI | [+]Details | |||||
Colourability
[?]
|
Unknown to ISGCI | [+]Details | |||||
Domination
[?]
|
XP | [+]Details | |||||
Feedback vertex set
[?]
|
XP | [+]Details | |||||
Graph isomorphism
[?]
|
Unknown to ISGCI | [+]Details | |||||
Hamiltonian cycle
[?]
|
Unknown to ISGCI | [+]Details | |||||
Hamiltonian path
[?]
|
Unknown to ISGCI | [+]Details | |||||
Independent set
[?]
|
XP | [+]Details | |||||
Maximum cut
[?]
(decision variant)
|
Unknown to ISGCI | [+]Details | |||||
Monopolarity
[?]
|
XP | [+]Details | |||||
Polarity
[?]
|
Unknown to ISGCI | [+]Details | |||||
Weighted clique
[?]
|
Unknown to ISGCI | [+]Details | |||||
Weighted feedback vertex set
[?]
|
XP | [+]Details | |||||
Weighted independent dominating set
[?]
|
XP | [+]Details | |||||
Weighted independent set
[?]
|
XP | [+]Details |