Min Cut is NP-complete for edge weighted trees
type: Item
instance of: scholarly article
title: Min Cut is NP-complete for edge weighted trees
zbMATH Open document ID: 0657.68034
DOI: 10.1016/0304-3975(88)90028-X
published in: Theoretical Computer Science
publication date: 1988-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 4074472
zbMATH Keywords: Min Cut linear arrangement
zbMATH Keywords: weighted trees
zbMATH Keywords: search number
zbMATH Keywords: NP- completeness
Wikidata QID: Q29030082
author: Burkhard Monien
author: I. H. Sudborough
reviewed by: Andreas Brandstädt
MaRDI profile type: Publication
cites work: On the Cutwidth and the Topological Bandwidth of a Tree
cites work: Polynomial Time Algorithms for the MIN CUT Problem on Degree Restricted Trees
cites work: Storage requirements for deterministic polynomial time recognizable languages
cites work: The vertex separation and search number of a graph
cites work: Q4198056
cites work: Complexity Results for Bandwidth Minimization
cites work: The Pebbling Problem is Complete in Polynomial Space
cites work: On Time Versus Space
cites work: Searching and pebbling
cites work: A tight bound for black and white pebbles on the pyramid
cites work: Recontamination does not help to search a graph
cites work: Black-white pebbles and graph separation
cites work: A Separator Theorem for Planar Graphs
cites work: A comparison of two variations of a pebble game on graphs
cites work: Q3661483
cites work: Topological Bandwidth
cites work: Q4159394
cites work: Q3208679
cites work: Bandwidth and pebbling
cites work: Complete Register Allocation Problems
cites work: A polynomial algorithm for the min-cut linear arrangement of trees
cites work: The Bandwidth Minimization Problem for Caterpillars with Hair Length 3 is NP-Complete
cites work: The NP-completeness of the bandwidth minimization problem
DBLP publication ID: journals/tcs/MonienS88
Recommended article: Q3725545
Recommended article: An improved algorithm for the planar 3-cut problem
Recommended article: Q3326858
Recommended article: A Polynomial-Time Algorithm for Planar Multicuts with Few Source-Sink Pairs
Recommended article: A fast algorithm for minimum weight odd circuits and cuts in planar graphs
Recommended article: A note on finding minimum cuts in directed planar networks by parallel computations
Recommended article: An $O ( | V |^2 )$ Algorithm for the Planar 3-Cut Problem
Recommended article: Polynomial Time Algorithms for the MIN CUT Problem on Degree Restricted Trees
Recommended article: Q3476627
Recommended article: The Complexity of Multiterminal Cuts
description: scientific article; zbMATH DE number 4074472