# Questions tagged [np-hard]

decision problems that are at least as hard as NP-complete problems

136 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
2k views

### Is it NP-hard to fill up bins with minimum moves?

There are $n$ bins and $m$ type of balls. The $i$th bin has labels $a_{i,j}$ for $1\leq j\leq m$, it is the expected number of balls of type $j$. You start with $b_j$ balls of type $j$. Each ball of ...
• 3,023
439 views

### Is finding a weight-balanced tree NP-hard?

In the following, we consider binary trees where only the leaves have weights. Let $T$ be a binary tree and $W(T)$ be the sum of the weights of its leaves. Let $T.l$ and $T.r$ be the left child and ...
• 306
227 views

### Minimum edge deletion partitioning of a planar graph

I'm interested in the time complexity of the following problem: Given an undirected planar graph $G=(V,E)$ and a weight function $w:E \rightarrow \mathbb{Z}$ (so weights can be negative, too), color ...
• 153
359 views

### NP-hardness for one-dimensional facility location problem with entrance fee for each customer

We have $n$ customers, $(x_1, \dots, x_n)$, sorted on the read line. For convenience, we also use $x_i$ to denote its coordinate on the line. We need to locate $m$ facilities on the real line. We note ...
• 51
585 views

### Minimum weighted vertex cover on grid graph

Let $G'_{m,n}=(V,E)$ be the grid graph $G_{m,n}$, to which we add "diagonal" edges. For example, here is $G'_{6,3}$: And for each vertex $v_i \in V$, we have a associated positive value $c_i$ ...
• 211
141 views

### NP-hardness of a special traveling salesman problem

Consider we have $n$ vertices, $v_1,\ldots,v_n$. We have two positive values $(a_i,b_i)$ associated with each $v_i$. The edge weight $w(v_iv_j)=a_ia_j+b_ib_j$. Is it NP-hard to solve the traveling ...
• 3,023
136 views

### Has this graph-theoretic problem got a known name? Is it NP-hard?

I am considering the following problem. We are given a Directed Acyclic Graph. In general, there would be some number of subgraphs that, contracted into one node, would make it a tree. For example, ...
• 386
2k views

### Time Complexity of a Knapsack-derived problem

Consider the following problem: Let there be a set A of $n$ items $A=\{z_1, ..., z_n\}$, and let $W$ be a strictly positive integer. Each item $z_i$ has a value $v_i$ and a weight $w_i$. Finding a ...
• 141
235 views

130 views

### Rectangle Packing with Constraints

I am aware that the general rectangle packing problem is NP-hard. I am trying to form an estimate for a version of the problem with constraints. Consider fitting rectangles of smaller size into a ...
• 41
150 views

### Is Hamiltonian cycle problem on graphs with out-degree at most 3 NP hard?

I am trying to show a different form of Hamiltonian cycle problem is NP Hard. The problem is as follows. We have a directed graph and each node can have at most 3 outgoing edges. Determine if this ...
• 49
37 views

### Finding the "most modular" subset of graph vertices, i.e. that minimize disagreement inside and outside

Let $G = (V, E)$ be a graph. I want to find the subset of vertices of $G$ that minimizes a certain modularity cost. In our setting, the modularity cost of a subset $X$ is defined as the number of ...
273 views

### Graph optimization problem with multiple objectives/constraints

Let's assume that we have a directed acyclic graph $G = (V, E)$, non-negative vertex weight functions $w_a(v)$ and $w_b(v)$, and a non-negative edge weight function $t(u,v)$. We want to divide ...
• 141
131 views

### Complexity of a non-linear knapsack problem

Minimize $$\sum_{i=1}^{n}\sum_{j=1}^{m_i}w_{i,j}v_{i,j}$$ subject to $$\sum_{i=1}^{n}\frac{m_i}{m_i+\sum_{j=1}^{m_i}v_{i,j}} < \theta$$ $$v_{i,j}\in\{0,1\}~\forall i,~j$$ where $w_{i,j}$ and ...
303 views

• 2,215
178 views

### Showing a problem on a specific class of graphs is NP-hard

We know that a set of problems like minimum clique cover problem, coloring problem, vertex cover, ... are NP-hard for general graphs, but may be polynomial-time solvable for some classes of specific ...
• 293
139 views

