A Survey of the Algorithmic Properties of Simplicial, Upper Bound and Middle Graphs <s> Simple Maximum Cut <s> Abstract The Uniform Partition (UP) and the Simple Max Partition (SMP) problems are NP-complete graph partitioning problems, and polynomial-time algorithms are known for few classes of graphs only. In the present paper, the class of line-graphs is considered and a polynomial algorithm is proposed to solve both problems in this class. When the instance space is extended to digraphs, a characterization is possible which leads to similar results. <s> BIB001 </s> A Survey of the Algorithmic Properties of Simplicial, Upper Bound and Middle Graphs <s> Simple Maximum Cut <s> The 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. <s> BIB002
For a graph G = (V, E), the simple maximum cut problem is to partition the vertex set into two sets so as to maximize the number of edges of G with one end in each set. For some time this problem has been known to be NP-complete for general graphs  , but for line graphs time O(n+e) is sufficient BIB001 . Just recently the problem has been shown to be NP-complete for split graphs BIB002 , and hence for simplicial graphs. The time complexities of this problem for upper bound graphs and for representative graphs of hereditary hypergraphs remain open problems.