NP-Complete operations research problems and approximation algorithms

For a large number of discrete optimization problems like the traveling salesman problem, the quadratic assignment problem, the general flow-shop problem, the knapsack problem etc. all known algorithms have the discouraging property that their (worst-case) running times on a computer grow exponentially with the size of the problem. All efforts to find polynomial bounded algorithms for these problems have failed. Recent results in complexity theory show that these problems belong to the classes ofNP-complete orNP-hard problems. It is a common belief that for problems belonging to these classes no polynomial bounded algorithms exist. Heuristics or approximation algorithms should be applied to these problems.The aim of this tutorial paper is to give a survey onNP-complete andNP-hard problems and on approximation algorithms. All concepts introduced are illustrated by examples which are closely related to the knapsack problem and can be understood easily. References to most other problems of interest to operations researchers are given.

---

Zusammenfassung Für eine große Anzahl von diskreten Optimierungsproblemen wie das Traveling Salesman Problem, das quadratische Zuordnungsproblem, das allgemeine Flowshop Problem, das Rucksackproblem usw. haben alle bisherigen Lösungsansätze die unangenehme Eigenschaft, daß der Rechenumfang der entsprechenden Algorithmen exponentiell mit dem Umfang der Probleme wächst. Alle Bemühungen polynomial beschränkte Verfahren für solche Probleme zu finden waren bislang ergebnislos. Neuere Ergebnisse der Komplexitätstheorie besagen, daß diese Probleme zu den Klassen derNP-vollständigen bzw.NP-schwierigen Probleme gehören und somit nach allgemein verbreiteter Auffassung wohl niemals polynomial lösbar sein werden. Die Anwendung von heuristischen Verfahren oder approximativen Algorithmen scheint der einzige Ausweg in dieser Situation.Ziel der Arbeit ist es, einen einführenden Uberblick über die Theorie derNP-vollständigen undNP-schwierigen Probleme sowie über approximative Verfahren zu geben. Alle in der Arbeit einge-führten Begriffe werden an einfach verständlichen Beispielen erläutert, die eng mit dem Rucksack-problem verwandt sind.Für weitere Probleme, die den Unternehmensforscher interessieren, findet der Leser ausführliche Literaturübersichten.

---

---

An invited survey.     

Co-NP-completeness of some matrix classification problems

The classes of P-, P ₀-, R ₀-, semimonotone, strictly semimonotone, column sufficient, and nondegenerate matrices play important roles in studying solution properties of equations and complementarity problems and convergence/complexity analysis of methods for solving these problems. It is known that the problem of deciding whether a square matrix with integer/rational entries is a P- (or nondegenerate) matrix is co-NP-complete. We show, through a unified analysis, that analogous decision problems for the other matrix classes are also co-NP-complete. Received: April 1999 / Accepted: March 1, 2000?Published online May 12, 2000     

Worst-case complexity bounds for algorithms in the theory of integral quadratic forms

The problem of factoring an integer and many other number-theoretic problems can be formulated in terms of binary quadratic Diophantine equations. This class of equations is also significant in complexity theory, subclasses of it having provided most of the natural examples of problems apparently intermediate in difficulty between P and NP-complete problems, as well as NP-complete problems [2, 3, 22, 26]. The theory of integral quadratic forms developed by Gauss gives some of the deepest known insights into the structure of classes of binary quadratic Diophantine equations. This paper establishes explicit polynomial worst-case running time bounds for algorithms to solve certain of the problems in this theory. These include algorithms to do the following: (1) reduce a given integral binary quadratic form; (2) quasi-reduce a given integral ternary quadratic form; (3) produce a form composed of two given integral binary quadratic forms; (4) calculate genus characters of a given integral binary quadratic form, when a complete prime factorization of its determinant D is given as input; (5) produce a form that is the square root under composition of a given form (when it exists), when a complete factorization of D and a quadratic nonresidue for each prime dividing D is given as input.     

Combinatorial flexibility problems and their computational complexity

The concept of flexibility—originated in the context of heat exchanger networks—is associated with a substructure which guarantees the performance of the original structure, in a given range of possible states. We extend this concept to combinatorial optimization problems, and prove several computational complexity results in this new framework.Under some monotonicity conditions, we prove that a combinatorial optimization problem polynomially transforms to its associated flexibility problem, but that the converse need not be true.In order to obtain polynomial flexibility problems, we have to restrict ourselves to combinatorial optimization problems on matroids. We also prove that, when relaxing in different ways the matroid structure, the flexibility problems become NP-complete. This fact is shown by proving the NP-completeness of the flexibility problems associated with the Shortest Path, Minimum Cut and Weighted Matching problems.     

