Tensor rank is NP-complete

We prove that computing the rank of a three-dimensional tensor over any finite field is NP-complete. Over the rational numbers the problem is NP-hard.     

DAG reversal is NP-complete

Runs of numerical computer programs can be visualized as directed acyclic graphs (DAGs). We consider the problem of restoring the intermediate values computed by such a program (the vertices in the DAG) in reverse order for a given upper bound on the available memory. The minimization of the associated computational cost in terms of the number of performed arithmetic operations is shown to be NP-complete. The reversal of the data-flow finds application, for example, in the efficient evaluation of adjoint numerical programs. We derive special cases of numerical programs that require the intermediate values exactly in reverse order, thus establishing the NP-completeness of the optimal adjoint computation problem. Last but not least we review some state-of-the-art approaches to efficient data-flow reversal taken by existing software tools for automatic differentiation.     

Optimal Jacobian accumulation is NP-complete

We show that the problem of accumulating Jacobian matrices by using a minimal number of floating-point operations is NP-complete by reduction from Ensemble Computation. The proof makes use of the fact that, deviating from the state-of-the-art assumption, algebraic dependences can exist between the local partial derivatives. It follows immediately that the same problem for directional derivatives, adjoints, and higher derivatives is NP-complete, too.      

Hamiltonian index is NP-complete

In this paper we show that the problem to decide whether the hamiltonian index of a given graph is less than or equal to a given constant is NP-complete (although this was conjectured to be polynomial). Consequently, the corresponding problem to determine the hamiltonian index of a given graph is NP-hard. Finally, we show that some known upper and lower bounds on the hamiltonian index can be computed in polynomial time.     

Maximizing edge-ratio is NP-complete

Given a graph G and a bipartition of its vertices, the edge-ratio is the minimum for both classes so defined of their number of internal edges divided by their number of cut edges. We prove that maximizing edge-ratio is NP-complete.     

splitting number is NP-complete

We consider two graph invariants that are used as a measure of nonplanarity: the splitting number of a graph and the size of a maximum planar subgraph. The splitting number of a graph G is the smallest integer k⩾0, such that a planar graph can be obtained from G by k splitting operations. Such operation replaces a vertex v by two nonadjacent vertices v₁ and v₂, and attaches the neighbors of v either to v₁ or to v₂. We prove that the splitting number decision problem is NP-complete when restricted to cubic graphs. We obtain as a consequence that planar subgraph remains NP-complete when restricted to cubic graphs. Note that NP-completeness for cubic graphs implies NP-completeness for graphs not containing a subdivision of K₅ as a subgraph.     

Deciding Frattini is NP-complete

We show that it is a NP-complete problem to decide whether a finite poset arises as the (Birkhoff) dual of the Frattini sublattice of some finite distributive lattice.This work was supported in part by Swiss NSF grant 20-32644.91.     

Planar 3DM is NP-complete

A restriction of the three-dimensional matching problem 3DM, in which the associated bipartite graph is planar, is shown to remain NP-complete. The restriction is inspired by that of Lichtenstein's planar 3SAT (Planar formulae and their uses, SIAM J. Comput. 11 (1982), 329–343). Like Planar 3SAT, Planar 3DM is principally a tool for use in NP-completeness proofs for planar restrictions of other problems. Several examples of its applications in this respect are given.     

All-shortest-path 2-interval routing is NP-complete

k-Interval Routing Scheme (k-IRS) is a compact routing method that allows up to k interval labels to be assigned to an arc. A fundamental problem is to characterize the networks that admit k-IRS. All of the problems related to single-shortest-path k-IRS have already been shown to be NP-complete. For all-shortest-path k-IRS, the characterization problems have been proved to be NP-complete for every k≥3, and remain open for k=1,2. In this paper, we close the open case of k=2 by showing that it is NP-complete to decide whether a graph admits an all-shortest-path 2-IRS. The same proof is also valid for all-shortest-path Strict 2-IRS. All-shortest-path Strict k-IRS is previously known to be polynomial for k=1, open for k=2,3, and NP-complete for every constant k≥4.     

Embedding partial steiner triple systems is NP-complete

