NP-hard
Even deciding OCT ≤ k is NP-complete. Approximation and parameterized approaches.
Advertisement
Approximation
O(log n) approximation via LP relaxation. Better: (2 - 2/OPT) approximation via multi-cut techniques.
Advertisement
FPT algorithm
Reed-Smith-Vetta: O(3^k · V · E). For each k, either solves or reports 'no OCT of size k'.