Linear-Time Approximation Algorithms for the Max Cut Problem
Nguyễn Văn Ngọc, Źsolt Tuza · Combinatorics Probability Computing · 1993
Let G be a connected graph with n vertices and m edges (multiple edges allowed), and let k ≥ 2 be an integer. There is an algorithm with (optimal) running time of O(m) that finds (i) a bipartite subgraph of G with ≥ m/2 + (n − 1)/4 edges, (ii) a bipartite subgraph of G with ≥ m/2 + 3(n−1)/8 edges if G is triangle-free, (iii) a k-colourable subgraph of G with ≥ m − m/k + (n−1)/k + (k − 3)/2 edges if k ≥ 3 and G is not k-colorable. Infinite families of graphs show that each of those lower bounds on the worst-case performance are best possible (for every algorithm). Moreover, even if short cycles are excluded, the general lower bound of m − m/k cannot be replaced by m − m/k + εm for any fixed ε > 0; and it is NP-complete to decide whether a graph with m edges contains a k-colorable subgraph with more than m − m/k + εm edges, for any k ≥ 2 and ε> 0, ε < 1/k.