A Faster Algorithm for Independent Cut

The previously fastest algorithm for deciding the existence of an independent cut had a runtime of ${\mathcal{O}}^{\ast }({1.4423}^n)$, where $n$ is the order of the input graph. We improve this to ${\mathcal{O}}^{\ast }({1.4143}^n)$. In fact, we prove a runtime of ${\mathcal{O}}^{\ast }\left(2^{(\frac{1}{2}-{\alpha }_{\mathrm{\Delta }})n}\right)$ on graphs of order $n$ and maximum degree at most $\mathrm{\Delta }$, where ${\alpha }_{\mathrm{\Delta }}=\frac{1}{2+4\lfloor \frac{\mathrm{\Delta }}{2}\rfloor }$. Furthermore, we show that the problem is fixed-parameter tractable on graphs of order $n$ and minimum degree at least $\beta n$ for some $\beta >\frac{1}{2}$, where $\beta$ is the parameter.