Min Cut is NP-complete for edge weighted trees (Q1111019): Difference between revisions

Let G be an (eventually edge-weighted) undirected graph \(G=(V,E)\) and L be a linear layout of G, i.e., an arrangement of the vertices of V along a horizontal line. The (weighted) cutwidth of L and G, denoted by cw(G,L), is the maximum number (weight sum) of edges connecting vertices on opposite sides of any vertical line drawn between consecutive vertices. The (weighted) cutwidth of G, denoted by cw(G), is the minimum over all (weighted) cw(G,L), L a linear layout of G. The (weighted) Min Cut problem asks whether cw(G)\(\leq k\) holds for a given undirected (edge- weighted) graph G and positive integer k. The investigation of the problem is motivated by problems of circuit design in which one wants to minimize the number of channels needed for wires connecting distinct circuit boards or gates. The weighted version may more closely model actual circuit design problems. It is known from \textit{M. Yannakakis} [J. Assoc. Comput. Mach. 32, 950-988 (1985; Zbl 0633.68063)] that Min Cut is solvable in time O(n log n) on trees. In this paper it is shown that 1) the Min Cut problem is NP-complete even when restricted to planar graphs with maximum vertex degree 3 and 2) the weighted Min Cut problem is NP-complete even when restricted to trees with polynomial size weights. It is also shown that `search number' is NP-complete for planar graphs with maximum vertex degree 3 which solves an open problem described by \textit{N. Megiddo, S. L. Hakimi, M. R. Garey, D. S. Johnson} and \textit{C. H. Papadimitriou} [ibid. 35, 18-44 (1988; Zbl 0637.68081)]. Furthermore the NP-completeness of vertex separation, progressive black/white pebble demand, and topological bandwidth for planar graphs with maximum degree 3 is shown.