On solvability of systems of polynomial equations

We study the computational complexity of the solvability problem of systems of polynomial equations over finite algebras. We prove a new dichotomy theorem that extends most of the dichotomy results which have been obtained over different families of finite algebras so far. As a corollary, for example, we get that if \mathbbA{\mathbb{A}} is a finite algebra of finite signature and omits the Hobby-McKenzie type 1, then the problem is solvable in polynomial time whenever \mathbbA{\mathbb{A}} is a reduct of a generalized affine algebra, and NP-complete otherwise.     

Two complexity results on c-optimality in experimental design

Finding a c-optimal design of a regression model is a basic optimization problem in statistics. We study the computational complexity of the problem in the case of a finite experimental domain. We formulate a decision version of the problem and prove its NP\boldsymbol{\mathit{NP}}-completeness. We provide examples of computationally complex instances of the design problem, motivated by cryptography. The problem, being NP\boldsymbol{\mathit{NP}}-complete, is then relaxed; we prove that a decision version of the relaxation, called approximate c-optimality, is P-complete. We derive an equivalence theorem for linear programming: we show that the relaxed c-optimality is equivalent (in the sense of many-one LOGSPACE-reducibility) to general linear programming.     

Computational Complexity in Algebraic Systems

Computability and computational complexity were first considered over the fields of real and complex numbers and generalized to arbitrary algebraic systems. This article approaches the theory of computational complexity over an arbitrary algebraic system by taking computability over the list extension for a computational model of it. We study the resultant polynomial complexity classes and mention some NP-complete problems.     

Polar permutation graphs are polynomial-time recognisable

Polar graphs generalise bipartite graphs, cobipartite graphs, and split graphs, and they constitute a special type of matrix partitions. A graph is polar if its vertex set can be partitioned into two, such that one part induces a complete multipartite graph and the other part induces a disjoint union of complete graphs. Deciding whether a given arbitrary graph is polar, is an NP$\text{NP}$-complete problem. Here, we show that for permutation graphs this problem can be solved in polynomial time. The result is surprising, as related problems like achromatic number and cochromatic number are NP$\text{NP}$-complete on permutation graphs. We give a polynomial-time algorithm for recognising graphs that are both permutation and polar. Prior to our result, polarity has been resolved only for chordal graphs and cographs.     

A polynomial path-following interior point algorithm for general linear complementarity problems

Linear Complementarity Problems (LCPs) belong to the class of \mathbbNP{\mathbb{NP}} -complete problems. Therefore we cannot expect a polynomial time solution method for LCPs without requiring some special property of the coefficient matrix. Our aim is to construct interior point algorithms which, according to the duality theorem in EP (Existentially Polynomial-time) form, in polynomial time either give a solution of the original problem or detects the lack of property P_*([(k)\tilde]){\mathcal{P}_*(\tilde\kappa)} , with arbitrary large, but apriori fixed [(k)\tilde]{\tilde\kappa}). In the latter case, the algorithms give a polynomial size certificate depending on parameter [(k)\tilde]{\tilde{\kappa}} , the initial interior point and the input size of the LCP). We give the general idea of an EP-modification of interior point algorithms and adapt this modification to long-step path-following interior point algorithms.     

Vertex fusion under distance constraints

In this paper, we analyze parameter improvement under vertex fusion in a graph G. This is a setting in which a new graph G^′ is obtained after identifying a subset of vertices of G in a single vertex. We are interested in distance parameters, in particular diameter, radius and eccentricity of a vertex v. We show that the corresponding problem is NP-Complete for the three parameters. We also find graph classes in which the problem can be solved in polynomial time.     

Algorithmic extremal problems in combinatorial optimization

An efficient approximation algorithm generator for the generalized maximum ψ-satisfiability problem is presented which produces an efficient approximation algorithm ψ-MAXMEAN¹ for each finite set ψ of relations. The algorithms ψ-MAXMEAN¹ are shown to be best-possible in the class of polynomial algorithms (if P ≠ NP), in both absolute and relative terms. The algorithms are of wide applicability, because of the central position of the generalized maximum satisfiability problem among the class of combinatorial optimization problems.     

Transparent Long Proofs: A First PCP Theorem for NPR

