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 > 12, where is the parameter.
Chernyshev et al. (Wed,) studied this question.