Bandwidth constrained NP-complete problems

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 ƒ(n) are log space hard for the class of problems solvable by polynomial time nondeterministic algorithms that use simultaneously at most ƒ(n) space. This class is denoted by Ntisp(poly, ƒ(n)). In fact, all of these problems restricted to bandwidth ƒ(n), except for Hamiltonian Circuit and Bandwidth Minimization, are shown to be log space complete for Ntisp(poly, ƒ(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 ⩽log3SAT restricted to well-formed formulae with bandwidth log n. Since it seems unlikely that all problems in Ntisp(poly, ƒ(n)) can be solved in polynomial time by deterministic algorithms, even for functions ƒ as small as log1 + ϵn, for ϵ > 0, our results suggest that NP-complete problems remain intractable even when restricted to small bandwidth. The problems become easier with diminishing bandwidth, but presumably remain intractable unless the bandwidth is restricted to c log2 n, for some c > 0.

Authors

• Burkhard Monien
• Ivan Hal Sudborough

Keywords

No keywords are indexed for this paper.