Maximum independent sets near the upper bound (Q2026337)

An independent set of a graph \(G\) is a set of vertices where no two vertices are adjacent. The independence number is the size of a maximum independent set in the graph and is denoted by \(\alpha(G)\). Let us recall the following upper bound for \(\alpha(G)\): Theorem. Let \(G\) be a graph of order \(n\) and size \(m\). Then \[\alpha(G)\leq p:=\lfloor \frac{1}{2}+\sqrt{\frac{1}{4}+n^2-n-2m}\rfloor.\] The author considers independent sets near the above upper bound and proved the following result: Theorem. There exists an algorithm with time complexity \(O(n^2)\) that, given as an input a graph \(G\) of order \(n\), size \(m\), \(p:=\lfloor \frac{1}{2}+\sqrt{\frac{1}{4}+n^2-n-2m}\rfloor\) and an integer \(k\geq 0\) with \(p\geq2k+1\), returns an induced subgraph \(G_{p,k}\) of \(G\) with \(n_0\leq p+2k+1\) vertices such that \(\alpha(G) \leq p-k\) if and only if \(\alpha(G_{p,k})\leq p-k.\) Furthermore, he shows that one can decide in \(O(1.2738^{3k}+n^2)\) time whether \(\alpha(G_{p,k})\leq p-k\).