Simpler Parameterized Algorithm for OCT

摘要

We give a simple and intuitive fixed parameter tractable algorithm for the ODD CYCLE TRANSVERSAL problem, running in time O(3~k·k·|E|·|V|). Our algorithm is best viewed as a reinterpretation of the classical Iterative Compression algorithm for ODD CYCLE TRANSVERSAL by Reed, Smith and Vetta [8].