AbstractThe complexity of the SIMPLE MAX CUT problem is investigated for several special classes of graphs. It is shown that this problem is NP-complete when restricted to one of the following classes: chordal graphs, undirected path graphs, split graphs, tripartite graphs, and graphs that are the complement of a bipartite graph. The problem can be solved in polynomial time, when restricted to graphs with bounded treewidth, or cographs. We also give large classes of graphs that can be seen as generalizations of classes of graphs with bounded treewidth and of the class of cographs, and allow polynomial time algorithms for the SIMPLE MAX CUT problem.
Categories and Subject Descriptors: F.2 [Analysis of Algorithms and Problem Complexity]; G.2 [Discrete Mathematics]
Additional Key Words and Phrases: max cut, graph algorithms, chordal graphs, treewidth, graph decomposition, cographs
Selected references
- Hans L. Bodlaender. Achromatic number is NP-complete for cographs and interval graphs. Information Processing Letters, 31(3):135-138, 8 May 1989.
- Hans L. Bodlaender. A linear-time algorithm for finding tree-decompositions of small treewidth. SIAM Journal on Computing, 25(6):1305-1317, December 1996.
- D. G. Corneil, Y. Perl, and L. K. Stewart. A linear recognition algorithm for cographs. SIAM Journal on Computing, 14(4):926-934, November 1985.
- M. R. Garey, D. S. Johnson, and L. Stockmeyer. Some simplified NP-complete graph problems. Theoretical Computer Science, 1(3):237-267, February 1976.
- Michel X. Goemans and David P. Williamson. .878-approximation algorithms for MAX CUT and MAX 2SAT. In Proceedings of the Twenty-Sixth Annual ACM Symposium on the Theory of Computing, pages 422-431, Montréal, Québec, Canada, 23-25 May 1994.
- John H. Muller and Jeremy Spinrad. Incremental modular decomposition. Journal of the ACM, 36(1):1-19, January 1989.
- Christos H. Papadimitriou and Mihalis Yannakakis. Optimization, approximation, and complexity classes. Journal of Computer and System Sciences, 43(3):425-440, December 1991.
- Neil Robertson and P. D. Seymour. Graph minors. II. Algorithmic aspects of tree-width. Journal of Algorithms, 7(3):309-322, September 1986.