A faster algorithm for independent cut
Vsevolod Chernyshev, Johannes Rauch, Dieter Rautenbach, Liliia Redina · Theoretical Computer Science · 2025
The previously fastest algorithm for deciding the existence of an independent cut had a runtime of O * ( 1 . 4423 n ) , where n is the order of the input graph. We improve this to O * ( 1 . 4143 n ) . In fact, we prove a runtime of O * ( 2 ( 1 2 − α Δ ) n ) on graphs of order n and maximum degree at most Δ , where α Δ = 1 2 + 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.