A Faster Algorithm for Independent Cut

Vsevolod Chernyshev, Johannes Rauch, Dieter Rautenbach +1

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…