A Faster Algorithm for Independent Cut

Abstract

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}-\hat{I}{\pm }_{\hat{I}}”)n}\right)$ on graphs of order $n$ and maximum degree at most $\hat{I}”$, where $\hat{I}{\pm }_{\hat{I}}”=\frac{1}{2+4\lfloor \frac{\hat{I}}{”}2\rfloor }$. Furthermore, we show that the problem is fixed-parameter tractable on graphs of order $n$ and minimum degree at least ${\hat{I}}^{2}n$ for some ${\hat{I}}^2>\frac{1}{2}$, where ${\hat{I}}^2$ is the parameter.