We introduce and study the notion of probabilistically checkable proofs (PCP) for real number algorithms. Our starting point is the computational model of Blum, Shub, and Smale (BSS) and the real analogue NP_R of NP in that model. We define in a straightforward manner verifiers as well as complexity classes PCP_R(r(n),q(n)) for the BSS model. Our main result is, to the best of our knowledge, the first PCP theorem for NP_R. It states that each problem in NP_R has transparent long proofs, i.e.,NP_R \subseteq PCP_R(poly,1), where poly denotes the class of univariate polynomial functions. The techniques used extend ideas from [12] for self-testing and self-correcting certain functions over so-called rational domains to more general domains over the real numbers. The latter arise from the particular NP_R-complete problem for which we construct a verifier of the required form.     

Some complexity problems on single input double output controllers

We investigate the time complexity of constructing single input double output state feedback controller structures, given the directed structure graph G of a system. Such a controller structure defines a restricted type of P₃-partition of the graph G. A necessary condition (∗) is described and some classes of graphs are identified where the search problem of finding a feasible P₃-partition is polynomially solvable and, in addition, (∗) is not only necessary but also sufficient for the existence of a P₃-partition. It is also proved that the decision problem on two particular graph classes — defined in terms of forbidden subgraphs — remains NP-complete, but is polynomially solvable on the intersection of those two classes. The polynomial-time solvability of some further related problems is shown, too.     

The polynomial dichotomy for three nonempty part sandwich problems

We classify into polynomial time or NP-complete all three nonempty part sandwich problems. This solves the polynomial dichotomy for this class of problems.     

Finding the connected components and a maximum clique of an intersection graph of rectangles in the plane

An intersection graph of rectangles in the (x, y)-plane with sides parallel to the axes is obtained by representing each rectangle by a vertex and connecting two vertices by an edge if and only if the corresponding rectangles intersect. This paper describes algorithms for two problems on intersection graphs of rectangles in the plane. One is an O(n log n) algorithm for finding the connected components of an intersection graph of n rectangles. This algorithm is optimal to within a constant factor. The other is an O(n log n) algorithm for finding a maximum clique of such a graph. It seems interesting that the maximum clique problem is polynomially solvable, because other related problems, such as the maximum stable set problem and the minimum clique cover problem, are known to be NP-complete for intersection graphs of rectangles. Furthermore, we briefly show that the k-colorability problem on intersection graphs of rectangles is NP-complete.     

Hard Tiling Problems with Simple Tiles

It is well known that the question of whether a given finite region can be tiled with a given set of tiles is \NP -complete. We show that the same is true for the right tromino and square tetromino on the square lattice, or for the right tromino alone. In the process we show that Monotone 1-in-3 Satisfiability is \NP -complete for planar cubic graphs. In higher dimensions we show \NP -completeness for the domino and straight tromino for general regions on the cubic lattice, and for simply connected regions on the four-dimensional hypercubic lattice. Received March 8, 2000, and in revised form May 14, 2001, and June 18, 2001. Online publication October 12, 2001.     

Systems of Polynomials for Detecting Orientable Matroids

We study systems of polynomial equations that correspond to a matroid M. Each of these systems has a zero solution if and only if M is orientable. Since determining if a matroid is orientable is NP-complete with respect to the size of the input data, determining if these systems have solutions is also NP-complete. However, we show that one of the associated polynomial systems corresponding to M is linear if M is a binary matroid and thus it may be determined if binary matroids are orientable in polynomial time given the circuits and cocircuits of said matroid as the input. In the case when M is not binary, we consider the associated system of non-linear polynomials. In this case Hilbertʼs Nullstellensatz gives us that M is non-orientable if and only if a certain certificate to the given polynomials system exists. We wish to place bounds on the degree of these certificates in future research.     

Existence of Polyhedral Embeddings of Graphs

It is proved that the decision problem about the existence of an embedding of face-width 3 of a given graph is NP-complete. A similar result is proved for some related decision problems. This solves a problem raised by Neil Robertson. Received July 6, 1998 RID="*" ID="*" Supported in part by the Ministry of Science and Technology of Slovenia, Research Project J1–0502–0101–98.     

La teoria della complessita’ del calcolo: Un nuovo capitolo dell’algoritmica

The theory of complexity, a continuation of the theory of computability, investigates the number of operations and quantity of memory required to solve given problems. Problems can thus be classified as polynomial or non-polynomial (intractable) according to the quantity of resource required for their solution. The classNP-complete collects a number of problems polynomially reducible one to the other, for which no polynomial solution is known to exist.