A Faster Algorithm for Independent Cut

The previously fastest algorithm for deciding the existence of an independent cut had a runtime of O^*(1.4423ⁿ), where n is the order of the input graph. We improve this to O^*(1.4143ⁿ). In fact, we prove a runtime of O^*( 2(1/2-α_Δ)n ) on graphs of order n and maximum degree at most Δ, where α_Δ=12+4 Δ/2. Furthermore, we show that the problem is fixed-parameter tractable on graphs of order n and minimum degree at least β n for some β > 1/2, where β is the parameter.