Bandwidth contrained NP-complete problems
type: Item
instance of: scholarly article
title: Bandwidth contrained NP-complete problems
zbMATH Open document ID: 0618.68043
DOI: 10.1016/0304-3975(85)90068-4
author: Burkhard Monien
author: I. H. Sudborough
published in: Theoretical Computer Science
publication date: 1985-01-01T00:00:00Z
review text: Bandwidth restrictions are considered on several NP-complete problems, including the following: 3SATISFIABILITY, INDEPENDENT SET, VERTEX COVER, HITTING SET, SIMPLE MAX CUT, 3-DIMENSIONAL MATCHING, EXACT COVER by 3 SETS, PARTITION INTO TRIANGLES, 3-COLORABILITY (even for planar graphs with maximum vertex degree four), DIRECTED AND UNDIRECTED HAMILTONIAN CIRCUIT and BANDWIDTH MINIMIZATION. It is shown that these problems when restricted to graphs, formulae, sets of triples, etc., of bandwidth f(n) are log space hard for the class of problems solvable by polynomial time nondeterministic algorithms that use simultaneously at most f(n) space. This class is denoted by NTISP(poly,f(n)). In fact, all of these problems restricted to bandwidth f(n), except for HAMILTONIAN CIRCUIT and BANDWIDTH MINIMIZATION, are shown to be log space complete for NTISP(poly,f(n)). Since NTISP(poly,log n)\(=NSPACE(\log n)\), this means we give several new additional examples of NSPACE(log n) complete problems. It also means that \(NP=NSPACE(\log n)\) if and only if \(3SAT\leq_{\log}3SAT\) restricted to well-formed formulae with bandwidth log n.
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 4003528
zbMATH Keywords: NP-completeness
zbMATH Keywords: graph algorithms
MaRDI profile type: Publication
full work available at URL: 0304-3975(85)90068-4
OpenAlex ID: W2039247498
cites work: On Languages Accepted in Polynomial Time
cites work: The bandwidth problem for graphs and matrices—a survey
cites work: Complete problems for space bounded subclasses of NP
cites work: Q4138187
cites work: Complexity Results for Bandwidth Minimization
cites work: Q4198056
cites work: Improved dynamic programming algorithms for bandwidth minimization and the MinCut Linear Arrangement problem
cites work: Q5592246
cites work: Q4142699
cites work: On the completeness of a generalized matching problem
cites work: Q4153600
cites work: The NP-completeness of the bandwidth minimization problem
cites work: Relationships between nondeterministic and deterministic tape complexities
cites work: Dynamic-Programming Algorithms for Recognizing Small-Bandwidth Graphs in Polynomial Time
cites work: The complexity of satisfiability problems
cites work: Bandwidth constraints on problems complete for polynomial time
cites work: Edge-Deletion Problems
Recommended article: Bandwidth constraints on problems complete for polynomial time
Recommended article: Q2721963
Recommended article: The bandwidth problem and operations on graphs
Recommended article: The Bandwidth Allocation Problem in the ATM network model is NP-complete
Recommended article: Q4240872
Recommended article: The combinatorial bandwidth packing problem
Recommended article: Lower bounds for the bandwidth problem
Recommended article: Hardness results for approximating the bandwidth
Recommended article: On Some Variants of the Bandwidth Minimization Problem
Recommended article: Q3839788
description: scientific article; zbMATH DE number 4003528