It is known that any partial Steiner triple system of order υ can be embedded in a Steiner triple system of order w whenever w?4υ+1, and w≡1, 3 (mod 6); moreover, it is conjectured that the same is true whenever w?2υ+1. By way of contrast, it is proved that deciding whether a partial Steiner triple system of order υ can be embedded in a Steiner triple system of order w for any w?2υ?1 is NP-complete. In so doing, it is proved that deciding whether a partial commutative quasigroup can be completed to a commutative quasigroup is NP-complete.     

Local edge-connectivity augmentation in hypergraphs is NP-complete

We consider a local edge-connectivity hypergraph augmentation problem. Specifically, we are given a hypergraph G=(V,E) and a subpartition of V. We are asked to find the smallest possible integer γ, for which there exists a set of size-two edges F, with |F|=γ, such that in G^′=(V,E∪F), the local edge-connectivity between any pair of vertices lying in the same part of the subpartition is at least a given value k. Using a transformation from the bin-packing problem, we show that the associated decision problem is NP-complete, even when k=2.     

Recognizing graphs with fixed interval number is NP-complete

A t-interval representation of a graph expresses it as the intersection graph of a family of subsets of the real line. Each vertex is assigned a set consisting of at most t disjoint closed intervals, in such a way that vertices are adjacent if and only if some interval for one intersects some interval for the other. The interval number i(G) of a graph G is the smallest number t such that G has a t-representation. We prove that, for any fixed value of t with t≥2, determining whether i(G)≤t is NP-complete.     

Computing the dimension ofN-free ordered sets is NP-complete

We show that the problem of deciding whether anN-free ordered set has dimension at most 3 is NP-complete.Both authors supported by Office of Naval Research contract N00014-85K-0494.     

The consensus string problem for a metric is NP-complete

Given a set S of strings, a consensus string of S based on consensus error is a string w that minimizes the sum of the distances between w and all the strings in S. In this paper, we show that the problem of finding a consensus string based on consensus error is NP-complete when the penalty matrix is a metric.     

The Sudoku completion problem with rectangular hole pattern is NP-complete

The sudoku completion problem is a special case of the latin square completion problem and both problems are known to be NP-complete. However, in the case of a rectangular hole pattern–i.e. each column (or row) is either full or empty of symbols–it is known that the latin square completion problem can be solved in polynomial time. Conversely, we prove in this paper that the same rectangular hole pattern still leaves the sudoku completion problem NP-complete.     

The harmonious coloring problem is NP-complete for interval and permutation graphs

In this paper, we prove that the harmonious coloring problem is NP-complete for connected interval and permutation graphs. Given a simple graph G, a harmonious coloring of G is a proper vertex coloring such that each pair of colors appears together on at most one edge. The harmonious chromatic number is the least integer k for which G admits a harmonious coloring with k colors. Extending previous work on the NP-completeness of the harmonious coloring problem when restricted to the class of disconnected graphs which are simultaneously cographs and interval graphs, we prove that the problem is also NP-complete for connected interval and permutation graphs.     

Completing partial commutative quasigroups constructed from partial Steiner triple systems is NP-complete

Deciding whether an arbitrary partial commutative quasigroup can be completed is known to be NP-complete. Here, we prove that it remains NP-complete even if the partial quasigroup is constructed, in the standard way, from a partial Steiner triple system. This answers a question raised by Rosa in [A. Rosa, On a class of completable partial edge-colourings, Discrete Appl. Math. 35 (1992) 293-299]. To obtain this result, we prove necessary and sufficient conditions for the existence of a partial Steiner triple system of odd order having a leave L such that E(L)=E(G) where G is any given graph.     

Some NP-complete problems in linear programming

Degeneracy checking in linear programming is NP-complete. So is the problem of checking whether there exists a basic feasible solution with a specified objective value.     

Survey of polynomial transformations between NP-complete problems

This paper aims at being a guide to understand polynomial transformations and polynomial reductions between NP-complete problems by presenting the methodologies for polynomial reductions/transformations and the differences between reductions and transformations. To this end the article shows examples of polynomial reductions/transformations and the restrictions to reduce/transform between NP-complete problems. Finally, this paper includes a digraph with the historical reductions/transformations between instances of NP-complete problems and introduces the term family of polynomial transformations.