A linear time algorithm for graph partition problems (Q1198016)

We present an \(O(| V|+| E|)\) time algorithm which partitions the set of vertices of an undirected graph \(G=\langle V,E\rangle\) with maximum degree \(\Delta\) and minimum degree \(\delta\) to \(\{A,\bar A\}\) such that the following hold: (i) The number of edges with one end point in \(A\) and the other end point in \(\bar A\) is at least \(| E|/2\). (ii) The difference between the number of vertices in \(A\) and the number of vertices in \(\bar A\) is 0 if \(| V|\) is even, and is 1 if \(| V|\) is odd. (iii) The absolute value of the difference between the number of edges with both end points in \(A\) and the number of edges with both end points in \(\bar A\) is at most \((\Delta-\delta)/2\) if \(| V|\) is even, and is at most \((\Delta+1)/2\) if \(| V|\) is odd. The partitioning algorithms for which (i) and (ii) hold are known, see \textit{M. K. Goldberg} and \textit{R. Gardner} [Progress in graph theory, Proc. Conf. Combinatorics, Waterloo/Ont. 1982, 295-305 (1984; Zbl 0559.05059)]. However, we are not aware of any algorithm for which (i), (ii), and (iii) simultaneously hold. Section 2 contains our main results. We describe our algorithm which has running time \(O(| V|+| E|)\) and \(O(| V|^ 2)\), for unweighted graphs and weighted graphs, respectively. Our algorithm is a modified version of the algorithm of \textit{C. H. Papadimitriou} and \textit{M. Yannakakis} [(*) Optimization, approximation, and complexity class, Proc. 20th ACM Symp. Theory Comp., 229-234 (1988)] for approximating the maximum cut problem. We remark that for the cut generated by the algorithm in (*) property (i) holds, but properties (ii) or (iii) may not hold. In Section 3 we describe the applications of our algorithm to three NP- hard problems: the maximum cut problem, the graph bisection problem, and the bottleneck bipartite number problem.