### Solving systems of boolean equations

So I have a system of equations where varibles range over $\{0,1\}$ and the only operation is logical or ($\lor$). Each equation is of the one of two forms 1) $a = b \lor c$ 2) $1 = a \lor b$ where ...
• 3,738
62 views

### Is this sparsity constrained convex projection problem NP-hard?

Suppose we are working in ${\mathbb R}^d$ (dimension is not fixed), and we have a set of $n$ points $X = \{x_1,\ldots,x_n\}$ in that space. Given a query point $y$ inside the convex hull of $X$ and an ...
• 1,681
100 views

### Is finding all valid nets of a polyhedron NP-hard?

Suppose I wanted to find all valid nets of a polyhedron. Is this kind of problem NP-Hard? My guess is that it is. If you were to increase the "complexity" of the polyhedron (maybe this is the number ...
• 131
94 views

### Hardness of a special case of maximum matching

Input: A set of $n$ Users $U=\{u_1, ..., u_n\}$ and a set of $m$ products $I=\{i_1, ..., i_m\}$. Associated with each pair $u \in U$ and $i \in I$ is the probability $p_{u,i}$ of $u$ purchasing the ...
• 31
30 views

### Do non-linear dynamical systems have the potential to have an edge on other algorithms when it comes to computing NP-complete problems?

In a recent presentation, I've seen the difficulty of NP-complete/NP-hard problems attributed to the fact that they often have "long range" correlations, or at least they can be interpreted ...
• 141
58 views

### Exact Cover variant: partition a family of subsets into exact coverings

I have found that a problem that I'm analyzing is equivalent to the following variant of the Exact Cover problem: Partition into $k$ Exact Covers Input: A universe ...
• 111
32 views

• 171
76 views

### Longest path in a *shrinked* graph

Some definitions: Consider the unweighted directed graph $G$, where each node is uniquely represented by an $n$-bit vector of $0$'s and $1$'s. Now consider this scenario: we want to 'shrink the ...
• 161
238 views

### Is there a name for the knapsack problem with no bound on knapsack capacity?

I am investigating heuristics for optimising the packing a fixed number of knapsacks with a set of items of defined weights, however the knapsacks do not have a defined capacity limit. The objective ...
283 views

### Is Max-2SAT with exactly 3 occurrences per variable APX-hard?

The Max-2SAT problem asks if at least k clauses of a 2CNF formula can be satisfied. The Max-2SAT(at-most-3) problem is the restriction in which every variable occurs in at most 3 clauses (counting ...
158 views

### Minimum cost edge disjoint paths - NP hard?

I've been stuck on this problem for a while now. Here it is: The Network Reliability Problem (NRP) is defined as follows: Given an undirected graph with $n$ vertices $v_{1}, \dots, v_{n}$, a ...
• 133
37 views

### A particular type of SOS hardness proof

Is there an example of a sum of squares (SOS) hardness proof where the constraint is something non-trivial (like with some polynomial constraint) rather than just imposing the the typical $x_i^2 =1$ ...
• 493
96 views

### Problem related to the Knapsack problem: Is it NP-hard?

I am trying to know whether the following problem is NP-hard: Input: A positive number $k$ and $N$ pairs of numbers. Each pair $i$, contains the positive numbers $a_i$ and $b_i$. The problem is to ...
• 21
204 views

### Hardness of a maximum contiguous subarray sum for a sparse multi-dimensional array

Suppose we have a d-dimensional array A (d > 1) where each dimension has length n. The array is given in sparse notation as input, and the number of given non-zero elements is N. We want to find a ...
• 1,681
235 views

### Travelling salesman problem with detours

I am interested if there exists a following version of the travelling salesman problem: INSTANCE: A finite set $C = \{1,2,\dots,k\}$ of cities, a positive integer distance $\delta(i,j)$ for each pair ...
• 337
1 vote
The problem is defined as https://npcomplete.owu.edu/2014/06/10/exact-cover-by-3-sets/: Given a set $X$, with $|X| = 3q$ (so, the size of $X$ is a multiple of $3$), and a collection \$C=\{(x_{i1},x_{...